一种快速的AP聚类算法

一、一种快速的AP聚类算法AP算法的步骤如下:步骤1计算待聚类数据点集},,,{21NxxxX的相似度矩阵S。.),(;,),(kikPkixxkiski（1）式中:S中所有非对角线元素的最小值、最大值和均值分别为Pmin,Pmax和Pmean。步骤2根据式（2）-（4）更新信息),(kir，),(kia和),(kka。)},(),({max),(),(..kiskiakiskirkktsk（2）},{..)}},(,0max{),(,0min{),(kiitsikirkkrkia（3）},{..)},(,0max{),(kiitsikirkka（4）步骤3消除聚类结果的数字振荡。),()1(),(),(),()1(),(),(kiakiakiakirkirkiroldnewoldnew（5）式中:下标old和new分别代表上一次和本次更新消息的最终结果；)10(为阻尼系数，越大消除振荡的效果越好，但收敛速度也越慢，反之亦然。步骤4确定点i的聚类中心。)},(),({maxargkirkiakk（6）式中:若i=k，则点i本身是聚类中心；若ik，则点k是点i的聚类中心。步骤5若满足以下两个条件中的任意一条，则终止迭代过程，AP算法结束，否则执行步骤2:1)聚类结果稳定，即聚类结果连续tN次保持不变；2)更新消息达到指定次数rN。基于收缩因子的AP算法收缩因子的定义公式为：42224（7）为了加速算法收敛,对),(kir和),(kia的更新公式作出如下变化:在分析了AP算法中的一个重要参数K对聚类结果影响的基础上,将收缩因子引入到AP算法中,提出一种快速的聚类算法:F-AP,在3个数据集上的数值实验表明,F-AP算法经过较少的迭代次数和较少的运行时间就能得到与AP算法一样的聚类性能,并且数据集越大这种速度优势就愈明显。同时在常用数据集Iris上的算法执行效果也表明提出的新算法具有较好的收敛性能。二、AP的半监督聚类对于一些聚类结构比较复杂的数据集,AP算法往往不能得到很好的聚类结果：使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整,进而达到提高AP算法的聚类性能。实脸结果表明,该方法不仅提高了AP对复杂数据的聚类结果,而且在约束对数全较多时,该方法要优于相关比对算法.AP算法中最重要的两个参数为相似度矩阵s和偏向参数p。如果相似度矩阵能够准确地给出数据之间的相似关系,则AP算法就能得到很好的聚类结果相似度矩阵的定义直接影响到基于相似度矩阵的聚类算法的性能偏向参数的大小可以改变聚类数的多少,它作为数据点独立的信息,只反映了每个数据点被选中为代表点的概率的人小,所以,利用先验信息来辅助偏向参数的确定的可操作性不强：但是,由于相似度矩阵包含了数据对之间的信息,因此,利用先验的数据成对约束调整相似矩阵更为合理。基于相似度矩阵调整的半监督的AP算法,即SAP算法。SAP算法是利用标签的数据信息来调整点与点之间的相似度形成新的相似度矩阵s,在新得到的相似度矩阵的基础上进行AP算法在半监督聚类中,我们得到的数据信息一般是带类标签的数据或者是成对点约束信息在很多实际问题中,获得成对约束信息相对于获得类标签信息要容易些,而且类标签信息可以转化为成对点约束信息,反之则不然.SAP算法是在近邻传播算法的基础上通过改变相似度矩阵对聚类进行指导实验结果表明,半监督的AP算法在聚类性能上有了显著的提高从实验结果可以看出,当获得较为充分的先验信息时,SAP算法的表现要好于比对算法。SAP算法除了在实验中测试数据集上表现了较好的聚类性能以外,由于人P法对相似度矩阵的对称性没有要求,这就放宽了对数据集本身的要求,SAP算法也因此具有相对广泛的应用范围三、近邻传播的聚类集成谱算法APCESAAPCESA算法的巧妙之处在于:1)该算法先通过聚类集成为谱分解提供有意义的相似度矩阵，避免了谱聚类算法在处理高维数据集时由于对数据集的簇分布缺乏先验知识导致相似度图参数设置困难的问题;2)由谱分解得到的文本低维嵌入在空间结构分布上更简单，以此作为AP算法的输入，有效的克服了AP算法在空间结构复杂的数据集上聚类不理想的缺点;3)在低维嵌入聚类阶段，AP算法由于无需指定初始点，从而避免了传统谱算法中由于Kmeans算法对于起始点的敏感性造成的聚类结果不稳定问题，保证了算法的稳定性．设B={b1，b2，…，bn}为文本集，F={F(1)，…，F(m)}为对其划分得到的m个聚类标签(聚类成员)组成的集合．先把各簇标签F(i)变为超图表示H(i)，则超图的n×t的邻接矩阵H={H(1)，…，H(r)}，其中n为超图的顶点数，t=mk为超边数．若采用余弦相似度，则相似度矩阵S=［s(i，j)］n×n=HHT/m．其中s(i，j)表示m个聚类成员中样本点i和样本点j属于一个簇的次数比例，以此作为2个样本点的相似度，得到超图的相似度矩阵作为谱聚类的权矩阵，避免了传统谱聚类算法中精确参数设计．这里m为常数，对矩阵分解无意义可舍弃不予考虑，则相似度矩阵S可简化为S=HHT．更重要的是，由此方法得到的相似度矩阵S的特征值分解问题可通过小矩阵Q=HTH进行间接求解．APCESA算法的主要步骤概括如下:输入:d×n的词－文本共现矩阵W，(d为文本集的特征词数，n为文本集的样本数)，簇个数k．1)对W中的每个行向量(对应于文本集中的一个文本)根据TF-IDF(termfrequency-inversedocumentfrequency)加权，经标准化后，随机选取初始点，运行K-means算法m次，以得到m个聚类成员．由m个聚类成员构建超图的邻接矩阵H，构造相似度矩阵S=［s(i，j)］n×n=HHT．2)计算S的前k个最大特征值λ1，…，λk对应的特征向量u1，…，uk．构造矩阵U=［u1…，uk］，设ui∈Rk为U的第i个行向量，Y={ui|i=1，…，n}即为文本集B对应的低维嵌入．3)计算低维嵌入的相似度矩阵S'=［s'(i，j)］n×n，设置初始偏执参数P，初始化代表度矩阵R=［r(i，j)］n×n和适选度矩阵A=［a(i，j)］n×n．4)按式(1)～(3)进行迭代至收敛，得到对应的类别数k'，判断k'是否等于k，是则输出聚类结果，给出对应的簇划分C1，…，Ck;不是则调节偏执参数p继续搜索．5)依行向量的簇划分将对应的文本归入到相应的簇中，得到最终的聚类结果B1，…，Bk，其中Bi={bj|zj∈Ci，bj∈B}，1≤i≤k．输出:文本簇B1，…Bk．该算法的优缺点：该算法克服了聚类集成谱算法在数据集簇分布为非理想分离时由于K-means算法的使用造成聚类结果不稳定的问题，同时，在一定程度上提高了算法的聚类质量．该算法通过聚类集成和谱分解得到文本的低维嵌入，间接实现了文本数据集的降维和空间结构转化，为AP算法提供较好的输入，克服了AP算法在复杂数据集上聚类不理想的缺点．在文本低维嵌入的聚类过程中，AP算法由于无需指定初始点，有效的避免了K-means算法由于初始点敏感性造成的算法不稳定问题．四、近邻传播算法在非监督图像聚类中的应用没有一种聚类算法可以普遍适用于各种数据集所呈现出来的多种多样的结构。本文综合考虑了聚类算法的效率及性能，首先采用近邻传播（AP）算法进行初次聚类，然后用k-means再次聚类，称为二次聚类，分别为粗糙聚类和精细聚类。（一）、图像特征提取：图像颜色、纹理和边缘特征，1.1图像纹理特征采用图像纹理谱描述方法，对于灰度图像，考虑像素点的3*3邻域，Ii(i=0,1,…,8)表示图像在该像素点处的灰度。如果像素点的灰度Vi看作纹理单元，并用二进制序列Vi=(0,1,…,7)来刻画领域内像素点的灰度沿水平方向的变化情况，即基元的排列，则Vi可定义为：（1）这里，Tl为正的阈值常数。为了刻画像素纹理谱分布和图像的光滑度（或粗糙度），并易于计算和理解，将二进制序列Vi=(0,1,…,7)作进一步处理，记lT=702iivi（2）lT即可唯一地表示图像在此像素点处的纹理模式，即像素灰度3*3领域中的变化情况。统计图像各像素点的纹理在值lT处的分布，就可以得到图像的纹理谱。假设用T(i,j)表示图像在像素点I(i,j)处的纹理值lT，{h[k]}(k=0,1,2,K,255)表示图像的纹理谱，则有（3）其中，otherwisekjiTjif0),(1),(m,n分别为图像的高度和宽度。1.2图像颜色特征：图像颜色谱采用HSV颜色空间。首先将RGB颜色空间转换到HSV颜色空间，然后对颜色进行量化。将H、S、V3个分量按照人的颜色感知进行非间隔的量化1.3图像边缘特征图像边缘谱首先将边界划分为3×3个子图像（Sub-image），然后将每个子图像进一步划分为一些小的图像块，块中边按方向和类别分为：空白型、0度型（水平方向）、45度型、90度型，135度型以及无序型。（二）、聚类算法运用二次聚类法：近邻传播（AP）算法粗糙聚类，k-means算法精细聚类。AP算法快速高效，且聚类结果得到的各类中心相对可靠，作为k-means初始中心能很快得到更佳精确的聚类结果。实验表明AP聚类的平均查全率和查准率分别为86.25%和71.25%，二次聚类的平均查全率和查准率分别为95%和95.11%，正确率明显得到提高。