Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Detecting outliers is an important topic in data mining. Sometimes the outliers are more interesting than the rest of the data. Outlier identification has lots of applications, such as intrusion detection, and unusual usage of credit cards or telecommunication services. In this paper, we propose a novel method for outlier identification which is based on network flow. We use the well known Maximum Flow Minimum Cut theorem from graph theory to find the outliers and strong outlier groups. Especially, it works on high dimensional data. This outlier detection occurs in a novel setting: to repair poor quality clusters generated by a clustering algorithm.

REFERENCES

• 1: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 2: Wen Jin , Anthony K. H. Tung , Jiawei Han, Mining top-n local outliers in large databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.293-298, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502554]
• 3: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 4: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems, v.25 n.5, p.345-366, July 2000 [doi>10.1016/S0306-4379(00)00022-3]
• 5: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 6: E. Knorr and R. Ng. A Unified Notion of Outliers: Properties and Computation. American Association for Artificial Intelligence.
• 7: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms

Keywords:
Maximum Flow Minimum Cut, data mining, graph theory, network flow, outlier detection