Feature bagging for outlier detection

ABSTRACT

Outlier detection has recently become an important problem in many industrial and financial applications. In this paper, a novel feature bagging approach for detecting outliers in very large, high dimensional and noisy databases is proposed. It combines results from multiple outlier detection algorithms that are applied using different set of features. Every outlier detection algorithm uses a small subset of features that are randomly selected from the original feature set. As a result, each outlier detector identifies different outliers, and thus assigns to all data records outlier scores that correspond to their probability of being outliers. The outlier scores computed by the individual outlier detection algorithms are then combined in order to find the better quality outliers. Experiments performed on several synthetic and real life data sets show that the proposed methods for combining outputs from multiple outlier detection algorithms provide non-trivial improvements over the base algorithm.

REFERENCES

• 1: Charu C. Aggarwal, Re-designing distance functions and distance-based applications for high dimensional data, ACM SIGMOD Record, v.30 n.1, p.13-18, March 2001 [doi>10.1145/373626.373638]
• 2: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
• 3: Charu C. Aggarwal , Philip S. Yu, Outlier detection for high dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.37-46, May 21-24, 2001, Santa Barbara, California, United States
• 4: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 5: V. Barnett and T. Lewis, Outliers in Statistical Data. New York, NY, John Wiley and Sons, 1994.
• 6: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 7: Nedret Billor , Ali S. Hadi , Paul F. Velleman, BACON: blocked adaptive computationally efficient outlier nominators, Computational Statistics & Data Analysis, v.34 n.3, p.279-298, Sept. 28, 2000 [doi>10.1016/S0167-9473(99)00101-2 ]
• 8: C. Blake,C. Merz, UCI Repository of machine learning databases,www.ics.uci.edu/~mlearn/MLRepository.html, 1998.
• 9: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350 ]
• 10: 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
• 11: N. Chawla, A. Lazarevic, L. Hall,K. Bowyer, SMOTEBoost: Improving the Prediction of Minority Class in Boosting, In Proceedings of the Principles of Knowledge Discovery in Databases, PKDD-2003, Cavtat, Croatia, September 2003.
• 12: Eleazar Eskin, Anomaly Detection over Noisy Data using Learned Probability Distributions, Proceedings of the Seventeenth International Conference on Machine Learning, p.255-262, June 29-July 02, 2000
• 13: E. Eskin, A. Arnold, M. Prerau, L. Portnoy, S. Stolfo, A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data, in Applications of Data Mining in Computer Security, Advances In Information Security, S. Jajodia D. Barbara, Ed. Boston: Kluwer, 2002.
• 14: Y. Freund, R. Schapire, Experiments with a New Boosting Algorithm, In Proceedings of the 13th International Conference on Machine Learning, Bari, Italy, 325--332, July 1996.
• 15: Simon Hawkins , Hongxing He , Graham J. Williams , Rohan A. Baxter, Outlier Detection Using Replicator Neural Networks, Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, p.170-180, September 04-06, 2002
• 16: Mahesh V. Joshi , Ramesh C. Agarwal , Vipin Kumar, Mining needle in a haystack: classifying rare classes via two-phase rule induction, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.91-102, May 21-24, 2001, Santa Barbara, California, United States
• 17: Mahesh V. Joshi , Ramesh C. Agarwal , Vipin Kumar, Predicting rare classes: can boosting make any weak learner strong?, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775092]
• 18: M. Joshi and V. Kumar, CREDOS: Classification using Ripple Down Structure (A Case for Rare Classes), In Proceedings of the SIAM International Conference on Data Mining, Lake Buena Vista, FL, April 2004.
• 19: 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
• 20: E. Kong and T. Dietterich, Error-Correcting Output Coding Corrects Bias and Variance, In Proceedings of the 12th International Conference on Machine Learning, San Francisco, CA, 313--321, 1995.
• 21: A. Lazarevic, L. Ertoz, A. Ozgur, J. Srivastava and V. Kumar, A comparative study of anomaly detection schemes in network intrusion detection, In Proceedings of the Third SIAM International Conference on Data Mining, San Francisco, CA, May 2003.
• 22: M. A. Maloof , P. Langley , T. O. Binford , R. Nevatia , S. Sage, Improved Rooftop Detection in Aerial Images with Machine Learning, Machine Learning, v.53 n.1-2, p.157-191, October-November 2003
• 23: Markos Markou , Sameer Singh, Novelty detection: a review—part 1: statistical approaches, Signal Processing, v.83 n.12, p.2481-2497, December 2003 [doi>10.1016/j.sigpro.2003.07.018]
• 24: Y. Ohsawa , Peter McBurney , Yukio Ohsawa , P. McBurney, Chance Discovery, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 25: R. Michalski, I. Mozetic, J. Hong and N. Lavrac, The Multi-Purpose Incremental Learning System AQ15 and its Testing Applications to Three Medical Domains, In Proceedings of the Fifth National Conference on Artificial Intelligence, Philadelphia, PA, 1041--1045, 1986.
• 26: Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001 [doi>10.1023/A:1007601015854 ]
• 27: 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
• 28: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003
• 29: Einoshin Suzuki , Jan M. Zytkow, Unified Algorithm for Undirected Discovery of Execption Rules, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.169-180, September 13-16, 2000
• 30: P. van der Putten, M. van Someren, CoIL Challenge 2000: The Insurance Company Case, Sentient Machine Research, Amsterdam and Leiden Institute of Advanced Computer Science, Leiden LIACS Technical Report 2000-09, June, 2000.
• 31: Dantong Yu , Gholamhosein Sheikholeslami , Aidong Zhang, Findout: finding outliers in very large datasets, Knowledge and Information Systems, v.4 n.4, p.387-412, October 2002 [doi>10.1007/s101150200013 ]
• 32: A. E. Howe, D. Dreilinger, SavvySearch: A meta-search engine that learns which search engines to query, AI Magazine, Vol. 18., No. 2, 1997.
• 33: Steve Lawrence , C. Lee Giles, Inquirus, the NECI meta search engine, Proceedings of the seventh international conference on World Wide Web 7, p.95-105, April 1998, Brisbane, Australia
• 34: B. Uygar Oztekin , George Karypis , Vipin Kumar, Expert agreement and content based reranking in a meta search environment using Mearf, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511490]
• 35: 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]
• 36: S. Papadimitriou, H. Kitagawa, P. B. Gibbons, C. Faloutsos: LOCI: Fast Outlier Detection Using the Local Correlation Integral. In Proceedings of IEEE International Conference on Data engineering, Bangalore, India March 2003.
• 37: Pei Sun , Sanjay Chawla, On Local Spatial Outliers, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.209-216, November 01-04, 2004
• 38: L. Ertoz, Similarity Measures, PhD dissertation, University of Minnesota, in progress, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS; Scientific databases

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
bagging, detection rate, false alarm, feature subsets, integration, outlier detection