1、聚 类报告人：熊 赟内容提要 符号说明及定义符号说明及定义 相似性度量相似性度量聚类分析中的数据类型聚类分析中的数据类型 聚类的准则函数聚类的准则函数 聚类分析的过程聚类分析的过程 聚类方法与算法聚类方法与算法符号说明符号说明 1.1.，由，由d d个属性值组成：个属性值组成：X X（x x1 1,x,x2 2,x,xd d），其中），其中x xi i表示样本中的各属性，表示样本中的各属性，d d是样本或样本空间的维数（或属性个数）。是样本或样本空间的维数（或属性个数）。 2.2.记为记为 X X1 1,X,X2 2,X,Xn n，第，第i i个样本个样本记为记为X Xi ix xi1i1,x
2、,xidid，许多情况下聚类的样，许多情况下聚类的样本本集看成是一个本本集看成是一个n nd(nd(n个样本个样本d d个属性个属性) )的数的数据矩阵：据矩阵： ndnfnidifidfxxxxxxxxx.111111符号说明符号说明 3.3.：数据样本集：数据样本集X X分成分成k k个簇，每个簇是相应个簇，每个簇是相应数据样本的集合，相似样本在同一簇中，相异样数据样本的集合，相似样本在同一簇中，相异样本在不同簇中。本在不同簇中。 簇簇C Ci i（i=1,2,ki=1,2,k）中样本的数量）中样本的数量n ni i。簇记为。簇记为C Ci iX Xj1j1i i,X,Xj2j2i i,X
3、,Xjnijnii i， C Ci i（i i1,1,k,k）是）是X X的子集，如下所示：的子集，如下所示： C C1 1C C2 2C Ck kX X 且且 C Ci iC Cj j，ijij符号说明符号说明 用下面的特征来描述簇：用下面的特征来描述簇： （centroidcentroid）：（样本的平均值）是）：（样本的平均值）是簇的簇的“中间值中间值”（middlemiddle），但并不需要是簇中），但并不需要是簇中实际点。实际点。 令令n ni i表示簇表示簇C Ci i中样本的数量，中样本的数量，m mi i表示对应样本的表示对应样本的均值：均值： centroidcentroid
4、 簇的半径，是簇中两个点间的均方差的平方根。簇的半径，是簇中两个点间的均方差的平方根。 i iC CX Xi ii iX Xn n1 1m m定 义 定 义定 义： 给 定 一 数 据 样 本 集： 给 定 一 数 据 样 本 集 X XX X1 1,X,X2 2,X,Xn n，根据数据点间的相似程度将数，根据数据点间的相似程度将数据集合分成据集合分成k k簇：簇：C C1 1,C,C2 2,C,Ck k的过程称为聚的过程称为聚类，类，i=1i=1k kC Ci iX X，C Ci iC Cj j，ijij 。相似样本在同一簇中，相异样本在不同簇中。相似样本在同一簇中，相异样本在不同簇中。 关
5、于同一簇中的样本比来自不同簇的样本更为相关于同一簇中的样本比来自不同簇的样本更为相似的判断问题主要涉及以下两个独立的子问题：似的判断问题主要涉及以下两个独立的子问题： a.a.； b.b.。 相似性度量相似性度量 （dissimilarity matrixdissimilarity matrix）用来存储）用来存储n n个样本两两之间的相似性，表现形式是一个个样本两两之间的相似性，表现形式是一个n nn n维的矩阵：维的矩阵： d(Xd(Xi i，X Xj j) )是样本是样本X Xi i和样本和样本X Xj j间相异性的量化表示。间相异性的量化表示。 最明显的相似性度量是最明显的相似性度量是
6、。 000021231312.),(),(.),(),(),(XXdXXdXXdXXdXXdnn相似性度量相似性度量 X Xi ix xi1i1,x,xidid和和X Xj jx xj1j1,x,xjdjd是两个具有是两个具有d d个属性的两个样本。距离度量标准个属性的两个样本。距离度量标准d d（X Xi i，X Xj j）表示第表示第i i个样本与第个样本与第j j个样本间的距离。个样本间的距离。 在聚类分析中，最常用的距离定义如下：在聚类分析中，最常用的距离定义如下： 最著名的距离度量标准是最著名的距离度量标准是d d维空间中的维空间中的： d d（X Xi i，X Xj j）（）（ 2
7、 2）1/21/2 dkjkikxx1)(相似性度量相似性度量 更广义的更广义的d d维空间中的度量为维空间中的度量为度量度量 L Lk k（X Xi i，X Xj j）（）（ k k）1/k1/k 通常也被称为通常也被称为，即即L L2 2范数。范数。而而L L1 1范数则常被称为范数则常被称为 dkjkikxx1|相似性度量相似性度量 例：对于一个例：对于一个4 4维向量维向量X X1 11,0,1,01,0,1,0和和X X2 22,1,-3,-12,1,-3,-1，这些距离的度量标准，这些距离的度量标准 L L1 1（X X1 1，X X2 2）1+1+4+11+1+4+17 7， L
8、 L2 2（X X1 1，X X2 2）（）（1+1+16+11+1+16+1）1/21/24.364.36 L L3 3（X X1 1，X X2 2）（）（1+1+64+11+1+64+1）1/31/34.064.06。 L Lk k（X Xi i，X Xj j）（）（ k k）1/k1/k dkjkikxx1| 聚类算法即是先定义一个合适的度量，然聚类算法即是先定义一个合适的度量，然后计算任意两个样本之间的距离。当两个后计算任意两个样本之间的距离。当两个样本之间的欧几里德距离小于某个阈值样本之间的欧几里德距离小于某个阈值d d0 0时，这两个样本就属于同一类。距离阈值时，这两个样本就属于同
9、一类。距离阈值d d0 0影响簇的数量和大小，影响簇的数量和大小，d d0 0越小，每个簇就越小，每个簇就越小，簇的数目就越多。如果越小，簇的数目就越多。如果d d0 0太大，则太大，则所有样本将会被分为同一簇；如果所有样本将会被分为同一簇；如果d d0 0太小，太小，每个样本又会单成一类。每个样本又会单成一类。聚类分析中的数据类型聚类分析中的数据类型 1.1.区间标度变量区间标度变量（interval-valued variablesinterval-valued variables） 2.2.二元变量（二元变量（Binary VariablesBinary Variables）样本样本X
10、Xj j1 10 0样本样本X Xi i1 1n n1,11,1n n1,01,00 0n n0,10,1n n0,00,0 3.3.标称型、序数型、比例标度型变量标称型、序数型、比例标度型变量 4.4.混合型变量混合型变量二元变量的相似度计算二元变量的相似度计算（simple matching coefficientsimple matching coefficient，SMCSMC）评价这样评价这样的两个样本的两个样本X Xi i和样本和样本X Xj j之间的相异度之间的相异度 评价系数是评价系数是 例：样本例：样本X Xi i和样本和样本X Xj j具有具有8 8个二元类型变量：个二元类
11、型变量： X Xi i0,0,1,1,0,1,0,10,0,1,1,0,1,0,1和和X Xj j0,1,1,0,0,1,0,00,1,1,0,0,1,0,0 则则n n1.11.12 2， n n1.01.02 2， n n0.10.11 1， n n0.00.0 3 3 S Ssmcsmc(X(Xi i,X,Xj j)=3/8)=3/8，S Sjcjc(X(Xi i,X,Xj j)=3/5)=3/5 001001111001.),(nnnnnn XXSjismc 1001111001.),(nnnnn XXSjijc 簇间的距离度量标准簇间的距离度量标准 用于簇用于簇C Ci i和簇和簇C
12、 Cj j之间的距离度量标准是：之间的距离度量标准是： 1)1)最小距离：最小距离： 其中其中X Xi iCCi i和和X Xj jCCj j 2)2)最大距离：最大距离： 其中其中X Xi iCCi i和和X Xj jCCj j|min),(minjijiXXCCD|max),(maxjijiXXCCD 3)3)中间距离：中间距离： 其中其中m mi i和和m mj j是是C Ci i和和C Cj j的质心的质心 4)4)平均距离：平均距离： 其中其中X Xi iCCi i和和X Xj jCCj j，且，且n ni i和和n nj j是类是类C Ci i和和C Cj j间的样间的样本数。本数
13、。|),(jijimeanmmCCD|),(jijijiavgXXnnCCD 1簇间的距离度量标准簇间的距离度量标准聚类的准则函数聚类的准则函数 （sum-of-squared-error criterionsum-of-squared-error criterion）：）： 其中其中XCXCi i，m mi i是是C Ci i的质心的质心 J Je e即所有样本的平方误差和。即所有样本的平方误差和。 21|iiCXkiemXJ聚类的分析过程聚类的分析过程 聚类技术概览聚类技术概览 划分的方法划分的方法 层次的方法层次的方法 基于密度的方法基于密度的方法 基于网格的方法基于网格的方法 基于模型
14、的方法基于模型的方法 划分方法划分方法（partitioning methodpartitioning method） 划分方法的基本思想是，给定一个划分方法的基本思想是，给定一个n n个样本个样本的数据库，划分方法将数据划分为的数据库，划分方法将数据划分为k k个划分个划分（k=nkX)=3.40 =X1 1CC1 1； d(Md(M1 1,X,X2 2)=1.79 )=1.79 和和 d(M d(M2 2,X,X2 2)=3.40 =X)=3.40 =X2 2CC1 1 d(Md(M1 1,X,X3 3)=0.83 )=0.83 和和 d(M d(M2 2,X,X3 3)=2.01 =X)
15、=2.01 =X3 3CC1 1 d(Md(M1 1,X,X4 4)=3.41 )=3.41 和和 d(M d(M2 2,X,X4 4)=2.01 =X)=2.01 =X4 4CC2 2 d(Md(M1 1,X,X5 5)=3.60 )=3.60 和和 d(M d(M2 2,X,X5 5)=2.01 =X)=2.01 =X5 5CC2 2 新簇新簇C C1 1X X1 1,X,X2 2,X,X3 3和和C C2 2X X4 4,X,X5 5基于质心的基于质心的 k kmeansmeans聚类算法聚类算法 第第3 3步：计算步：计算： M M1 10.50.5，0.670.67； M M2 25
16、.05.0，1.01.0。 相应的方差及总体平方误差分别是：相应的方差及总体平方误差分别是： e e1 12 24.174.17； e e2 22 22.002.00； E E6.176.17； 可以看出第一次迭代后，总体误差显著减小（从可以看出第一次迭代后，总体误差显著减小（从值值27.4827.48到到6.176.17）。在这个简单的例子中，第一）。在这个简单的例子中，第一次迭代同时也是最后一次迭代，因为如果继续分次迭代同时也是最后一次迭代，因为如果继续分析新中心和样本间的距离，样本将会全部分给同析新中心和样本间的距离，样本将会全部分给同样的簇，不将重新分配，算法停止。样的簇，不将重新分配
17、，算法停止。 k kmeansmeans算法的变体算法的变体 要求用户必须事先给出要生成的簇的数目要求用户必须事先给出要生成的簇的数目，选择选择初始划分的最佳方向、更新分区和停止准则初始划分的最佳方向、更新分区和停止准则 大小很不相同的簇或具有凹状的簇。大小很不相同的簇或具有凹状的簇。 算法只有在簇的平均值被定义的情况下才能使用，算法只有在簇的平均值被定义的情况下才能使用，这不适涉及有分类属性的数据。这不适涉及有分类属性的数据。 k kprototypesprototypes算法对数值与离散两种混合的数算法对数值与离散两种混合的数据聚类，据聚类， k kmodesmodes方法方法对离散属性对
18、离散属性 对噪音和异常点非常敏感对噪音和异常点非常敏感 基于有代表性对象的技术基于有代表性对象的技术k-mediodsk-mediods方法方法 基本策略：不采用簇中样本的平均值作为参照点，基本策略：不采用簇中样本的平均值作为参照点，选用簇中位置最中心的对象选用簇中位置最中心的对象中心点作为参照中心点作为参照点。点。 PAMPAM(Partitioning Around Medoids(Partitioning Around Medoids围绕中心点划分围绕中心点划分) )+Oi P Oj + + Orandom+Oi Oj + P + OrandomC Cd(p,Od(p,Oi i)-d(p
19、,O)-d(p,Oj j) ) C Cd(d(p p,O,Orandomrandom)-d()-d(p p,O,Oj j) ) +Oi P Oj + + Orandom+Oi Oj + + P OrandomC C0 0 C Cd(d(p p,O,Orandomrandom)-d()-d(p p,O,Oi i) ) S S C C PAMPAM算法：算法：1.1.随机选择随机选择k k个代表对象作为初始的中心点。个代表对象作为初始的中心点。 2.repeat2.repeat 3.3.指派每个剩余对象给离它最近的中心点所代指派每个剩余对象给离它最近的中心点所代表的簇；表的簇； 4.4.随机的选择
20、一个非中心点对象随机的选择一个非中心点对象O Orandomrandom 5.5.计算用计算用O Orandomrandom代替代替O Oj j的总代价的总代价TcTcihih 6.if s6.if s为负，则为负，则O Orandomrandom代替代替O Oj j，形成新的，形成新的k k个中个中心点的集合心点的集合 7.Until 7.Until 不发生变化不发生变化层次聚类层次聚类 凝聚的层次聚类采用自底向上策略，首先将每个凝聚的层次聚类采用自底向上策略，首先将每个样本作为一个簇，然后合并这些原子簇形成越来样本作为一个簇，然后合并这些原子簇形成越来越大的簇，减少簇的数目，直到所有的样本
21、都在越大的簇，减少簇的数目，直到所有的样本都在一个簇中，或某个终结条件被满足。一个簇中，或某个终结条件被满足。 分裂的层次聚类采用自顶向下策略，首先将所有分裂的层次聚类采用自顶向下策略，首先将所有样本置于一个簇中，然后逐渐细分为越来越小的样本置于一个簇中，然后逐渐细分为越来越小的簇，来增加簇的数目，直到每个样本自成一个簇，簇，来增加簇的数目，直到每个样本自成一个簇，或者达到某个终结条件，例如达到了某个希望的或者达到某个终结条件，例如达到了某个希望的簇的数目或两个最近的簇之间的距离超过了某个簇的数目或两个最近的簇之间的距离超过了某个阈值。阈值。凝聚层次聚类凝聚层次聚类 1.1.初始化：计算包含每
22、对样本间距离（如欧氏距初始化：计算包含每对样本间距离（如欧氏距离）的相似矩阵，把每个样本作为一个簇；离）的相似矩阵，把每个样本作为一个簇； 2.2.选择：使用相似矩阵查找最相似的两个簇；选择：使用相似矩阵查找最相似的两个簇； 3.3.更新：将两个簇合并为一个簇，簇的个数通过更新：将两个簇合并为一个簇，簇的个数通过合并被更新；同时更新相似矩阵，将两个簇的两合并被更新；同时更新相似矩阵，将两个簇的两行（两列）距离用行（两列）距离用1 1行（行（1 1列）距离替换反映合并列）距离替换反映合并操作。操作。 4.4.重复：执行重复：执行n-1n-1次步骤次步骤2 2和步骤和步骤3 3； 5.5.结束：当
23、所有样本都合并成一个簇或满足指定结束：当所有样本都合并成一个簇或满足指定的簇的数目时，整个过程结束。的簇的数目时，整个过程结束。 一一(single-linkage) (single-linkage) （最近邻（最近邻(Nearest Neighbor)(Nearest Neighbor)）：）： 基本思想：两个簇之间的距离用从两个簇中抽取基本思想：两个簇之间的距离用从两个簇中抽取的每对样本的最小距离的每对样本的最小距离 作为距离度量，一旦最近的两个类的距离超过某作为距离度量，一旦最近的两个类的距离超过某个任意给定的阈值，算法就自动结束。个任意给定的阈值，算法就自动结束。 二二 三三),(mi
24、njiCCD凝聚层次聚类凝聚层次聚类 先将五个样本都分别看成是一个簇，最靠近的两先将五个样本都分别看成是一个簇，最靠近的两个簇是个簇是3 3和和4 4，因为他们具有最小的簇间距离，因为他们具有最小的簇间距离 D D（3 3，4 4）=5.0=5.0。第一步：合并簇第一步：合并簇3 3 和和4 4 ，得 到 新 簇 集 合，得 到 新 簇 集 合 1 , 2 ,1 , 2 ,（3434）,5,5 单连接算法单连接算法 更新距离矩阵：更新距离矩阵： D(1,(34) = min(D(1,3),D(1,4) = min(20.6, D(1,(34) = min(D(1,3),D(1,4) = min
25、(20.6, 22.4) = 20.6;22.4) = 20.6; D(2,(34) = min(D(2,3),D(2,4) = min(14.1, D(2,(34) = min(D(2,3),D(2,4) = min(14.1, 11.2) = 11.2;11.2) = 11.2; D(5,(34) = min(D(3,5),D(4,5) = min(25.0, D(5,(34) = min(D(3,5),D(4,5) = min(25.0, 25.5) = 25.0.25.5) = 25.0. 原有簇原有簇1,2,51,2,5间的距离不变，修改后的距离矩阵间的距离不变，修改后的距离矩阵如图
26、所示，在四个簇如图所示，在四个簇1,2,(34),51,2,(34),5中，最靠近的两中，最靠近的两个簇是个簇是1 1和和5 5，它们具有最小簇间距离，它们具有最小簇间距离D D（1,51,5）7.077.07。单连接算法单连接算法 单连接算法单连接算法 单连接算法单连接算法改进的层次聚类改进的层次聚类 BIRCHBIRCH是一个综合的层次聚类方法，它引入了两是一个综合的层次聚类方法，它引入了两个概念：聚类特征和聚类特征树（个概念：聚类特征和聚类特征树（CFCF树）树） CURECURE方法采用了一种新颖的层次聚类算法，该算方法采用了一种新颖的层次聚类算法，该算法选择基于质心和基于代表对象方法
27、之间的中间法选择基于质心和基于代表对象方法之间的中间策略。策略。 ROCKROCK方法是一个可选的凝聚的层次聚类算法，适方法是一个可选的凝聚的层次聚类算法，适用于分类属性。用于分类属性。 ChameleonChameleon（变色龙）方法是一个在层次聚类中（变色龙）方法是一个在层次聚类中采用动态模型的层次聚类算法采用动态模型的层次聚类算法 基于密度的方法基于密度的方法 基于样本之间的距离的聚类方法只能发现球状的基于样本之间的距离的聚类方法只能发现球状的簇，基于密度的方法可用来过滤簇，基于密度的方法可用来过滤“噪声噪声”孤立点孤立点数据，以发现任意形状的簇。其主要思想是只要数据，以发现任意形状的
28、簇。其主要思想是只要临近区域的密度（样本的数目）超过某个阈值则临近区域的密度（样本的数目）超过某个阈值则继续聚类。即对于给定簇中的每个样本，在一个继续聚类。即对于给定簇中的每个样本，在一个给定范围的区域中必须至少包含某个数目的样本。给定范围的区域中必须至少包含某个数目的样本。基于密度的方法基于密度的方法 基于密度聚类的相关定义：基于密度聚类的相关定义： a.a.给定对象半径给定对象半径内的区域称为该对象的内的区域称为该对象的邻邻域。域。 b.b.如果一个对象的如果一个对象的邻域至少包含最小数目邻域至少包含最小数目MinPtsMinPts个对象，则称该对象为核心对象。个对象，则称该对象为核心对象
29、。 c.c.给定一个对象集合给定一个对象集合D D，如果，如果p p是在是在q q的的邻域邻域内，而内，而q q是一个核心对象，则称对象是一个核心对象，则称对象p p从对象从对象q q出出发是直接密度可达的。发是直接密度可达的。基于密度的方法基于密度的方法 d.d.如果存在一个对象链如果存在一个对象链p p1 1,p,p2 2,p,pn n，p p1 1q q，p pn np p，对，对p pi iDD（1=i=n1=i=n），），p pi+1i+1是从是从p pi i关关于于和和MinPtsMinPts直接密度可达的，则对象直接密度可达的，则对象p p是是从对象从对象q q关于关于和和Min
30、PtsMinPts密度可达的。密度可达的。 e.e.如果对象集合如果对象集合D D中存在一个对象中存在一个对象o o，使得，使得对象对象p p和和q q是从是从o o关于关于和和MinPtsMinPts密度可达的，密度可达的，那么对象那么对象p p和和q q是关于是关于和和MinPtsMinPts密度相连密度相连的。的。基于密度的方法基于密度的方法 一基于高密度连接区域的聚类方法：一基于高密度连接区域的聚类方法：DBSCAN DBSCAN 二通过对象排序识别聚类结构的聚类方法：二通过对象排序识别聚类结构的聚类方法：OPTICS OPTICS a.a.核心距离：一个对象核心距离：一个对象p p的
31、核心距离是使得的核心距离是使得p p成为成为核心对象的最小的核心对象的最小的。如果。如果p p不是核心对象，不是核心对象，p p的的核心距离没有定义；核心距离没有定义； b.b.可达距离：一个对象可达距离：一个对象q q关于另一个对象关于另一个对象p p的可达的可达距离是距离是p p的核心距离和的核心距离和p p与与q q的欧几里得距离之间的欧几里得距离之间的较大值。如果的较大值。如果p p不是一个核心对象，不是一个核心对象，p p和和q q之间之间的可达距离没有定义。的可达距离没有定义。 三三. .基于密度分布函数的聚类方法：基于密度分布函数的聚类方法：DENCLUEDENCLUE 基于网格的方法基于网格的方法 基于网格的多分辨率方法基于网格的多分辨率方法STINGSTING，在网格单元中，在网格单元中收集统计信息。收集统计信息。 WaveClusterWaveCluster是一个多分辨率的聚类方法，通过是一个多分辨率的聚类方法，通过小波变换来转换原始的特征空间。小波变换来转换原始的特征空间。 CLQUECLQUE是一个综合了基于密度和基于网格方法的是一个综合了基于密度和基于网格方法的聚类算法，对于大型数据库中的高维数据的聚类聚类算法，对于大型数据库中的高维数据的聚类非常有效。非常有效。基于模型的方法基于模型的方法 统计学方法和神经网络方法统计学方法和神经网络方法
