Outlier detection based on Linear programming

Outlier detection is an important step in many data-mining applications. In this paper, we propose an outlier detection mathod based on Linear Programming. The essential idea behind this technique is that two neighbor data points must be normal points or outliers in the same time, this is consistent with Markov property, hence we construct k-nearest neighbor graph model. As the main result of this paper, we show that Linear Programming method can detect outliers correctly, even if the data has outliers that form a small cluster, in contrast to state of the art outlier detection algorithm LOF