基于聚类划分的两阶段离群点检测算法  

Two stage outliers detection algorithm based on clustering division

作　　者：杨福萍[1,2] 王洪国[1] 董树霞[3] 牛家洋[1,2] 丁艳辉[1,2] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014 [2]山东省分布式计算机软件新技术重点实验室,济南250014 [3]山东女子学院,济南250300

出　　处：《计算机应用研究》2013年第7期1942-1945,共4页Application Research of Computers

基　　金：山东省自然科学基金资助项目(ZR2011FQ029;ZR2011FL026);山东省科技发展计划资助项目(2011YD01099;2011YD01100);山东省高等学校科技计划资助项目(J11LG32)

摘　　要：针对基于距离的离群点检测算法受全局阈值的限制,只能检测全局离群点,提出了基于聚类划分的两阶段离群点检测算法挖掘局部离群点。首先基于凝聚层次聚类迭代出K-means所需的k值,然后再利用K-means的方法将数据集划分成若干个微聚类;其次为了提高挖掘效率,提出基于信息熵的聚类过滤机制,判定微聚类中是否包含离群点;最后从包含离群点的微聚类中利用基于距离的方法挖掘出相应的局部离群点。实验结果表明,该算法效率高、检测精度高、时间复杂度低。Subjecting to the restrictions of the global threshold,the distance-based outlier detection algorithm can only detect global outliers.This paper proposed two-stage outlier detection algorithm based on clustering.First,it iterated to get the value k that the K-means required based on agglomerative hierarchical clustering.Then,it divided the data set into a number of micro-clustering by the K-means method.To improve the efficiency of mining,it proposed the clustering filter mechanism based on information entropy to determine whether the micro-clustering contained outliers.Finally,it used distance-based approach to detect local outliers from the micro-clustering with outliers.Experimental results show that the proposed algorithm has high efficiency,high precision and low time complexity.

关 键 词：层次聚类 K-均值 信息熵 距离和 离群点检测 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]