Mining distance-based outliers in near linear time with randomization and a simple pruning rule

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Mining distance-based outliers in near linear time with randomization and a simple pruning rule

Full text

Pdf (221 KB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

Washington, D.C.

SESSION: Research track table of contents

Pages: 29 - 38

Year of Publication: 2003

ISBN:1-58113-737-0

Authors

Stephen D. Bay	Institute for the Study of Learning and Expertise, Palo Alto, CA
Mark Schwabacher	NASA Ames Research Center, Moffet Field, CA

Sponsors

SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 118, Citation Count: 33

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/956750.956758 What is a DOI?

ABSTRACT

Defining outliers by their distance to neighboring examples is a popular approach to finding unusual examples in a data set. Recently, much work has been conducted with the goal of finding fast algorithms for this task. We show that a simple nested loop algorithm that in the worst case is quadratic can give near linear time performance when the data is in random order and a simple pruning rule is used. We test our algorithm on real high-dimensional data sets with millions of examples and show that the near linear scaling holds over several orders of magnitude. Our average case analysis suggests that much of the efficiency is because the time to process non-outliers, which are the majority of examples, does not depend on the size of the data set.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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
	2	Fabrizio Angiulli , Clara Pizzuti, Fast Outlier Detection in High Dimensional Spaces, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.15-26, August 19-23, 2002
	3	V. Barnett and T. Lewis. Outliers in Statistical Data. John Wiley & Sons, 1994.
	4	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]
	5	Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
	6	G. Bisson. Learning in FOL with a similarity measure. In Proceedings of the Tenth National Conference on Artificial Intelligence, pages 82--87, 1992.
	7	R. J. Bolton and D. J. Hand. Statistical fraud detection: A review (with discussion). Statistical Science, 17(3):235--255, 2002.
	8	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
	9	W. Emde and D. Wettschereck. Relational instance-based learning. In Proceedings of the thirteenth International Conference on Machine Learning, 1996.
	10	E. Eskin, A. Arnold, M. Prerau, L. Portnoy, and S. Stolfo. A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data. In Data Mining for Security Applications, 2002.
	11	E. Fix and J. L. Hodges. Discriminatory analysis: Nonparametric discrimination: Small sample performance. Technical Report Project 21-49-004, Report Number 11, USAF School of Aviation Medicine, Randolf Field, Texas, 1952.
	12	Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	13	D. Hawkins. Identification of outliers. Chapman and Hall, 1980.
	14	S. Hettich and S. D. Bay. The UCI KDD archive. {http://kdd.ics.uci.edu/}. Irvine, CA: University of California, Department of Information and Computer Science, 1999.
	15	Tamás Horváth , Stefan Wrobel , Uta Bohnebeck, Relational Instance-Based Learning with Lists and Terms, Machine Learning, v.43 n.1-2, p.53-80, April-May 2001 [doi>10.1023/A:1007668716498]
	16	Edwin M. Knorr , Raymond T. Ng, Finding Intensional Knowledge of Distance-Based Outliers, Proceedings of the 25th International Conference on Very Large Data Bases, p.211-222, September 07-10, 1999
	17	Edwin M. Knorr , Raymond T. Ng , Vladimir Tucakov, Distance-based outliers: algorithms and applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.237-253, February 2000 [doi>10.1007/s007780050006]
	18	Terran Lane , Carla E. Brodley, Temporal sequence learning and data reduction for anomaly detection, ACM Transactions on Information and System Security (TISSEC), v.2 n.3, p.295-331, Aug. 1999 [doi>10.1145/322510.322526]
	19	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
	20	S. Ruggles and M. Sobek. Integrated public use microdata series: Version 2.0. {http://www.ipums.umn.edu/}, 1997.
	21	Rulequest Research. Gritbot. {http://www.rulequest.com/}.

CITED BY 33

	Shuxin Li , Robert Lee , Sheau-Dong Lang, Detecting outliers in interval data, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
	Aleksandar Lazarevic , Vipin Kumar, Feature bagging for outlier detection, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Fabrizio Angiulli , Stefano Basta , Clara Pizzuti, Detection and prediction of distance-based outliers, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Aaron Ceglar , John F. Roddick , David M. W. Powers, CURIO: a fast outlier and outlier cluster detection algorithm for large datasets, Proceedings of the 2nd international workshop on Integrating artificial intelligence and data mining, p.39-47, December 01-01, 2007, Gold Coast, Australia
	Sanjay Chawla , Pei Sun, SLOM: a new measure for local spatial outliers, Knowledge and Information Systems, v.9 n.4, p.412-429, April 2006
	Fabrizio Angiulli , Fabio Fassetti, Detecting distance-based outliers in streams of data, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Daniel Barbará , Carlotta Domeniconi , James P. Rogers, Detecting outliers using transduction and statistical testing, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Yufei Tao , Xiaokui Xiao , Shuigeng Zhou, Mining distance-based outliers from large databases in any metric space, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Alexander V. Mirgorodskiy , Naoya Maruyama , Barton P. Miller, Scalable systems software---Problem diagnosis in large-scale computing environments, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
	Fabrizio Angiulli , Stefano Basta , Clara Pizzuti, Distance-Based Detection and Prediction of Outliers, IEEE Transactions on Knowledge and Data Engineering, v.18 n.2, p.145-160, February 2006
	Fabrizio Angiulli , Fabio Fassetti, Very efficient mining of distance-based outliers, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Fabrizio Angiulli , Gianluigi Greco , Luigi Palopoli, Outlier detection by logic programming, ACM Transactions on Computational Logic (TOCL), v.9 n.1, p.7-es, December 2007
	Matthew Eric Otey , Amol Ghoting , Srinivasan Parthasarathy, Fast Distributed Outlier Detection in Mixed-Attribute Data Sets, Data Mining and Knowledge Discovery, v.12 n.2-3, p.203-228, May 2006
	Amol Ghoting , Gregory Buehrer , Srinivasan Parthasarathy , Daehyun Kim , Anthony Nguyen , Yen-Kuang Chen , Pradeep Dubey, A characterization of data mining algorithms on a modern processor, Proceedings of the 1st international workshop on Data management on new hardware, June 12-12, 2005, Baltimore, Maryland
	Li Wei , Eamonn Keogh , Xiaopeng Xi , Melissa Yoder, Efficiently finding unusual shapes in large image databases, Data Mining and Knowledge Discovery, v.17 n.3, p.343-376, December 2008
	Yu Qian , Fang Qiu , Jie Chang , Kang Zhang, Visualization-informed noise elimination and its application in processing high-spatial-resolution remote sensing imagery, Computers & Geosciences, v.34 n.1, p.35-52, January, 2008
	Bo Sheng , Qun Li , Weizhen Mao , Wen Jin, Outlier detection in sensor networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada
	Mingxi Wu , Christopher Jermaine, A Bayesian method for guessing the extreme values in a data set?, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Amol Ghoting , Srinivasan Parthasarathy , Matthew Eric Otey, Fast mining of distance-based outliers in high-dimensional datasets, Data Mining and Knowledge Discovery, v.16 n.3, p.349-364, June 2008
	Gregory Buehrer , Srinivasan Parthasarathy , Matthew Goyder, Data mining on the cell broadband engine, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Fabrizio Angiulli , Rachel Ben-Eliyahu -- Zohary , Luigi Palopoli, Outlier detection using default reasoning, Artificial Intelligence, v.172 n.16-17, p.1837-1872, November, 2008
	Hans-Peter Kriegel , Matthias S hubert , Arthur Zimek, Angle-based outlier detection in high-dimensional data, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Hui (Wendy) Wang , Ruilin Liu, Hiding distinguished ones into crowd: privacy-preserving publishing data with outliers, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Feng Jiang , Yuefei Sui , Cungen Cao, Some issues about outlier detection in rough set theory, Expert Systems with Applications: An International Journal, v.36 n.3, p.4680-4687, April, 2009
	Umaa Rebbapragada , Pavlos Protopapas , Carla E. Brodley , Charles Alcock, Finding anomalous periodic time series, Machine Learning, v.74 n.3, p.281-313, March 2009
	Xinjie Lu , Tian Yang , Zaifei Liao , Manzoor Elahi , Wei Liu , Hongan Wang, Incremental outlier detection in data streams using local correlation integral, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Mingxi Wu , Chris Jermaine, Guessing the extreme values in a data set: a Bayesian method and its applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.2, p.571-597, April 2009
	Fabrizio Angiulli , Fabio Fassetti, DOLPHIN: An efficient algorithm for mining distance-based outliers in very large datasets, ACM Transactions on Knowledge Discovery from Data (TKDD), v.3 n.1, p.1-57, March 2009
	Dragomir Yankov , Eamonn Keogh , Umaa Rebbapragada, Disk aware discord discovery: finding unusual time series in terabyte sized datasets, Knowledge and Information Systems, v.17 n.2, p.241-262, November 2008
	Hui Xiong , Gaurav Pandey , Michael Steinbach , Vipin Kumar, Enhancing Data Analysis with Noise Removal, IEEE Transactions on Knowledge and Data Engineering, v.18 n.3, p.304-319, March 2006
	Yingyi Bu , Lei Chen , Ada Wai-Chee Fu , Dawei Liu, Efficient anomaly monitoring over moving object trajectory streams, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Varun Chandola , Arindam Banerjee , Vipin Kumar, Anomaly detection: A survey, ACM Computing Surveys (CSUR), v.41 n.3, p.1-58, July 2009
	Malik Agyemang , Ken Barker , Rada Alhajj, A comprehensive survey of numeric and symbolic outlier mining techniques, Intelligent Data Analysis, v.10 n.6, p.521-538, December 2006