一种快速的AP聚类算法(共4页).doc
《一种快速的AP聚类算法(共4页).doc》由会员分享,可在线阅读,更多相关《一种快速的AP聚类算法(共4页).doc(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上 一、 一种快速的AP聚类算法A P算法的步骤如下:步骤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-A P, 在3个数据集上的数值实验表明, F-AP算法经过较少的迭代次数和较少的运行时间就能得到与AP算法一样的聚类性能, 并且数据集越大这种速度优势就愈明显。同时在常用数据集Iris上的算法执行效果也表明提出的新算法具有较好的收敛性能。二、 AP的半监督聚类对于一些聚类结
3、构比较复杂的数据集, A P 算法往往不能得到很好的聚类结果:使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整, 进而达到提高A P 算法的聚类性能。实脸结果表明, 该方法不仅提高了A P 对复杂数据的聚类结果, 而且在约束对数全较多时, 该方法要优于相关比对算法. AP 算法中最重要的两个参数为相似度矩阵s和偏向参数p。如果相似度矩阵能够准确地给出数据之间的相似关系, 则A P 算法就能得到很好的聚类结果相似度矩阵的定义直接影响到基于相似度矩阵的聚类算法的性能偏向参数的大小可以改变聚类数的多少, 它作为数据点独立的信息, 只反映了每个数据点被选中为代表点的概率的人小, 所以,
4、利用先验信息来辅助偏向参数的确定的可操作性不强:但是, 由于相似度矩阵包含了数据对之间的信息, 因此, 利用先验的数据成对约束调整相似矩阵更为合理。基于相似度矩阵调整的半监督的A P 算法, 即SA P 算法。SA P 算法是利用标签的数据信息来调整点与点之间的相似度形成新的相似度矩阵s,在新得到的相似度矩阵的基础上进行A P 算法在半监督聚类中, 我们得到的数据信息一般是带类标签的数据或者是成对点约束信息在很多实际问题中, 获得成对约束信息相对于获得类标签信息要容易些, 而且类标签信息可以转化为成对点约束信息, 反之则不然.SA P 算法是在近邻传播算法的基础上通过改变相似度矩阵对聚类进行指
5、导实验结果表明, 半监督的A P 算法在聚类性能上有了显著的提高从实验结果可以看出, 当获得较为充分的先验信息时,SA P 算法的表现要好于比对算法。SA P 算法除了在实验中测试数据集上表现了较好的聚类性能以外, 由于人P法对相似度矩阵的对称性没有要求, 这就放宽了对数据集本身的要求, SA P 算法也因此具有相对广泛的应用范围三、 近邻传播的聚类集成谱算法 APCESA APCESA 算法的巧妙之处在于: 1) 该算法先通过聚类集成为谱分解提供有意义的相似度矩阵,避免了谱聚类算法在处理高维数据集时由于对数据集的簇分布缺乏先验知识导致相似度图参数设置困难的问题; 2) 由谱分解得到的文本低维
6、嵌入在空间结构分布上更简单,以此作为AP 算法的输入,有效的克服了AP 算法在空间结构复杂的数据集上聚类不理想的缺点; 3) 在低维嵌入聚类阶段,AP 算法由于无需指定初始点,从而避免了传统谱算法中由于Kmeans算法对于起始点的敏感性造成的聚类结果不稳定问题,保证了算法的稳定性设B = b1,b2,b n 为文本集,F = F( 1) ,F( m) 为对其划分得到的m 个聚类标签( 聚类成员)组成的集合 先把各簇标签F( i) 变为超图表示H( i) ,则超图的n t 的邻接矩阵H = H( 1) ,H( r) ,其中n 为超图的顶点数,t = mk 为超边数 若采用余弦相似度,则相似度矩阵
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 快速 AP 算法
限制150内