Source-linked AI summary
A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data
Ke Zhang, Marcus Hutter, Huidong Jin
TL;DR
Scattered real-world datasets challenge existing outlier detectors because implicit neighbourhood patterns and parameter choices complicate reliable detection. The paper introduces top-n LDOF, which measures an object’s relative distance from its neighbours, analyzes its properties, and reports improved, stable detection on the considered datasets.
Problem
Existing outlier detection methods are ineffective on scattered real-world datasets and difficult to parameterize without anomaly labels or expert confirmation.
Method
LDOF measures how much an object deviates from its k-nearest-neighbourhood using a relative distance factor, with top-n selection and theoretical analyses of its properties.
Results
The experiments report significant improvement over top-n KNN and top-n LOF for scattered datasets, including 100% accuracy across neighbourhood sizes 20-50 in one experiment.
Takeaways & Limitations
Top-n LDOF provides a scattered-data outlier detector whose performance remains stable over a large range of neighbourhood sizes.
Takeaways & Limitations
The theoretical generalization assumes a density continuous at xp and uses a uniform-density argument before taking a limit.
Abstract
from arXiv · showhide
Detecting outliers which are grossly different from or inconsistent with the remaining dataset is a major challenge in real-world KDD applications. Existing outlier detection methods are ineffective on scattered real-world datasets due to implicit data patterns and parameter setting issues. We define a novel "Local Distance-based Outlier Factor" (LDOF) to measure the {outlier-ness} of objects in scattered datasets which addresses these issues. LDOF uses the relative location of an object to its neighbours to determine the degree to which the object deviates from its neighbourhood. Properties of LDOF are theoretically analysed including LDOF's lower bound and its false-detection probability, as well as parameter settings. In order to facilitate parameter settings in real-world applications, we employ a top-n technique in our outlier detection approach, where only the objects with the highest LDOF values are regarded as outliers. Compared to conventional approaches (such as top-n KNN and top-n LOF), our method top-n LDOF is more effective at detecting outliers in scattered data. It is also easier to set parameters, since its performance is relatively stable over a large range of parameter values, as illustrated by experimental results on both real-world and synthetic datasets.
1 Introduction
Existing outlier detectors struggle with scattered real-world data and difficult parameter tuning. The paper proposes top-n LDOF, which measures deviation from neighbours and reports improved detection on scattered datasets.
- Problem: Scattered real-world data lacks explicit local patterns because objects form loosely distributed mini-clusters.Existing definitions often assume that normal objects occupy a few crowded main clusters.
- Problem: Parameter tuning is difficult because real-world datasets usually lack anomaly labels and require domain experts to confirm detection results.Improper parameters can make detection results uncontrollable.
- Existing approaches: Top-n methods rank objects by outlier-ness and let domain experts re-examine a small selected set instead of applying a binary threshold.This interaction alleviates parameter-setting difficulty in real-world applications.
- Existing approaches: Top-n KNN ranks objects by k-distance, while top-n LOF ranks them by local outlier factor.Top-n KNN selects the n objects with highest k-distance; top-n LOF selects objects with the highest LOF values.
- Contribution: The paper introduces LDOF to measure deviation from scattered neighbourhoods, analyzes its properties, and applies a top-n selection strategy.Experiments compare top-n LDOF with top-n KNN and top-n LOF on synthetic and real-world datasets.
- Contribution: The paper reports that top-n LDOF has significantly improved outlier-detection capability on scattered datasets.Its experimental evaluation covers both synthetic and real-world datasets.
2 Problem Formulation
High dimensionality and sparse feature ranges make real-world objects scattered, with normal data forming loosely bounded mini-clusters. Top-n KNN and top-n LOF can fail when neighbourhoods span multiple mini-clusters, motivating LDOF.
- Scattered data: High dimensionality and sparse feature ranges cause real-world objects to be scattered in feature space.The paper illustrates this using the typically 30-dimensional WDBC dataset.
- Scattered data: In scattered datasets, normal objects form loosely distributed mini-clusters, while genuine outliers do not belong to any object group.The local appearance may be patternless even though global mini-clusters exist.
- Neighbourhood structure: A neighbourhood becomes sparser as k grows because it includes objects from multiple mini-clusters.This differs from neighbourhoods formed within crowded main clusters.
- Failures of existing methods: Top-n KNN can rank mini-cluster objects above genuine outliers when k exceeds a small cluster’s size.In the example, this occurs when k is greater than the cardinality of C3, which is 10.
- Failures of existing methods: Top-n LOF can also fail because a sparse mini-cluster has lower density than a denser cluster.The paper states that this prevents several genuine outliers from receiving the highest rankings.
- Motivation for LDOF: LDOF measures neighbourhood violation through relative distance rather than global distance or local density.The formal definition is introduced in the following section.
3 Formal Definition of Local Distance-based Outliers
LDOF quantifies how far an object lies from its k-nearest-neighbour system by comparing its distance to the neighbourhood with distances within that neighbourhood. Higher values indicate greater deviation.
- Definition: The formal LDOF definition is designed to avoid the shortcomings identified for existing scattered-data detectors.It treats the k-nearest neighbours as the relevant neighbourhood system.
- Components: The k-nearest-neighbours distance averages distances from object xp to its k neighbours, excluding xp.The neighbour set is denoted Np.
- Components: The k-nearest-neighbours inner distance averages pairwise distances among the neighbours in Np.This captures the internal spread of the neighbourhood.
- LDOF interpretation: LDOF is a distance ratio that captures how much xp deviates from its neighbourhood system.It compares the object’s relation to the neighbourhood with the neighbourhood’s internal distances.
- LDOF interpretation: When LDOF is approximately below 1, xp is surrounded by a data cloud; when it is much greater than 1, xp lies outside that cloud.Higher LDOF indicates that xp is farther from its neighbourhood system.
- Geometric interpretation: LDOF can represent scattered-neighbour outlier-ness using a reformed neighbourhood region centered at the neighbourhood centre.In the illustrated example, xp lies outside that region and has LDOF greater than 1.
4 Properties of LDOF
LDOF's theoretical properties provide a lower-bound interpretation and quantify false-detection risk under local distributional assumptions. These results also motivate practical pruning and neighbourhood-size choices.
- Lower bound of LDOF: LDOFlb identifies an inlier when an object's LDOF is below the asymptotic lower bound, under continuity assumptions.The threshold is problem dependent because real-world datasets have complex structures.
- Lower bound of LDOF: For N ≫ k ≫ 1 and a density continuous at xp, the lower bound satisfies LDOFlb ≈ 1.The analysis considers neighbourhoods that become locally approximately uniform as sample size increases.
- Practical implications: Objects with LDOFs smaller than 1/2 can be ignored in practice, providing a potential pruning rule without knowing the data's effective dimension.The lower bound does not depend on the dimension of X, which supports use on lower-dimensional manifolds.
- Lower bound of LDOF: Under the stated sampling assumptions, expected distance quantities concentrate so that their ratio is approximately 1/2 with high probability.The result follows for large k and N, using concentration around the respective expectations.
- False-detection probability: For a uniform neighbourhood and threshold c > 1/2, the probability of falsely detecting xp as an outlier decreases exponentially with k.The bound also holds for non-uniform densities continuous at xp when N ≫ k.
5 LDOF Outlier Detection Algorithm and Its Complexity
Top-n LDOF ranks objects by their LDOF values after computing neighbourhood-based scores, discarding objects below the lower bound. Its overall complexity is O(N log N) with appropriate index support, while neighbourhood queries dominate runtime.
- Top-n LDOF: Top-n LDOF outputs the n objects with the highest LDOF values after ranking candidate objects.Objects with LDOF < LDOF_lb are discarded before sorting.
- Neighbourhood size: Choosing k requires k > m, where m is the effective dimension of the manifold, while excessively large k makes the method global.Performance rises and then remains stable as k increases to the dataset dimension.
- Top-n LDOF: The algorithm retrieves each object's k-nearest neighbours, calculates its LDOF, sorts the values, and returns the top n objects.
- Algorithm complexity: O(N log N) is the overall complexity with appropriate index support, although naive k-nearest-neighbour querying costs O(N^2).Tree-based spatial indexes can reduce the query complexity to O(N log N).
6 Experiments
Experiments compare top-n LDOF with top-n KNN and top-n LOF on synthetic and real-world datasets. LDOF maintains strong detection precision across neighbourhood sizes, including 100% accuracy over k=20-50 in one experiment and statistically significant improvement on WDBC.
- Experimental design: The experiments compare top-n LDOF, top-n KNN, and top-n LOF on synthetic and real-world datasets.Detection precision is used to evaluate performance, with n set to the number of real outliers when possible.
- Synthetic Data: 0 precision is reached by top-n KNN when k exceeds 10 in the synthetic dataset because of mini-cluster effects.
- Synthetic Data: 100% accuracy is maintained by the proposed approach across neighbourhood sizes k=20-50 in the synthetic-data experiment.
- Medical Diagnosis Data: WDBC evaluation uses 569 diagnosis records with 32 attributes, including 30 real-valued input features and benign or malignant diagnoses.
- Space Shuttle Data: The Shuttle experiment mixes 13 label-2 outliers with 1,000 randomly sampled normal objects and reports mean precision over 15 runs.
7 Conclusion
The paper concludes that LDOF measures deviation from scattered neighbourhoods and, with a top-n strategy, detects outliers precisely and stably across neighbourhood sizes. It also identifies improving detection accuracy on scattered real-world data as future work.
- Conclusion: LDOF measures how much an object deviates from its scattered neighbourhood using a local distance-based outlier factor.
- Conclusion: The approach analyses LDOF's lower bound and false-detection probability and suggests a method for selecting k.
- Conclusion: Experiments report higher precision and stability over a large range of neighbourhood sizes than top-n KNN and top-n LOF.
- Conclusion: Future work aims to further enhance outlier-detection accuracy for scattered real-world datasets.