Discovering outlier filtering rules from unlabeled data: combining a supervised learner with an unsupervised learner

ABSTRACT

This paper is concerned with the problem of detecting outliers from unlabeled data. In prior work we have developed SmartSifter, which is an on-line outlier detection algorithm based on unsupervised learning from data. On the basis of SmartSifter this paper yields a new framework for outlier filtering using both supervised and unsupervised learning techniques iteratively in order to make the detection process more effective and more understandable. The outline of the framework is as follows: In the first round, for an initial dataset, we run SmartSifter to give each data a score, with a high score indicating a high possibility of being an outlier. Next, giving positive labels to a number of higher scored data and negative labels to a number of lower scored data, we create labeled examples. Then we construct an outlier filtering rule by supervised learning from them. Here the rule is generated based on the principle of minimizing extended stochastic complexity. In the second round, for a new dataset, we filter the data using the constructed rule, then among the filtered data, we run SmartSifter again to evaluate the data in order to update the filtering rule. Applying of our framework to the network intrusion detection, we demonstrate that 1) it can significantly improve the accuracy of SmartSifter, and 2) outlier filtering rules can help the user to discover a general pattern of an outlier group.

REFERENCES

• 1: V. Barnett and T. Lewis, Outliers in Statistical Data, John Wiley & Sons, 1994.
• 2: F. Bonchi , F. Giannotti , G. Mainetto , D. Pedreschi, A classification-based methodology for planning audit strategies in fraud detection, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.175-184, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312224]
• 3: P. Burge and J. Shawe-Taylor, Detecting cellular fraud using adaptive prototypes, in Proc. of AI Approaches to Fraud Detection and Risk Management, pp:9-13, 1997.
• 4: Tom Fawcett , Foster Provost, Adaptive Fraud Detection, Data Mining and Knowledge Discovery, v.1 n.3, p.291-316, 1997 [doi>10.1023/A:1009700419189]
• 5: http://www.hnc.com
• 6: http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html
• 7: 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
• 8: 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
• 9: 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]
• 10: W. Lee, S. J. Stolfo, and K. W. Mok, Mining audit data to build intrusion detection models, in Proc. of KDD-98, 1998.
• 11: Hang Li , Kenji Yamanishi, Text classification using ESC-based stochastic decision lists, Proceedings of the eighth international conference on Information and knowledge management, p.122-130, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.319966]
• 12: Y. Moreau and J. Vandewalle, Detection of mobile phone fraud using supervised neural networks: a first prototype, Available via: ftp://ftp.esat.kuleuven.ac.jp/pub/SISTA/ moreau/reports/icann97_TR97-44.ps.
• 13: Uzi Murad , Gadi Pinkas, Unsupervised Profiling for Identifying Superimposed Fraud, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.251-261, September 15-18, 1999
• 14: J. Rissanen, Fisher information and stochastic complexity, IEEE Trans. Inf. Theory, IT-42, 1, pp. 40-47 (1996).
• 15: R. M. Neal and G. E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, ftp://ftp.cs.toronto.edu/pub/radford/www/publications.html 1993.
• 16: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• 17: Saharon Rosset , Uzi Murad , Einat Neumann , Yizhak Idan , Gadi Pinkas, Discovery of fraud rules for telecommunications—challenges and solutions, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.409-413, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312303]
• 18: J.Takeuchi and K.Yamanishi, Empirical evaluation of an outlier detection engine SmartSifter, in Proc. of Symposium on Information and Its Applications (in Japanese), 2000.
• 19: Kenji Yamanishi, A Learning Criterion for Stochastic Rules, Machine Learning, v.9 n.2-3, p.165-203, July 1992 [doi>10.1007/BF00992676]
• 20: K. Yamanishi, A decision-theoretic extension of stochastic complexity and its application to learning, IEEE Trans. on Inf. Theory, IT-44, pp.1424-1439 (1998).
• 21: Kenji Yamanishi , Jun-Ichi Takeuchi , Graham Williams , Peter Milne, On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.320-324, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347160]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Design, Performance