基于相对距离的反k近邻树离群点检测

Outlier Detection Based on Reversed K-Nearest Neighborhood MST of Relative Distance Measure

针对分布复杂且离群类型多样的数据集进行离群检测困难的问题,提出基于相对距离的反k近邻树离群检测方法RKNMOD(Reversed K-Nearest Neighborhood).首先,将经典欧氏距离、对象局部密度和对象邻域结合,定义了对象的相对距离,能同时有效检出全局和局部离群点.其次,以最小生成树结构为基础,采取最大边切割法以快速分割离群点和离群簇.最后,人工合成数据集和UCI数据集试验均表明,新算法的检测准确率更高,为分布异常且离群类型多样的数据集的离群检测提供了一条有效的新途径.

For outlier detection difficulty of data sets with complex distribution and various types of outliers,a new outlier detection method based on reversed k-nearest neighborhood MST of relative distance measure is proposed.Firstly,relative distance of object is defined with the combination of classical distance,local density and neighborhood of object,which can be used to detect global outliers and local outliers both.Secondly,on basis of minimum spanning tree structure,by tactics of maximum-edge-cutting,outliers and outlier clusters can be obtained.Finally,experiments of synthetic and UCI data sets show that the new algorithm is much more correct and effective.It is a new effective way for detecting outliers of data sets with abnormal distribution and diversity outlier types.