半监督AP聚类算法的并行计算.ppt

半监督AP聚类算法的并行计算
聚类算法概述
聚类分析是研究数据挖掘技术的有效手段,是一种无监督的分类方法。聚类的目标是将相似的对象划分到同一个簇中,将不相似的对象划分到不同的簇中。聚类可分为:
基于划分的聚类方法如K-means,K中心等
基于层次的聚类方法如凝聚和分裂方法
基于网格和密度的聚类方法
基于模型的聚类方法
聚类算法的数学描述
设模式样本集为, 其中为d 维模式向量, 聚类问题就是要找到一个划分, 满足􀀂
并且使得总的类间离散度和达到最小, 其中为第k 个聚类的中心, 为样本到对应聚类中心距离, 聚类准则函数J即为各类样本到对应聚类中心距离的总和。这里为欧氏空间的距离, 即。
AP聚类算法
以往的很多聚类算法都是通过选取类代表点来完成聚类的。传统的寻找类代表点的方法是,随机地选择初始类代表点集合,然后迭代调整类代表点,直到类代表点不再发生明显改变时结束,其聚类结果会受到初始类代表点选择的影响。
2007年,Frey 等人提出了一种近邻传播(Affinity Propagation,AP)算法,该算法将信任传播思想用于数据点之间的信息交换,为每个数据点找到类代表点,从而完成聚类。近邻传播算法以数据点对之间的相似度为基础,将所有的数据点都看作是潜在的类代表点,通过数据点之间交换信息,得到一个较为理想的类代表点的集合。该算法快速、有效,引起了学者的广泛关注。
2008年,软件学报的一篇文章中提出了半监督的近邻传播聚类算法(Semi-supervised clustering based on Affinity Propagation,SAP),该算法在AP算法的基础上引入半监督思想,利用成对点约束信息对相似度矩阵进行调整,然后利用AP算法进行聚类。
半监督聚类
半监督聚类是利用样本先验知识,利用有标签的样本来指导无标签的样本的聚类方法,由于在数据挖掘中获得少量有标签的样本相对比较容易,故半监督聚类算法成为机器学****中重要内容之一。
半监督聚类
主要方法:基于成对约束的方法
must-link cannot-link
基于距离的方法
利用成对约束来学****距离度量
基于约束和距离的方法
两种方法的综合
成对限制先验信息
用must-link和cannot-link来辅助聚类搜索,must-link规定两个样本必须在同一聚类中,cannot-link规定两个样本不能在同一聚类中。
传递性:
SAP聚类算法
分析SAP 算法,发现算法的时间复杂度较高,为O(n3)。随着数据集的增大,运行时间增加很快。因此给出了半监督近邻传播聚类算法的并行计算方法( PSAP ),实验发现该并行算法的运行时间约为原算法的1/8~1/4。
PSAP聚类算法
其基本思想是将待测数据集随机分成两部分,然后分别在每部分中采用SAP 算法获取相应的类代表点集合,最后将两个类代表点集合合并成新的数据集再运行一次SAP算法。
假设待测数据集的规模为n,SAP 算法的时间复杂度为O(n3),而PSAP算法由于数据规模减半,因此所耗时间约为原计算时间的1/8,从而降低了时间的消耗。
PSAP聚类算法
采用数据划分的PSAP 算法与未划分数据的SAP 算法的约束信息应一致,由于约束信息是以数据点在数据集中的序号表示的,因此PSAP算法必须将原来的约束信息传递到数据子集上。PSAP 算法主要解决待测数据集分开计算和最后的合并计算时约束信息和数据点序号的转换问题。约束信息的转换发生在数据集的分割、部分数据集的SAP聚类、聚类结果的合并以及每个原始数据点最后确定类代表点的各个时刻。约束信息的转换和数据点的序号转换是同时进行的。