Detecting outliers using transduction and statistical testing

ABSTRACT

Outlier detection can uncover malicious behavior in fields like intrusion detection and fraud analysis. Although there has been a significant amount of work in outlier detection, most of the algorithms proposed in the literature are based on a particular definition of outliers (e.g., density-based), and use ad-hoc thresholds to detect them. In this paper we present a novel technique to detect outliers with respect to an existing clustering model. However, the test can also be successfully utilized to recognize outliers when the clustering information is not available. Our method is based on Transductive Confidence Machines, which have been previously proposed as a mechanism to provide individual confidence measures on classification decisions. The test uses hypothesis testing to prove or disprove whether a point is fit to be in each of the clusters of the model. We experimentally demonstrate that the test is highly robust, and produces very few misdiagnosed points, even when no clustering information is available. Furthermore, our experiments demonstrate the robustness of our method under the circumstances of data contaminated by outliers. We finally show that our technique can be successfully applied to identify outliers in a noisy data set for which no information is available (e.g., ground truth, clustering structure, etc.). As such our proposed methodology is capable of bootstrapping from a noisy data set a clean one that can be used to identify future outliers.

REFERENCES

• 1: Fabrizio Angiulli , Clara Pizzuti, Outlier Mining in Large High-Dimensional Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.203-215, February 2005 [doi>10.1109/TKDE.2005.31]
• 2: Stephen D. Bay , Mark Schwabacher, Mining distance-based outliers in near linear time with randomization and a simple pruning rule, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956758]
• 3: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 4: Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander, LOF: identifying density-based local outliers, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.93-104, May 15-18, 2000, Dallas, Texas, United States
• 5: Brodatz, P. (1966) Textures: A Photographic Album for Artists and Designers, Dover Publications,Inc., New York.
• 6: Elena project data. ftp://ftp.dice.ucl.ac.be/pub/neural-nets/ELENA/databases/
• 7: Ester, M., Kriegel, H., Sander, J., and Xu, X. (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. Proc. of the 2nd Intl. Conference on Knowledge Discovery and Data Mining. 226--231.
• 8: Eugene S Edgington, Randomization tests, Marcel Dekker, Inc., New York, NY, 1986
• 9: Alex Gammerman , Volodya Vovk, Prediction algorithms and confidence measures based on algorithmic randomness theory, Theoretical Computer Science, v.287 n.1, p.209-217, 25 September 2002 [doi>10.1016/S0304-3975(02)00100-7]
• 10: Guerin-Dugue, A., and Aviles-Cruz, C. (1993) High Order Statistics from Natural Textured Images, ATHOS workshop on System Identification and High Order Statistics. Sophia-Antipolis, France.
• 11: Guerin-Dugue, A. et al., (1995) Deliverable R3-B4-P - Task B4: Benchmarks, Technical report, Elena-NervesII "Enhanced Learning for Evolutive Neural Architecture", ESPRIT-Basic Research Project Number 6891.
• 12: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 13: Hardin, J., and Rocke, D.M. (2004) Outlier detection in the multiple cluster setting using the minimum covariance determinant estimator. Computational statistics and data analysis, Vol 44, pp. 625--638.
• 14: Hawkins, D. (1980) Identification of Outliers. Chapman and Hall, London.
• 15: Hubert, M., Rousseeuw, P.J, and Van Aelst, S. (2005) Multivariate Outlier Detection and Robustness. In Handbook of Statistics, Vol. 24, C.R. Rao, E. Wegman, J. Solka, editors. Elsevier.
• 16: Jennifer Neville , David Jensen , Lisa Friedland , Michael Hay, Learning relational probability trees, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956830]
• 17: Wen Jin , Anthony K. H. Tung , Jiawei Han, Mining top-n local outliers in large databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.293-298, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502554]
• 18: Edwin M. Knorr , Raymond T. Ng, Algorithms for Mining Distance-Based Outliers in Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.392-403, August 24-27, 1998
• 19: Lewis, B.V. (1994) Outliers in Statistical Data. John Wiley.
• 20: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 21: Swanwa Liao , Mario A. Lopez , Scott T. Leutenegger, High Dimensional Similarity Search With Space Filling Curves, Proceedings of the 17th International Conference on Data Engineering, p.615-622, April 02-06, 2001
• 22: Menasce, D., Abrahão, B., Barbará, D., Almeida, V., Ribeiro, F. (2002) Fractal Characterization of Web Workloads. Proceedings of the "Web Engineering" Track of WWW2002, Honolulu, Hawaii, USA , 7--11.
• 23: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 24: Kostas Proedrou , Ilia Nouretdinov , Volodya Vovk , Alexander Gammerman, Transductive Confidence Machines for Pattern Recognition, Proceedings of the 13th European Conference on Machine Learning, p.381-390, August 19-23, 2002
• 25: Sagan, H. (1994)Space Filling Curves. Springer-Verlag.
• 26: Sridhar Ramaswamy , Rajeev Rastogi , Kyuseok Shim, Efficient algorithms for mining outliers from large data sets, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.427-438, May 15-18, 2000, Dallas, Texas, United States
• 27: Gholamhosein Sheikholeslami , Surojit Chatterjee , Aidong Zhang, WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.428-439, August 24-27, 1998
• 28: Shashi Shekhar , Chang-Tien Lu , Pusheng Zhang, A Unified Approach to Detecting Spatial Outliers, Geoinformatica, v.7 n.2, p.139-166, June 2003 [doi>10.1023/A:1023455925009]
• 29: Jian Tang , Zhixiang Chen , Ada Wai-Chee Fu , David Wai-Lok Cheung, Enhancing Effectiveness of Outlier Detections for Low Density Patterns, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.535-548, May 06-08, 2002
• 30: UCI Machine Learning Repository. http://www.ics.uci.edu/ mlearn/MLRepository.html
• 31: Vapnik. V. (1998) Statistical Learning Theory, New York: Wiley.
• 32: Volodya Vovk , Alexander Gammerman , Craig Saunders, Machine-Learning Applications of Algorithmic Randomness, Proceedings of the Sixteenth International Conference on Machine Learning, p.444-453, June 27-30, 1999
• 33: Ho, S.S., and Wechsler, H. (2003) Transductive Confidence Machine for Active Learning, Int. Joint Conf. on Neural Networks, Portland, OR.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering