Finding Local Anomalies in Very High Dimensional Space
Authors:
- Timothy de VriesTVTimothy de Vries
- Sanjay ChawlaSCSanjay Chawla
- Michael E. HouleMHMichael E. Houle
- 1 December 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 8 (15504786) , 128-137
Abstract
Time, cost and energy efficiency are critical factors for many data analysis techniques when the size and dimensionality of data is very large. We investigate the use of Local Outlier Factor (LOF) for data of this type, providing a motivating example from real world data. We propose Projection-Indexed Nearest-Neighbours (PINN), a novel technique that exploits extended nearest neighbour sets in the a reduced dimensional space to create an accurate approximation for k-nearest-neighbour distances, which is used as the core density measurement within LOF. The reduced dimensionality allows for efficient sub-quadratic indexing in the number of items in the data set, where previously only quadratic performance was possible. A detailed theoretical analysis of Random Projection(RP) and PINN shows that we are able to preserve the density of the intrinsic manifold of the data set after projection. Experimental results show that PINN outperforms the standard projection methods RP and PCA when measuring LOF for many high-dimensional real-world data sets of up to 300000 elements and 102600 dimensions.Keywords
This publication has 15 references indexed in Scilit:
- Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data2009
- Fast principal component analysis using fixed-point algorithmPattern Recognition Letters, 2007
- The Amsterdam Library of Object ImagesInternational Journal of Computer Vision, 2005
- Mining distance-based outliers in near linear time with randomization and a simple pruning rule2003
- Finding nearest neighbors in growth-restricted metrics2002
- Database-friendly random projections2001
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- LOFACM SIGMOD Record, 2000
- Distance-based outliers: algorithms and applicationsThe VLDB Journal, 2000
- A geometric consistency theorem for a symbolic perturbation scheme1988