《各种聚类算法介绍及对比》由会员分享，可在线阅读，更多相关《各种聚类算法介绍及对比（9页珍藏版）》请在金锄头文库上搜索。
1、、层次聚类1、层次聚类的原理及分类1) 层次法( Hierarchical methods ) 先计算样本之间的距离。每次将距离最近的点合并到同 一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并， 直到合成了一个类。 其中类与类的距离的计算方法有：最短距离法，最长距离法， 中间距离 法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为： 自下底向上和自上向下， 即凝聚的层次聚类算法和 分裂的层次聚类算法( agglomerative 和 divisive )，也可以理解为自下而上法( bottom-up
2、 ) 和自上而下法( top-down )。 自下而上法就是一开始每个个体( object )都是一个类，然后 根据 linkage 寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都 属于一个“类”，然后根据 linkage 排除异己，最后每个个体都成为一个“类”。 这两种路 方法没有孰优孰劣之分， 只是在实际应用的时候要根据数据特点以及你想要的 “类”的个数， 来考虑是自上而下更快还是自下而上更快。至于根据 Linkage 判断“类”的方法就是最短距 离法、 最长距离法、 中间距离法、类平均法等等(其中类平均法往往被认为是最常用也最好 用的方法，一方面因为其良好的单调性，
3、另一方面因为其空间扩张 / 浓缩的程度适中)。为 弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。2) Hierarchical methods 中比较新的算法有 BIRCH( Balanced Iterative Reducing and Clustering Using Hierarchies 利用层次方法的平衡迭代规约和聚类)主要是在数据量很大的时候使用， 而且数据类型是 numerical 。首先利用树的结构对对象集进行划分，然后再利用其它聚类方 法对这些聚类进行优化； ROCK( A Hierarchical Clustering Algorithm for C
4、ategorical Attributes ) 主要用在 categorical 的数据类型上 ； Chameleon( A Hierarchical Clustering Algorithm Using Dynamic Modeling )里用到的 linkage 是 kNN( k-nearest-neighbor )算法，并以此构建一个 graph ， Chameleon的聚类效果被认为非常强大，比 BIRCH好用，但运算复杂度很高， O(nA2)。2、层次聚类的流程凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇， 直到所有对象都在一个簇中， 或者某个终结条
5、件被满足。 绝大多数层次聚类属于凝聚型层次 聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程：(1) 将每个对象看作一类，计算两两之间的最小距离；(2) 将距离最小的两个类合并成一个新类；(3) 重新计算新类与所有类之间的距离；(4) 重复 (2) 、 (3) ，直到所有类最后合并成一类。聚类的效果如下图，黑色是噪音点：VA.,4t * flk:“哄*二兮-u1 r * .另外我们可以看出凝聚的层次聚类并没有类似基本K均值的全局目标函数，没有局部极小问题或是很难选择初始点的问题。合并的操作往往是最终的，一旦合并两个簇之后就不会撤销。当然其计算存储的代价是昂
6、贵的。3、层次聚类的优缺点优点：1,距离和规则的相似度容易定义，限制少；2，不需要预先制定聚类数；3，可以发现类的层次关系；4,可以聚类成其它形状缺点：1,计算复杂度太高；2,奇异值也能产生很大影响；3，算法很可能聚类成链状r语言中使用 hclust(d, method = complete, members=NULL):进行层次聚类。d为距离矩阵； method表示类的合并方法，single最短距离法，complete最长距离法，median中间距离法， mcquitty相似法，average类平均法，centroid重心法，ward离差平方和法；members为NULL 或d长度的矢量。二
7、、划分聚类法k-means基于划分的方法(Partition-based methods )：其原理简单来说就是，想象你有一堆散点需 要聚类，想要的聚类效果就是“类内的点都足够近，类间的点都足够远”。首先你要确定这堆散点最后聚成几类，然后挑选几个点作为初始中心点，再然后依据预先定好的启发式算法(heuristic algorithms )给数据点做迭代重置(iterative relocation )，直到最后到达“类内的 点都足够近，类间的点都足够远”的目标效果。Partition-based methods聚类多适用于中等体量的数据集，但我们也不知道“中等”到底有多“中”，所以不妨理解成，
8、数据集越大，越有可能陷入局部最小。1、Kmeans算法的原理k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相 似度较低。k-means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代 表了一个簇的平均值或中心，即选择K个初始质心；对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；然后重新计算每个簇的平均值。这个过程不断重复，直到准则 函数收敛，直到质心不发生明显的变化。通常，采用平方误差准则，误差的平方和SSE作为此时，簇的质心就全局的目标函数，即最小化每个点到最近质心的欧几里得距离的平方和。 是该簇内所有数据点的平均值 。选择K个
9、点作为初始质心repeat将每个点指派到最近的质心，形成K个簇重新计算每个簇的质心un til簇不发生变化或达到最大迭代次数时间复杂度：O（tKmn），其中，t为迭代次数，K为簇的数目，m为记录数，n为维数空间复杂度：O（m+K）n），其中，K为簇的数目，m为记录数，n为维数#K-Means算法的详细过程从上图中，我们可以看到，A, B, C, D, E是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。然后，K-Means的算法如下： 随机在图中取 K （这里K=2）个种子点。 然后对图中的所有点求到这K个种子点的距离，假如点 Pi离种子点Si最近，
10、那么Pi属于Si点群。（我们可以看到A,B属于上面的种子点，C,D,E属于下面中部的种子点） 接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步） 然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了 A,B,C,下面的种子点聚合了D, E）。聚类的效果如下图，折线是历次循环时3个簇的质心的更新轨迹，黑点是初始质心:我们查看基本K均值算法实现步骤及上面的聚类效果可以发现, 进行了指派，不识别噪音点。另外选择适当的初试质心是基本该聚类算法将所有数据点都K均值过程的关键。2、k均值的优缺点及分类2，时间复杂度低优点：1,简单，易于理解和实现;
11、缺点：1) kmeans 要手工输入类数目， 对初始值的设置很敏感 ；所以有了 k-means+、 intelligent k-means、 genetic k-means ；2) k-means 对噪声和离群值非常敏感 ，所以有了 k-medoids 和 k-medians ；3) k-means 只用于 numerical 类型数据，不适用于 categorical 类型数据 ，所以 k-modes ；4) k-means 不能解决非凸( non-convex )数据 ，所以有了 kernel k-means 。5) k-means 主要发现圆形或者球形簇，不能识别非球形的簇。3、k-me
12、ans 与 DBSCAN的区别k-means聚类算法的初始点选择不稳定，是随机选取的，这就引起聚类结果的不稳定。k-means属于动态聚类， 往往聚出来的类有点圆形或者椭圆形。 kmeans 对于圆形区域聚类效果较好， dbscan 基于密度，对于集中区域效果较好。对于不规则形状，kmeans 完全无法用， dbscan可以起到很好的效果。4、k-means注意问题1)K 如何确定kmenas算法首先选择K个初始质心，其中 K是用户指定的参数，即所期望的簇的个 数。这样做的前提是我们已经知道数据集中包含多少个簇， 但很多情况下， 我们并不知道数 据的分布情况，实际上聚类就是我们发现数据分布的一
13、种手段。如何有效的确定 K值，这里大致提供几种方法： 与层次聚类结合 2经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗 的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。 稳定性方法 3稳定性方法对一个数据集进行 2 次重采样产生 2个数据子集， 再用相同的聚类算法对 2个数据子集进行聚类，产生 2个具有k个聚类的聚类结果，计算 2个聚类结果的相似度的 分布情况。2个聚类结果具有高的相似度说明k个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个k，找到合适的k值。 系统演化方法 3系统演化方法将一个数据集视为伪热力学系统，当数据集被划
14、分为K个聚类时称系统处于状态K。系统由初始状态 K=1出发，经过分裂过程和合并过程，系统将演化到它的稳 定平衡状态Ki,所对应的聚类结构决定了最优类数Ki。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，适用于明显分离的聚类结构和轻微重叠的聚类结构。 使用 canopy 算法进行初始划分 4基于 Canopy Method 的聚类算法将聚类过程分为两个阶段Stagel、聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、 计算代价较低的方法计算对象相似性, 将相似的对象放在一个子集中, 这个子 集被叫做 Canopy ,通过一系列计算得到若干
15、Canopy, Canopy 之间可以是重叠的,但不会 存在某个对象不属于任何 Canopy 的情况,可以把这一阶段看做数据预处理；Stage2、在各个Canopy内使用传统的聚类方法(如K-means),不属于同一 Canopy的 对象之间不进行相似性计算。从这个方法起码可以看出两点好处：首先， Canopy 不要太大且 Canopy 之间重叠的不要太 多的话会大大减少后续需要计算相似性的对象的个数； 其次，类似于 K-means 这样的聚类方 法是需要人为指出 K的值的，通过Stagel得到的Canopy个数完全可以作为这个 K值，一 定程度上减少了选择 K的盲目性。其他方法如贝叶斯信息准则方法（BIC）可参看文献5。2）初始质心的选取选择适当的初始质心是基本 kmeans 算法的关键步骤。常见的方法是随机的选取初 始质心，但是这样簇的质量常常很差。 处理选取初始质心问题的一种常用技术是： 多次运行， 每次使用一组不同的随机初始质心，然后选取具有最小SSE（误差的平方和）的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。第二种有效的方法是，取一个样
