半监督ap聚类算法的并行计算

《半监督ap聚类算法的并行计算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、半监督AP聚类算法的并行计算聚类算法概述聚类分析是研究数据挖掘技术的有效手段，是一种无监督的分类方法。聚类的目标是将相似的对象划分到同一个簇中，将不相似的对象划分到不同的簇中。聚类可分为:基于划分的聚类方法如K-means，K中心等基于层次的聚类方法如凝聚和分裂方法基于网格和密度的聚类方法基于模型的聚类方法聚类算法的数学描述设模式样本集为,其中为d维模式向量,聚类问题就是要找到一个划分,满足?并且使得总的类间离散度和达到最小,其中为第k个聚类的中心,为样本到对应聚类中心距离,聚类准则函数J即为各类样本到对应聚类中心距离的总和。这里为欧氏空间的距离,即。AP聚类算法以往的很多聚类

2、算法都是通过选取类代表点来完成聚类的。传统的寻找类代表点的方法是，随机地选择初始类代表点集合，然后迭代调整类代表点，直到类代表点不再发生明显改变时结束，其聚类结果会受到初始类代表点选择的影响。2007年，Frey等人提出了一种近邻传播（AffinityPropagation，AP）算法，该算法将信任传播思想用于数据点之间的信息交换，为每个数据点找到类代表点，从而完成聚类。近邻传播算法以数据点对之间的相似度为基础，将所有的数据点都看作是潜在的类代表点，通过数据点之间交换信息，得到一个较为理想的类代表点的集合。该算法快速、有效，引起了学者的广泛关注。2008年，软件学报的一篇文章中提

3、出了半监督的近邻传播聚类算法（Semi-supervisedclusteringbasedonAffinityPropagation，SAP），该算法在AP算法的基础上引入半监督思想，利用成对点约束信息对相似度矩阵进行调整，然后利用AP算法进行聚类。半监督聚类半监督聚类是利用样本先验知识，利用有标签的样本来指导无标签的样本的聚类方法，由于在数据挖掘中获得少量有标签的样本相对比较容易，故半监督聚类算法成为机器学习中重要内容之一。半监督聚类主要方法：基于成对约束的方法must-linkcannot-link基于距离的方法利用成对约束来学习距离度量基于约束和距离的方法两种方法的综合成对

4、限制先验信息用must-link和cannot-link来辅助聚类搜索，must-link规定两个样本必须在同一聚类中，cannot-link规定两个样本不能在同一聚类中。传递性：SAP聚类算法分析SAP算法，发现算法的时间复杂度较高，为O（n3）。随着数据集的增大，运行时间增加很快。因此给出了半监督近邻传播聚类算法的并行计算方法（PSAP），实验发现该并行算法的运行时间约为原算法的1/8~1/4。PSAP聚类算法其基本思想是将待测数据集随机分成两部分，然后分别在每部分中采用SAP算法获取相应的类代表点集合，最后将两个类代表点集合合并成新的数据集再运行一次SAP算法。假设待测数据

5、集的规模为n，SAP算法的时间复杂度为O（n3），而PSAP算法由于数据规模减半，因此所耗时间约为原计算时间的1/8，从而降低了时间的消耗。PSAP聚类算法采用数据划分的PSAP算法与未划分数据的SAP算法的约束信息应一致，由于约束信息是以数据点在数据集中的序号表示的，因此PSAP算法必须将原来的约束信息传递到数据子集上。PSAP算法主要解决待测数据集分开计算和最后的合并计算时约束信息和数据点序号的转换问题。约束信息的转换发生在数据集的分割、部分数据集的SAP聚类、聚类结果的合并以及每个原始数据点最后确定类代表点的各个时刻。约束信息的转换和数据点的序号转换是同时进行的。PSAP聚

6、类算法步骤（1）以数据点的序号对表示成对点约束信息。以ML={（xi，xj）}表示must-linked约束，CL={（xi，xj）}表示cannot-linked约束。（2）将待测数据集（data）随机地分成两部分，分别为firstDB和secondDB。（3）ML中的约束信息分成三部分，两个数据点都被分到firstDB中的约束信息，记为ML1；两个数据点都被分到secondDB中的约束信息，记为ML2；一个在firstDB中，另一个在secondDB中，此时的约束信息记为part_ML。同样地，CL也被分成了三部分，CL1、CL2以及part_CL。（4）以ML1和CL1分别

7、作为firstDB数据集的must-linked和cannot-linked约束，在firstDB上进行SAP算法，得到firstDB数据集的类代表点坐标信息cp1。（5）以ML2和CL2分别作为secondDB数据集的must-linked和cannot-linked约束，在secondDB上进行SAP算法，得到secondDB数据集的类代表点坐标信息cp2。（6）将cp1和cp2合并，作为新的待测数据集merge。（7）将part_ML和part_CL中的每对约束信息进行转换