《半监督AP聚类算法的并行计算》由会员分享，可在线阅读，更多相关《半监督AP聚类算法的并行计算（24页珍藏版）》请在金锄头文库上搜索。
1、半监督AP聚类算法的 并行计算,聚类算法概述,聚类分析是研究数据挖掘技术的有效手段，是一种无监督的分类方法。聚类的目标是将相似的对象划分到同一个簇中，将不相似的对象划分到不同的簇中。聚类可分为: 基于划分的聚类方法 如K-means，K中心等 基于层次的聚类方法 如凝聚和分裂方法 基于网格和密度的聚类方法 基于模型的聚类方法,聚类算法的数学描述,设模式样本集为 , 其中 为d 维模式向量, 聚类问题就是要找到一个划分 , 满足 并且使得总的类间离散度和 达到最小, 其中 为第k 个聚类的中心, 为样本到对应聚类中心距离, 聚类准则函数J即为各类样本到对应聚类中心距离的总和。这里 为欧氏空间的距
2、离, 即 。,AP聚类算法,以往的很多聚类算法都是通过选取类代表点来完成聚类的。传统的寻找类代表点的方法是，随机地选择初始类代表点集合，然后迭代调整类代表点，直到类代表点不再发生明显改变时结束，其聚类结果会受到初始类代表点选择的影响。 2007年，Frey 等人提出了一种近邻传播（Affinity Propagation，AP）算法，该算法将信任传播思想用于数据点之间的信息交换，为每个数据点找到类代表点，从而完成聚类。近邻传播算法以数据点对之间的相似度为基础，将所有的数据点都看作是潜在的类代表点，通过数据点之间交换信息，得到一个较为理想的类代表点的集合。该算法快速、有效，引起了学者的广泛关注。
3、 2008年，软件学报的一篇文章中提出了半监督的近邻传播聚类算法（Semi-supervised clustering based on Affinity Propagation，SAP），该算法在AP算法的基础上引入半监督思想，利用成对点约束信息对相似度矩阵进行调整，然后利用AP算法进行聚类。,半监督聚类,半监督聚类是利用样本先验知识，利用有标签的样本来指导无标签的样本的聚类方法，由于在数据挖掘中获得少量有标签的样本相对比较容易，故半监督聚类算法成为机器学习中重要内容之一。,半监督聚类,主要方法：基于成对约束的方法 must-link cannot-link基于距离的方法 利用成对约束来学习
4、距离度量基于约束和距离的方法 两种方法的综合,成对限制先验信息,用must-link和cannot-link来辅助聚类搜索，must-link规定两个样本必须在同一聚类中，cannot-link规定两个样本不能在同一聚类中。 传递性：,SAP聚类算法,分析SAP 算法，发现算法的时间复杂度较高，为O（n3）。随着数据集的增大，运行时间增加很快。因此给出了半监督近邻传播聚类算法的并行计算方法（ PSAP ），实验发现该并行算法的运行时间约为原算法的1/81/4。,PSAP聚类算法,其基本思想是将待测数据集随机分成两部分，然后分别在每部分中采用SAP 算法获取相应的类代表点集合，最后将两个类代表点
5、集合合并成新的数据集再运行一次SAP算法。 假设待测数据集的规模为n，SAP 算法的时间复杂度为O（n3），而PSAP算法由于数据规模减半，因此所耗时间约为原计算时间的1/8，从而降低了时间的消耗。,PSAP聚类算法,采用数据划分的PSAP 算法与未划分数据的SAP 算法的约束信息应一致，由于约束信息是以数据点在数据集中的序号表示的，因此PSAP算法必须将原来的约束信息传递到数据子集上。PSAP 算法主要解决待测数据集分开计算和最后的合并计算时约束信息和数据点序号的转换问题。约束信息的转换发生在数据集的分割、部分数据集的SAP聚类、聚类结果的合并以及每个原始数据点最后确定类代表点的各个时刻。约
6、束信息的转换和数据点的序号转换是同时进行的。,PSAP聚类算法步骤,（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
7、以及part_CL。 （4）以ML1和CL1分别作为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 中的每对约束信息进行转换整合后在merge数据集上作为约束运行SA
8、P算法。 （8）为原始数据集data中的每个点确定最后的类标号。,PSAP聚类算法,下面以一个包含40 个数据点的交叉形数据集为例说明PSAP算法的运行过程，如图1 所示。,PSAP聚类算法,其中的相似性约束为：ML=（14，23），（8，40），（10，35），CL=（8，14），（14，35），（23，35）。这里的数值均为数据点序号。图1 中3 条连线为3 个must-linked，两个黑色的圆点是并行聚类算法（PSAP）最终得出的类代表点；两个标有+号的点是非并行聚类算法（SAP）得出的类代表点。在当前约束下，正确的聚类结果应为左上角的10 个数据点和右下的10 个数据点为一簇，而左下
9、角的10个数据点和右上角的10个数据点为一簇。,PSAP聚类算法,将data 随机分成firstDB、secondDB，其中8、14、35、40 分到firstDB中，10、23 分到secondDB中，如图2 所示。,PSAP聚类算法,经过数据集的分割，每个数据点在子数据集中都有了新的序号。为了使子数据集能独立运行SAP 算法，必须将约束信息转换到子数据集上。本例中有1 个ML约束和2 个CL约束转换到firstDB 中了，而secondDB 没有得到约束信息。在firstDB 中约束信息转换过程为： ML1=（8，40）ML1=（3，19） CL1=（8，14），（14，35）CL1=（3
10、，6），（6，17）,PSAP聚类算法,此时两个数据集及其上的约束信息已经转换完毕，可以分别独立地运行SAP 算法了。由于是并行计算，这个步骤所需的时间应为两个运行时间中的较大者。每个数据集都得出自己的类代表点集合，将这两个类代表点集合合并，注意在合并之后secondDB提供的类代表点序号依次下移。,PSAP聚类算法,PSAP聚类算法,part_ML 和part_CL 约束所涉及到的数据点分别被划分在两个数据集上，只有在合并之后才能起到约束作用。具体情况如下： part_ML 中的约束（14，23），序号为14 的数据点被分到firstDB 中，新序号为6； 在firstDB 上进行SAP算法
11、，得到6 的类代表点为2。 序号为23 的数据点被分到secondDB中，新序号为12。在secondDB 上进行SAP算法，得到12 的类代表点为4，在两个类代表点集cp1和cp2合并后，cp2中的4对应合并后的7。所以，两个类代表点集合合并后约束（14，23）转换为（2，7）。其余类似。 part_ML=（14，23），（10，35）part_ML=（2，7），（5，3） part_CL=（23，35）part_CL=（7，3）,PSAP聚类算法,如此转换约束后运行SAP，得出最后的类代表点集合，如图4所示。,PSAP聚类算法,考虑原始数据集中的点，如10（2.2，1.4），在second
12、DB 中标号为7，SAP 得出的类代表点为2。该类代表点在合并后的序号为5，经过SAP 得出的类代表点为3（5.2，4.5）。从图1 中可以看出这样的类代表点是正确的。同理可以为每个原始数据点确定最终所属的类标号。在约束ML、CL 下，用SAP 算法对原始数据集进行聚类，得出的类代表点的坐标分别为（2.1，1.3）和（5.2，1.2），在图1 中用+号标出。从图1 中不难看出，虽然两个算法得出的类代表点不同，但是它们都能正确地表示聚类结果。,算法对比实验,实验数据来自UCI 数据集，测试了Iris 数据集、Wine 数据集、Glass 数据集和Heart 数据集。各数据集的基本情况下表所示。,
13、算法对比实验,测试方案为：指定约束个数如100，给出10 组约束个数均为100 的约束集合，其中must-linked 和cannot-linked各占一半。采用相同的约束测试每个算法，记录相应的结果。,结论,主要工作是将半监督的近邻传播算法SAP 并行化，为了保持成对点约束信息不变，给出了数据序号转换和约束转换方法。实验证实PSAP可以在SAP运行时间的1/81/4 内完成半监督聚类，节约了运行时间。在PSAP 中，每个数据子集都能抽取出各自的类代表点，在一定程度上去掉了冗余信息，然后在所有类代表点中找出整个数据集的类代表点，因此PSAP的聚类质量有所提高。,THE END ,Thank you,
