第11章 数据挖掘聚类分析

1、数据挖掘聚类分析引言引言o “物以类聚，人以群分物以类聚，人以群分”。对事物进行分类，是人们认识。对事物进行分类，是人们认识事物的出发点，也是人们认识世界的一种重要方法。因此，事物的出发点，也是人们认识世界的一种重要方法。因此，分类学已成为人们认识世界的一门基础科学。分类学已成为人们认识世界的一门基础科学。o 在生物、经济、社会、人口等领域的研究中，存在着大量在生物、经济、社会、人口等领域的研究中，存在着大量量化分类研究。例如：在生物学中，为了研究生物的演变，量化分类研究。例如：在生物学中，为了研究生物的演变，生物学家需要根据各种生物不同的特征对生物进行分类。生物学家需要根据各种生物不同的特征

2、对生物进行分类。o 在经济研究中，为了研究不同地区城镇居民生活中的收入在经济研究中，为了研究不同地区城镇居民生活中的收入和消费情况，往往需要划分不同的类型去研究。和消费情况，往往需要划分不同的类型去研究。o 在地质学中，为了研究矿物勘探，需要根据各种矿石的化在地质学中，为了研究矿物勘探，需要根据各种矿石的化学和物理性质和所含化学成分把它们归于不同的矿石类。学和物理性质和所含化学成分把它们归于不同的矿石类。o 在人口学研究中，需要构造人口生育分类模式、人口死亡在人口学研究中，需要构造人口生育分类模式、人口死亡分类状况，以此来研究人口的生育和死亡规律。分类状况，以此来研究人口的生育和死亡规律。 o

3、 但历史上这些分类方法多半是人们主要依靠经验作定性分但历史上这些分类方法多半是人们主要依靠经验作定性分类，致使许多分类带有主观性和任意性，不能很好地揭示类，致使许多分类带有主观性和任意性，不能很好地揭示客观事物内在的本质差别与联系；特别是对于多因素、多客观事物内在的本质差别与联系；特别是对于多因素、多指标的分类问题，定性分类的准确性不好把握。指标的分类问题，定性分类的准确性不好把握。o 为了克服定性分类存在的不足，人们把数学方法引入分类为了克服定性分类存在的不足，人们把数学方法引入分类中，形成了数值分类学。中，形成了数值分类学。o 后来随着多元统计分析的发展，从数值分类学中逐渐分离后来随着多元

4、统计分析的发展，从数值分类学中逐渐分离出了聚类分析方法。出了聚类分析方法。o 随着计算机技术的不断发展，利用数学方法研究分类不仅随着计算机技术的不断发展，利用数学方法研究分类不仅非常必要而且完全可能，因此近年来，聚类分析的理论和非常必要而且完全可能，因此近年来，聚类分析的理论和应用得到了迅速的发展。应用得到了迅速的发展。o 聚类分析就是分析如何对样品（或变量聚类分析就是分析如何对样品（或变量-在多元统计中，它在多元统计中，它就是一个向量）进行量化分类的问题。通常聚类分析分为就是一个向量）进行量化分类的问题。通常聚类分析分为Q型聚类和型聚类和R型聚类。型聚类。Q型聚类是对样品进行分类处理，型聚类

5、是对样品进行分类处理，R型聚类是对变量进行分类处理。型聚类是对变量进行分类处理。什么是聚类什么是聚类o 聚类（聚类（clustering）就是将数据分组成多）就是将数据分组成多个簇（个簇（cluster），使得同一个簇的对象之），使得同一个簇的对象之间具有较高的相似度，不同簇的对象相异间具有较高的相似度，不同簇的对象相异o 早在孩提时代，人就通过不断改进下意识中早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗、动物和的聚类模式来学会如何区分猫和狗、动物和植物植物聚类无所不在聚类无所不在聚类无所不在聚类无所不在聚类无所不在聚类无所不在聚类的应用领域聚类的应用领域有贡献的领域有

6、贡献的领域什么情况下应该聚类什么情况下应该聚类聚类分析原理聚类分析原理聚类与分类聚类与分类相似性及其度量相似性及其度量o 从复杂数据中提取相对简单分组结构的主要从复杂数据中提取相对简单分组结构的主要工作是找到一个工作是找到一个“紧密度紧密度”或相似性度量或相似性度量o “当我们看到它的时候，我们即可领会当我们看到它的时候，我们即可领会”o 基于特征来测量相似性基于特征来测量相似性n 产生特征产生特征n 提炼特征提炼特征n 规范化特征规范化特征n 减少特征减少特征测量相似性测量相似性o 在选择相似性度量时掺杂着大量的主观因素：在选择相似性度量时掺杂着大量的主观因素：变量的本质（离散的、连续的、二

