资源描述：
《一种快速的AP聚类算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、一种快速的AP聚类算法AP算法的步骤如下:步骤1计算待聚类数据点集的相似度矩阵S。（1）式中:S中所有非对角线元素的最小值、最大值和均值分别为Pmin,Pmax和Pmean。步骤2根据式（2）-（4）更新信息，和。（2）（3）（4）步骤3消除聚类结果的数字振荡。（5）式中:下标old和new分别代表上一次和本次更新消息的最终结果；为阻尼系数，越大消除振荡的效果越好，但收敛速度也越慢，反之亦然。步骤4确定点的聚类中心。（6）式中:若i=k，则点i本身是聚类中心；若ik，则点k是点i的聚类中心。步骤5若满足以下两个条
2、件中的任意一条，则终止迭代过程，AP算法结束，否则执行步骤2:1)聚类结果稳定，即聚类结果连续次保持不变；2)更新消息达到指定次数。基于收缩因子的AP算法收缩因子的定义公式为：（7）为了加速算法收敛,对和的更新公式作出如下变化:在分析了AP算法中的一个重要参数K对聚类结果影响的基础上,将收缩因子引入到AP算法中,提出一种快速的聚类算法:F-AP,在3个数据集上的数值实验表明,F-AP算法经过较少的迭代次数和较少的运行时间就能得到与AP算法一样的聚类性能,并且数据集越大这种速度优势就愈明显。同时在常用数据集Iris上的
3、算法执行效果也表明提出的新算法具有较好的收敛性能。二、AP的半监督聚类对于一些聚类结构比较复杂的数据集,AP算法往往不能得到很好的聚类结果：使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整,进而达到提高AP算法的聚类性能。实脸结果表明,该方法不仅提高了AP对复杂数据的聚类结果,而且在约束对数全较多时,该方法要优于相关比对算法.AP算法中最重要的两个参数为相似度矩阵s和偏向参数p。如果相似度矩阵能够准确地给出数据之间的相似关系,则AP算法就能得到很好的聚类结果相似度矩阵的定义直接影响到基于相似度矩阵的聚类
4、算法的性能偏向参数的大小可以改变聚类数的多少,它作为数据点独立的信息,只反映了每个数据点被选中为代表点的概率的人小,所以,利用先验信息来辅助偏向参数的确定的可操作性不强：但是,由于相似度矩阵包含了数据对之间的信息,因此,利用先验的数据成对约束调整相似矩阵更为合理。基于相似度矩阵调整的半监督的AP算法,即SAP算法。SAP算法是利用标签的数据信息来调整点与点之间的相似度形成新的相似度矩阵s,在新得到的相似度矩阵的基础上进行AP算法在半监督聚类中,我们得到的数据信息一般是带类标签的数据或者是成对点约束信息在很多实际问题中
5、,获得成对约束信息相对于获得类标签信息要容易些,而且类标签信息可以转化为成对点约束信息,反之则不然.SAP算法是在近邻传播算法的基础上通过改变相似度矩阵对聚类进行指导实验结果表明,半监督的AP算法在聚类性能上有了显著的提高从实验结果可以看出,当获得较为充分的先验信息时,SAP算法的表现要好于比对算法。SAP算法除了在实验中测试数据集上表现了较好的聚类性能以外,由于人P法对相似度矩阵的对称性没有要求,这就放宽了对数据集本身的要求,SAP算法也因此具有相对广泛的应用范围三、近邻传播的聚类集成谱算法APCESAAPCESA
6、算法的巧妙之处在于:1)该算法先通过聚类集成为谱分解提供有意义的相似度矩阵，避免了谱聚类算法在处理高维数据集时由于对数据集的簇分布缺乏先验知识导致相似度图参数设置困难的问题;2)由谱分解得到的文本低维嵌入在空间结构分布上更简单，以此作为AP算法的输入，有效的克服了AP算法在空间结构复杂的数据集上聚类不理想的缺点;3)在低维嵌入聚类阶段，AP算法由于无需指定初始点，从而避免了传统谱算法中由于Kmeans算法对于起始点的敏感性造成的聚类结果不稳定问题，保证了算法的稳定性．设B={b1，b2，…，bn}为文本集，F={F(
7、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可简
8、化为S=HHT．更重要的是，由此方法得到的相似度矩阵S的特征值分解问题可通过小矩阵Q=HTH进行间接求解．APCESA算法的主要步骤概括如下:输入:d×n的词－文本共现矩阵W，(d为文本集的特征词数，n为文本集的样本数)，簇个数k．1)对W中的每个行向量(对应于文本集中的一个文本)根据TF-IDF(termfrequency-inversedo
