几种聚类的算法 - 图文

几种聚类的算法 安世亚太研究院 2012-12-5 作者: 张晓燕 几种聚类的算法 目录 1.1 1.2 谱聚类 ........................................................................................................... 2 增量谱聚类 .................................................................................................... 2 一、 增量谱聚类........................................................................................................ 2 二． AFFINITY PROPAGATION 聚类算法 .............................................................................. 5 2.1 AFFINITY PROPAGATION 算法详细介绍 ........................................................................ 5 2.2 AP算法的具体过程 ............................................................................................... 7 三．K-MEANS算法简介................................................................................................. 7 四． AFFINITY PROPAGATION 算法与KMEANS 算法比较 ......................................................... 8 几种聚类的算法 | 2012/12/5 1 一、 增量谱聚类 1.1 谱聚类 谱聚类的思想是将样本看作顶点，样本间的相似度看作带权的边，从而将聚类问题转为图分割问题：找到一种图分割的方法使得连接不同组的边的权重尽可能低（这意味着组间相似度要尽可能低），组内的边的权重尽可能高（这意味着组内相似度要尽可能高）。 关于谱聚类详细算法参见：http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/luxburg06_TR_v2_4139[1].pdf 随着谱聚类的应用越来越广泛，对于谱聚类算法能否作增量计算的关注也越来越多，下一节将介绍一种的增量谱聚类的方法。 1.2 增量谱聚类 由上文我们知道谱聚类是通过计算Lq??Dq的第二小的特征值对应的特征向量来分类的，这里L 是拉普拉斯矩阵，D是degree matrix，所以想要做增量更新我们需要知道如何更新L D ?和q。 一些预备知识： 1，L?D?W这里W是相似矩阵； 2，引理1 ： T如果L = D ?W ?Rn?n是一个拉普拉斯矩阵, 那么就存在一个incidence matrix R stL?RR，并且, R包含所有 incidence vectors rij(wij), 1 ?i?j?n, that canbeinanyorder； 2，?L=L?L??wijuijuTij ~?D=L?L??wijdiag{vij} 其中uij是i行为1 j 行为-1其余元素皆为0 的列向量，vij只有i行和j 行为1其余元素皆为0 的列向量。 特征向量的增量： 几种聚类的算法 | 2012/12/5 ~?qij?(KTNijKNij)?1KTNijh 其中 K?L??D h?(??D???D??L)q 2 Nij?{kwik?0,wjk?0}：如果?wij是点i和j 之间相似性的改变，Nij是i和j 的空间邻域，我们假设?qk为0如果k?Nij然后从?q中删除?qk以及删除K 中相应的列向量，由此我们可以得到?qij?(KTNijKNij)?1KTNijh，通过这种算法可以很好的减少计算量。 特征值的增量： ????wij其中 a?b 1?c?da?(qi?qj)2??(q2i?q2j) b?(qi?qj)(?qi??qj)??(qi?qi?qj?qj) c??wij(q2i?q2j) d?k?Nij?(qd?q) kkkIterative refinement of ??和?q： 1：Set ?q=0. 2: 计算??由????wija?b。 1?c?d3：计算?q由?qij?(KTNijKNij)?1KTNijh 4：重复第2 和第3 步直到??和?q没有大的变化. 实验： 下图1是在原有的图上增加100个点第二个最小特征值的变化， 点是通过增量的算法的来的 横线是直接应用谱聚类算法的来的 几种聚类的算法 | 2012/12/5 3 0.790.780.770.760.750.740.730.720102030405060708090100 直接应用谱聚类算法得到的第二最小特征值对应的特征向量： 0.0150.010.0050-0.005-0.01-0.015-0.020100200300400500600 直接应用谱聚类算法得到的第二最小特征值对应的特征向量： 几种聚类的算法 | 2012/12/5 4