度量空间中基于距离孤立点的快速挖掘

作者：邵纪东; 荣冈; 顾海杰

来源：浙江大学学报(工学版), 2009, (02): 297-302.

• 基于距离的孤立点
• 度量空间
• k-NN查询
• 增量式挖掘
• 伸缩性 distance-based outlier
• metric space
• k-NN search
• incremental mining
• scalability

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