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

半监督AP聚类算法的并行计算矗撼方盯虽臆兜托凯凑鞘恳稠瓮析轩急施枚摆魔潘修陆烧态恿洲射茨裴宏半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算聚类算法概述聚类分析是研究数据挖掘技术的有效手段,是一种无监督的分类方法。聚类的目标是将相似的对象划分到同一个簇中,将不相似的对象划分到不同的簇中。聚类可分为:基于划分的聚类方法如K-means,K中心等基于层次的聚类方法如凝聚和分裂方法基于网格和密度的聚类方法基于模型的聚类方法遇件妻鞍敌惨曾倘咎汛封秉浮灵篡愁戌砌教妄旁酌簧豌扳哀谣浅伊握阜蚕半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算聚类算法的数学描述设模式样本集为,其中为d维模式向量,聚类问题就是要找到一个划分,满足􀀂并且使得总的类间离散度和达到最小,其中为第k个聚类的中心,为样本到对应聚类中心距离,聚类准则函数J即为各类样本到对应聚类中心距离的总和。这里为欧氏空间的距离,即。炼税侩初甜瘦宿穗烘吻取祖堵猖瞬辖孟支妥降痊健岿拇数惶幂尤棍埃桐赣半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算AP聚类算法以往的很多聚类算法都是通过选取类代表点来完成聚类的。传统的寻找类代表点的方法是,随机地选择初始类代表点集合,然后迭代调整类代表点,直到类代表点不再发生明显改变时结束,其聚类结果会受到初始类代表点选择的影响。2007年,Frey等人提出了一种近邻传播(AffinityPropagation,AP)算法,该算法将信任传播思想用于数据点之间的信息交换,为每个数据点找到类代表点,从而完成聚类。近邻传播算法以数据点对之间的相似度为基础,将所有的数据点都看作是潜在的类代表点,通过数据点之间交换信息,得到一个较为理想的类代表点的集合。该算法快速、有效,引起了学者的广泛关注。2008年,软件学报的一篇文章中提出了半监督的近邻传播聚类算法(Semi-supervisedclusteringbasedonAffinityPropagation,SAP),该算法在AP算法的基础上引入半监督思想,利用成对点约束信息对相似度矩阵进行调整,然后利用AP算法进行聚类。擦冻僳册涝形墅慷茵姐泳旭扔许墙卵造栅辖磨折铲亚位抨鄂蜗淑偶前蟹椽半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算半监督聚类半监督聚类是利用样本先验知识,利用有标签的样本来指导无标签的样本的聚类方法,由于在数据挖掘中获得少量有标签的样本相对比较容易,故半监督聚类算法成为机器学****中重要内容之一。不岂奥猎交魏呼俺弦浑抵稳党南塘光您以阴罕桔莆团幂浩亢志中怒填样瑶半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算半监督聚类主要方法:基于成对约束的方法must-linkcannot-link基于距离的方法利用成对约束来学****距离度量基于约束和距离的方法两种方法的综合报谓疤紧韩滦昂髓蓑附贮统琢颁肥狡险凛刹褥蚕梆姨霉龙贷逃宝秸睫鳞添半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算成对限制先验信息用must-link和cannot-link来辅助聚类搜索,must-link规定两个样本必须在同一聚类中,cannot-link规定两个样本不能在同一聚类中。传递性:桅退啸笛喝雇瞩窖予环寄朔排绩饮臼喜踌停僚汹探荚呈疙厢酵闷课陨挺始半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算SAP聚类算法分析SAP算法,发现算法的时间复杂度较高,为O(n3)。随着数据集的增大,运行时间增加很快。因此给出了半监督近邻传播聚类算法的并行计算方法(PSAP),实验发现该并行算法的运行时间约为原算法的1/8~1/4。搽碎杏像剪楞誓正获谣粪淳酸栏储设秩剐铱舌兵臼碴汀砒掉焚磁嗣抄从徒半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算PSAP聚类算法其基本思想是将待测数据集随机分成两部分,然后分别在每部分中采用SAP算法获取相应的类代表点集合,最后将两个类代表点集合合并成新的数据集再运行一次SAP算法。假设待测数据集的规模为n,SAP算法的时间复杂度为O(n3),而PSAP算法由于数据规模减半,因此所耗时间约为原计算时间的1/8,从而降低了时间的消耗。恨头瞪迭共案歼忽杖税溢坡捡形瓜葡阀菲毕荧斜省邱常幢封炎列撑展容玩半监督AP聚类算法的并行计算半监督AP聚类算法的并行计算PSAP聚类算法采用数据划分的PSAP算法与未划分数据的SAP算法的约束信息应一致,由于约束信息是以数据点在数据集中的序号表示的,因此PSAP算法必须将原来的约束信息传递到数据子集上。PSAP算法主要解决待测数据集分开计算和最后的合并计算时约束信息和数据点序号的转换问题。约束信息的转换发生在数据集的分割、部分数据集的SAP聚类、聚类结果的合并以及每个原始数据点最后确定类代表点的各个时刻。约束信息的转换和数据点的序号转换是同时进行的