数据挖掘2015最新精品课程完整课件(第13讲)---聚类分析

1、u聚类聚类u基于分割的聚类基于分割的聚类u层次聚类层次聚类u基于密度的聚类基于密度的聚类u发现对象簇(Cluster)，使得同一个簇内的对象尽量相似，不同簇间的对象尽量不同。Inter-cluster distances are maximizedIntra-cluster distances are minimizedHow many clusters?Four Clusters Two Clusters Six Clusters u无监督的学习(Unsupervised learning): 与分类不同，没有事先定义的类别标记。u聚类的用途： 作为单独的数据分析工具 可作为其它方法的预处理

2、手段u理解(Understanding) 相关文档的组, 有相似功能的基因和蛋白质组, 或有相似价格波动的股票等。u概括(Summarization) 减小数据集的规模Clustering precipitation in Australiau数据概括(Summarization): 服务于回归(regression), 主成分分析(PCA), 分类(classification), 关联分析(association analysis)u压缩(Compression): 图像处理(Image processing)u寻找K-最近邻居(K-nearest Neighbors) 在一个簇或几个簇内

3、进行局部搜索u高质量的聚类： 高簇内相似性(high intra-class similarity) 低簇间相似性(low inter-class similarity)u聚类的质量不但依赖于所使用的方法，而且也依赖于实现方式。u聚类质量最主要的评价标准还是用户的满意程度。u相似性度量: 一般通过距离函数来描述: d(i, j) 针对不同数据，如区间值数据、布尔数据、类别数据、顺序数据等，会有不同的距离函数 根据不同应用和数据的语义，变量会被赋予不同的权重。u聚类的质量: 通常会有明确的质量函数来度量聚类质量的好坏。 很难定义“足够好” 这类问题的答案往往具有明显的主观色彩。u数据矩阵u差别矩

4、阵u通常距离函数须具备如下性质： d(i,j) 0，非负性 d(i,i) = 0 d(i,j) = d(j,i)，对称性 d(i,j) d(i,k) + d(k,j)，三角不等式 u假设每条记录有n个属性, 两个元组(xi1, , xin)和(xj1, , xjn)的相似性可通过如下方式来度量：uMinkowski距离：u若属性具有不同的权重，此时的距离可定义为：u通常使用的是Minkowski距离的特殊形式：u可使用Minkowski距离及其特殊形式u使用距离函数之前，要对属性的值进行规范化，如z-值规范化：u使用平均绝对偏差(Mean Absolute Deviation, MAD)，而不