7、值的）或变量的本质（离散的、连续的、二值的）或测量刻度（标称的、顺序的、间隔的、比值测量刻度（标称的、顺序的、间隔的、比值的）及主题知识的）及主题知识o 当所有项被聚类后，通常用距离表明邻近度当所有项被聚类后，通常用距离表明邻近度o 变量通常基于相关系数或关联度量而聚合变量通常基于相关系数或关联度量而聚合距离度量的常见计算方法距离度量的常见计算方法o 令令O1和和O2表示客观世界中的两个对象，表示客观世界中的两个对象，O1和和O2之间的距离（相异性）是一个实数，用之间的距离（相异性）是一个实数，用distance(O1,O2)或或d(O1，O2)o 明考夫斯基距离明考夫斯基距离o （4）幂距离

8、）幂距离o （5）差异百分率）差异百分率nkrpjkikoooocedis11)()2, 1(tannooNumberofoocedisjkik)(100)2, 1(tan二元属性对象的相似性二元属性对象的相似性o 当项不能用有意义的当项不能用有意义的p维测量表示时，项对之间的维测量表示时，项对之间的比较通常根据某些特征的存在和缺失完成，相似的比较通常根据某些特征的存在和缺失完成，相似的项具有更多的共同项项具有更多的共同项o 引入二元变量来描述是否具有某种特征，若具有该引入二元变量来描述是否具有某种特征，若具有该特征变量值为特征变量值为1，否则变量值为，否则变量值为0o 个体对的变量得分计算得

9、分矩阵个体对的变量得分计算得分矩阵n1 1的个数为的个数为an1 0的个数为的个数为bn0 1的个数为的个数为cn0 0的个数为的个数为d相似性系数相似性系数o 简单匹配系数简单匹配系数SMCo Jaccard系数系数o Rao系数系数)()(),(dcbabaxxSjismccbaaxxSjijc),()(),(dcbaaxxSjirc实例分析实例分析聚类的基本类型聚类的基本类型层次聚类层次聚类o 自底向上（凝聚）自底向上（凝聚）n 假定所有项属于一个单独簇，然后寻找最佳配假定所有项属于一个单独簇，然后寻找最佳配对并合并成一个新的簇对并合并成一个新的簇o 自顶向下（分裂）自顶向下（分裂）n

10、开始将所有数据看作一个簇，考虑所有可能的开始将所有数据看作一个簇，考虑所有可能的方法，将簇一分为二选择最佳划分，并递归第方法，将簇一分为二选择最佳划分，并递归第在这两个上继续划分在这两个上继续划分凝聚层次聚类凝聚层次聚类o 依靠共同的距离度量，聚类过程从寻找距依靠共同的距离度量，聚类过程从寻找距离最近的簇开始，并把这两个簇合并为一个离最近的簇开始，并把这两个簇合并为一个簇。簇。o 在开始时，让每个对象自成一簇，每个簇都在开始时，让每个对象自成一簇，每个簇都以选定的距离度量定义以选定的距离度量定义o 合并后，如何确定新簇之间的距离？合并后，如何确定新簇之间的距离？n 单连接（单连接（single

11、 linkage）n 完全连接（完全连接（complete linkage）单连接（最近邻）单连接（最近邻）o 两个簇的距离由不同簇的两个最近的对象间两个簇的距离由不同簇的两个最近的对象间的距离决定的距离决定n 簇的距离是属于不同簇的两个样本间的最近距簇的距离是属于不同簇的两个样本间的最近距离离o d(c1,c2)=mind(o,O)完全连接（最远邻）完全连接（最远邻）o 两个簇的距离隶属于不同簇的距离最远的两两个簇的距离隶属于不同簇的距离最远的两个对象的距离所决定（最远邻的距离）个对象的距离所决定（最远邻的距离）组平均组平均o 两个簇的距离就是隶属不同簇的所有对象的距离两个簇的距离就是隶属不

12、同簇的所有对象的距离的平均的平均o 加权平均加权平均o 组质心组质心o 加权组质心加权组质心o 沃德法沃德法2, 1,(211)2, 1(cocoOodnnccd单连接单连接完全连接完全连接层次聚类的优缺点层次聚类的优缺点o 优点优点n可以通过观察树状图来确定正确的簇数目可以通过观察树状图来确定正确的簇数目n层次的本质很好地反映了人类对某些领域的直觉层次的本质很好地反映了人类对某些领域的直觉n树状图的一个潜在应用时可以用来检测离群点树状图的一个潜在应用时可以用来检测离群点o 缺点缺点n有时会表现出无意义的或者不合逻辑的模式有时会表现出无意义的或者不合逻辑的模式o 无需事先指定簇的数目无需事先指

13、定簇的数目o 层次本质很好地反映了人类对某些领域认识的直觉层次本质很好地反映了人类对某些领域认识的直觉o 可伸缩性不好：时间复杂性至少为可伸缩性不好：时间复杂性至少为O(n2),n是所是所有对象的数量有对象的数量o 和任何启发式搜素算法一样，局部最优是一个问题和任何启发式搜素算法一样，局部最优是一个问题o 对结果的解释具有主观性对结果的解释具有主观性算法的步骤算法的步骤o 决定决定k的取值的取值o 初始化初始化k个簇中心个簇中心o 通过把对象分配给最近的簇中心来确定通过把对象分配给最近的簇中心来确定N个个对象的簇隶属关系对象的簇隶属关系o 假设上面所得的隶属关系是正确的，重新计假设上面所得的隶

14、属关系是正确的，重新计算算k个簇中心个簇中心o 若在最后一次迭代中若在最后一次迭代中N个对象无一再改变隶个对象无一再改变隶属关系，则退出，否则再转第属关系，则退出，否则再转第3步步K-means算法算法o 基本思想是初始随机给定基本思想是初始随机给定K个簇中心，按照最邻近个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值代，直到簇心的移动距离小于某个给定的值 o K-Means聚类算法主要分为三个步骤：聚类算法主

15、要分为三个步骤：(1)第一步是为待聚类的点寻找聚类中心第一步是为待聚类的点寻找聚类中心(2)第二步是计算每个点到聚类中心的距离，将每第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去个点聚类到离该点最近的聚类中去(3)第三步是计算每个聚类中所有点的坐标平均值，第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心并将这个平均值作为新的聚类中心反复执行反复执行(2)、(3)，直到聚类中心不再进行大范，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止围移动或者聚类次数达到要求为止 o K-均值非常适合用于产生球状簇，是数值的、非均值非常适合用于产生球状簇

16、，是数值的、非监督的、非确定的、迭代的监督的、非确定的、迭代的211)(kjnijjiCxJ2)(jjiCx表示数据点表示数据点x xi ij j到簇中心到簇中心CjCj的距离度量的距离度量，也指示，也指示n n个数据点及其各自簇中心的个数据点及其各自簇中心的距离距离K-中心点中心点o 与与k-均值相同的过程，只有样本空间中的数均值相同的过程，只有样本空间中的数据点可以作为中心点据点可以作为中心点o K-重点店是典型的划分算法。对于给定的重点店是典型的划分算法。对于给定的k，采用该算法的目标是在数据集中寻找采用该算法的目标是在数据集中寻找k个代个代表，使得每个对象划归到它最邻近的代表所表，使得

17、每个对象划归到它最邻近的代表所表示的簇中时，对象和代表的距离最小表示的簇中时，对象和代表的距离最小算法算法1）任意选取）任意选取k个对象作为初始中心点个对象作为初始中心点2）Repeat 把剩余对象分配到距离它最近的中心点所在的簇把剩余对象分配到距离它最近的中心点所在的簇 随机选择一个非中心点对象随机选择一个非中心点对象O 计算随机用计算随机用O交换交换Oj的总代价的总代价S 如如S0,则用则用O交换交换Oj，形成新的，形成新的k个中心点的集合个中心点的集合 Until 无变化发生无变化发生3）结束）结束工作方式工作方式o 首先在数据中为每个簇随意选一个对象，从而在首先在数据中为每个簇随意选一

18、个对象，从而在n个对象中发现个对象中发现k个簇个簇o 这些作为代表的对象称为中心点，其余对象为非中这些作为代表的对象称为中心点，其余对象为非中心点心点o 计算所有非中心点到每个中心点的距离，并将所有计算所有非中心点到每个中心点的距离，并将所有非中心点划分到距它最近的簇非中心点划分到距它最近的簇o 只要聚类结果可以改善，便不断地用非中心点代替只要聚类结果可以改善，便不断地用非中心点代替中心点中心点o 聚类质量通过代价函数来评价，该代价函数反映了聚类质量通过代价函数来评价，该代价函数反映了对象和它所属簇的代表之间的平均相异性对象和它所属簇的代表之间的平均相异性工作方式工作方式1）任意选择）任意选择

19、k个代表对象个代表对象2）计算每对代表对象）计算每对代表对象Oi和非代表兼和非代表兼Oh的的TCih3）选择满足）选择满足min(Oi,Oh,TCih)的的Oi,Oh对对 如果最小的如果最小的TCih为负，用为负，用Oh代替代替Oi，返回，返回到第到第2步步4）否则，为每个非代表对象寻找最相似对象）否则，为每个非代表对象寻找最相似对象现代聚类方法现代聚类方法o 五类：五类：n 层次方法（层次方法（BIRCH/CURE/ROCK)n 划分方法划分方法(K-均值均值/PAM/CLARA/CLARANS/K-众数）众数）n 基于密度方法基于密度方法n 基于网格方法基于网格方法n 基于模型方法基于模型

20、方法增量聚类增量聚类o 现在，有些应用涉及到成千上万个高维数据现在，有些应用涉及到成千上万个高维数据集。由于数据集规模太大，不可能把整个数集。由于数据集规模太大，不可能把整个数据集储存在主存储器里。据集储存在主存储器里。o 有三个方法可处理这类数据的聚类分析：有三个方法可处理这类数据的聚类分析：1. 可以把数据集存储在辅助存储器里，对数据可以把数据集存储在辅助存储器里，对数据的各个子集进行独立地聚类，然后合并生成的各个子集进行独立地聚类，然后合并生成整个数据集的聚类，称为分治方法。整个数据集的聚类，称为分治方法。2. 可以使用增量聚类算法。可以使用增量聚类算法。3. 可以并行实现聚类算法，并行

21、计算的好处是可以并行实现聚类算法，并行计算的好处是提高了分治方法的效率。提高了分治方法的效率。o 增量聚类算法的步骤：增量聚类算法的步骤：1. 把第一个数据项分配到第一个类里。把第一个数据项分配到第一个类里。2. 考虑下一个数据项，把它分配到目前某个类考虑下一个数据项，把它分配到目前某个类中或一个新类中。它基于一些准则的，例如中或一个新类中。它基于一些准则的，例如新数据项到目前类的重心的距离。在这种情新数据项到目前类的重心的距离。在这种情况下，每次添加一个新数据项到一个目前的况下，每次添加一个新数据项到一个目前的类中时，需要重新计算重心的值。类中时，需要重新计算重心的值。3. 重复步骤重复步骤

22、2，直到所有的数据样本都被聚类，直到所有的数据样本都被聚类完毕。完毕。o 增量算法是非迭代的，需要主存储空间非常增量算法是非迭代的，需要主存储空间非常小，所需要的时间也很少，即使采用迭代算小，所需要的时间也很少，即使采用迭代算法，所需的计算时间也不会显著增加。法，所需的计算时间也不会显著增加。o 增量聚类存在的一个明显的缺点：对样本的增量聚类存在的一个明显的缺点：对样本的顺序非常敏感。不同的顺序会产生不同的分顺序非常敏感。不同的顺序会产生不同的分区。区。o 例如：仍然采用上例的数据集。假定样本的例如：仍然采用上例的数据集。假定样本的顺序是顺序是x1,x2,x3,x4,x5，则类相似度阈值，则类

23、相似度阈值水平是水平是=3。1. 第一样本第一样本x1为第一个类为第一个类C1=x1。C1的重的重心为心为M1=0,2。2. 开始分析其他样本。开始分析其他样本。 a)把第二个样本把第二个样本x2和和M1比较，距离比较，距离d为：为： d(x2,M1)=(02+22)1/2=2.03 因此，因此， x2属于类属于类C1 ，新的重心是：，新的重心是： M1=0,1 b)第三个样本第三个样本x3和重心和重心M1比较：比较： d(x3,M1)=(1.52+12)1/2=1.83 x4 C2 =x4 M2=5,0 d)第五个样本和这两个类的重心相比较：第五个样本和这两个类的重心相比较： d(x5,M1

24、)=(4.52+1.442)1/2=4.723 d(x5,M2)=(02+22)1/2=23 x5 C2 C2 =x4,x5 M2=5,13. 分析完所有的样本，聚类结果是获得两个类：分析完所有的样本，聚类结果是获得两个类： C1 =x1,x2,x3和和C2 =x4,x5o如果观察的样本的顺序不同，聚类结果也不同。如果观察的样本的顺序不同，聚类结果也不同。 o 对于大多数分区聚类算法，包括迭代方法，对于大多数分区聚类算法，包括迭代方法，都是通过该类的特征向量都是通过该类的特征向量CF给出的类的简要给出的类的简要表示，每个类的参数由表示，每个类的参数由3部分组成，类中点部分组成，类中点(样本样本)的个数，类的重心和类的半径。的个数，类的重心和类的半径。o 类的半径定义为类中的点到重心的平均平方类的半径定义为类中的点到重心的平均平方距离的平方根距离的平方根(平均类内方差平均类内方差)。o 当添加和删除类中的点时，可以通过旧的当添加和删除类中的点时，可以通过旧的CF来计算新来计算新CF，而不需要用类中所有点去计算，而不需要用类中所有点去计算新的新的CF，这一点非常重要。，这一点非常重要。o 如果样本是分类的数据，就没有办法计算类如果样本是分类的数据，就没有办法计算类的重心来表述类。另一种算法的重心来表述类。另一种算法K-最近邻法可最近邻法可用于估计样本和目前类间的距