各种聚类算法介绍及对比(9页).docx

-第 1 页各种聚类算法介各种聚类算法介绍及对比绍及对比-第 2 页一一、层次聚类层次聚类1、层次聚类的原理及分类、层次聚类的原理及分类1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative 和 divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个类，然后根据 linkage 寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据 linkage 排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据 Linkage 判断“类”的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。2）Hierarchical methods 中比较新的算法有 BIRCH（Balanced Iterative Reducing and ClusteringUsing Hierarchies 利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是 numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在 categorical 的数据类型上；Chameleon（A Hierarchical Clustering Algorithm UsingDynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon 的聚类效果被认为非常强大，比 BIRCH 好用，但运算复杂度很高，O(n2)。2、层次聚类的流程、层次聚类的流程凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程：(1)将每个对象看作一类，计算两两之间的最小距离；(2)将距离最小的两个类合并成一个新类；(3)重新计算新类与所有类之间的距离；(4)重复(2)、(3)，直到所有类最后合并成一类。聚类的效果如下图，黑色是噪音点：另外我们可以看出凝聚的层次聚类并没有类似基本 K 均值的全局目标函数，没有局部极小问题或是很难选择初始点的问题。合并的操作往往是最终的，一旦合并两个簇之后就不会撤销。当然其计算存储的代价是昂贵的。-第 3 页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 长度的矢量。二、划分聚类法二、划分聚类法 k-meansk-means基于划分的方法（Partition-based methods）：其原理简单来说就是，想象你有一堆散点需要聚类，想要的聚类效果就是“类内的点都足够近，类间的点都足够远”。首先你要确定这堆散点最后聚成几类，然后挑选几个点作为初始中心点，再然后依据预先定好的启发式算法（heuristic algorithms）给数据点做迭代重置（iterative relocation），直到最后到达“类内的点都足够近，类间的点都足够远”的目标效果。Partition-based methods 聚类多适用于中等体量的数据集，但我们也不知道“中等”到底有多“中”，所以不妨理解成，数据集越大，越有可能陷入局部最小。1、Kmeans 算法的原理算法的原理k-means 算法以 k 为参数，把 n 个对象分成 k 个簇，使簇内具有较高的相似度，而簇间的相似度较低。k-means 算法的处理过程如下：首先，随机地选择 k 个对象，每个对象初始地代表了一个簇的平均值或中心，即选择 K 个初始质心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛，直到质心不发生明显的变化。通常，采用平方误差准则，误差的平方和 SSE 作为全局的目标函数，即最小化每个点到最近质心的欧几里得距离的平方和。此时，簇的质心就是该簇内所有数据点的平均值。选择 K 个点作为初始质心repeat将每个点指派到最近的质心，形成 K 个簇重新计算每个簇的质心until 簇不发生变化或达到最大迭代次数时间复杂度：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）个种子点。-第 4 页然后对图中的所有点求到这 K 个种子点的距离，假如点 Pi 离种子点 Si 最近，那么 Pi 属于Si 点群。（我们可以看到 A,B 属于上面的种子点，C,D,E 属于下面中部的种子点）接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）然后重复第 2）和第 3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了 A,B,C，下面的种子点聚合了 D，E）。聚类的效果如下图，折线是历次循环时 3 个簇的质心的更新轨迹，黑点是初始质心：我们查看基本 K 均值算法实现步骤及上面的聚类效果可以发现，该聚类算法将所有数据点都进行了指派，不识别噪音点。另外选择适当的初试质心是基本 K 均值过程的关键。2、k 均值的优缺点及分类均值的优缺点及分类优点：1，简单，易于理解和实现；2，时间复杂度低缺点：1）kmeans 要手工输入类数目，对初始值的设置很敏感；所以有了 k-means+、intelligentk-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-means 与与 DBSCAN 的区别的区别k-means聚类算法的初始点选择不稳定，是随机选取的，这就引起聚类结果的不稳定。k-means属于动态聚类，往往聚出来的类有点圆形或者椭圆形。kmeans 对于圆形区域聚类效果较好，dbscan 基于密度，对于集中区域效果较好。对于不规则形状，kmeans 完全无法用，dbscan可以起到很好的效果。4、k-means 注意问题注意问题1）K 如何确定kmenas 算法首先选择 K 个初始质心，其中 K 是用户指定的参数，即所期望的簇的个数。这样做的前提是我们已经知道数据集中包含多少个簇，但很多情况下，我们并不知道数据的分布情况，实际上聚类就是我们发现数据分布的一种手段。如何有效的确定 K 值，这里大致提供几种方法：与层次聚类结合2经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。稳定性方法3稳定性方法对一个数据集进行 2 次重采样产生 2 个数据子集，再用相同的聚类算法对2 个数据子集进行聚类，产生 2 个具有 k 个聚类的聚类结果，计算 2 个聚类结果的相似度的分布情况。2 个聚类结果具有高的相似度说明 k 个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个 k，找到合适的 k 值。-第 5 页系统演化方法3系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为 K 个聚类时称系统处于状态 K。系统由初始状态 K=1 出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态 Ki，所对应的聚类结构决定了最优类数 Ki。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，适用于明显分离的聚类结构和轻微重叠的聚类结构。使用 canopy 算法进行初始划分4基于 Canopy Method 的聚类算法将聚类过程分为两个阶段Stage1、聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method 在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做 Canopy，通过一系列计算得到若干 Canopy，Canopy 之间可以是重叠的，但不会存在某个对象不属于任何 Canopy 的情况，可以把这一阶段看做数据预处理；Stage2、在各个 Canopy 内使用传统的聚类方法(如 K-means)，不属于同一 Canopy 的对象之间不进行相似性计算。从这个方法起码可以看出两点好处：首先，Canopy 不要太大且 Canopy 之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于 K-means 这样的聚类方法是需要人为指出 K 的值的，通过 Stage1 得到的 Canopy 个数完全可以作为这个 K 值，一定程度上减少了选择 K 的盲目性。其他方法如贝叶斯信息准则方法（BIC）可参看文献5。2）初始质心的选取选择适当的初始质心是基本 kmeans 算法的关键步骤。常见的方法是随机的选取初始质心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小 SSE（误差的平方和）的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取 K 个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：（1）样本相对较小，例如数百到数千（层次聚类开销较大）；（2）K 相对于样本大小较小第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少（多了就不是离群点了），它们多半不会在随机样本中出现。计算量也大幅减少。第四种方法就是上面提到的 canopy 算法。3）距离的度量常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间-1,1，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？从几何意义上来说，n 维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。-第 6 页4）质心的计算对于距离度量不管是采用欧式距离还是采用余弦相似度，簇的质心都是其均值，即向量各维取平均即可。5）算法停止条件一般是目标函数达到最优或者达到最大的迭代次数即可终止。对于不同的距离度量，目标函数往往不同。当采用欧式距离时，目标函数一般为最小化对象到其簇质心的距离的平方和。当采用余弦相似度时，目标函数一般为最大化对象到其簇质心的余弦相似度和。6）空聚类的处理如果所有的点在指派步骤都未分配到某个簇，就会得到空簇。如果这种情况发生，则需要某种策略来选择一个替补质心，否则的话，平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。另一种方法是从具有最大 SSE 的簇中选择一个替补的质心。这将分裂簇并降低聚类的总 SSE。如果有多个空簇，则该过程重复多次。另外，编程实现时，要注意空簇可能导致的程序 bug。三三、基于密度的聚类基于密度的聚类基于密度的方法（Density-based methods）：k-means 解决不了不规则形状的聚类。于是就有了 Density-based methods 来系统解决这个问题。该方法同时也对噪声数据的处理比较好。基于密度聚类的思想：思路就是定一个距离半径，最少有多少个点，然后把可以到达的点都连起来，判定为同类。其原理简单说画圈儿，其中要定义两个参数，一个是圈儿的最大半径，一个是一个圈儿里最少应容纳几个点。最后在一个圈里的，就是一个类。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）就是其中的典型，可惜参数设置也是个问题，对这两个参数的设置非常敏感。DBSCAN 的扩展叫 OPTICS（Ordering Points ToIdentify Clustering Structure）通过优先对高密度（high density）进行搜索，然后根据高密度的特点设置参数，改善了 DBSCAN 的不足。1、DBSCAN 的概念的概念dbscan 基于密度，对于集中区域效果较好，为了发现任意形状的簇，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域；一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据中发现任意形状的簇。DBSCAN 中的几个定义：邻域：给定对象半径为内的区域称为该对象的邻域；核心对象：如果给定对象领域内的样本点数大于等于 MinPts，则称该对象为核心对象；直接密度可达：对于样本集合 D，如果样本点 q 在 p 的领域内，并且 p 为核心对象，那么对象 q 从对象 p 直接密度可达。密度可达：对于样本集合 D，给定一串样本点 p1,p2.pn，p=p1,q=pn,假如对象 pi 从 pi-1 直接密度可达，那么对象 q 从对象 p 密度可达。注意：密度可达是单向的，密度可达即可容纳同一类。密度相连：存在样本集合 D 中的一点 o，如果对象 o 到对象 p 和对象 q 都是密度可达的，那么 p 和 q 密度相联。-第 7 页密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相连是对称关系。DBSCAN 目的是找到密度相连对象的最大集合。有了以上的概念接下来就是算法描述了：DBSCAN 通过检查数据库中每点的 r 邻域来搜索簇。如果点p的r邻域包含的点多于MinPts个，则创建一个以p为核心对象的新簇。然后，DBSCAN迭代的聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以添加到任何簇时，该过程结束。例如：Eg:假设半径=3，MinPts=3，点 p 的 E 领域中有点m,p,p1,p2,o,点 m 的 E 领域中有点m,q,p,m1,m2,点 q 的 E 领域中有点q,m,点 o 的 E 领域中有点o,p,s,点 s 的 E 领域中有点o,s,s1.那么核心对象有 p,m,o,s(q 不是核心对象，因为它对应的 E 领域中点数量等于 2，小于MinPts=3)；点 m 从点 p 直接密度可达，因为 m 在 p 的 E 领域内，并且 p 为核心对象；点 q 从点 p 密度可达，因为点 q 从点 m 直接密度可达，并且点 m 从点 p 直接密度可达；点 q 到点 s 密度相连，因为点 q 从点 p 密度可达，并且 s 从点 p 密度可达。2、簇的生成原理及过程、簇的生成原理及过程1）DBSCAN 聚类算法原理的基本要点：确定半径 eps 的值DBSCAN 算法需要选择一种距离度量，对于待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度，说明了点与点是否能够聚到同一类中。由于 DBSCAN 算法对高维数据定义密度很困难，所以对于二维空间中的点，可以使用欧几里德距离来进行度量。DBSCAN 算法需要用户输入 2 个参数：一个参数是半径（Eps），表示以给定点 P 为中心的圆形邻域的范围；另一个参数是以点 P 为中心的邻域内最少点的数量（MinPts）。如果满足：以点 P 为中心、半径为 Eps 的邻域内的点的个数不少于 MinPts，则称点 P 为核心点。DBSCAN 聚类使用到一个 k-距离的概念，k-距离是指：给定数据集 P=p(i);i=0,1,n，对于任意点 P(i)，计算点 P(i)到集合 D 的子集 S=p(1),p(2),p(i-1),p(i+1),p(n)中所有点之间的距离，距离按照从小到大的顺序排序，假设排序后的距离集合为 D=d(1),d(2),d(k-1),d(k),d(k+1),d(n)，则 d(k)就被称为 k-距离。也就是说，k-距离是点 p(i)到所有点（除了 p(i)点）之间距离第 k 近的距离。对待聚类集合中每个点 p(i)都计算 k-距离，最后得到所有点的 k-距离集合 E=e(1),e(2),e(n)。根据经验计算半径 Eps：根据得到的所有点的 k-距离集合 E，对集合 E 进行升序排序后得到 k-距离集合 E，需要拟合一条排序后的 E集合中 k-距离的变化曲线图，然后绘出曲线，通过观察，将急剧发生变化的位置所对应的 k-距离的值，确定为半径 Eps 的值。根据经验计算最少点的数量 MinPts：确定 MinPts 的大小，实际上也是确定 k-距离中 k 的值，DBSCAN 算法取 k=4，则 MinPts=4。另外，如果觉得经验值聚类的结果不满意，可以适当调整 Eps 和 MinPts 的值，经过多次迭代计算对比，选择最合适的参数值。可以看出，如果 MinPts 不变，Eps 取得值过大，会导致大多数点都聚到同一个簇中，Eps 过小，会导致一个簇的分裂；如果 Eps 不变，MinPts 的值取得过大，会导致同一个簇中点被标记为噪声点，MinPts 过小，会导致发现大量的核心点。我们需要知道的是，DBSCAN 算法，需要输入 2 个参数，这两个参数的计算都来自经验知识。半径 Eps 的计算依赖于计算 k-距离，DBSCAN 取 k=4，也就是设置 MinPts=4，然后需要根据k-距离曲线，根据经验观察找到合适的半径 Eps 的值。2）连通核心点生成簇-第 8 页核心点能够连通（有些书籍中称为：“密度可达”），它们构成的以 Eps 长度为半径的圆形邻域相互连接或重叠，这些连通的核心点及其所处的邻域内的全部点构成一个簇。假设MinPts=4，则连通的核心点示例，如下图所示：计算连通的核心点的思路是，基于广度遍历与深度遍历集合的方式：从核心点集合 S 中取出一个点 p，计算点 p 与 S 集合中每个点（除了 p 点）是否连通，可能会得到一个连通核心点的集合 C1，然后从集合 S 中删除点 p 和 C1 集合中的点，得到核心点集合 S1；再从 S1 中取出一个点 p1，计算 p1 与核心点集合 S1 集中每个点（除了 p1 点）是否连通，可能得到一个连通核心点集合 C2，再从集合 S1 中删除点 p1 和 C2 集合中所有点，得到核心点集合 S2，最后得到 p、p1、p2、，以及 C1、C2、就构成一个簇的核心点。最终将核心点集合 S 中的点都遍历完成，得到所有的簇。参数 eps 的设置，如果 eps 设置过大，则所有的点都会归为一个簇，如果设置过小，那么簇的数目会过多。如果 MinPts 设置过大的话，很多点将被视为噪声点。3、根据数据点的密度分为三类点：、根据数据点的密度分为三类点：(1)核心点：该点在邻域内的密度超过给定的阀值 MinPs。(2)边界点：该点不是核心点，但是其邻域内包含至少一个核心点。(3)噪音点：不是核心点，也不是边界点。有了以上对数据点的划分，聚合可以这样进行：各个核心点与其邻域内的所有核心点放在同一个簇中，把边界点跟其邻域内的某个核心点放在同一个簇中。聚类的效果如下图，黑色是噪音点：初识聚类算法:因为 DBSCAN 使用簇的基于密度的定义，因此它是相对抗噪音的，并且能处理任意形状和大小的簇。但是如果簇的密度变化很大，例如 ABCD 四个簇，AB 的密度大大大于 CD，而且 AB附近噪音的密度与簇 CD 的密度相当，这是当 MinPs 较大时，无法识别簇 CD，簇 CD 和 AB附近的噪音都被认为是噪音；当 MinPs 较小时，能识别簇 CD，但 AB 跟其周围的噪音被识别为一个簇。这个问题可以基于共享最近邻(SNN)的聚类结局。4、DBSCAN 的优缺点：的优缺点：优点：1.与 K-means 方法相比，DBSCAN 不需要事先知道要形成的簇类的数量。2.与 K-means 方法相比，DBSCAN 可以发现任意形状的簇类。3.同时，DBSCAN 能够识别出噪声点。4.DBSCAN 对于数据库中样本的顺序不敏感，即 Pattern 的输入顺序对结果的影响不大。但是，对于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动。缺点：1.DBScan 不能很好反映高尺寸数据。2.DBScan 不能很好反映数据集变化的密度。3.对于高维数据，点之间极为稀疏，密度就很难定义了。