第8章_聚类分析：基本概念和算法

聚类分析：基本概念和算法第8章聚类分析：基本概念和算法什么是聚类分析?聚类分析将数据划分成有意义或有用的组（簇）。聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：–高的簇内相似性–低的簇间相似性聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式；聚类的复杂性Howmanyclusters?FourClustersTwoClustersSixClusters不同的聚类类型划分聚类（PartitionalClustering）层次聚类（HierarchicalClustering）互斥（重叠）聚类（exclusiveclustering）非互斥聚类（non-exclusive）模糊聚类（fuzzyclustering）完全聚类（completeclustering）部分聚类（partialclustering）划分聚类（PartitionalClustering）OriginalPointsAPartitionalClustering划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。层次聚类（HierarchicalClustering）p4p1p3p2p4p1p3p2p4p1p2p3p4p1p2p3TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram层次聚类是嵌套簇的集族，组织成一棵树。互斥的、重叠的、模糊的互斥的（Exclusive）–每个对象都指派到单个簇.重叠的（overlapping）或非互斥的（non-exclusive）–聚类用来反映一个对象.同时属于多个组（类）这一事实。–例如：在大学里，一个人可能既是学生，又是雇员模糊聚类（Fuzzyclustering）–每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。部分的（Partial）–部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。完全的（complete）–完全聚类将每个对象指派到一个簇。不同的簇类型明显分离的基于原型的基于图的基于密度的概念簇簇类型:明显分离的（Well-Separated）每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。3well-separatedclusters簇类型:基于原型的每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。基于中心的（Center-Based）的簇：每个点到其簇中心的距离比到任何其他簇中心的距离更近。4center-basedclusters簇类型:基于图的如果数据用图表示，其中节点是对象，而边代表对象之间的联系。簇可以定义为连通分支（connectedcomponent）：互相连通但不与组外对象连通的对象组。基于近邻的（Contiguity-Based）：其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8contiguousclusters簇类型:基于密度的（Density-Based）簇是对象的稠密区域，被低密度的区域环绕。6density-basedclusters簇类型:概念簇（ConceptualClusters）可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。.2OverlappingCirclesK均值聚类基本K均值算法1.选择k个点作为初始的质心2.repeat3.将每个点指派到最近的质心，形成k个簇4.重新计算每个簇的质心5.until质心不发生变化数据对象之间的相异度EuclideanDistancenkkkyxyxd12)(),(明可夫斯基距离（MinkowskiDistance）MinkowskiDistancer=1.城市块(曼哈顿,出租车,L1范数)距离.r=2.欧氏距离（L2范数）r.上确界(Lmax或L范数)距离.rnkrkkyxyxd11)||(),(二元数据的相似性度量两个仅包含二元属性的对象之间的相似性度量也称相似系数两个对象的比较导致四个量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=匹配的个数/不涉及0-0匹配的属性个数=(f11)/(f01+f10+f11)余弦相似度Ifd1andd2aretwodocumentvectors,thencos(x,y)=(xy)/||x||||y||,Example:x=3205000200y=1000000102x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+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.245cos(d1,d2)=0.3150误差平方和（sumofthesquarederror，SSE）误差平方和它可以度量聚类的质量。误差平方和越小，意味着质心是簇中点的更好代表。可以证明：当紧邻函数是欧式距离（L2）时，使簇的SSE最小的质心是均值，即可以证明：当紧邻函数是曼哈顿距离（L1）时，使簇的L1绝对误差和（SAE）最小的质心是中位数21(,)ikiixCSSEdistcx1iixCicxm当紧邻函数是欧式距离时，可对SSE求导2121()()2()012()0iikkkkiixCkkkiixCkkkxCkkkkxCxckSSEcxcccxccxcxcxm选择初始的质心随机选择从层次聚类中提取K个簇，并用这些簇的质心作为初始质心随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点二分K均值二分k均值二分k均值算法是基本k均值算法的直接k个簇。它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇二分k均值算法初始化簇表，使之包含由所有的点组成的簇。Repeat从簇表中取出一个簇。fori=1to实验次数do使用基本k均值，二分选定的簇。endfor从二分实验中选择具有最小总sse的两个簇。将这两个簇添加到簇表中。Until簇表中包含k个簇。Kmeans的优点与缺点优点：算法简单适用于球形簇二分k均值等变种算法运行良好，不受初始化问题的影响。缺点：不能处理非球形簇、不同尺寸和不同密度的簇对离群点、噪声敏感K-means的局限性K-meanshasproblemswhenclustersareofdiffering–Sizes大小–Densities密度–Non-globularshapes非球形LimitationsofK-means:DifferingSizesOriginalPointsK-means(3Clusters)LimitationsofK-means:DifferingDensityOriginalPointsK-means(3Clusters)LimitationsofK-means:Non-globularShapesOriginalPointsK-means(2Clusters)K-means局限性的克服OriginalPointsK-meansClustersOnesolutionistousemanyclusters.Findpartsofclusters,butneedtoputtogether.OvercomingK-meansLimitationsOriginalPointsK-meansClustersOvercomingK-meansLimitationsOriginalPointsK-meansClusters层次聚类层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。按自底向上层次分解，则称为凝聚的层次聚类。按自顶向下层次分解，就称为分裂的层次聚类。13254600.050.10.150.212345612345凝聚的和分裂的层次聚类凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。凝聚的和分裂的层次聚类a,b,c,d,ec,d,ed,ea,bedcba第4步第3步第2步第1步第0步凝聚的（AGENS）第0步第1步第2步第3步第4步分裂的（DIANA）基本凝聚层次聚类方法凝聚层次聚类算法1.计算临近度矩阵2.让每个点作为一个cluster3.Repeat4.合并最近的两个类5.更新临近度矩阵，以反映新的簇与原来的簇之间的临近性6.Until仅剩下一个簇关键的操作是twoclusters的邻近度计算–不同的邻近度的定义区分了各种不同的凝聚层次技术起始步骤Startwithclustersofindividualpointsandaproximitymatrixp1p3p5p4p2p1p2p3p4p5......ProximityMatrix...p1p2p3p4p9p10p11p12中间步骤经过部分融合之后，我们得到一些clusterC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix...p1p2p3p4p9p10p11p12中间步骤我们希望合并两个最邻近的cluster(C2andC5)并更新临近度矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix...p1p2p3p4p9p10p11p12最终合并如何更新临近度矩阵？C1C4C2UC5C3???????C2UC5C1C1C3C4C2UC5C3C4ProximityMatrix...p1p2p3p4p9p10p11p12如何定义cluster间的相似性p1p3p5p4p2p1p2p3p4p5......Similarity?MINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunction–Ward’sMethodusessquarederrorProximityMatrixp1p3p5p4p2p1p2p3p4p5......ProximityMatrixMINMAXGroup