聚类算法比较

聚类算法：1.划分法 :K-MEANS 算法、K-MEDOIDS 算法、CLARANS 算法；1) K-means 算法：基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按 平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某 个给定的值。K-Means聚类算法主要分为三个步骤：(1) 第一步是为待聚类的点寻找聚类中心(2) 第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去(3) 第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止 下图展示了对n个样本点进行K-means聚类的效果，这里k取2：(a) 未聚类的初始点集(b) 随机选取两个点作为聚类中心(c) 计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去(d) 计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心(e) 重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去(f) 重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心(b)(c)3)(0优点：1算法快速、简单；2. 对大数据集有较高的效率并且是可伸缩性的；3. 时间复杂度近于线性，而且适合挖掘大规模数据集。 缺点：1. 在K-means算法中K是事先给定的，这个K值的选定是非常难以估计的。2. 在K-means算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分 进行优化。这个初始聚类中心的选择对聚类结果有较大的影响。3. 从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整 后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。4. 产生类的大小相差不会很大，对于脏数据很敏感。2）K-MEDOIDS （k-medoids）算法与k-means很像，不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前 cluster中所有数据点的平均值，在K-medoids算法中，我们将从当前cluster中选取这 样一个点 它到其他所有（当前cluster中的）点的距离之和最小 作为中心点。选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。K-MED0DIS的具体流程如下：1）任意选取K个对象作为medoids （01,02,。匚。*）。2）将余下的对象分到各个类中去（根据与medoid最相近的原则）；3）对于每个类，顺序选取一个对象，计算用这个对象代替原中心点的方差。选择方差最小 的那个对象来代替原中心点。这样K个medoids就改变了。4）重复2、3步直到K个medoids固定下来。优点：不容易受到那些由于误差之类的原因产生的脏数据的影响缺点：计算量显然要比K-means要大，一般只适合小数据量3） CLARANS （A Clustering Algorithm based on Randomized Search 基于随机选择的聚 类算法）：将采样技术（CLARAC/ara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这 些抽样的数据上利用K-medo/ds算法得到最佳的medo/ds。C/ara算法从实际数据中抽取多个采 样，在每个采样上都用-medo/ds算法得到相应的Ol,O2-Oi-Ok），然后在这当中选取E 最小的一个作为最终的结果和PAM （找出中心点）结合起来。CLARA的主要思想是：不 考虑整个数据集合，而是选择实际数据的一小部分作为数据的代表。然后用PAM方法从样 本中选择中心点。如果样本是以非常随机的方式选取的，那么它应当接近代表原来的数据集。 从中选出代表对象（中心点）很可能和从整个数据集合中选出的代表对象相似o CLARA抽 取数据集合的多个样本，对每个样本应用PAM算法，并返回最好的聚类结果作为输出。CLARA的有效性主要取决于样本的大小。如果任何一个最佳抽样中心点不在最佳的K 个中心之中，则CLARA将永远不能找到数据集合的最佳聚类。同时这也是为了聚类效率做 付出的代价。CLARANS聚类则是将CLARA和PAM有效的结合起来，CLARANS在任何时候都不 把自身局限于任何样本，CLARANS在搜素的每一步都以某种随机性选取样本。算法步骤如 下（算法步骤摘自百度文库）：1、 输入参数numlocal和maxneighbor。numlocal表示抽样的次数， maxneighbor表示 一个节点可以与任意特定邻居进行比较的数目令：=1,i用来表示已经选样的次数min cost 为最小代价，初始时设为大数。2、设置当前节点current为Gn中的任意一个节点。3、令j =1（j用来表示已经与current进行比较的邻居的个数）4、考虑当前点的一个随机的邻居S,并计算两个节点的代价差。5、如果S的代价较低，则current:=S，转到步骤3。6、否则，令j=j+1。如果jmax neighbor,当前节点为本次选样最小代价节点.如果其代价小于min cost, 令min cost为当前节点的代价，best node为当前的节点。&令i= i+1，如果inumlocal,输出best node,运算中止.否则，转到步骤2。对上面出 现一些概念进行说明：（1）代价值，主要描述一个对象被分到一个类别中的代价值，该代价值由每个对象与其 簇中心点间的相异度（距离或者相似度）的总和来定义。代价差则是两次随机领域的代价差 值。（2）更新邻接点，CLARANS不会把搜索限制在局部区域，如果发现一个更好的近邻， CLARANS就移到该近邻节点，处理过程从新开始；否则，当前的聚类则产生了一个局部最 小。如果找到一个局部最小，CLARANS从随机选择的新节点开始，搜索新的局部最小。当 搜索的局部最小解达到用户指定的数目时，最好的局部最小作为算法的输出。从上面的算法 步骤也可以看出这一思想。在第5步中更新节点current。2.层次法 :自顶向下，自底向上。BIRCH算法、CURE算法、CHAMELEON算法等； BIRCH算法（最大的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍 扫描数据集能最小化I/O代价。如果簇不是球形的，BIRCH不能很好的工作，因为它用了半径或直径 的概念来控制聚类的边界。）：算法的核心：通过扫描数据库，建立一个初始存放于内存中的聚类特征树，然后对聚类特 征树的叶结点进行聚类。它的核心是聚类特征（CF）和聚类特征树（CF Tree）CURE算法：CURE (Clustering Using Representatives)是一种针对大型数据库的高效的 聚类算法。基于划分的传统的聚类算法得到的是球状的，相等大小的聚类，对异常数据比较 脆弱。CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。并且在处理 大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量 数据。基本目标聚类算法CURE的算法实现。对图形进行聚类，在时间，结果方面对其性能进行评估。算 法流程CURE的算法在开始时，每个点都是一个簇，然后将距离最近的簇结合，一直到簇的个数 为要求的K。它是一种分裂的层次聚类。算法分为以下6步：1)从源数据对象中抽取一个 随机样本S。2)将样本S分割为一组划分。3)对划分局部的聚类。4)通过随机取样提出孤立点。如果一个簇增长得太慢，就去掉它。5)对局部的簇进行聚 类。6)用相应的簇标签标记数据。算法设计(1)基本聚类算法procedure cluster(S, k)/*将数据集 S 聚类成为 k 个簇*/ begin1. T := build_kd_tree(S) /* 对 应 数 据 集 S 建 立一个 K-DTree T*/ 2. Q := build_heap(S) /* 对应数据集 S 建立一个 堆Q*/ 3. while size(Q) k do /*聚类直至簇的个数为k */4.u := extract_mi n(Q)/* 找到最近的两个簇u ，v */ 5.v := u.cloest 6.delete(Q, v)7.w := merge(u, v)/*将u,v合并为簇w */ 8.delete_rep(T, u);delete_rep(T, v); in sert_rep(T, w)9.w.cloest := x/* x is an arbitrary cluster in Q*/ 10.for each xQ do /*调节因合并带来的T和Q的变化*/ 11.if (dist(w,x) dist(w,w.cloest) 12.w.cloest := x13. if x.cloest is either u or v 14. if dist(x, x.cloest) dist(x, w) 21.x.cloest := w 22.relocate(Q, x) 23. 24.25.in sert(Q, w) 26. end此程序段用到的数据结构有Heap，和K-DTree。为了合并距离最短的两个聚类，需要构建 一个K-DTree来找到空间中的一聚类最近的一个聚类，之后把K-DTree中的聚类按照其与 最近的聚类的距离进行排序(用的是堆排序)，找到最近的两个的聚类，将它们合并(对应 函数 merge ()。CHAMELEON是一种两阶段聚类法。第一阶段把点分成很多小的簇；第二阶段根据相近程度合并这 些小的簇。第一阶段采用K最邻近法，即把一个点和它最邻近的K个点连接起来。第二阶段计算任 意两个簇的互连性RI和紧密性RC ,当两个指标都比较大时才合并这两个簇。下图是第一阶段后形成的几个小的子簇：3密度算法 :DBSCAN 算法、OPTICS 算法、DENCLUE 算法等DBSCAN 算法：DBSCAN （Density-Based Spatial Clustering of Applications with Noise, 具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划 分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。该算法利用基于密度的聚类的概念，即要求聚类空间中的一定区域内所包含对象（点或其他空间对象） 的数目不小于某一给定阈值。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现 任意形状的空间聚类。但是由于它直接对整个数据库进行操作且进行聚类时使用了一个全局性的表征 密度的参数，因此也具有两个比较明显的弱点：(1) 当数据量增大时，要求较大的内存支持I/O消耗也很大；(2) 当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差。DBSCAN和传统聚类算法对比DBSCAN算法的目的在于过滤低密度区域，发现稠密度样本点。跟传统的基于层次的聚类和划分聚 类的凸形聚类簇不同，该算法可以发现任意形状的聚类簇，与传统的算法相比它有如下优点：(1) 与K-MEANS比较起来，不需要输入要划分的聚类个数；(2) 聚类簇的形状没有偏倚；(3) 可以在需要时输入过滤噪声的参数；算法涉及的基本定义：EE(1) 邻域：给定对象半径 内的区域称为该对象的 邻域。E(2) 核心对象：如果给定对象邻域内的样本点数大于等于MinPts,则称该对象为核心对象。E(3) 直接密度可达：给定一个对象集合D,如果p在q的 邻域内，且q是一个核心对象，则我们说对象p从对象q出发是直接密度可达的(directly density-reachable )。PPrPn Pl = q, Pn = P(4) 密度可达：对于样本集合D,如果存在一个对象链，PieD(lin) pi+1 Pi e对于，是从关于 和MinPts直接密度可达，则对象p是从对象Eq 关于和 Min Pts 密度可达的(den sity-reachable)。O E DE(5) 密度相连：如果存在对象，使对象p和q都是从o关于 和Min Pts密度可达的，那E么对象p到q是关于一和MinPts密度相连的(density-connected)。可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。只有核心对象之间相互 密度可达。然而，密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。DBSCAN算法的聚类过程DBSCAN算法基于一个事实：一个聚类可以由其中的任何核心对象唯一确定。等价可以表述为：任 一满足核心对象条件的数据对象P，数据库D中所有从p密度可达的数据对象o所组成的集合构成 了一个完整的聚类C,且p属于Co算法的具体聚类过程如下：扫描整个数据集，找到任意一个核心点，对该核心点进行扩充。扩充的方法是寻找从该核心点 出发的所有密度相连的数据点（注意是密度相连）。遍历该核心点的E邻域内的所有核心点（因为 边界点是无法扩充的），寻找与这些数据点密度相连的点，直到没有可以扩充的数据点为止。最后聚 类成的簇的边界节点都是非核心数据点。之后就是重新扫描数据集（不包括之前寻找到的簇中的任何 数据点），寻找没有被聚类的核心点，再重复上面的步骤，对该核心点进行扩充直到数据集中没有新 的核心点为止。数据集中没有包含在任何簇中的数据点就构成异常点。算法伪代码算法描述：算法：DBSCAN输入：E半径MinPts 给定点在E邻域内成为核心对象的最小邻域点数。D集合。输出：目标类簇集合方法：Repeat1）判断输入点是否为核心对象2）找出核心对象的E邻域中的所有直接密度可达点。Un til所有输入点都判断完毕Repeat针对所有核心对象的E邻域内所有直接密度可达点找到最大密度相连对象集合，中间涉及到一些密度 可达对象的合并。Un til所有核心对象的E领域都遍历完毕OPTICS算法的最大优点是对输入参数不敏感。算法：OPTICS输入：样本集D,邻域半径E,给定点在E领域内成为核心对象的最小领域点数Mi nPts输出：具有可达距离信息的样本点输出排序方法：1创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及 其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的 输出次序）；2如果所有样本集D中所有点都处理完毕，则算法结束。否则，选择一个未 处理（即不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样 本点，如过该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距 离排序；3如果有序队列为空，则跳至步骤2,否则，从有序队列中取出第一个样本 点（即可达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中， 如果它不存在结果队列当中的话。3.1判断该拓展点是否是核心对象，如果不是，回到步骤3,否则找到 该拓展点所有的直接密度可达点；3.2判断该直接密度可达样本点是否已经存在结果队列，是则不处理， 否则下一3.2如果有序队列中已经存在该直接密度可达点，如果此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序;3.3如果有序队列中不存在该直接密度可达样本点，则插入该点，并对 有序队列重新排序；4算法结束，输出结果队列中的有序样本点。DENCLUE 算法4. 图论聚类法5. 网格算法 :STING 算法、CLIQUE 算法、WAVE-CLUSTER算法；6模型算法:统计的方案和神经网络的方案