Title: Outlier detection and evaluation by network flow

Authors: Ying Liu, Alan P. Sprague

Addresses: Department of Computer and Information Sciences, University of Alabama at Birmingham, Birmingham, AL 35294, USA. ' Department of Computer and Information Sciences, University of Alabama at Birmingham, Birmingham, AL 35294, USA

Abstract: This paper introduces a novel method to separate abnormal points from normal data, based on network flow. This approach uses the Maximum Flow Minimum Cut theorem from graph theory to find the outliers and strong outlier groups, and evaluate the outliers by outlier degrees. Similar outliers are discovered together and delivered to the user together; in an application where outliers are the points of the greatest interest, this will allow similar outliers to be analysed together. Effectiveness of the method is demonstrated in comparison with three other outlier detection algorithms. Further experimental application testifies this algorithm can improve the query accuracy on a content-based image data set. This algorithm is effective on higher dimensional data as well as low dimension.

Keywords: outliers; clustering; outlier detection; network flow; maximum flow minimum cut; graph theory.

DOI: 10.1504/IJCAT.2008.021946

International Journal of Computer Applications in Technology, 2008 Vol.33 No.2/3, pp.237 - 246

Published online: 10 Dec 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article