《第10章聚类方法ppt课件.pptx》由会员分享，可在线阅读，更多相关《第10章聚类方法ppt课件.pptx（91页珍藏版）》请在三一办公上搜索。
1、第10章 聚类方法,10.1 聚类概述10.2 基于划分的聚类算法10.3 基于层次的聚类算法10.4 基于密度的聚类算法10.5 基于网格的聚类算法10.6 基于模型的聚类算法10.7 离群点分析,分类和聚类是两个容易混淆的概念，事实上它们具有显著区别。在分类中，为了建立分类模型而分析的数据对象的类别是已知的，然而，在聚类时处理的所有数据对象的类别都是未知的。因此，分类是有指导的，是通过例子（训练样本集）学习的过程，而聚类是无指导的，是通过观察学习的过程 。,10.1 聚类概述,10.1.1 什么是聚类,聚类是将数据对象的集合分成相似的对象类的过程。使得同一个簇（或类）中的对象之间具有较高的
2、相似性，而不同簇中的对象具有较高的相异性。,定义10.1 聚类可形式描述为：D=o1，o2，on表示n个对象的集合，oi表示第i（i=1，2，n）个对象，Cx表示第x（x=1，2，k）个簇，CxD。用sim(oi，oj)表示对象oi与对象oj之间的相似度。若各簇Cx是刚性聚类结果，则各Cx需满足如下条件：,其中，条件和表示所有Cx是D的一个划分，条件表示簇内任何对象的相似度均大于簇间任何对象的相似度。,聚类,簇1,簇2,簇3,（a）原来的点,（b）3个簇,10.1.2 相似性测度,1. 距离相似性度量,曼哈坦距离,欧几里得距离,闵可夫斯基距离,通常相似度与距离成反比，在确定好距离函数后，可设计
3、相似度函数如下：,2. 密度相似性度量,密度是单位区域内的对象个数。密度相似性度量定义为：density(Ci，Cj)=|didj|其中di、dj表示簇Ci、Cj的密度。其值越小，表示密度越相近，Ci、Cj相似性越高。这样情况下，簇是对象的稠密区域，被低密度的区域环绕。,3. 连通性相似性度量,数据集用图表示，图中结点是对象，而边代表对象之间的联系，这种情况下可以使用连通性相似性，将簇定义为图的连通分支，即图中互相连通但不与组外对象连通的对象组。也就是说，在同一连通分支中的对象之间的相似性度量大于不同连通分支之间对象的相似性度量。,某种距离函数,4. 概念相似性度量,若聚类方法是基于对象具有的
4、概念，则需要采用概念相似性度量，共同性质（比如最近邻）越多的对象越相似。簇定义为有某种共同性质的对象的集合。,狗,鸡,猫,苹果,葡萄,语义上的相似性,10.1.3 聚类过程,10.1.4 聚类算法的评价,一个好的聚类算法产生高质量的簇，即高的簇内相似度和低的簇间相似度。通常估聚类结果质量的准则有内部质量评价准则和外部质量评价准则。,1. 内部质量评价准则,例如，CH指标的定义如下：,其中：,traceB表示簇间距离，traceW表示簇内距离，CH值越大，则聚类效果越好。,为整个数据集的均值,为簇Ci的均值,【例10.1】如图10.2（a）所示的数据集有图10.2（b）、（c）、（d）三种聚类结
5、果，这里n=16，距离函数采用欧几里得距离。采用CH指标判断聚类结果的好坏。,CH=5.39,CH=6.25625,CH=3.96,2. 外部质量评价准则,常用的外部质量评价指标有聚类熵等。,对于簇Ci，其聚类熵定义为：,整体聚类熵定义为所有聚类熵的加权平均值：,显然，E越小，聚类效果也越好，反之亦然。,E0,E0.58,例如(P274)：,10.1.5 聚类方法的分类,按照聚类的尺度，聚类方法可被分为以下三种：,基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度。基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。基于互连性的聚类算法：通常
6、基于图或超图模型。高度连通的对象聚为一类。,按照聚类分析方法的主要思路，可以被归纳为如下几种。,划分法：基于一定标准构建数据的划分。层次法：对给定数据对象集合进行层次的分解。密度法：基于数据对象的相连密度评价。网格法：将数据空间划分成为有限个单元的网格结构，基于网格结构进行聚类。模型法：给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集。,10.1.6 聚类分析在数据挖掘中的应用, 聚类分析可以用于数据预处理。 可以作为一个独立的工具来获得数据的分布情况。 聚类分析可以完成孤立点挖掘。,10.1.7 聚类算法的要求, 可伸缩性。 具有处理不同类型属性的能力。 能够发现任意形状的聚
7、类。 需要（由用户）决定的输入参数最少。 具有处理噪声数据的能力。 对输入记录顺序不敏感。 具有处理高维数据的能力。 支持基于约束的聚类。 聚类结果具有好的可解释性和可用性。,10.2 基于划分的聚类算法,划分聚类算法预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化目标函数的值，当目标函数收敛时，得到最终聚类结果。,划分后每个类中的数据点到该类中心的距离最小,10.2.1 k-均值算法,k-均值（k-means）算法的基本过程如下：,首先输入k的值，即希望将数据集D=o1，o2，on经过聚类得到k个分类或分组。从数据集D中随机选择k个数据点作为簇质心，每个簇质心代表一个簇。这样得到的簇质
8、心集合为Centroid=Cp1，Cp2，Cpk。对D中每一个数据点oi，计算oi与Cpj（j=1，2，k）的距离，得到一组距离值，从中找出最小距离值对应的簇质心Cps，则将数据点oi划分到以Cps为质心的簇中。,1. k-均值算法的过程,根据每个簇所包含的对象集合，重新计算得到一个新的簇质心。若|Cx|是第x个簇Cx中的对象个数，mx是这些对象的质心，即：,如果这样划分后满足目标函数的要求，可以认为聚类已经达到期望的结果，算法终止。否则需要迭代步骤。通常目标函数设定为所有簇中各个对象与均值间的误差平方和（Sum of the Squared Error，简称SSE）小于某个阈值，即：,这里的
9、簇质心mx是簇Cx的均值，这就是k-均值算法名称的由来。,k-均值算法示例,【例10.3】如图10.4所示是二维空间中的10个数据点（数据对象集），采用欧几里得距离，进行2-均值聚类。其过程如下：,初始的10个点,（1）k=2，随机选择两个点作为质心，假设选取的质心在图中用实心圆点表示。（2）第一次迭代，将所有点按到质心的距离进行划分，其结果如图10.5所示。,第1次迭代,（3）假设这样划分后不满足目标函数的要求，重新计算质心，如图10.6所示，得到两个新的质心。,求新的质心,第2次迭代,（4）第2次迭代，其结果如图10.7所示。,（5）假设这样划分后满足目标函数的要求，则算法结束，第2次划分
10、的结果即为所求；否则还需要继续迭代。,序号 属性 1 属性 21 1 12 2 13 1 24 2 2,根据所给的数据通过对其实施k均值算法（设n=8，k=2），其主要执行执行步骤：第1次迭代：假定随机选择的两个对象，如序号1和序号3当作初始点，分别找到离两点最近的对象，并产生两个簇1，2和3，4，5，6，7，8。对于产生的簇分别计算平均值，得到平均值点：,示例：,样本数据,序号 属性 1 属性 25 4 36 5 37 4 48 5 4,对于1，2，平均值点为（1.5，1）（这里的平均值是简单的相加除2）；对于3，4，5，6，7，8，平均值点为（3.5，3）。,本题采用欧几里得距离,第2次迭
11、代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点（1.5，1）、（3.5，1）最近的原则重新分配。得到两个新的簇：1，2，3，4和5，6，7，8。重新计算簇平均值点，得到新的平均值点为（1.5，1.5）和（4.5，3.5）。第3次迭代：将所有点按离平均值点（1.5，1.5）和（4.5，3.5）最近的原则重新分配，调整对象，簇仍然为1，2，3，4和5，6，7，8，发现没有出现重新分配，而且准则函数收敛，程序结束。,2. k-均值算法,输入：数据对象集合D，簇数目k，阈值输出：k个簇的集合方法：其过程描述如下：,从D中随机选取k个不同的数据对象作为k个簇C1、C2、Ck的中心m1
12、、m2、mk;while (true) for (D中每个数据对象o) 求i，使得;将o分配到簇Ci中; for (每个簇Ci)计算 /计算新的质心，|Ci|为簇Ci中的对象数目计算误差平方和if (SSE) break;/满足条件，退出循环,优点复杂度：O(tkn)，其中n 是对象的数目，k 是簇的数目，t 是迭代的次数。 通常k、t n。通常以局部最优结束。 使用遗传算法技术可以达到全球最优。缺点只有在簇的平均值被定义的情况下才能使用，那当涉及有分类属性的数据时该怎么办?需要事先给出k，即簇的数目不能处理噪声数据和孤立点不适合发现非凸面形状的簇,3. k-均值算法的特点,5. 二分k-均值
13、算法,二分k-均值算法是基本k-均值算法的直接扩充，它基于一种简单的想法：为了得到k个簇，将所有点的集合分为两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇。,二分k-均值算法如下：,输入：数据对象集合D，簇数目k，二分次数b输出：k个簇的集合方法：其过程描述如下：,将D的所有对象构成一个簇C1，将其加入到簇表S中，即S=C1;do 从簇表S中取出一个簇Ci; for (j=1 to b)使用基本k-均值算法，二分簇Ci，得到一对子簇Ci1、Ci2; 从上述得到的b对子簇中选择具有最小SSE的一对子簇，将其加入S中; until 簇表S中包含k个簇;,10.2.2 k-中心点算法,
14、改进的方法是不采用簇中对象的均值作为质心，而是在每个簇中选出一个实际的对象来代表该簇，这个对象称为簇的中心点，其余的每个对象聚类到与其最相似的中心点所在簇中。划分方法仍然基于最小化所有对象与其对应的中心点之间的距离之和的原则来执行。目标函数（或误差函数）使用绝对误差标准，其定义如下：,其中，E是数据集D中所有对象的绝对误差和。ox是簇Cx的中心点。,PAM是最早提出的k-中心点算法之一。 PAM算法的过程如下：,任意选择k个对象作为k个中心点。计算每个非中心点对象到每个中心点的距离。把每个非中心点对象分配到距离它最近的中心点所代表的簇中。随机选择一个非中心点对象oi，计算用oi代替某个簇Cx的
15、中之点ox所能带来的好处（用E表示代替后和代替前误差函数值之差，意思是使误差E增加多少）。若E0，表示代替后误差会减少，则用oi代替ox，即将oi作为簇Cx的中心点；否则，不代替。重复，直到k个中心点不再发生改变。,【例10.4】有9个人的年龄分别是1、2、6、7、8、10、15、17、20，采用PAM算法将年龄分为3组。其过程如下：,（1）随机选取3个年龄作为中心点，假设是6、7、8。（2）计算每个年龄和这3个中心点的距离后，将年龄分为3组：1，2，6，7，8，10，15，17，20，对应的E=5+4+0+0+0+2+7+9+12=39。（3）假设随机选取年龄10，用它代替中心点6，即新的3
16、个中心点为10、7、8，这样产生的分组为1，2，6，7，8，10，15，17，20，对应的E=6+5+1+0+0+0+5+7+10=34。E=E-E=34-39=-50，则用10代替中心点6，新的E=34。,（4）再随机选取年龄17，用它代替中心点7，即新的3个中心点为10、17、8，这样产生的分组为1，2，6，7，8，10，15，17，20，对应的E=7+6+2+1+0+0+2+0+3=21。E=E-E=21-34=-130，则用17代替中心点7，新的E=21。（5）再随机选取年龄1，用它代替中心点10，即新的3个中心点为1、17、8，这样产生的分组为1，2，6，7，8，10，15，17，2
17、0，对应的E=0+1+2+1+0+2+2+0+3=11。E=E-E=11-21=-100，则用1代替中心点10。（6）以后重复均不会改变中心点，算法结束，所以最后生成的簇为1，2，6，7，8，10，15，17，20。,10.3 基于层次的聚类算法,层次聚类方法是一种已得到广泛使用的经典方法，是通过将数据对象组织成若干组并形成一个相应的树来进行聚类。常用的层次聚类算法有DIANA、AGNES、BIRCH、CURE、ROCK和Chameleon等。,10.3.1 层次聚类算法概述,1. 层次聚类过程,（1）自顶向下（层次分裂）方法,也称为划分层次法。从包含所有点（对象）的簇开始，每一步分裂一个簇，
18、直到仅剩下单点簇。这种方式需要确定每一步分裂哪个簇，以及如何分裂。后面介绍的层次聚类算法大都采用这个过程。,（2）自底向上（层次凝聚）方法,也称为聚合层次法。最初每个点作为一个簇（原子簇），每一步合并两个最相似的簇。这种方法需要定义簇的相似性度量和算法终止的条件。,2. 层次聚类结果表示,3. 类间距离度量, 最短距离法（最大相似度）：定义两个类中最靠近的两个对象间的距离为类间距离。即：, 最长距离法（最小相似度）：定义两个类中最远的两个对象间的距离为类间距离。即：, 类平均法：它计算两个类中任意两个对象间的距离，并且平均它们为类间距离。即：, 中心法：定义两类的两个中心间的距离为类间距离。即
19、：,mi、mj分别为Ci、Cj的中心点,【例10.5】如表10.2所示的6个点，在二维空间中位置如图10.21所示。,采用最短距离法的聚类结果如图10.22所示，采用最长距离法的聚类结果如图10.23所示，采用类平均法的聚类结果如图10.24所示，图中圆圈上的数字表示采用自底向上方法时的聚类次序。从中看到，选定的类间距离的度量不同，聚类的次序和结果可能不同。,采用最短距离法的聚类结果,采用最长距离法的聚类结果,采用类平均法的聚类结果,采用层次凝聚时使用最短距离法称为单链或MIN层次凝聚，采用层次凝聚时使用最长距离法称为全链或MAX层次凝聚。,10.3.2 DIANA算法和AGNES算法,1.
20、DIANA算法,DIANA（Divisive ANAlysis）算法是典型的层次分裂聚类方法。在聚类中，用户指定希望得到的簇数目作为一个结束条件。同时，它使用下面两种度量方法：,簇的直径：在一个簇中的任意两个数据点的距离中的最大值。平均相异度（平均距离）：,采用自顶向下分裂的DIANA算法如下：,输入：包含n个点（对象）的数据集，簇的数目k。输出：k个簇，达到终止条件规定簇数目。方法：其过程描述如下：,将所有对象整个当成一个初始簇;将splinter group和old party两个对象集合置为空;for (i=1; ik; i+) 在所有簇中挑出具有最大直径的簇C; 找出C中与其他点平均相
21、异度最大的一个点p; 把p放入splinter group，剩余的点放在old party中； do 在old party里找出到splinter group中点的最近距离不大于到old party中点的最近距离的点; 将该点加入splinter group; until (没有新的old party的点被分配给splinter group); splinter group和old party为被选中的簇分裂成的两个簇，与其他簇一起组成新的簇集合;,【例10.6】对于表10.3所示的样本数据集，假设终止条件为k=2，采用DIANA算法进行层次聚类的过程如下。,初始簇为1，2，3，4，5，6，7
22、，8。第1步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定dist采用是欧几里得距离）。点1的平均相异度：(1+1+1.414+3.6+4.24+4.47+5)/7=2.96类似地，点2的平均相异度为2.526；点3的平均相异度为2.68；点4的平均相异度为2.18；点5的平均相异度为2.18；点6的平均相异度为2.68；点7的平均相异度为2.526；点8的平均相异度为2.96。将平均相异度最大的点1放到splinter group中，剩余点在old party中。,第2步，在old party里找出到最近的splinter group中的点的距离不大于到old party中最近的
23、点的距离的点，将该点放入splinter group中，该点是2。第3步，重复第2步的工作，在splinter group中放入点3。第4步，重复第2步的工作，在splinter group中放入点4。第5步，没有新的old party中的点放入到splinter group中，此时分裂的簇数为2，达到终止条件，算法结束。如果没有到终止条件，下一阶段还会从分裂好的簇中选一个直径最大的簇继续分裂。最终的聚类结果为1，2，3，4和5，6，7，8两个簇。,2. AGNES算法,AGNES（AGglomerative NESting）算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。
24、两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有的对象最终满足簇数目。,自底向上凝聚的AGNES算法算法如下：,输入：包含n个点（对象）的数据集，簇的数目k。输出：k个簇，达到终止条件规定簇数目。方法：其过程描述如下：,将每个点当成一个初始簇;do 根据两个簇中最近的数据点找到最近的两个簇; 合并两个簇，生成新的簇的集合; until (达到定义的簇的数目);,【例10.7】对于表10.3所示的样本数据集，假设终止条件为k=2，采用AGNES算法进行层次聚类的过程如下。,10.3.3 BIRCH算法,1. 聚类特征（CF）,定义10.2 如果某个
25、簇包含N个d维的数据对象o1，o2，oN，则聚类特征定义为一个三元组CF=(N，LS，SS)。其中LS是N个对象的线性和，SS是N个对象的平方和，即：,聚类特征概括了对象簇的信息，在BIRCH算法中做出聚类决策所需要的度量值，如簇的质心、半径、直径、簇间质心距离和平均簇间距离等都可以CF计算出来。例如，给定一个簇的聚类特待CF=(N，LS，SS)，可以用以下公式计算簇的质心om和半径R：,例如，假定在簇C1中有两个点(1，2)和(2，1)，簇C2中有两个点(7，8)和(8，9)，簇C21由C1和C2合并而成。则：CF1=(2，(1+2，2+1)，(12+22，22+12)=(2，(3，3)，(
26、5，5)CF2=(2，(7+8，8+9)，(72+82，82+92)=(2，(15，17)，(113，145)CF21=(2+2，(3+15，3+17)，(5+113，5+145)=(4，(18，20)，(118，150)从而利用上述公式可以通过CF21直接求出簇C21的质心和半径等。,2. 聚类特征树（CF树）,CF树是一棵高度平衡的树，它有两个参数：分支因子B和阈值T。每个非叶结点最多包含B个条目Li（i=1，2，B），Li形如CFi，childi，childi是指向第i个孩子的指针，CFi是由这个孩子所代表的子簇的聚类特征，如图10.25（a）所示。一个非叶结点代表了一个簇，这个簇由该结
27、点的条目所代表的所有子簇构成。,一个叶结点最多包含L个形如CFi（i=1，2，L）的条目。每个叶结点也代表了一个簇，这个簇由该叶结点的条目所代表的所有子簇构成，这些子簇的直径必须小于阈值T。如图10.25（b）所示。所有叶结点通过prev和next指针链起来构成一个双链表，便于前面查找。,3. CF树的构造,CF树的构造过程与B-树的构造过程相似，就是对象不断插入的过程，因此BIRCH算法支持增量聚类。在CF树中插入Ent对象的过程如下：,识别合适的叶结点：从根结点开始逐层下降，计算当前条目与要插入数据点之间的距离，寻找距离最小的那个路径，直到找到与该数据点最接近的叶结点中的条目。,修改叶结点
28、：假设叶结点中与Ent对象最近的条目是Li，检测Li与Ent对象合并的簇直径是否小于阈值T，若小于，则更新Li的CF；否则为Ent对象创建一个新条目。如果叶结点有空间存放这个新条目，则存储，否则分裂该叶结点。分裂时选择相距最远的条目作为种子，其余条目按最近距离分配到两个新的叶结点中。,修改到叶结点的路径：将Ent对象插入一个叶结点后，更新每一个非叶结点的CF信息。如果不存在分裂，只需要进行加法运算；如果发生分裂，则在其父结点上要插入一个非叶结点来描述新创造的叶结点。修改过程重复进行，直至根结点。,在每次分裂之后跟随一个合并步。如果一个叶结点发生分裂，并且分裂过程持续到非叶结点Nj，扫描Nj，找
29、出两个最近的条目。如果不对应于刚分裂产生的条目，则试图合并这些条目及其对应的孩子结点。如果两个孩子结点中的条目多于一页所能容纳的条目，则将合并结果再次分裂。,一棵B=6、L=5的CF树,4. BIRCH算法,BIRCH算法采用了一种多阶段聚类技术，数据集合的单遍扫描产生一个基本的好聚类，一或多遍历的额外扫描可以用来进一步（优化）改进聚类质量。它主要包括两个阶段：阶段一：BIRCH扫描数据库，将一个个对象插入到最近的叶结点中，最后构造一棵能够存放于内存中的初始CF树，它可以看作数据的多层压缩，试图保留数据的内在的聚类结构。阶段二：BIRCH选用某个聚类算法对CF树的叶结点进行聚类，把稀疏的簇当做
30、离群点删除，把稠密的簇合并为更大的簇。,【例10.8】如表10.6所示是一份申请出国留学的TOEFT和GMAT成绩表，对其进行聚类分析。表中成绩对应的二维空间位置如图10.27所示。若采用欧几里得距离作为衡量学生聚类分析的相似度度量，显然距离越小，相似度越高。,采用BIRCH算法得到层次聚类CF树如图10.28所示。其中可以将5、6、14看作是离群点，在这里他们属于最优秀的学生。,10.3.4 CURE算法,CURE（Clustering Using Representatives）是一个新的层次聚类算法，该算法属于自顶向下和自底向上方法的中间方法。,CURE算法一旦选定代表点，便以一个特定的
31、收缩因子将它们向簇中心“收缩”。假设C是一个簇，用Cm表示其质心，p是它的一个代表点，其收缩操作是p+(Cmp)。通过收缩操作使得到的簇更紧凑，有助于减轻离群点的影响（离群点一般远离中心，因此收缩更多）。例如，若=0.7，一个到质心的距离为10个单位的代表点将移动3个单位，而到质心距离为1个单位的代表点仅移动0.3个单位。,CURE利用层次聚类过程的特性，在聚类过程的两个不同阶段删除离群点。如果一个簇增长缓慢，则意味它主要是由离群点组成，因为通常离群点远离其他点，并且不会经常与其他点合并。在CURE中，第一个离群点删除阶段一般出现在簇的个数是原来点数的1/3时。第二个离群点删除阶段出现在簇的个
32、数达到k（期望的簇个数）的量级点，小簇又被删除。,CURE算法如下：,输入：簇的数目k；数据集D；划分的个数p，期望压缩q，代表点个数c，收缩因子。输出：k个簇。方法：其过程描述如下：,从数据集D中抽取一个随机样本。样本中包含点的数目s可以由经验公式得到;把样本划分成p份，每个划分的大小相等，即为s/p个点。对每个划分进行局部聚类，将每个划分中的点聚类成个s/(pq)子簇，共得到总共s/p个子簇。对局部簇进一步合并聚类，对落在每个新形成的簇中的代表点（个数为c）根据收缩因子收缩或向簇中心移动，直到只剩下k个簇。在此过程中若一个子簇增长得太慢，就去掉它，另外在聚类结束的时候，删除非常小子簇;用相
33、应的簇标签来标记数据点;,【例10.9】有一个数据集根据经验公式随机抽取s=12个样本，如图10.29所示。设k、p均为2，、q=1，c=1，=0.5，CURE算法的过程如下：,（1）s=12，这些点被划分为p个划分，每个划分包含s/p=6个点，假设划分见图10.29中的虚线。,（2）对每个划分进行局部聚类，共产生s/(pq)=6个子簇，并计算这些子簇的c个代表点，如图10.30所示，每个子簇用虚线圆圈标出，实心圆点表示该簇的代表点。,共聚类为6个子簇,（3）合并聚类，先由子簇的代表点计算出两个子簇的最小距离，将最近的两个子簇合并，计算新的质心，将原来的代表点根据向新的质心收缩。其结果如图10
34、.31所示。,（4）删除增长最太慢的子簇，这里删除最左边的一个子簇，仅剩下2个子簇，即为所求。最后产生的聚类结果如图10.32所示。,最终聚类结果,10.3.5 ROCK算法,ROCK（Robust Clustering using linKs，使用链的鲁棒聚类）算法也是一个凝聚层次聚类算法。,定义10.3 数据集中两个点pi和pj是近邻，如果sim(pi，pj)，其中sim是相似度函数，是指定的阈值。两个点pi和pj的链接数定义为这两点的共同近邻个数。数据点对之间的链接数越多，它们越有可能属于同一个簇。,例如，购物篮数据集包含关于商品ag的事务记录。簇C1涉及商品a，b，c，d，e，簇C2涉
35、及商品a，b，f，g，它们包含的事务如表10.7所示。,事务之间的相似度采用Jaccard系数表示，A、B两个集合的Jaccard系数等于A、B交集的元素个数与A、B并集的元素个数之间的比值，即A、B集合的Jaccard系数:,如果只考虑相似度而忽略邻域信息。C1中a，b，c和b，d，e之间的Jaccard系数等于1/5=0.2，而C1中的a，b，c和C2中的a，b，f的Jaccard系数等于2/4=0.5。这说明仅根据Jaccard系数，很容易导致聚类错误。,例如，令=0.5，则C2中的事务a，b，f与a，b，g的链接数是5，它们的共同近邻是a，b，c、a，b，d、a，b，e、a，f，g、b
36、，f，g；而C2中的事务a，b，f与C1中的事务a，b，c之间的链接数是3，它们的共同近邻是a，b，d、a，b，e、a，b，g。因此，ROCK能够正确地区分出两个不同的事务簇。,如果考虑链接数，可以成功地把这些事务划分到恰当地簇中。,ROCK算法首先根据所给数据集的相似矩阵（由所有两个点的相似度构成的矩阵）和相似度阈值，构造出一个松散图，然后在这一松散图上应用一个层次聚类算法产生最终聚类结果。,10.3.6 Chameleon算法,Chameleon（Hierarchical Clustering Using Dynamic Modeling，一个利用动态模型的层次聚类算法，俗称变色龙算法）也
37、是一种凝聚层次聚类算法。其关键思想是：依据簇中对象的相对互连度和簇的相对接近度来定义簇之间的相似度，即如果两个簇的互连性都很高且它们又靠得很近则将其合并。,1. 相关定义,定义10.4 两个簇Ci和Cj的相对互连度RI(Ci，Cj)定义为它们之间绝对互连度除以这两个簇内的连接，也就是用这两个簇内部互连度规范化它们的绝对互连度，即：,两个簇Ci和Cj的绝对互连度EC(Ci，Cj)是指连接Ci和Cj之间的边之和。簇Ci的内部互连度EC(Ci)是将Ci划分成大致相等的两部分的割边的最小和。,定义10.5 两个簇Ci和Cj的相对接近度RC(Ci，Cj)定义如下：,其中，ni和nj分别表示簇Ci、Cj的
38、大小；是连接簇Ci、Cj的（k-最近邻图的）边的平均权值，即,是最小二分簇Ci的边的平均值，即 是最小二分簇Cj的边的平均值；EC表示割边。,RC(Ci，Cj)就是用Ci、Cj的内部接近度来规范化它们的绝对接近度。仅当Ci、Cj两个簇合并后的簇中点之间的接近程度几乎与原来的每个簇一样时，这两个簇才合并。,2. k-最近邻图,k-最近邻图Gk中的每个点表示数据集中的一个数据点。若数据点pi到另一个数据点pj的距离值是所有数据点到数据点pj的距离值中k个最小值之一，则称数据点pi是数据点pj的k-最近邻点，则在这两个点之间加一条带权边，边的权重表示这两个数据点之间的相似度，即它们之间的距离越大，则
39、它们之间的相似度越小，它们之间的边的权重也越小。,3. Chameleon算法,Chameleon算法根据每对簇Ci和Cj的相对互连度RI(Ci，Cj)和相对接近度RC(Ci，Cj)来决定它们之间的相似度。首先由数据集构造成一个k-最近邻图Gk，再通过一个多层图划分算法将图Gk划分成大量的子图，每个子图代表一个初始子簇，最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇。,在k-最近邻图Gk中，结点表示数据点，边表示数据点间的相似度，结点u、v之间的边表示结点u在结点v的k个最相似点中，或者结点v在结点u的k个最相似点中。k-最近邻图Gk可以看成是原完全图的稀疏图。,多层图划分算法的过
40、程是：从图Gk开始，二分当前最大的子簇，直到没有一个簇多于MIN_SIZE个点，其中MIN_SIZE是用户指定的参数。这一过程导致大量的大小大致相等、良连接的点（高度相似的数据点）的集合。目的是确保每个划分包含的对象大部分都来自一个真正的簇。,最后使用的凝聚层次聚类算法是合并子簇，两个子簇Ci，Cj之间的相似度函数采用: (RI(Ci，Cj)RC(Ci，Cj)表示，即取相对互连性和相对接近度之积最大的一对子簇合并，其中是用户指定的参数，通常大于1。,图10.33 Chameleon算法的聚类过程,Chameleon算法由三个关键步骤组成，稀疏化、图划分和层次聚类。例如，如图10.33所示给出了一个数据集采用Chameleon算法进行聚类的过程，这里m=3，即最终产生3个簇。,Chameleon算法将互连度和接近度都大的簇合并。其优点是可以发现高质量的任意形状的簇，对噪声和离群点具有很好的鲁棒性。存在的问题是，k-最近邻图中k值的选取，最小二等分的选取；用户指定方式中阈值的选取。,
