Detecting outlying properties of exceptional objects

ABSTRACT

Assume you are given a data population characterized by a certain number of attributes. Assume, moreover, you are provided with the information that one of the individuals in this data population is abnormal, but no reason whatsoever is given to you as to why this particular individual is to be considered abnormal. In several cases, you will be indeed interested in discovering such reasons. This article is precisely concerned with this problem of discovering sets of attributes that account for the (a priori stated) abnormality of an individual within a given dataset. A criterion is presented to measure the abnormality of combinations of attribute values featured by the given abnormal individual with respect to the reference population. In this respect, each subset of attributes is intended to somehow represent a “property” of individuals. We distinguish between global and local properties. Global properties are subsets of attributes explaining the given abnormality with respect to the entire data population. With local ones, instead, two subsets of attributes are singled out, where the former one justifies the abnormality within the data subpopulation selected using the values taken by the exceptional individual on those attributes included in the latter one. The problem of individuating abnormal properties with associated explanations is formally stated and analyzed. Such a formal characterization is then exploited in order to devise efficient algorithms for detecting both global and local forms of most abnormal properties. The experimental evidence, which is accounted for in the article, shows that the algorithms are both able to mine meaningful information and to accomplish the computational task by examining a negligible fraction of the search space.

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: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: 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
• 4: 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]
• 5: Arning, A., Aggarwal, C., and Raghavan, P. 1996. A linear method for deviation detection in large databases. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD), 164--169.
• 6: Barnett, V. and Lewis, T. 1994. Outliers in Statistical Data. John Wiley & Sons.
• 7: Breiman, L., Friedman, J., Olshen, R., and Stone, C. 1984. Classification and Regression Trees. Wadsworth, Belmont.
• 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: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 10: Zhi-Zhong Chen , Seinosuke Toda, The complexity of selecting maximal solutions, Information and Computation, v.119 n.2, p.231-239, June 1995 [doi>10.1006/inco.1995.1087]
• 11: Codd, E., Codd, S., and Salley, C. 1993. Providing OLAP (on-line analytical processing) to user-analysts: An it mandate. Tech. rep., Codd & Date, Inc.
• 12: De Benedictis, G., Rose, G., Carrieri, G., Luca, M. D., Falcone, E., Passarino, G., Bonafè, M., Monti, D., Baggio, G., Bertolini, S., Mari, D., Mattace, R., and Franceschi, C. 1999. Mitochondrial DNA inherited variants are associates with successful aging and longevity in humans. FASEB J. 13, 12, 1532--1536.
• 13: Garasto, S., Berardelli, M., Rango, F. D., Mari, V., Feraco, E., and Benedictis, G. D. 2004. A study of the average effect of the 3'apob-vntr polymorphism on lipidemic parameters could explain why the short alleles (< 35 repeats) are rare in centenarians. BMC Medical Genetics 5, 3.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Gini, C. 1921. Measurement of inequality of incomes. The Economic J. 31, 124--126.
• 16: Griffiths, A. J. F., Miller, J. H., Suzuki, D. T., Lewontin, R. C., and Gelbart, W. M. 1996. An Introduction to Genetic Analysis. W. H. Freeman.
• 17: Victoria Hodge , Jim Austin, A Survey of Outlier Detection Methodologies, Artificial Intelligence Review, v.22 n.2, p.85-126, October 2004 [doi>10.1023/B:AIRE.0000045502.10941.a9]
• 18: Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum, New York, 85--103.
• 19: Willi Klösgen, Explora: a multipattern and multistrategy discovery assistant, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 20: 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
• 21: 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
• 22: 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]
• 23: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 24: Mark W. Krentel, The complexity of optimization problems, Journal of Computer and System Sciences, v.36 n.3, p.490-509, June 1988 [doi>10.1016/0022-0000(88)90039-6]
• 25: Manish Mehta , Rakesh Agrawal , Jorma Rissanen, SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.18-32, March 25-29, 1996
• 26: Newman, D. J., Hettich, S., Blake, C. L., and Merz, C. 1998. UCI repository of machine learning databases.
• 27: Papadimitriou, C. 1994. Computational Complexity. Addison-Wesley, USA.
• 28: Passarino, G., Montesanto, A., Dato, S., Giordano, S., Domma, F., Mari, V., Feraco, E., and Benedictis, G. D. 2006. Sex and age specificity of susceptibility genes modulating survival at old age. Human Heredity (Int. J. Hum. Medical Genetics) 62, 4, 213--220.
• 29: 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
• 30: Rymon, R. 1992. Search through systematic set enumeration. In Proceedings of the International Conference on Principles of Knowledge and Reasoning (KR), 539--550.
• 31: Sunita Sarawagi , Rakesh Agrawal , Nimrod Megiddo, Discovery-Driven Exploration of OLAP Data Cubes, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.168-182, March 23-27, 1998
• 32: Alan L. Selman, A taxonomy of complexity classes of functions, Journal of Computer and System Sciences, v.48 n.2, p.357-381, April 1994 [doi>10.1016/S0022-0000(05)80009-1]
• 33: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 34: Suzuki, E. 2006. Data mining methods for discovering interesting exceptions from an unsupervised table. J. Universal Comput. Sci. 12, 6, 627--653.
• 35: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 36: Wei, L., Qian, W., Zhou, A., Jin, W., and Yu, J. 2003. Hot: Hypergraph-Based outlier test for categorical data. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 399--410.
• 37: Ji Zhang , Qigang Gao , Hai Wang, A Novel Method for Detecting Outlying Subspaces in High-dimensional Databases Using Genetic Algorithm, Proceedings of the Sixth International Conference on Data Mining, p.731-740, December 18-22, 2006 [doi>10.1109/ICDM.2006.6]
• 38: Ji Zhang , Hai Wang, Detecting outlying subspaces for high-dimensional data: the new task, algorithms, and performance, Knowledge and Information Systems, v.10 n.3, p.333-355, October 2006 [doi>10.1007/s10115-006-0020-z]
• 39: Cui Zhu , Hiroyuki Kitagawa , Christos Faloutsos, Example-Based Robust Outlier Detection in High Dimensional Datasets, Proceedings of the Fifth IEEE International Conference on Data Mining, p.829-832, November 27-30, 2005 [doi>10.1109/ICDM.2005.59]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

General Terms:
Algorithms, Management

Keywords:
Data mining, knowledge discovery, outlier characterization