Local peculiarity factor and its application in outlier detection

ABSTRACT

Peculiarity oriented mining (POM), aiming to discover peculiarity rules hidden in a dataset, is a new data mining method. In the past few years, many results and applications on POM have been reported. However, there is still a lack of theoretical analysis. In this paper, we prove that the peculiarity factor (PF), one of the most important concepts in POM, can accurately characterize the peculiarity of data with respect to the probability density function of a normal distribution, but is unsuitable for more general distributions. Thus, we propose the concept of local peculiarity factor (LPF). It is proved that the LPF has the same ability as the PF for a normal distribution and is the so-called µ-sensitive peculiarity description for general distributions. To demonstrate the effectiveness of the LPF, we apply it to outlier detection problems and give a new outlier detection algorithm called LPF-Outlier. Experimental results show that LPF-Outlier is an effective outlier detection algorithm.

REFERENCES

• 1: Naoki Abe , Bianca Zadrozny , John Langford, Outlier detection by active learning, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150459]
• 2: Narayan L. Bhamidipati , Sankar K. Pal, Comparing rank-inducing scoring systems, Proceedings of the 18th International Conference on Pattern Recognition, p.300-303, August 20-24, 2006 [doi>10.1109/ICPR.2006.390]
• 3: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 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: N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer. Smote: Synthetic minority oversampling technique. Journal of Artificial Intelligence Research, 16:321--357, 2002.
• 6: L. Ertoz. Similarity Measures. Ph.D. Dissertation, University of Minnesota, 2005.
• 7: 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
• 8: Zengyou He , Xiaofei Xu , Shengchun Deng, Discovering cluster-based local outliers, Pattern Recognition Letters, v.24 n.9-10, p.1641-1650, 01 June 2003 [doi>10.1016/S0167-8655(03)00003-5]
• 9: Z. Y. He, X. F. Xu, Z. X. Huang, and S. C. Deng. A frequent pattern discovery method for outlier detection. Proceedings of the 5th International Conference on Web-Age Information Management, pages 726--732, 2004.
• 10: 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
• 11: Aleksandar Lazarevic , Vipin Kumar, Feature bagging for outlier detection, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081891]
• 12: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, pages 80--86, 1998.
• 13: Ken McGarry, A survey of interestingness measures for knowledge discovery, The Knowledge Engineering Review, v.20 n.1, p.39-61, March 2005 [doi>10.1017/S0269888905000408]
• 14: G. Merz and P. Murphy. Uci repository of machine learning databases. http://www.ics.uci.edu/mlearn/MLRepository.html, 1996.
• 15: Muneaki Ohshima , Ning Zhong , Yiyu Yao , Chunnian Liu, Relational peculiarity-oriented mining, Data Mining and Knowledge Discovery, v.15 n.2, p.249-273, October 2007 [doi>10.1007/s10618-006-0046-6]
• 16: M. Ohshima, N. Zhong, Y. Y. Yao, and S. Murata. Peculiarity oriented analysis in multi-people tracking images. Advances in Knowledge Discovery and Data Mining, pages 508--518, 2004.
• 17: 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
• 18: D. Saso and L. Nada. An introduction to inductive logic programming. Relational Data Mining, pages 48--73, 2001.
• 19: Yiyu Yao , Fei-Yue Wang , Jue Wang , Daniel Zeng, Rule + Exception Strategies for Security Information Analysis, IEEE Intelligent Systems, v.20 n.5, p.52-57, September 2005 [doi>10.1109/MIS.2005.93]
• 20: Y. Y. Yao and N. Zhong. An analysis of peculiarity oriented data mining. Proceedings of the 2002 IEEE International Conference on Data Mining Workshop on the Foundation of Data Mining and Discovery, pages 185--188, 2002.
• 21: Ning Zhong , Chunnian Liu , Y. Y. Yao , Muneaki Ohshima , Mingxin Huang , Jiajin Huang, Relational Peculiarity Oriented Data Mining, Proceedings of the Fourth IEEE International Conference on Data Mining, p.575-578, November 01-04, 2004
• 22: Ning Zhong , Muneaki Ohshima , Setsuo Ohsuga, Peculiarity Oriented Mining and Its Application for Knowledge Discovery in Amino-Acid Data, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.260-269, April 16-18, 2001
• 23: Ning Zhong , Yiyu (Y. Y. ) Yao , Muneaki Ohshima, Peculiarity Oriented Multidatabase Mining, IEEE Transactions on Knowledge and Data Engineering, v.15 n.4, p.952-960, July 2003 [doi>10.1109/TKDE.2003.1209011]
• 24: Interestingness, Peculiarity, and Multi-database Mining, Proceedings of the 2001 IEEE International Conference on Data Mining, p.566, November 29-December 02, 2001

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms, Theory

Keywords:
∈-sensitive peculiarity description, data mining, local peculiarity factor, outlier detection, peculiarity factor