聚类融合通过把具有一定差异性的聚类成员进行组合，能够得到比单一算法更为优越的结果，是近年来聚类算法研究领域的热点问题之一。提出了一种基于自适应最近邻的聚类融合算法ANNCE，能够根据数据分布密度的不同，为每一个数据点自动选择合适的最近邻选取范围。该算法与已有的基于KNN的算法相比，不仅解决了KNN算法中存在的过多参数需要实验确定的问题，还进一步提高了聚类效果。
黄少滨,李建,刘刚:一种基于自适应最近邻的聚类融合方法 2012,48(19)159 数据点的最近邻,有极大的可能性是属于相同的类。 (1)计算数据集D中两两数据点之间的欧氏距 将n个数据点的N次KNN搜索,映射为一个mn离,形成D的距离矩阵M。 的 similarity矩阵,矩阵元素值 similarity(p,q)表示数 (2)计算每一个数据点i与数据集中其他的n-1 据点p和数据点q的相似度,即如公式(1)所示: 个数据点的平均距离R,得到个平均距离组{R}, similarity(p,g)=pq 其中÷1,2 2N 3)计算这个平均距离组{R},得到它们的均值R*。 其中,n是在N次搜索k个最近邻中,p和q为邻居的 (4)由一个距离d指定近邻,凡是与源数据点i的 次数。 距离小于d的点都是该源数据点i的近邻。d的选取 根据形成的 similarity矩阵,使用 single-link算标准如下(如图3所示): 法构建层次聚类树。在 similarity矩阵中,每次合并 ①当R≤R*时,d在(RR*)2,R*)选取; 相似度最大的数据点(且要大丁一个阈值),逐层建 ②2当R>R*时,d在(R*,(R+R*)/2)选取。 立层次树,直到没有相似度大于阈值的数据点,算法 停止。 R R 3基于自适应近邻的聚类融合算法( ANNE) R 给定一个数据集D={X,X,…,X,…,Xn},其中, TR+R*2 MR++)/2 X={x,x2…,x}为一个数据点,n为D中数据点的数 目,d为每个数据点的维度,假设n>2。 ANNCE算法 图3d的两种选取标准图 先对数据集D多次运行ANN,形成划分集合P {P,P2,…,P},再利用划分集合P更新其所对应的 (5)根据选择的d值产生的近邻关系来更新 similarity矩阵;最后根据 similarity矩阵对数据点进 similarity矩阵。 行合并,得到最终的聚类结果 6)用于产生聚类分量的循环变量7=7+1。如果 3.1 ANNE算法的提出 T<N,则回溯执行步骤(4);否则继续执行下一步。 ANCE与 KNNCE算法基于相同的假设:与某 (7)利用 single-link算法,根据形成的相似度矩 数据点属丁同一类的数据点,往往是与其距离最 阵,对数据集进行划分:如果两个数据点(p,q)的相 近的数据点。所不同的是寻找最近邻的途径,KNN 似度S(p,q)>δ(δ为阈值),并且S(p,q)是相似度矩阵 是通过一个固定的近邻数K来确定数据点的最近邻, 中的最大值,那么就将p,q)归为一类;如果相似度 而本文提出的ANN则是基于自适应距离来确定数据 矩阵中不再有满足S(p,q)>δ的,那么则继续执行下 点的最近邻。在这里,需要特别指出的是,AN比一步 KNN在使用中更具有优势。这是由于以下两个原 (8)停止算法,产生最终的聚类结果C*。 因:(1)在KNN中,对于每个数据点,它的最近邻的数 算法的步骤图如图4。 ANNCE算法可以分为两 量K唯有通过实验才能取到最佳值,因此并不容易获个阶段。算法的第一阶段:形成相似度矩阵。相似 得;(2)在实际应用中,数据的分布密度通常是不同度矩阵的形成是基于ANN思想的聚类融合算法的核 的,因此,有效的邻居数目应该是变量。可以在图2心步骤。 ANce算法通过N次循环使用ANN的思 中考虑数据集的不同的局部分布。 想,以形成相似度矩阵。在每次循环中,根据R与R* 的大小关系,判定是否为最近邻的距离标准d在区间 ((R+R*)12,R*)或(R,(R+R*)12)内随机选取。算法 的第二阶段:使用 Single-link算法构建层次聚类树。 算法1基于自适应最近邻的聚类融合算法 (ANNCE) 输入:数据集D;ANN运行次数S;相似度國值δ 输出:聚类结果C*。 图2数据集中不同的局部分布图 初始化:相似度矩阵置空;循环执行ANN次数t=0 Step1生成 similarity矩阵 3.2算法的过程 (a)平均距离R←距离矩阵M; ANCE算法的完整过程如下 (b)距离均值R*←R; 1602012,48(19) Computer Engineering and Applications计算机工程与应用 第阶段:产生相似度矩阵 第二阶段:最近邻融 甲"世t+ 1-■→题- 形成距离矩阵M 把数据点标记为一类 计算平均距离均值R* 更新 similarity矩阵 根据R与R*的大小关系 S=max(similarity 迒择最近邻 Y 更新 similarity矩阵 形成划分 haid Bi aI I 图4一种基于自适应最近邻的聚类融合算法 ANNCE (c)For t1 to s do 4实验与分析 i fo 4.1实验设置 {tmpd←(R+R)2 实验测试采用来自于UCI的 Iris wine、 Ionosphere if(R≤R*){ 数据集(htp:/ archive. ics. uci. edu/ml/),具体描述见 d+-tmpd+ran. nextDouble()*(R*-tmpd) 表1 else if (R>R*)i dtR*+ran. nextDouble(*(R -tmpd); i 表1实验数据集 根据d确定最近邻,更新 similarity矩阵 数据集属性维数类别数数据点个数 /*s(p,q)=s(P,q)+12n* 150 Wine 13 178 Ionosphere 34 2 351 Step2遍历 similarity矩阵,把相似度大于國值的标记为 算法参数设置如下:为了与 KNNCE算法比较 同一类; 参考文献[9], ANNCE同样运行10次以产生相似度矩 /* single-link,自底向上的层次聚类* 阵,阈值δ根据实验对不同的数据集取最佳值;对比算 Step3返回聚类结果C*。 法K- means设置k为实验数据集的实际分类数, 33算法复杂度分析 KNNCE的三个参数:阈值δ、最近邻个数km,以及km 因为算法中需要计算数据集(包含n个点)中每均根据实验取最佳值。参考文献[2],聚类正确率计 个点到其余n-1个点的欧氏距离,所以算法主要算公式为P=1-(错分数据点个数数据点总数) 的时间都用丁计算由点对之间的欧氏距离形成的距42实验结果 离矩阵M。由丁M为nxn的矩阵,所以,运行ANN构 对于lris数据集, ANNCE算法在阈值取0.78-0.,93 建聚类成员的时间复杂度为O(nN);采用 Single-link时,达到了最佳的聚类正确率,且为100%,见表2。 层次算法处理相似度矩阵的时间复杂度为O(n),其 对应的阈值-正确率图,如图5。 屮,n是数据点的数目,N是聚类成员的个数。因此, ANCE算法与 KNNCH、K- means算法对is数 算法的总的渐近时间复杂度为O(n2)。 据集的聚类结果,见表3 黄少滨,李建,刘刚:一种基于自适应最近邻的聚类融合方法 2012,48(19)161 表2 ANNCE算法在Iis数据集 表5三种算法在Wine数据集 上的聚类正确率 上的聚类结果 阈值 正确率/(%) 算法 聚类正确率(%) 0.40 ANCE 0.78 100.00 KNNCE 67.98 0.93 100.00 means 66.33 0.94 8667 0.98 63.33 由表5可见,随着实验数据集的属性维数的增加 (wine数据集中数据为13维,lris数据集中数据为3 维),三种算法的聚类正确率都有所下降。但是,与 KNNCE和K- means算法相比, ANNCE算法能够更正 确地划分Wine数据集。 对于 Ionosphere数据集, ANCE算法在國值取 0.4 0.6 0 0.30时,达到最佳的聚类正确率6866%,见表6。 阈值 图5 ANNE算法在Iris数据集上的聚类正确率 表6 ANNE算法在 ionosphere数据集 上的聚类正确率 表3三种算法在Iris数据集 上的聚类结果 阈值 正确率(%) 0.29 62.68 算法 聚类正确率/(%) 0.30 68.60 ANNE 100.00 0.40 KNNCE 97.33 0.50 61.25 K-means 由表3可见,与 KNNCE和K- means算法相比, 对应的阈值-正确率图,如图7。 ANNCE算法能够更正确的划分Iris数据集,且正确 100 率为100%。 对丁wine数据集, ANNE算法在阀值取064 40 0.80时,达到最佳的聚类正确率73.59%,见表4 20 表4 ANNE算法在Wine数据集 上的聚类正确率 0.1 0.2 0.3 0.4 0.5 阈值 阈值 正确率/(%) 图7 ANce算法在 ionosphere数据集上的聚类正确率 0.50 66.85 ANNCE算法与 KNNCE、K- means算法对Iono sphere数据集的聚类结果,见表7。 0.80 73.59 0.85 67.42 表7三种算法在 Ionosphere数据集 0.95 56.74 上的聚类结果 对应的阈值正确率图,如图6。 算法 聚类正确率(%) ANNE 68.66 100 means 40 由表7可见,随着实验数据集的属性维数和数据 点个数的迅速增加( Ionosphere数据集中数据为34 维,351个数据点), KNNCE算法的聚类正确率是最 00.20.4 0.6 1.0 阈值 好的,但是本文提出的 ANCE算法的聚类结果与 图6 ANCE算法在Wine数据集上的聚类正确率 KNNCE算法是非常接近的。 ANN(F算法与 KNNCE、K- means算法对wne43参数评估 数据集的聚类结果,见表5。 阈值δ对聚类的过程影响最人。δ的值越人,在算 1622012,48(19) Computer Engineering and Applications计算机工程与应用 法每一次迭代的合并过程中,合并的数据点越少,相近邻数目,从而取得更好的聚类效果,并较好地解决 应地,最终获得的数据簇就越多。 了基于KNN的算法屮存在的过多参数需要实验确定 由 ANCE算法在三个数据集Iris、wine、Iono-的问题。下一步,针对本文算法的改进可以考虑以 sphere的阈值-正确率图,可以得知,随着阈值的逐渐下三个方向,以求进一步提高算法的聚类效果。 增人,算法的聚类正确率有一个先上升再下降的趋个方向是加权聚类融合,对于同一数据点的n次聚类 势,而且算法在各个数据集上取最佳正确率的阈值划分中的权重进行融合或对于数据点不同维的属性 各不相同,但是却有定的规律性。下面将具体给出。给予不同的权重,而设置权重的规则和依据是需要 44实验结论 仔细考虑和权衡的;另一个方向是利用模糊学习的 (1)由三个算法在不同的实验数据集上的实验思想,即基于模糊ANN的聚类融合;第三个方向是针 结果可知: ANCE算法的聚类效果要明显好于对高维数据聚类而言的,对高维数据应先作一个降 K-means算法,大部分情况下明显好于 KNNCE算维过程,以减少维数对于算法的影响,同时有效降低 法。而且 ANCE算法遥免了 KNNCE算法需要实验算法的复杂度。 寻找最优的最近邻个数的弊端,而后者过多的参数 设置(3个:阈值6最近邻个数km、k)给实验带来了参考文献: 很大的不便。 [I Han J W, Kamber M Data mining: concepts and tech- 2)由 ANNcee算法在实验数据集上的聚类结 niques[ M].2nd ed. San Francisco: Morgan Kaufmann Pub 果可知:随着数据集规模的増大和其数据点属性维 lisher,2001:223-260 数的增多,ANN算法的正确率在还渐降低,而且算法[2]孙吉贵,刘杰,赵连宇聚类算法研究门软件学报,20019 1):48-61 能够产生最优聚类结果的阈值有逐渐下降的趋势。 [3 Lingzhu H Locally linear embedding algorithIn with adap (3)通过对 ANNCE算法在不同数据集上的实验 tive neighbors[C]/Proceedings of the International Work 结果进行比对,可以发现:相对于数据集的规模,数 shop on Intelligent Systems and Applications(ISA 2009) 中据点的维数更能影响AN算法的实验结果,也就是 2009:14 说,ANN算法对于数据点的维数更加敏感。因此,[4]王和勇基于聚类和改进距离的LLE方法在数据降维中的 ANN算法适合于低维数据而不太适合于高维数据。应用几计算机研究与发展,20043(8):1485-1490 究其原因,是因为本文算法中计算点对之间的距离5毕华,梁洪力,土珏重采样方法与机器学习计算机学 时采用的是欧氏距离,而且没有考虑每一维属性的 报,2009,32(5):862-877 [6] Topchy A Analysis of consensus partition in cluster 权重等。 ensemble[C]/Proceedings of the 4th IEEE International (4) ANNCE算法在不同数据集上聚类结果的差 Conference on Data Mining(ICDM 2004 ).[S. 1 ] IEEE 异,也是因为算法是基于“与某一数据点属于同一类 Computer Society, 2004: 225-232 的数据点,往往是与其距离最近的数据点。”这样 [7 Topchy A, Jain A K, Punch WA mixture model for clus- 个假设的基础之上设计的,这就注定了其本身更适 tering ensembles[C]/Proceedings of the 4th SIAM Inter 合于那些在空间中位于类与类之间的点分布不密集 national Conference on Data Mining, 2004: 379-390 (不超过阈值)的数据集。 [8 Minaei-bidgoli B, Topchy A, Punch W FA comparison of resampling methods for clustering ensembles[C]/ Proc of int conf on mlmta.2004.939-945 5结论 [9]翁芳菲,陈黎飞,姜青山.一种基于KNN的融合聚类算法[ 提出一种基于自适应最近邻的聚类融合算法 计算机併究与发展,2007,44:187-191 ANNE,结合局部线性嵌入算法中“近邻”的思想,能「10aiA, Murty M, Flynn P Data clustering: a review[J 够根据数据的分布密度不同,有效地选择不同的最 ACM Computing Surveys( CSUR ), 1999, 31(3): 264-323