《第8章聚类分析基本概念和算法》由会员分享，可在线阅读，更多相关《第8章聚类分析基本概念和算法（84页珍藏版）》请在金锄头文库上搜索。
1、聚类分析：基本概念和算法聚类分析：基本概念和算法第第8章章 聚类分析：基本概念和算法聚类分析：基本概念和算法什么是聚类分析什么是聚类分析?l聚类分析将数据划分成有意义或有用的组（簇）。l聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。Inter-cluster distances are maximizedIntra-cluster distances are minimized什么是一个好的聚类方法什么是一个好的聚类方法?l一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低
2、的簇间相似性 l聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；l聚类方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式；聚类的复杂性聚类的复杂性How many clusters?Four Clusters Two Clusters Six Clusters 不同的聚类类型不同的聚类类型l划分聚类（Partitional Clustering）l层次聚类（Hierarchical Clustering）l互斥（重叠）聚类（exclusive clustering）l非互斥聚类（non-exclusive）l模糊聚类（fuzzy clustering）l完全聚类（
3、complete clustering）l部分聚类（partial clustering）划分聚类（划分聚类（Partitional Clustering）Original PointsA Partitional Clusteringl划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。层次聚类（层次聚类（Hierarchical Clustering）Traditional Hierarchical ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditiona
4、l Dendrograml层次聚类是嵌套簇的集族，组织成一棵树。互斥的、重叠的、模糊的互斥的、重叠的、模糊的l互斥的（Exclusive）每个对象都指派到单个簇.l重叠的（overlapping）或非互斥的（non-exclusive）聚类用来反映一个对象.同时属于多个组（类）这一事实。例如：在大学里，一个人可能既是学生，又是雇员l模糊聚类（Fuzzy clustering ）每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。l部分的（Partial） 部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。l完全的（com
5、plete）完全聚类将每个对象指派到一个簇。不同的簇类型不同的簇类型l明显分离的l基于原型的l基于图的l基于密度的l概念簇簇类型簇类型: 明显分离的（明显分离的（Well-Separated）l每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。3 well-separated clusters簇类型簇类型:基于原型的基于原型的l每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。l基于中心的（ Center-Based）的簇：每个点到其簇中心的距离比到任何其他
6、簇中心的距离更近。4 center-based clusters簇类型簇类型:基于图的基于图的l如果数据用图表示，其中节点是对象，而边代表对象之间的联系。l簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通的对象组。l基于近邻的（ Contiguity-Based）：其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8 contiguous clusters簇类型簇类型: 基于密度的（基于密度的（Density-Based）l簇是对象的稠密区域，被低密度的区域环绕。6 density-
7、based clusters簇类型簇类型: 概念簇（概念簇（Conceptual Clusters）l可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。. 2 Overlapping CirclesK均值聚类均值聚类基本基本K均值算法均值算法l1.选择k个点作为初始的质心l2.repeatl3. 将每个点指派到最近的质心，形成k个簇l4. 重新计算每个簇的质心l5.until 质心不发生变化数据对象之间的相异度数据对象之间的相异度lEuclidean Distance 明可夫斯基距离（明可夫斯基距离（Minkowski Dista
8、nce）lMinkowski Distancelr = 1. 城市块 (曼哈顿, 出租车, L1 范数) 距离. lr = 2. 欧氏距离（ L2 范数）lr . 上确界 (Lmax或L 范数) 距离. 二元数据的相似性度量二元数据的相似性度量l两个仅包含二元属性的对象之间的相似性度量也称相似系数l两个对象的比较导致四个量f00 = x取0并且y取0的属性个数f01 = x取0并且y取1的属性个数f10 = x取1并且y取0的属性个数f11 = x取1并且y取1的属性个数l简单匹配系数SMC = 值匹配的属性个数 / 属性个数 = (f11 +f00) / (f01 + f10 + f11 +
9、 f00)lJaccard(雅卡尔 ) 系数 （非对称二元属性）J = 匹配的个数 / 不涉及0-0匹配的属性个数= (f11) / (f01 + f10 +f11) 余弦相似度余弦相似度l If d1 and d2 are two document vectors, then cos( x, y ) = (x y) / |x| |y| , l 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
10、| = (3*3+2*2+0*0+5*5+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误差平方和（误差平方和（sum of the squared error，SSE）l误差平方和l它可以度量聚类的质量。误差平方和越小，意味着质心是簇中点的更好代表。l可以证明：当紧邻函数是欧式距离（L2）时，使簇的SSE最小的质心是均值，即l可以证明：当紧邻函数是曼哈顿距离（L1
11、）时，使簇的L1绝对误差和（SAE）最小的质心是中位数l当紧邻函数是欧式距离时，可对SSE求导选择初始的质心选择初始的质心l随机选择l从层次聚类中提取K个簇，并用这些簇的质心作为初始质心l随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点l二分K均值二分二分k均值均值l二分k均值算法是基本k均值算法的直接k个簇。l它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇二分二分k均值算法均值算法l初始化簇表，使之包含由所有的点组成的簇。lRepeatl 从簇表中取出一个簇。l for i=1 to 实验次数
12、dol 使用基本k均值，二分选定的簇。l end forl 从二分实验中选择具有最小总sse的两个簇。l 将这两个簇添加到簇表中。lUntil 簇表中包含k个簇。K means 的优点与缺点的优点与缺点l优点：l算法简单l适用于球形簇l二分k均值等变种算法运行良好，不受初始化问题的影响。l缺点：l不能处理非球形簇、不同尺寸和不同密度的簇l对离群点、噪声敏感K-means 的局限性的局限性lK-means has problems when clusters are of differing Sizes大小Densities密度Non-globular shapes非球形Limitations
13、of K-means: Differing SizesOriginal PointsK-means (3 Clusters)Limitations of K-means: Differing DensityOriginal PointsK-means (3 Clusters)Limitations of K-means: Non-globular ShapesOriginal PointsK-means (2 Clusters)K-means 局限性的克服局限性的克服Original PointsK-means ClustersOne solution is to use many clust
14、ers.Find parts of clusters, but need to put together.Overcoming K-means LimitationsOriginal PointsK-means ClustersOvercoming K-means LimitationsOriginal PointsK-means Clusters层次聚类层次聚类l层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。 l按自底向上层次分解，则称为凝聚的层次聚类。 l按自顶向下层次分解，就称为分裂的层次聚类。 凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 l凝聚的层次聚类采用自底向上的
15、策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。 l分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。l传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 基本凝聚层次聚类方法基本凝聚层次聚类方法l凝聚层次聚类算法1.计算临近度矩阵2.让每个点作为一个cluster3.Repeat4.合并最近的两个类5.更新临近度矩阵，以反映新的簇与原来的簇之间的临近性6.Until 仅剩下一个簇 l关键的操作是two
16、 clusters的邻近度计算不同的邻近度的定义区分了各种不同的凝聚层次技术起始步骤起始步骤 lStart with clusters of individual points and a proximity matrixp1p3p5p4p2p1p2p3p4p5. . .Proximity Matrix中间步骤中间步骤l经过部分融合之后 ，我们得到一些clusterC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix中间步骤中间步骤l我们希望合并两个最邻近的cluster (C2 and C5) 并更新临近度矩阵C1C4C2C5C3C2C1C1C3C5C
17、4C2C3C4C5Proximity Matrix最终合并最终合并l如何更新临近度矩阵？ C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4Proximity Matrix如何定义如何定义cluster间的相似性间的相似性 p1p3p5p4p2p1p2p3p4p5. . .Similarity?lMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared errorPro
18、ximity Matrix p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOt
19、her methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性 p1p3p5p
20、4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between Centroidsl其它方法Wards Method 利用平方误差增量 如何定义如何定义cluster间的相似性间的相似性MIN or 单链单链 l两个cluster的相似性定义为基于这两个cluster中最大相似度（最近距离）l由一对最近邻点决定12345分层聚类分层聚类: MIN单链聚类单链聚类单链树状图单链树状图12345612345单链的优势单链的优势Original PointsTwo Clusters 单链技术可以处理非椭圆形状的簇单链
21、技术可以处理非椭圆形状的簇单链的局限性单链的局限性Original PointsTwo Clusters但对噪音和离群点很敏感但对噪音和离群点很敏感Cluster Similarity: MAX or 全链全链两个cluster的相似性定义为基于这两个cluster中最小相似度（最大距离）12345分层聚类分层聚类: MAX 或全链或全链全链聚类全链聚类全链树状图全链树状图12345612534Original PointsTwo Clusters对噪音和离群不敏感对噪音和离群不敏感全链的优势全链的优势Original PointsTwo Clusters可能使大的簇破裂可能使大的簇破裂偏好球
22、型簇偏好球型簇全链的局限性全链的局限性Cluster Similarity: 组平均组平均l两个簇的邻近度定义为不同的所有点对的平均逐对邻近度，是一种单链与全链的折中算法.12345分层聚类分层聚类: Group AverageNested ClustersDendrogram12345612534l优势对噪音和极端值影响小l局限偏好球型簇分层聚类分层聚类: Group Average其它近似度其它近似度lWard：两个簇合并时导致的误差平方和的增量l质心：簇质心之间的距离lLance-Willianms公式Cluster Similarity: Wards Methodl两个簇的邻近度定义为
23、两个簇合并时导致的平方误差增量当邻近度取它们之间的平方时，ward与组平均类似对噪音和极端值影响小l偏好球型簇Hierarchical Clustering: ComparisonGroup AverageWards Method12345612534MINMAX123456125341234561253412345612345优点与缺点优点与缺点l优点：l某些应用领域需要层次结构。如：系统发生树，基因芯片l有些研究表明，这种算法能够产生较高质量的聚类l缺点：l计算量、存储量大l对噪声、高维数据敏感DBSCAN算法算法lDBSCAN 是一种简单、有效的基于密度的聚类算法.l基于中心的DBSCA
24、Nl在基于中心的方法中，数据集中特定点的密度通过对该点Eps半径之内的点计数（包括点本身）来估计l该方法实现简单，但是点的密度依赖于指定的半径。例如，如果半径足够大，则所有点的密度都等于数据集中的点数m。类似地，如果半径太小，则所有点的密度都是1。DBSCAN: 核心点核心点, 边界点边界点, 噪声点噪声点DBSCAN 算法算法l将所有点标记为核心点、边界点或噪声点l删除噪声点l为距离在Eps之内的所有核心点之间赋予一条边。l每组连通的核心点形成一个簇。l将每个边界点指派到一个与之关联的核心点的簇中。DBSCAN: 选择选择 EPS and MinPtsl基本方法是观察点到它的k个最近邻的距离
25、（称为k-距离）的特性。l计算所有点的k-距离，以递增次序将它们排序，然后绘制排序后的值，则我们预期会看到k-距离的急剧变化，对应于合适的Eps值。l如果我们选取该距离为Eps参数，而取k的值为MinPts参数。Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4变密度的簇变密度的簇l如果簇的密度变化很大，DBSCAN可能会有问题。考虑图8-24，它包含4个埋藏在噪声中的簇。l簇和噪声区域的密度由它们的明暗度指出。较密的两个簇A和B周围的噪声的密度与簇C和D的密度相同。l如果Eps域值足够低，使得DBSCA
26、N可以发现簇C和D，则A、B和包围它们的点将变成单个簇。l如果Eps域值足够高，使得DBSCAN可以发现A和B，并且将包围它们的点标记为噪声，则C、D和包围它们的点也将标记为噪声。Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) Varying densities High-dimensional dataDBSCAN的优点与缺点的优点与缺点l因为DBSCAN使用簇的基于密度的定义，因此它是相对抗噪声的，并且能够处理任意形状和大小的簇。这样，DBSCAN可以发现使用K均值不能发现的许多簇。l然而，正如前面所指出的，当簇的密度变化
27、太大时，DBSCAN就会有麻烦。对于高维数据，它也有问题，因为对于这样的数据，密度定义更困难。最后，当近邻计算需要计算所有的点对近邻度时，DBSCAN可能是开销很大的。簇评估簇评估 l如何评估聚类结果的好坏？l为什么要评估聚类?To avoid finding patterns in noiseTo compare clustering algorithmsTo compare two sets of clustersTo compare two clusters随机数据的聚类结果随机数据的聚类结果Random PointsK-meansDBSCANComplete LinkMeasuring
28、 Cluster Validity Via CorrelationlCorrelation of incidence and proximity matrices for the K-means clusterings of the following two data sets. Corr = -0.9235Corr = -0.5810lOrder the similarity matrix with respect to cluster labels and inspect visually. Using Similarity Matrix for Cluster ValidationUs
29、ing Similarity Matrix for Cluster ValidationClusters in random data are not so crispDBSCANUsing Similarity Matrix for Cluster ValidationlClusters in random data are not so crispK-meansUsing Similarity Matrix for Cluster ValidationlClusters in random data are not so crispComplete LinkUsing Similarity
30、 Matrix for Cluster ValidationDBSCANlSSE is good for comparing two clusterings or two clusters (average SSE).lCan also be used to estimate the number of clustersInternal Measures: SSElExampleCompare SSE of 0.005 against three clusters in random dataHistogram shows SSE of three clusters in 500 sets of random data points of size 100 distributed over the range 0.2 0.8 for x and y values对于对于 SSE的显著性的显著性
