几种聚类的算法.docxVIP

几种聚类的算法目录一、增量谱聚类21.1谱聚类21.2增量谱聚类2二． Affinity propagation 聚类算法52.1 Affinity propagation 算法详细介绍52.2 AP算法的具体过程7三．K-MEANS算法简介7四． Affinity propagation 算法 与Kmeans 算法比较8增量谱聚类 谱聚类谱聚类的思想是将样本看作顶点，样本间的相似度看作带权的边，从而将聚类问题转为图分割问题：找到一种图分割的方法使得连接不同组的边的权重尽可能低（这意味着组间相似度要尽可能低），组内的边的权重尽可能高（这意味着组内相似度要尽可能高）。关于谱聚类详细算法参见：http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/luxburg06_TR_v2_4139%5b1%5d.pdfhttp://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/luxburg06_TR_v2_4139%5b1%5d.pdf随着谱聚类的应用越来越广泛，对于谱聚类算法能否作增量计算的关注也越来越多，下一节将介绍一种的增量谱聚类的方法。增量谱聚类由上文我们知道谱聚类是通过计算的第二小的特征值对应的特征向量来分类的，这里L 是拉普拉斯矩阵，D是degree matrix，所以想要做增量更新我们需要知道如何更新L D 和q。一些预备知识：1， 这里W是相似矩阵；2，引理1 ：如果 L = D ?W 是一个拉普拉斯矩阵, 那么就存在一个incidence matrix R st ，并且, R包含所有 incidence vectors , , that can be in any order；2， 其中是i 行为1 j 行为-1其余元素皆为0 的列向量，只有i 行和j 行为1其余元素皆为0 的列向量。特征向量的增量：其中：如果是点 i和j 之间相似性的改变， 是i和j 的空间邻域，我们假设 为0如果 然后从 中删除以及删除K 中相应的列向量，由此我们可以得到，通过这种算法可以很好的减少计算量。特征值的增量：其中 Iterative refinement of 和：1：Set =0.2:计算由 。3： 计算 由 4：重复第2 和第3 步直到和 没有大的变化.实验：下图1是在原有的图上增加100个点 第二个最小特征值的变化，点是通过增量的算法的来的横线是直接应用谱聚类算法的来的直接应用谱聚类算法得到的第二最小特征值对应的特征向量：直接应用谱聚类算法得到的第二最小特征值对应的特征向量：结论：为了避免实验误差，增量R次后 要对数据进行初始化，i.e. 用谱聚类的传统算法重新计算L 等，在进行增量计算。实验数据对实验结果又有很大的影响，所以R的选择要具体问题具体分析。二． Affinity propagation 聚类算法Affinity Propagation (AP) 聚类是最近在Science杂志上提出的一种新的聚类算法。它根据N个数据点之间的相似度进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度一样(如欧氏距离);也可以是不对称的,即两个数据点互相之间的相似度不等。这些相似度组成N×N的相似度矩阵S(其中N为有N个数据点)。AP算法不需要事先指定聚类数目,相反它将所有的数据点都作为潜在的聚类中心,称之为exemplar。2.1 Affinity propagation 算法详细介绍以S矩阵的对角线上的数值s (k, k)作为k点能否成为聚类中心的评判标准,这意味着该值越大,这个点成为聚类中心的可能性也就越大,这个值又称作参考度p ( preference) 。聚类的数量受到参考度p的影响,如果认为每个数据点都有可能作为聚类中心,那么p就应取相同的值。如果取输入的相似度的均值作为p的值,得到聚类数量是中等的。如果取最小值,得到类数较少的聚类。AP算法中传递两种类型的消息, (responsiblity)和(availability) 。r(i,k)表示从点i发送到候选聚类中心k的数值消息,反映k点是否适合作为i点的聚类中心。a(i,k)则从候选聚类中心k发送到i的数值消息,反映i点是否选择k作为其聚类中心。r (i, k)与a (i, k)越强,则k点作为聚类中心的可能性就越大,并且i点隶属于以k点为聚类中心的聚类的可能性也越大。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值,直到产生m个高质量的exemplar,同时将其余的数据点分配到相应的聚类中。在这里介绍几个文中常出现的名词：exemplar：