聚类算法简介

聚类算法简介最小生成树聚类K-means聚类密度峰聚类最小生成树聚类•什么是最小生成树？最小生成树定义MinimumSpanningTree（MST）在一给定的无向图G=(V,E)中，(u,v)代表连接顶点u与顶点v的边（即(u,v)∈E），而w(u,v)代表此边的权重，若存在T为E的子集（即T⊂E）且为无循环图，使得w(T)=(u,v)∈Tw(u,v)的w(T)最小，则此T为G的最小生成树。最小生成树其实是最小权重生成树的简称。构造最小生成树的算法•Prim算法（普里姆算法）•Kruskal算法（克鲁斯克尔算法）两者皆为贪婪算法Prim算法•此为原始的加权连通图。每条边一侧的数字代表其权值。•顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。•下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。•算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。•在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E最近，因此将顶点E与相应边BE高亮表示。•这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。•顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。•现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。Kruskal算法•首先第一步，我们有一张图Graph，有若干点和边•将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想，资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。这样我们的图就变成了下图•在剩下的边中寻找。我们找到了CE。这里边的权重也是5•依次类推我们找到了6,7,7，即DF，AB，BE。•下面继续选择，BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了，所以不需要选择他们。类似的BD也已经连通了，最后就剩下EG和FG了，当然我们选择了EG。最小生成树性质•最小生成树的边数必然是顶点数减一，|E|=|V|-1。•最小生成树不可以有循环。•最小生成树不必是唯一的。最小生成树聚类步骤•构造完全图G，计算每条边的权重（距离）•求出完全图G的最小生成树（MST）•删除权值大于给定阈值的边•聚类结果就是删除这些边后，MST仍然连在一起的部分•优点•只需计算一次距离•Prim算法时间复杂度O(𝑉2)，V为顶点数•Kruskal算法时间复杂度O(𝐸𝑙𝑜𝑔2𝐸)，E为边数•缺点•需要给定聚类阈值K-means聚类•k-means算法是一种得到最广泛使用的基于划分的聚类算法，把n个对象分为k个簇，以使簇内具有较高的相似度。•算法首先随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇，然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。算法过程•样本点{𝑥1…𝑥𝑛},每个𝑥𝑖∈𝑅𝑑,目标是将这𝑛点分配到𝑘(𝑘≤𝑛)个集合𝑆={𝑆1…𝑆𝑘}使得准则函数𝑉最小:𝑉=𝑖=1𝑘𝑥𝑗∈𝑆𝑖:||𝑥𝑗−𝜇𝑖||2𝜇𝑖为𝑆𝑖中的点的平均.•0.随机选取𝑘个聚类质心𝑚1(1)…𝑚𝑘1•迭代以下两步直到收敛•1.每个点分配到𝑘个聚类中距离最近的那个类𝑆𝑖(𝑡)={𝑥𝑝:||𝑥𝑝−𝑚𝑖(𝑡)||2≤||𝑥𝑝−𝑚𝑗(𝑡)||2∀𝑗，1≤𝑗≤𝑘}•2.计算新的质心𝑚𝑖(𝑡+1)=1|𝑆𝑖(𝑡)|𝑥𝑗∈𝑆𝑖(𝑡)𝑥𝑗•优点算法尝试找出使平方误差函数值最小的𝑘个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。•缺点需要事先给定簇类数目𝑘对初值敏感需要反复迭代，计算距离，运算量大一般会得到局部最优解密度峰聚类•源于《Clusteringbyfastsearchandfindofdensitypeak》.AlexRodriguez,AlessandroLaio•发表于Science上的一篇聚类算法文章•作者(AlexRodriguez,AlessandroLaio)提出了一种很简洁优美的聚类算法,可以识别各种形状的类簇,并且其参数很容易确定.•原理该算法的假设是类簇的中心由一些局部密度比较低的点围绕,并且这些中心点距离其他有高局部密度的点的距离都比较大.•局部密度𝜌𝑖:𝜌𝑖=𝑗𝜒(𝑑𝑖𝑗−𝑑𝑐)𝜒𝑥=1𝑖𝑓𝑥0𝜒𝑥=0otherwise𝑑𝑖𝑗表示𝑖,𝑗两点间的距离，满足三角不等式。𝑑𝑐是一个截断距离,是一个参数。所以𝜌𝑖相当于距离点𝑖的距离小于𝑑𝑐的点的个数。•距离高密度点的最近距离𝛿𝑖（最近邻距离）：𝛿𝑖=min𝑗:𝜌𝑗𝜌𝑖(𝑑𝑖𝑗)即为点𝑖到其他密度比其大的点的最小距离对于密度最大的点𝛿𝑖=max𝑗(𝑑𝑖𝑗)•以𝜌𝑖为横轴，𝛿𝑖为纵轴画图•注意到只有全局或者局部密度最大的点的𝛿𝑖才远大于一般的最近邻距离，所以聚类中心就是这些𝛿𝑖异常大的点•𝑑𝑐的选取方法一种推荐做法是选择𝑑𝑐使得平均每个点的邻居数为所有点的1%-2%•算法中具体实现的方法就是选取最小的2%的距离做截断，也就是最小的2%的距离中最大的那个距离就是𝑑𝑐•得到聚类中心之后，如何分配每个剩余点所属的聚类？•考虑𝛿𝑖的计算方法𝛿𝑖=min𝑗:𝜌𝑗𝜌𝑖(𝑑𝑖𝑗)•令𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟𝑖=𝑎𝑟𝑔min𝑗:𝜌𝑗𝜌𝑖(𝑑𝑖𝑗)，此为密度比𝑖大的点中与𝑖距离最近的点，定义为点𝑖的“邻居”•按密度从大到小排序，每个剩余点分配到与他的“邻居”同一个聚类，因为𝑅ℎ𝑜𝑖𝑅ℎ𝑜(𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟𝑖),分配可以一步到位•优点只需计算一次距离，不需要参数，不需要迭代，可以针对对各种类型的点集聚类谢谢！