一种基于快速k-近邻的最小生成树离群检测方法

发布时间：2018-12-13 06:55

【摘要】：离群检测也称异常点检测,是数据挖掘领域很有意义的热点问题之一,在很多方面都有广泛应用,如入侵行为、欺诈行为、医学上疾病前期的征兆等.基于k-近邻的算法能够很好的运用到大数据集上,因此在基于距离和基于密度的离群检测技术方面得到广泛应用.然而k-近邻算法的时间复杂度为O(N~2),随着数据集规模的增加,时间开销大大增加.基于最小生成树的聚类算法在使用Prim或者Kruskal算法构建最小生成树时空间复杂度和时间复杂度均为O(N~2),聚类结果依赖于用户参数的选择,而且容易漏检稠密簇中的局部离群点.针对以上问题,融合基于密度和基于聚类方法的优势,提出一种新的离群检测方法.该方法具有以下优点:(1)计算k-近邻的时间复杂度为O(kN)(kN);(2)构建最小生成树的时间复杂度为O(NlogN);(3)自适应识别聚类数目;(4)能够检测出多种类型的离群数据.最后通过大量实验验证了文中所提的KDNS算法,FkNN算法和ADC算法的有效性.实验结果表明,相对于现有算法,文中算法可以大幅度降低时间复杂度并显著提高离群检测率.
[Abstract]:Outlier detection, also known as outlier detection, is one of the most significant hot issues in the field of data mining. It is widely used in many fields, such as intrusion, fraud, medical symptoms of pre-disease, and so on. The algorithm based on k-nearest neighbor can be well applied to big data set, so it is widely used in outlier detection based on distance and density. However, the time complexity of k- nearest neighbor algorithm is O (N ~ (2). With the increase of data set size, the time cost increases greatly. The clustering algorithm based on minimum spanning tree is O (NN2) in space complexity and time complexity when using Prim or Kruskal algorithm to construct the minimum spanning tree. The clustering result depends on the choice of user parameters. Moreover, it is easy to miss the local outliers in dense clusters. To solve the above problems, a new outlier detection method is proposed by combining the advantages of density-based and clustering based methods. The advantages of this method are as follows: (1) the time complexity of O (kN) (kN); (_ 2 is O (kN) (kN); (_ 2) and the time complexity of constructing minimum spanning tree is O (NlogN); (_ 3); (4) it can detect many kinds of outlier data. Finally, the effectiveness of the proposed KDNS algorithm, FkNN algorithm and ADC algorithm is verified by a large number of experiments. The experimental results show that the proposed algorithm can greatly reduce the time complexity and improve the outlier detection rate compared with the existing algorithms.
【作者单位】：西安交通大学软件学院;
【基金】：国家自然基金项目(61473220) 陕西省自然基金项目(S2015YFJM2129)资助~~
【分类号】：TP311.13

【相似文献】