论文研究-一种基于迭代KNN图的自适应密度聚类方法 .pdf

所需积分/C币:10 2019-08-16 09:39:35 502KB .PDF
1
收藏 收藏
举报

一种基于迭代KNN图的自适应密度聚类方法,岳江,韩静,密度聚类能发现任意形状、大小的类,但现有方法严重依赖经验确定的参数,且难以处理多重密度,为此,提出了一种新型基于密度的自
中国科技论文在线 http://www.paper.edu.cn 样本点密度估计方法是密度聚类的核心,文献10给出了利用高斯函数和KNN图的新 型密度估计方法。首先定义了两个样本点p、i的高斯影响函数,形式如下: (P,i)= 根据上述影响函数,任意日标对象P的密度定义为 ity(P) 其中d(P,i)是p与其第个邻域点的欧拉距离。该方法核心在于利用KNN图来衡量每一个 样本点的密度,找出局部最大值为中心点,从中心点向周围搜索直到样本密度与中心点密度 80比值降到给定的阈值,从而实现聚类。然而笼统的利用KNN图来统计样本点密度,在多重 密度连接处并不准确,例如图2中与方形点相连接的KNN点大多是密度比其大的圆形点, 从而使其密度人于实际密度,造成聚类不准确 图2KNN示意图,K=4 Fig 2 Demonstration of knn. K-4 12迭代生长KNN图 基于图论的聚类方法通常利用无向图G(Ⅳ,E)来表小待聚类数据,其中Ⅴ是图的顶点表 示待聚类所有数据点,E是图的边表示数据点间的距离。KNN图记作Gk(,Ek),V是所有 数据样本,即与G图中的V是相同的集合。F表示为 Ex=E(i,D)li,jE V, Dis(i,,)<= Dis, Keyr j 其中Di;κs是样木点i与其第K个邻域点的距离;E(;j是样木点i、j所确定的边,大 小为Ds(i,j。 密度聚类的宗旨在于通过定义良好的密度测度,使处在不同密度内的点自动分离。 虽然通过KNN图可以初步估计出点的密度,但是如图2所展示的,在密度交叉区域并 95不能很好的度量其窣度大小,有在小密度点的密度会被拉人的现象。为了解决上述问题, 本文提出采用迭代的方式,根据上一级的KNN图Gn(V,E1)所确定的点间距离来获得下 级的KN图G+/(,E(+1): E(+)={E(,1)D"(,)<=DR} (4) 其中Dkc是样本点i与其第K个邻域点的距离(根据G确定):E()是样本点 100j所确定的边,大小为Di"(G,j 中国科技论文在线 http://www.paper.edu.cn 在迭代的过程中点间的距离加入距离调节因了,使距离不是单纯的绝对距离(次式 距离),还关联其上一级KNN图所确定的密度,原则为“如果样本点间的密度越相似, 则其相对距离越近”,样本间的距离如式5。 Disgu-d(, D)=D( D)*Max( Density () Density 0) Density() De 105DG,)为样本点;、j的欧拉距离(绝对距离);Mx(Den3Q),Den(m)为密度 Density ()) Density(i) 调节因了; Density(i)是样本点i根据G所桷定的密度 对于仟何数据点的K邻域点,如图3所示,其中图3(b)中红圈区域是K个邻域点最 长边所包含的区域。区域内数据点个数和区域大小决定了该区域的密度,其中数据点的 个数是固定值为K+1,而区域大小直接与其最长的边有关,本文定义区域大小与最长边 110为线性关系,所以样本点在G,中的密度为 Density (1)=Maxd Dis(i, iwN)<K (6) 其中Dis(i,b2M)为G中样本点i与其第p个邻域点的距离 ∴ a)待聚类数据点 指定点K邻近点 L15 图3K邻域距离演示 Fig 3 Demonstration of distance of Knn 迭代生长KNN图,不仅重新利用迭代来获得每一级KNN图,也重新定义了点间的 距离(边),与上一级KNN图确定的密度相关,使KNN图倾向于连接密度相同的点, 120达到自动分离不同密度点间的连接,图4展示了利用迭代生长的KNN图。图4与图2 相比,交叉密度点间的连线大大减小。 图4迭代生长KNN示意图,K=4 Fig 4 result of iterative KNN, K-4 125 13自适应密度阙值 通过样本点密度定义及KNN图迭代生长,不同密度点间连接已被自动最大分离。实 现密度聚类只需要选择合适的密度阈值对数据点进行分类,从图论观点看是移除KNN图的 部分边实现划分。因为KNN图已经对不同密度点的连接做了最大分离,所以最佳、最安仝 4 中国科技论文在线 http://www.paper.edu.cn 130的密度阈值选择原则是←根据该阈值划分KNN图,移除的边数量为最小极值”。 根据上述最佳密度阈值原则,确定最佳阈值搜索方法。先寻找KNN图划分所需移除边 数量的极小值,然后确定极小值中的最小值,其对应的密度值为最佳密度阈值。图5展示了 待聚类数据(图I(c)不同密度阈值下,KNN图划分所需移除的边数。 135 图5不同阙值下KNN图划分移除的边数 Fig 5 Removed number of edge in graph cut for different thresholds 2实验结果 木文实验数据一共选择了4组,如图2所示,除了图2(a)为木文生成外,其余数据分别 米源于文献8和11。实验步骤如下,其中κ值的选择对聚类结果没有关键性影响,K值大 l40小影响此次聚类结果中每一类点的最小数量,例如本文所有K值取6,表示最终分类结果每 类最小点数量为6。 步骤1计算待聚类数据K=1的KNN图G1(V,F1),即计算出所有样本点的最邻近点,方 法与传统KNN图计算方法相同。 步骤2.根据G1迭代计算G+1)。首先根据公式(6,计算所有数据点在G中的密度值 145然后利用距离调节因子和公式(5)重新计算所有数据点间的距离。在重新计算完图中所有点 间距离后,按照通常的KNN图算法获得G+1) 步骤3.根据步骤2的KNN图迭代计算方法,得到本文定义的迭代生长KNN图。然后 按照公式(6)计算所有待聚类数据点的最终密度值。 步骤4.寻找最佳密度阈值。遍历所有密度值,根据所有数据点的最终密度作密度聚类, 150利用聚类结果移除KNN图中不需要的连接边完成图的划分,寻找移除边的最小极小值,其 对应的密度即为最佳密度阈值。 步骤5.根据获得密度阈值和数据点最终密度实现密度聚类。 利用上述步骤对所有数据实现聚类,最终密度阈值如表格1,各组数据不同密度下KNN 图划分所移除的边数由线如图6所示,聚类结果如图7所示。 155 表1聚类最终密度阈值 Tab 1 Final thresholds used in clustering for data above 聚类数据K值|密度阈值1密度阙值2 Fig2 2.3 4.2 Fig2(b) 6 2.1 Fig2(c) 6 3.2 Fig2(d) 2.6 中国科技论文在线 http://www.paper.edu.cn (a)图2a)移除边数(b)图2(b)移除边数 160 (c)图2(c)移除边数(d)图2(d)移除边数 图6不同密度下KNN图划分需移除的边数 Fig 6 Removed numbers of edge in clustering for data above 165 :,… 能:? (a)本文聚类结果 (b) DBSCAN聚类结果(c)EM聚类结果 170 图7聚类结果 Fig7 results of several different clusters 实验结果显小,该方法能较好的对数据进行自适应聚类。与 DBSCAN和EM聚类结果 对比,可以发现本文方法较为為定,能很好的处理多重密度难题图2(a)。虽然通过手动反复 175选择参数的 DBSCAN聚类效果良好,但是这种非自适应方法其应用范围严重受限,而且无 法处理多重密度聚类。EM算法除对图2(c)有较好聚类效果外,其他的效果都差强人意,适 应性欠仕 中国科技论文在线 http://www.paper.edu.cn 相对于 DBSCAN、 OPTICS等通过设定半径和最小邻域个数参数实现密度分类,本方法 可以很好处理多重密度。例如从图6(a)可以看出两个明显的极小值,每一个明显的极小值对 l80应的密度阈值反映KNN图中该密度附近密度间连接分离良好,是较安全、较可靠的阈值, 聚类结果给出了很好的印证。另一方面,同一类中边缘数据点由于密度比中心位置小,大多 被分类到大密度区域造成结果与视觉习惯不同,这是密度聚类自身固有的特点,与聚类准确 性无关。 3结论 185 本文从密度聚类的密度定义着手,提出了一种新的KNN图算法,采用迭代的方式利用 上一级KNN图导出下一级。在距离计算中加入了距离调节因子,使距离不单纯的为绝对距 离也与上一级密度相关,使KNN图更倾向于连接密度相似的点,较好的分离不同密度点在 KNN图中的连接。在确定最佳密度阈值过程中,探索了一种新型判断原则,即利用最佳阈 值聚类结果划分KNN图,所需移除边数应为显著极小值。 190 该方法不用设置显著决定聚类结果的参数,唯一的参数K偵不会直接影响聚类结果π 确性,只会决定结果中每类点的最小数量,实现了高度自适应。聚类结果中,由于密度聚类 固有特点,对数据边的缘聚类结果不能很好的符合人眼视觉特性,如何利用约束手段如纹理、 形状来解决此问题是我们后续收进方向。 感谢 195 感谢教育部博士点基金对本论文的资助。 参考文献]( References [1] Caiming Zhong, Duoqian Miao, Pasi Franti Minimum spanning trcc bascd split-and-mcrge: A hierarchical clustering method [] Information Sciences: 2011, 181, 3397-3410 [2Yang, CC, Dorbin Ng, T. Analyzing and Visualizing Wcb Opinion Devclopmcnt and Social Interactions With 200 Density-Based Clustering[J]. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 201,41(,1144-1155 [3] Anthony McGregor, Mark Hall, Perry Lorier, James Brunskill. Flow Clustering Using Machine Learning Techniques[J]. Lecture Notes in Computer Science: 2004, 3015, 205-214 [4]Wci Hu, Nianhua Xic, Maybank S. Unsupcrviscd Activc Lcarning Bascd on Hicrarchical Graph-Thcorctic 205 Clustering[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics: 2009, 39(5),1147-1161 5] M. Hasanzadeh, S. Kasaei. A Multispectral Image Segmentation Method Using Size-Weighted Fuzzy Clustering and Membership Connectedness[J]. IEEE Geoscience and Remote Sensing Letters: 2010. 7(3), 520-524 210 [6]Caiming Zhong, DuoqianMiao, Ruizhi Wang. A Graph-theoretical dustering Method Based on Two Rounds of Minimun Spanning Trees[]. Pattern Recognition 2010, 43, 752-766 Hans-Pctcr Kricgcl, Pccr Kroger, Jorg Sander, Arthur Zimck. Dcnsity-bascd clustcring]. Wilcy Interdisciplinary Reviews: Data Mining and Knowledge Discovery: 2011, 1(3), 231-240 [8 Zahn, C.T. Graph-theoretical methods for detecting and describing gestalt clusters[J]. IEEE Transaction on Computer:1971,20(1),68-86. 15 [9]P. Franti, O. Virmajoki, V. Hautamaki. Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph[J] IEEE Transactions on Pattern Analysis and Machine Intelligence: 2006, 28(11), 1875-1881 [10 Jianhao Tan, Jing Zhang, Weixiong Li. An Improved Clustering Algorithm Based on Density Distribution Function[J]. Computcr and Information Scicncc: 2010. 3(2), 23-29 [11] Chang H, D.Y. Yeung. Robust path-based spectral clustering]. Pattern Recognition: 2008, 41(1),191-203 220

...展开详情
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840650 你的留言是对我莫大的支持
2019-08-16
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