【数据挖掘】聚类算法总结


【数据挖掘】聚类算法总结 【数据挖掘】聚类算法总结 一、层次聚类 1、层次聚类的原理及分类 1)层次法(Hierarchicalmethods)先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后,再计算类与 类之间的距离,将距离最近的类合并为一个大类。不停的合并,直到合成了一个类。其中类与类的距离的计算方法有: 最短距离法,最长距离法,中间距离法,类平均法等。比如最短距离法,将类与类的距离定义为类与类之间样本的最短 距离。 层次聚类算法根据层次分解的顺序分为:自下底向上和自上向下,即凝聚的层次聚类算法和分裂的层次聚类算法 (agglomerative和divisive),也可以理解为自下而上法(bottom-up)和自上而下法(top-down)。自下而上法就 是一开始每个个体(object)都是一个类,然后根据linkage寻找同类,最后形成一个“类”。自上而下法就是反过来, 一开始所有个体都属于一个“类”,然后根据linkage排除异己,最后每个个体都成为一个“类”。这两种路方法没有孰 优孰劣之分,只是在实际应用的时候要根据数据特点以及你想要的“类”的个数,来考虑是自上而下更快还是自下而上 更快。至于根据Linkage判断“类”的方法就是最短距离法、最长距离法、中间距离法、类平均法等等(其中类平均法往 往被认为是最常用也最好用的方法,一方面因为其良好的单调性,另一方面因为其空间扩张/浓缩的程度适中)。为弥补 分解与合并的不足,层次合并经常要与其它聚类方法相结合,如循环定位。 2)Hierarchical methods中比较新的算法有BIRCH(Balanced Iterative Reducingand Clustering Using Hierarchies 利用层次方法的平衡迭代规约和聚类)主要是在数据量很大的时候使用,而且数据类型是numerical。首先利用树的结构 对对象集进行划分,然后再利用其它聚类方法对这些聚类进行优化;ROCK(A Hierarchical ClusteringAlgorithm for Categorical Attributes)主要用在categorical的数据类型上;Chameleon(A Hierarchical ClusteringAlgorithm Using Dynamic Modeling)里用到的linkage是kNN(k-nearest-neighbor)算法,并以此构建一个 graph,Chameleon的聚类效果被认为非常强大,比BIRCH好用,但运算复杂度很高,O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有对象都在一个簇 中,或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类,它们只是在簇间相似度的定义上有所不同。 这 里给出采用最小距离的凝聚层次聚类算法流程: (1) 将每个对象看作一类,计算两两之间的最小距离; (2) 将距离最小的两个类合并成一个新类; (3) 重新计算新类与所有类之间的距离; (4) 重复(2)、(3),直到所有类最后合并成一类。 聚类的效果如下图,黑色是噪音点: 另外我们可以看出凝聚的层次聚类并没有类似基本K均值的全局目标函数,没有局部极小问题或是很难选择初始点的问 题。合并的操作往往是最终的,一旦合并两个簇之后就不会撤销。当然其计算存储的代价是昂贵的。 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-means 基于划分的方法(Partition-based methods):其原理简单来说就是,想象你有一堆散点需要聚类,想要的聚类效果就 是“类内的点都足够近,类间的点都足够远”。首先你要确定这堆散点最后聚成几类,然后挑选几个点作为初始中心 点,再然后依据预先定好的启发式算法(heuristicalgorithms)给数据点做迭代重置(iterativerelocation),直到最后 到达“类内的点都足够近,类间的点都足够远”的目标效果。 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)个种子点。 ②然后对图中的所有点求到这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++、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-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值。 ③系统演化方法[3] 系统演化方法将一个数据集视为伪热力学系统,当数据集被划分为K个聚类时称系统处于状态K。系统由初始状态 K=1出发,经过分裂过程和合并过程,系统将演化到它的稳定平衡状态Ki,所对应的聚类结构决定了最优类数Ki。系统演 化方法能提供关于所有聚类之间的相对边界距离或可分程度,适用于明显分离的聚类结构和轻微重叠的聚类结构。 ④使用canopy算法进行初始划分[4] 基于CanopyMethod的聚类算法将聚类过程分为两个阶段 Stage1、聚类最耗费计算的地方是计算对象相似性的时候,CanopyMethod在第一阶段选择简单、计算代价较低 的方法计算对象相似性,将相似的对象放在一个子集中,这个子集被叫做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),这两位用户的认知其实是一样的,但是欧式距离给出的解显然没有余弦值合理。 4)质心的计算 对于距离度量不管是采用欧式距离还是采用余弦相似度,簇的质心都是其均值,即向量各维取平均即可。 5)算法停止条件 一般是目标函数达到最优或者达到最大的迭代次数即可终止。对于不同的距离度量,目标函数往往不同。当采用欧 式距离时,目标函数一般为最小化对象到其簇质心的距离的平方和。 当采用余弦相似度时,目标函数一般为最大化对象到其簇质心的余弦相似度和。 6)空聚类的处理 如果所有的点在指派步骤都未分配到某个簇,就会得到空簇。如果这种情况发生,则需要某种策略来选择一个替 补质心,否则的话,平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。这将消除当前对总平方误差 影响最大的点。另一种方法是从具有最大SSE的簇中选择一个替补的质心。这将分裂簇并降低聚类的总SSE。如果有多个 空簇,则该过程重复多次。另外,编程实现时,要注意空簇可能导致的程序bug。 三、基于密度的聚类 基于密度的方法(Density-based methods):k-means解决不了不规则形状的聚类。于是就有了Density-based methods来系统解决这个问题。该方法同时也对噪声数据的处理比较好。基于密度聚类的思想:思路就是定一个距离半 径,最少有多少个点,然后把可以到达的点都连起来,判定为同类。其原理简单说画圈儿,其中要定义两个参数,一个 是圈儿的最大半径,一个是一个圈儿里最少应容纳几个点。最后在一个圈里的,就是一个类。DBSCAN(Density- Based Spatial Clustering ofApplications with Noise)就是其中的典型,可惜参数设置也是个问题,对这两个参数的 设置非常敏感。DBSCAN的扩展叫OPTICS(OrderingPoints To Identify 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密度相联。 密度可达是直接密度可达的传递闭包,并且这种关系是非对称的。密度相连是对称关系。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)连通核心点生成簇 核心点能够连通(有些书籍中称为:“密度可达”),它们构成的以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.对于高维数据,点之间极为稀疏,密度就很难定义了。
还剩5页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

aowushuang

贡献于2017-03-07

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf