第8章+聚类分析：基本概念和算法课件

1、聚类分析：基本概念和算法第8章 聚类分析：基本概念和算法聚类分析：基本概念和算法第8章什么是聚类分析?聚类分析将数据划分成有意义或有用的组（簇）。聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。Inter-cluster distances are maximizedIntra-cluster distances are minimized什么是聚类分析?聚类分析将数据划分成有意义或有用的组（簇）。什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低的簇

2、间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式；什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类聚类的复杂性How many clusters?Four Clusters Two Clusters Six Clusters 聚类的复杂性How many clusters?Four C不同的聚类类型划分聚类（Partitional Clustering）层次聚类（Hierarchical Clustering）互斥（重叠）聚类（exclusive clustering）非互斥聚类（non-

3、exclusive）模糊聚类（fuzzy clustering）完全聚类（complete clustering）部分聚类（partial clustering）不同的聚类类型划分聚类（Partitional Cluste划分聚类（Partitional Clustering）Original PointsA Partitional Clustering划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。划分聚类（Partitional Clustering）Or层次聚类（Hierarchical Clustering）Traditional Hierarchical

4、ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram层次聚类是嵌套簇的集族，组织成一棵树。层次聚类（Hierarchical Clustering）T互斥的、重叠的、模糊的互斥的（Exclusive）每个对象都指派到单个簇.重叠的（overlapping）或非互斥的（non-exclusive）聚类用来反映一个对象.同时属于多个组（类）这一事实。例如：在大学里，一个人可能既是学生，又是雇员模糊聚类（Fuzzy clustering ）每个对象以一个0（绝

5、对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。部分的（Partial） 部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。完全的（complete）完全聚类将每个对象指派到一个簇。互斥的、重叠的、模糊的互斥的（Exclusive）不同的簇类型明显分离的基于原型的基于图的基于密度的概念簇不同的簇类型明显分离的簇类型: 明显分离的（Well-Separated）每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。3 well-separated clusters簇类型: 明显分离的（Well-Separated）每个点到簇类型:基于原

6、型的每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。基于中心的（ Center-Based）的簇：每个点到其簇中心的距离比到任何其他簇中心的距离更近。4 center-based clusters簇类型:基于原型的每个对象到定义该簇的原型的距离比到其他簇的簇类型:基于图的如果数据用图表示，其中节点是对象，而边代表对象之间的联系。簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通的对象组。基于近邻的（ Contiguity-

7、Based）：其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8 contiguous clusters簇类型:基于图的如果数据用图表示，其中节点是对象，而边代表对簇类型: 基于密度的（Density-Based）簇是对象的稠密区域，被低密度的区域环绕。6 density-based clusters簇类型: 基于密度的（Density-Based）簇是对象的簇类型: 概念簇（Conceptual Clusters）可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别

8、出来。. 2 Overlapping Circles簇类型: 概念簇（Conceptual Clusters）可K均值聚类K均值聚类基本K均值算法1.选择k个点作为初始的质心2.repeat3. 将每个点指派到最近的质心，形成k个簇4. 重新计算每个簇的质心5.until 质心不发生变化基本K均值算法1.选择k个点作为初始的质心数据对象之间的相异度Euclidean Distance 数据对象之间的相异度Euclidean Distance明可夫斯基距离（Minkowski Distance）Minkowski Distancer = 1. 城市块 (曼哈顿, 出租车, L1 范数) 距离.

9、r = 2. 欧氏距离（ L2 范数）r . 上确界 (Lmax或L 范数) 距离. 明可夫斯基距离（Minkowski Distance）Min二元数据的相似性度量两个仅包含二元属性的对象之间的相似性度量也称相似系数两个对象的比较导致四个量f00 = x取0并且y取0的属性个数f01 = x取0并且y取1的属性个数f10 = x取1并且y取0的属性个数f11 = x取1并且y取1的属性个数简单匹配系数SMC = 值匹配的属性个数 / 属性个数 = (f11 +f00) / (f01 + f10 + f11 + f00)Jaccard(雅卡尔 ) 系数 （非对称二元属性）J = 匹配的个数 /

10、 不涉及0-0匹配的属性个数= (f11) / (f01 + f10 +f11) 二元数据的相似性度量两个仅包含二元属性的对象之间的相似性度量余弦相似度 If d1 and d2 are two document vectors, then cos( x, y ) = (x y) / |x| |y| , Example: x = 3 2 0 5 0 0 0 2 0 0 y = 1 0 0 0 0 0 0 1 0 2 x y= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5 |x| = (3*3+2*2+0*0+5*5+

11、0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481 |y| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245 cos( d1, d2 ) = 0.3150余弦相似度 If d1 and d2 are two doc误差平方和（sum of the squared error，SSE）误差平方和它可以度量聚类的质量。误差平方和越小，意味着质心是簇中点的更好代表。可以证明：当紧邻函数是欧式距离（L2）时，使簇的SSE最小的质心是均值，即可以证明：当紧邻函数是曼哈顿距离（L1）

12、时，使簇的L1绝对误差和（SAE）最小的质心是中位数误差平方和（sum of the squared error当紧邻函数是欧式距离时，可对SSE求导当紧邻函数是欧式距离时，可对SSE求导选择初始的质心随机选择从层次聚类中提取K个簇，并用这些簇的质心作为初始质心随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点二分K均值选择初始的质心随机选择第8章+聚类分析：基本概念和算法课件第8章+聚类分析：基本概念和算法课件第8章+聚类分析：基本概念和算法课件二分k均值二分k均值算法是基本k均值算法的直接k个簇。它将所有点的集合分裂成两个簇，从这

13、些簇中选取一个继续分裂，如此下去，直到产生k个簇二分k均值二分k均值算法是基本k均值算法的直接k个簇。二分k均值算法初始化簇表，使之包含由所有的点组成的簇。Repeat 从簇表中取出一个簇。 for i=1 to 实验次数 do 使用基本k均值，二分选定的簇。 end for 从二分实验中选择具有最小总sse的两个簇。 将这两个簇添加到簇表中。Until 簇表中包含k个簇。二分k均值算法初始化簇表，使之包含由所有的点组成的簇。K means 的优点与缺点优点：算法简单适用于球形簇二分k均值等变种算法运行良好，不受初始化问题的影响。缺点：不能处理非球形簇、不同尺寸和不同密度的簇对离群点、噪声敏感

14、K means 的优点与缺点优点：K-means 的局限性K-means has problems when clusters are of differing Sizes大小Densities密度Non-globular shapes非球形K-means 的局限性K-means has probleLimitations of K-means: Differing SizesOriginal PointsK-means (3 Clusters)Limitations of K-means: DifferLimitations of K-means: Differing DensityOrig

15、inal PointsK-means (3 Clusters)Limitations of K-means: DifferLimitations of K-means: Non-globular ShapesOriginal PointsK-means (2 Clusters)Limitations of K-means: Non-glK-means 局限性的克服Original PointsK-means ClustersOne solution is to use many clusters.Find parts of clusters, but need to put together.

16、K-means 局限性的克服Original PointsOvercoming K-means LimitationsOriginal PointsK-means ClustersOvercoming K-means LimitationsOvercoming K-means LimitationsOriginal PointsK-means ClustersOvercoming K-means Limitations层次聚类层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。 按自底向上层次分解，则称为凝聚的层次聚类。 按自顶向下层次分解，就称为分裂的层次聚类。 层次聚类层次聚类按

17、数据分层建立簇，形成一棵以簇为节点的树，称凝聚的和分裂的层次聚类 凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。 分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。凝聚的和分裂的层次聚类 凝聚的层次聚类采用自底向上的策略，开凝聚的和分裂的层次聚类 凝聚的和分裂的层次聚类 基本凝聚层次聚类方法凝聚层次聚类算法计算临近度矩阵让每个点作为一个clusterRepeat合并最

18、近的两个类更新临近度矩阵，以反映新的簇与原来的簇之间的临近性Until 仅剩下一个簇 关键的操作是two clusters的邻近度计算不同的邻近度的定义区分了各种不同的凝聚层次技术基本凝聚层次聚类方法起始步骤 Start with clusters of individual points and a proximity matrixp1p3p5p4p2p1p2p3p4p5. . .Proximity Matrix起始步骤 Start with clusters of in中间步骤经过部分融合之后 ，我们得到一些clusterC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Prox

19、imity Matrix中间步骤经过部分融合之后 ，我们得到一些clusterC1C中间步骤我们希望合并两个最邻近的cluster (C2 and C5) 并更新临近度矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix中间步骤我们希望合并两个最邻近的cluster (C2 an最终合并如何更新临近度矩阵？ C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4Proximity Matrix最终合并如何更新临近度矩阵？ C1C4C2 U C5C3? 如何定义cluster间的相似性 p1p3p5p4p2p1

20、p2p3p4p5. . .Similarity?MINMAXGroup AverageDistance Between CentroidsOther methods driven by an objective functionWards Method uses squared errorProximity Matrix如何定义cluster间的相似性 p1p3p5p4p2p1p p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between CentroidsOther methods driven b

21、y an objective functionWards Method uses squared error如何定义cluster间的相似性 p1p3p5p4p2p1p2p3p4p5. . .Pro p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between CentroidsOther methods driven by an objective functionWards Method uses squared error如何定义cluster间的相似性 p1p3p5p4p2p1p2p3p4p5.

22、 . .Pro p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between CentroidsOther methods driven by an objective functionWards Method uses squared error如何定义cluster间的相似性 p1p3p5p4p2p1p2p3p4p5. . .Pro p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between Centroi

23、ds其它方法Wards Method 利用平方误差增量如何定义cluster间的相似性 p1p3p5p4p2p1p2p3p4p5. . .ProMIN or 单链 两个cluster的相似性定义为基于这两个cluster中最大相似度（最近距离）由一对最近邻点决定12345MIN or 单链 两个cluster的相似性定义为基于这两分层聚类: MIN单链聚类单链树状图12345612345分层聚类: MIN单链聚类单链树状图12345612345单链的优势Original PointsTwo Clusters 单链技术可以处理非椭圆形状的簇单链的优势Original PointsTwo Clus

24、te单链的局限性Original PointsTwo Clusters但对噪音和离群点很敏感单链的局限性Original PointsTwo ClustCluster Similarity: MAX or 全链两个cluster的相似性定义为基于这两个cluster中最小相似度（最大距离）12345Cluster Similarity: MAX or 全链两分层聚类: MAX 或全链全链聚类全链树状图12345612534分层聚类: MAX 或全链全链聚类全链树状图12345612Original PointsTwo Clusters对噪音和离群不敏感全链的优势Original PointsT

25、wo Clusters对噪音Original PointsTwo Clusters可能使大的簇破裂偏好球型簇全链的局限性Original PointsTwo Clusters可能使Cluster Similarity: 组平均两个簇的邻近度定义为不同的所有点对的平均逐对邻近度，是一种单链与全链的折中算法.12345Cluster Similarity: 组平均两个簇的邻近度分层聚类: Group AverageNested ClustersDendrogram12345612534分层聚类: Group AverageNested Clus优势对噪音和极端值影响小局限偏好球型簇分层聚类: Gr

26、oup Average分层聚类: Group Average其它近似度Ward：两个簇合并时导致的误差平方和的增量质心：簇质心之间的距离Lance-Willianms公式其它近似度Ward：两个簇合并时导致的误差平方和的增量Cluster Similarity: Wards Method两个簇的邻近度定义为两个簇合并时导致的平方误差增量当邻近度取它们之间的平方时，ward与组平均类似对噪音和极端值影响小偏好球型簇Cluster Similarity: Wards MetHierarchical Clustering: ComparisonGroup AverageWards Method123

27、45612534MINMAX123456125341234561253412345612345Hierarchical Clustering: Compa优点与缺点优点：某些应用领域需要层次结构。如：系统发生树，基因芯片有些研究表明，这种算法能够产生较高质量的聚类缺点：计算量、存储量大对噪声、高维数据敏感优点与缺点优点：DBSCAN算法DBSCAN 是一种简单、有效的基于密度的聚类算法.基于中心的DBSCAN在基于中心的方法中，数据集中特定点的密度通过对该点Eps半径之内的点计数（包括点本身）来估计该方法实现简单，但是点的密度依赖于指定的半径。例如，如果半径足够大，则所有点的密度都等于数据集中

28、的点数m。类似地，如果半径太小，则所有点的密度都是1。DBSCAN算法DBSCAN 是一种简单、有效的基于密度的聚第8章+聚类分析：基本概念和算法课件DBSCAN: 核心点, 边界点, 噪声点DBSCAN: 核心点, 边界点, 噪声点DBSCAN 算法将所有点标记为核心点、边界点或噪声点删除噪声点为距离在Eps之内的所有核心点之间赋予一条边。每组连通的核心点形成一个簇。将每个边界点指派到一个与之关联的核心点的簇中。DBSCAN 算法将所有点标记为核心点、边界点或噪声点DBSCAN: 选择 EPS and MinPts基本方法是观察点到它的k个最近邻的距离（称为k-距离）的特性。计算所有点的k-

29、距离，以递增次序将它们排序，然后绘制排序后的值，则我们预期会看到k-距离的急剧变化，对应于合适的Eps值。如果我们选取该距离为Eps参数，而取k的值为MinPts参数。DBSCAN: 选择 EPS and MinPts基本方法是Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4Original PointsPoint types: co变密度的簇如果簇的密度变化很大，DBSCAN可能会有问题。考虑图8-24，它包含4个埋藏在噪声中的簇。簇和噪声区域的密度由它们的明暗度指出。较密的两个簇A和B周围的噪声的密

30、度与簇C和D的密度相同。如果Eps域值足够低，使得DBSCAN可以发现簇C和D，则A、B和包围它们的点将变成单个簇。如果Eps域值足够高，使得DBSCAN可以发现A和B，并且将包围它们的点标记为噪声，则C、D和包围它们的点也将标记为噪声。变密度的簇如果簇的密度变化很大，DBSCAN可能会有问题。考第8章+聚类分析：基本概念和算法课件Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) Varying densities High-dimensional dataOriginal Points(MinPts=4, Eps=DBSCAN

31、的优点与缺点因为DBSCAN使用簇的基于密度的定义，因此它是相对抗噪声的，并且能够处理任意形状和大小的簇。这样，DBSCAN可以发现使用K均值不能发现的许多簇。然而，正如前面所指出的，当簇的密度变化太大时，DBSCAN就会有麻烦。对于高维数据，它也有问题，因为对于这样的数据，密度定义更困难。最后，当近邻计算需要计算所有的点对近邻度时，DBSCAN可能是开销很大的。DBSCAN的优点与缺点因为DBSCAN使用簇的基于密度的定簇评估 如何评估聚类结果的好坏？为什么要评估聚类?To avoid finding patterns in noiseTo compare clustering algorithmsTo compare two sets of clustersTo compare two clusters簇评估 随机数据的聚类结果Random PointsK-meansDBSCANComplete Link随机数据的聚类结果Random PointsK-meansDMeasuring Cluster Validity Via CorrelationCorrelation of incidence and proximity matrices for the K-means clusterings of the following two data sets. Corr = -0