【摘要】 将数据点的k最近邻(k-NN)距离作为孤立程度指标能够有效地发现数据集中的孤立点,但是基本算法需要O(N2)次数据点间的距离计算,不适用于大数据集.为此提出了一种利用度量空间中三角不等式的快速挖掘算法———提前修剪(ADVP).ADVP利用每次k-NN查询中保存的近邻点到被查询点的距离计算出近邻点的孤立程度上界.孤立程度上界小于已发现最弱孤立点的孤立程度的数据点可被修剪而无须进行k-NN查询.基于抽样方法优化了搜索次序以提高修剪效果.同时将ADVP自然地扩展为增量式算法.在标准大数据集上的实验结果表明,ADVP和现有算法相比明显节省了计算开销,具有更好的伸缩性;增量式ADVP能够有效地处理新增数据.更多还原

【Abstract】 Outliers can be effectively detected by searching for the points with the largest k-nearest-neighbor(k-NN) distance.But the baseline algorithm needs O(N2) distance evaluations between data points,so it is not suitable for large data sets.An efficient mining algorithm named advance pruning(ADVP) was proposed which is based on the triangle inequality in metric space.Utilizing the distance values between the query point and its neighbors which are memorized in each k-NN query,ADVP calculates an upper bound of the outlierness for each neighbor of the query point.Points with an upper bound of outlierness lower than that of the weakest outlier already discovered can be pruned.A sampling based search order optimization scheme was introduced to increase the number of pruning.Moreover,ADVP can be naturally extended to incremental mode.Results of the experiments on benchmark large datasets showed that ADVP scales much better than the state-of-the-art algorithm,and that the incremental ADVP deals with new coming data efficiently.更多还原