5、用标准差的原因： 前者比后者抗噪声能力更强 用前者更容易检测到噪声u顺序属性(ordinal attribute)可以是连续的，也可以是离散的 可通过离散化把连续属性转换为顺序属性u顺序比实际的值更重要u转换后可看作是连续属性 将实际的值xiA用其排序(rank)riA来代替, riA 1, , MA 将排序映射到0, 1 再使用Minkowski距离u使用列联表(contingency table)u对称属性(symmetric attribute)的距离: u非对称属性(asymmetric attribute)的距离: Jaccard系数：1-d(i,j)dcbacb jid),(cba

6、cb jid),(pdbcasumdcdcbabasum0101Object iObject j 性别是对称属性，其余均是非对称属性 设Y和P代表1，N代表0 相异性只由非对称属性计算NameGender Fever Cough Test-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),( maryjimdjimjackdmaryjackdu二值数型的泛化,可取两个以上的值, 如red, yellow, blue, greenu方法1: 简单匹配 m: # of matc

7、hes, p: total # of variablesu方法2: 转化为二值属性pmpjid),(u将不同类型的属性转换到0, 1u不同的属性可被赋予不同的权重u向量对象: 文档中的关键字等.u应用广泛: 信息检索, 生物信息学等.uCosine measure (,)XYsXYXY u聚类就是要得到一系列的簇u主要分为分割聚类和层次聚类u分割聚类(Partitional Clustering) 将数据对象分割为不重叠的子集，使得每个数据对象只属于其中的一个子集。u层次聚类(Hierarchical clustering) 将数据对象分割为一系列嵌套的、树状的簇Original Points

8、A Partitional Clusteringp4p1p3p2 p4 p1 p3 p2 p4p1p2p3p4p1 p2p3Traditional Hierarchical ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogramu排它的与非排它的 非排它聚类中，对象可能属于多个簇u模糊与非模糊的 模糊聚类中，每个点与每个簇都有一个0到1之间的隶属度 这些隶属度的和必须是1u部分与完全的 在某些情况下，可能只对一部分数据进行聚类u同构与异构的 可能对不同类型

9、的对象进行聚类u良分割聚类(Well-separated clusters)u基于中心的聚类(Center-based clusters)u邻近聚类(Contiguous clusters)u基于密度的聚类(Density-based clusters)u基于概念的聚类(Concept-based clusters)u基于目标函数的聚类(Objective Function clusters)u每个点到簇内其它点的距离都小于到簇外其它点的距离。3 well-separated clustersu每个点与其所在簇中心的距离都小于与其它簇中心的距离。u簇的中心可以是质心(centroid), 即簇

10、内所有点的均值；或是medoid, 即簇内最有代表性的点。（它到其他所有（当前cluster中的）点的距离之和最小）4 center-based clustersu簇是密度超过一定阈值的点的集合，簇与簇之间被一些低密度度区域分开。u适用于簇不规则(irregular)、或相互纠缠(intertwined), 及存在噪声和孤立点(outlier) 的情况。7 density-based clustersu用目标函数来定义簇 构建簇，使目标函数最大或最小。 枚举所有可能的把对象点构成簇的方式，并使用目标函数对这些簇进行评价，评价结果最好的作为最终的聚类方式。(NP Hard) 可以有全局和局部目标

11、 层次聚类通常是局部目标 分割聚类通常是全局目标u可将聚类问题映射到不同的域，并在这些域内求解问题： 相关矩阵(Proximity matrix)定义了一个加权图，其中结点是用于聚类的点，加权的边代表结点间的相关性。 聚类等价于将图分割为互连的子图，每个子图代表一个簇。 目标是使簇间的权重和最小，簇内的权重和最大。u聚类聚类u基于分割的聚类基于分割的聚类u层次聚类层次聚类u分割聚类方法u每个簇都有一个中心点(centroid) u每个点最终都归属于一个与其距离最近的中心点所决定的簇。u簇的数目K需要事先给定u基本的算法非常简单u初始中心点是随机选择的每次迭代之后簇往往会发生变化.u中心点一般是

12、该簇的均值.u“相似性”一般是通过Euclidean距离, cosine 相似性等来度量的.u在以上这些相似性度量标准下，K-平均聚类一般都会收敛.u复杂性O( n * K * I * d )n = number of points, K = number of clusters, I = number of iterations, d = number of attributes-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xySub-optimal Clustering-2-1.5-1-0.500

13、.511.5200.511.522.53xyOptimal ClusteringOriginal Points-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0

14、.500.511.5200.511.522.53xyIteration 6-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.

15、522.53xyIteration 6u误差的平方和(Sum of Squared Error, SSE)是最基本的方法。 对每个点，其差指该点与其所在簇间的距离 计算所有的差，并对这些结果平方求和. X是簇Ci 内的点，mi 是代表簇Ci 的点 mi 可取簇的均值 给定两种聚类方案，取SSE小的方案。 减小SSE的一种可能的办法是增加K,即簇的数量 一个好的聚类方案可以在较少簇的前提下，同样具有较小的SSE.KiCxiixmdistSSE12),(k-means优缺点优缺点u主要优点： 是解决聚类问题的一种经典算法，简单、快速。 对处理大数据集，该算法是相对可伸缩和高效率的。 当结果簇是密集

16、的，它的效果较好。u主要缺点 在簇的平均值被定义的情况下才能使用。 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。 不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。uK-中心点(K-Medoids): 使用中心点(medoids)，而不是平均值进行聚类，所谓中心点是指簇内最中心的实际数据点。012345678910012345678910012345678910012345678910初始聚类中心的选取决定着计算的迭代次数，甚至决初始聚类中心的选取决定着计算的迭代次数，甚至决定着最终的解是否为全局最优。定着最

17、终的解是否为全局最优。首先选择第一个样本点作为第一个聚类中心。首先选择第一个样本点作为第一个聚类中心。然后选取距离第一个点最远的点作为第二个聚类中心。然后选取距离第一个点最远的点作为第二个聚类中心。第第j个聚类中心要远离第个聚类中心要远离第1j-1个聚类中心。个聚类中心。 或者可以多次随机取初始聚类中心，得到聚类结果，或者可以多次随机取初始聚类中心，得到聚类结果，取平均值。取平均值。u若有K个实际的簇，则从每个簇中选择一个初始点的概率是非常小的。u多次执行 可缓解，但效果不一定好u抽样并执行层次聚类来确定初始中心点u设置多于K个的初始中心点，然后从中选取。 选择K个分割效果最好的中心点u后处理

18、u二分K-平均聚类(Bisecting K-means) 不再对初始中心点敏感u前处理(Pre-processing) 对数据进行规范化 消除孤立点u后处理(Post-processing) 消除那些有可能是孤立点的规模小的簇 分割“松散”的簇, 即SSE高的簇 合并“紧凑”的簇，即距离近且SSE小的簇 可在聚类过程中使用这些手段u把所有点看成一个簇，用K-均值 聚类将其分成两个簇。u在结果中选（最大的簇，最大SSE的簇，或基于大小和SSE标准）进行二分。u重复以上步骤，直到得到K个簇为止。u当簇在如下方面不同时，K-平均聚类存在局限： 规模(Size) 密度(Density) 非球状(Non

19、-globular shapes)u当数据包含孤立点(Outlier)时， K-平均聚类的性能也不好。Original PointsK-means (3 Clusters)Original PointsK-means (3 Clusters)Original PointsK-means (2 Clusters)Original PointsK-means Clusters一种方案是使用尽可能多的簇，然后执行合并操作一种方案是使用尽可能多的簇，然后执行合并操作u聚类聚类u基于分割的聚类基于分割的聚类u层次聚类层次聚类 u产生一系列可组织为层次树的嵌套簇u可组织为系统树图(dendrogram)

20、可顺序合并或分割记录的类似于直方图的树。13254600.012345612345u无需事先指定簇的个数 可通过对系统树图指定的层进行分割的方式来得到合适的簇的数量。u可以和分类法结合起来 如生物学、图书分类法等。u层次聚类主要分两大类 凝聚聚类(Agglomerative): 初始时，把每个数据点都看成一个簇 每步合并最近的簇，直到得到一个簇为止 分裂聚类(Divisive): 初始时，把所有数据点都看成一簇 每步分割一个簇，直到每个簇只包含一个数据点（或分为k个簇）为止。u传统的层次聚类使用相似性或距离矩阵 每次合并或分割一个簇u基本算法直截了当Compute the

21、 proximity matrixLet each data point be a clusterRepeatMerge the two closest clustersUpdate the proximity matrixUntil only a single cluster remains u关键操作是计算两个簇的相关性不同的算法有不同的距离定义 u每个点都作为初始的簇p1p3p5p4p2p1p2p3p4p5. . .Proximity Matrixu经过若干合并步骤后, 初始数据点合并为了若干簇 C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix

22、u合并最近的簇C2和C5，并更新相关矩阵(proximity matrix)C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrixu合并之后如何更新相关矩阵?C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4Proximity Matrixu最小(MIN)u最大(MAX)u簇间的平均距离u中心点(Centroid)间的距离u其它由目标函数所决定的距离p1p3p5p4p2p1p2p3p4p5. . .Similarity?Proximity Matrixu最小(MIN)u最大(MAX)u簇间的平均距离u中心点(C

23、entroid)间的距离u其它由目标函数所决定的距离p1p3p5p4p2p1p2p3p4p5. . .Proximity Matrixu最小(MIN)u最大(MAX)u簇间的平均距离u中心点(Centroid)间的距离u其它由目标函数所决定的距离p1p3p5p4p2p1p2p3p4p5. . .Proximity Matrixu最小(MIN)u最大(MAX)u簇间的平均距离u中心点(Centroid)间的距离u其它由目标函数所决定的距离p1p3p5p4p2p1p2p3p4p5. . .Proximity Matrix u两个簇间的距离是由这两个簇中最近的两个最近的两个点所决定点所决定。Nest

24、ed ClustersDendrogram36254100.012345612345Original PointsTwo Clusters能处理非椭圆形的簇能处理非椭圆形的簇Original PointsTwo Clusters对噪声和孤立点敏感对噪声和孤立点敏感u两个簇间的距离由这两个簇中最不相似的点所决定12345612534Original PointsTwo Clusters对噪声和孤立点不是特别敏感对噪声和孤立点不是特别敏感Original PointsTwo Clusters有可能会割裂大的簇有可能会割裂大的簇倾向于球状的簇倾向于球状的簇u簇间的相似性由两个簇

25、中每对数据点的平均距离来决定u避免了最大距离偏向于大簇的问题。|Cluster|Cluster)p,pproximity()Cluster,Clusterproximity(jiClusterpClusterpjijijjiiNested ClustersDendrogram12345612534层次聚类方法u层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为： 凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。 分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越

26、小的簇，直到达到了某个终结条件。u层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。层次聚类优缺点u层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。u另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。u在不必要的情况下应该小心使用层次聚类方法。聚类举例例1：设有五位推销员，其教育水平和推销能力的评分如下，试用最短距离法将它们分类。在聚类前先标准化，用标准化后的数据进行聚类：2022-6-1177推销员推销员推销能力推销能力教育程度教育程度9.62.

27、49.60推销员推销员12345推销能力000.711教育程度0.330.6710.670规格化变换u样品间采用绝对值距离：u因此，G1与G2合并成新类G6。2022-6-1178ijijijdXXYY12034500.341.371.341.3301.0311.6700.631.3000.670GGDGGG12345GGGGG12000.330.670.34du计算G6与其他类的距离：u由此得，2022-6-1179631323min(,)min(1.37,1.03)1.03Ddd641424min(,)min(1.34,1)1Ddd651525min(,)min(1.33,1.67)1.3

28、3Ddd6314501.0311.3300.631.3000.670GGDGG6345GGGG12034500.341.371.341.3301.0311.6700.631.3000.670GGDGGG12345GGGGGuG4与G3合并成新类G7，它与其它各类的距离如下：u由此得，2022-6-1180676364min(,)min(1.03,1)1Ddd753545min(,)min(1.30,01.67)0.67Ddd6275011.3300.670GDGG675GGG6314501.0311.3300.631.3000.670GGDGG6345GGGGuG7与G5合并成新类G8，它与其它各类的距离如下：u由此得，u最后，将G6与G8合并为一类，由此结束聚类。2022-6-1181686765min(,)min(1,1.33)1Ddd638010GDG68GG6275011.3300.670GDGG675GGGu将聚类过程通过谱系图反映出来。2022-6-1182u谱系聚