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

聚类分析：基本概念和算法,第6章聚类分析：基本概念和算法,什么是聚类分析?,聚类分析将数据划分成有意义或有用的组（簇）。聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。,什么是一个好的聚类方法?,一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式；,聚类的复杂性,不同的聚类类型,划分聚类（PartitionalClustering）层次聚类（HierarchicalClustering）互斥（重叠）聚类（exclusiveclustering）非互斥聚类（non-exclusive）模糊聚类（fuzzyclustering）完全聚类（completeclustering）部分聚类（partialclustering）,划分聚类（PartitionalClustering）,OriginalPoints,APartitionalClustering,划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。,层次聚类（HierarchicalClustering）,TraditionalHierarchicalClustering,Non-traditionalHierarchicalClustering,Non-traditionalDendrogram,TraditionalDendrogram,层次聚类是嵌套簇的集族，组织成一棵树。,互斥的、重叠的、模糊的,互斥的（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）,可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。.,2OverlappingCircles,K均值聚类,基本K均值算法,1.选择k个点作为初始的质心2.repeat3.将每个点指派到最近的质心，形成k个簇4.重新计算每个簇的质心5.until质心不发生变化,数据对象之间的相异度,EuclideanDistance,明可夫斯基距离（MinkowskiDistance）,MinkowskiDistancer=1.城市块(曼哈顿,出租车,L1范数)距离.r=2.欧氏距离（L2范数）r.上确界(Lmax或L范数)距离.,二元数据的相似性度量,两个仅包含二元属性的对象之间的相似性度量也称相似系数两个对象的比较导致四个量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)=(xy)/|x|y|,Example:x=3205000200y=1000000102xy=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）最小的质心是中位数,当紧邻函数是欧式距离时，可对SSE求导,选择初始的质心,随机选择从层次聚类中提取K个簇，并用这些簇的质心作为初始质心随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点二分K均值,二分k均值,二分k均值算法是基本k均值算法的直接k个簇。它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇,二分k均值算法,初始化簇表，使之包含由所有的点组成的簇。Repeat从簇表中取出一个簇。fori=1to实验次数do使用基本k均值，二分选定的簇。endfor从二分实验中选择具有最小总sse的两个簇。将这两个簇添加到簇表中。Until簇表中包含k个簇。,Kmeans的优点与缺点,优点：算法简单适用于球形簇二分k均值等变种算法运行良好，不受初始化问题的影响。缺点：不能处理非球形簇、不同尺寸和不同密度的簇对离群点、噪声敏感,K-means的局限性,K-meanshasproblemswhenclustersareofdifferingSizes大小Densities密度Non-globularshapes非球形,LimitationsofK-means:DifferingSizes,OriginalPoints,K-means(3Clusters),LimitationsofK-means:DifferingDensity,OriginalPoints,K-means(3Clusters),LimitationsofK-means:Non-globularShapes,OriginalPoints,K-means(2Clusters),K-means局限性的克服,OriginalPointsK-meansClusters,Onesolutionistousemanyclusters.Findpartsofclusters,butneedtoputtogether.,OvercomingK-meansLimitations,OriginalPointsK-meansClusters,OvercomingK-meansLimitations,OriginalPointsK-meansClusters,层次聚类,层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。按自底向上层次分解，则称为凝聚的层次聚类。按自顶向下层次分解，就称为分裂的层次聚类。,凝聚的和分裂的层次聚类,凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。,凝聚的和分裂的层次聚类,基本凝聚层次聚类方法,凝聚层次聚类算法计算临近度矩阵让每个点作为一个clusterRepeat合并最近的两个类更新临近度矩阵，以反映新的簇与原来的簇之间的临近性Until仅剩下一个簇关键的操作是twoclusters的邻近度计算不同的邻近度的定义区分了各种不同的凝聚层次技术,起始步骤,Startwithclustersofindividualpointsandaproximitymatrix,ProximityMatrix,中间步骤,经过部分融合之后，我们得到一些cluster,C1,C4,C2,C5,C3,ProximityMatrix,中间步骤,我们希望合并两个最邻近的cluster(C2andC5)并更新临近度矩阵,C1,C4,C2,C5,C3,ProximityMatrix,最终合并,如何更新临近度矩阵？,C1,C4,C2UC5,C3,?,?,?,?,C2UC5,C1,C1,C3,C4,C2UC5,C3,C4,ProximityMatrix,如何定义cluster间的相似性,Similarity?,MINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWardsMethodusessquarederror,ProximityMatrix,ProximityMatrix,MINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWardsMethodusessquarederror,如何定义cluster间的相似性,ProximityMatrix,MINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWardsMethodusessquarederror,如何定义cluster间的相似性,ProximityMatrix,MINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWardsMethodusessquarederror,如何定义cluster间的相似性,ProximityMatrix,MINMAXGroupAverageDistanceBetweenCentroids其它方法WardsMethod利用平方误差增量,如何定义cluster间的相似性,MINor单链,两个cluster的相似性定义为基于这两个cluster中最大相似度（最近距离）由一对最近邻点决定,分层聚类:MIN,单链聚类,单链树状图,单链的优势,OriginalPoints,TwoClusters,单链技术可以处理非椭圆形状的簇,单链的局限性,OriginalPoints,TwoClusters,但对噪音和离群点很敏感,ClusterSimilarity:MAXor全链,两个cluster的相似性定义为基于这两个cluster中最小相似度（最大距离）,分层聚类:MAX或全链,全链聚类,全链树状图,OriginalPoints,TwoClusters,对噪音和离群不敏感,全链的优势,OriginalPoints,TwoClusters,可能使大的簇破裂偏好球型簇,全链的局限性,ClusterSimilarity:组平均,两个簇的邻近度定义为不同的所有点对的平均逐对邻近度，是一种单链与全链的折中算法.,分层聚类:GroupAverage,NestedClusters,Dendrogram,优势对噪音和极端值影响小局限偏好球型簇,分层聚类:GroupAverage,其它近似度,Ward：两个簇合并时导致的误差平方和的增量质心：簇质心之间的距离Lance-Willianms公式,ClusterSimilarity:WardsMethod,两个簇的邻近度定义为两个簇合并时导致的平方误差增量当邻近度取它们之间的平方时，ward与组平均类似对噪音和极端值影响小偏好球型簇,HierarchicalClustering:Comparison,GroupAverage,WardsMethod,MIN,MAX,优点与缺点,优点：某些应用领域需要层次结构。如：系统发生树，基因芯片有些研究表明，这种算法能够产生较高质量的聚类缺点：计算量、存储量大对噪声、高维数据敏感,DBSCAN算法,DBSCAN是一种简单、有效的基于密度的聚类算法.基于中心的DBSCAN在基于中心的方法中，数据集中特定点的密度通过对该点Eps半径之内的点计数（包括点本身）来估计该方法实现简单，但是点的密度依赖于指定的半径。例如，如果半径足够大，则所有点的密度都等于数据集中的点数m。类似地，如果半径太小，则所有点的密度都是1。,DBSCAN:核心点,边界点,噪声点,DBSCAN算法,将所有点标记为核心点、边界点或噪声点删除噪声点为距离在Eps之内的所有核心点之间赋予一条边。每组连通的核心点形成一个簇。将每个边界点指派到一个与之关联的核心点的簇中。,DBSCAN:选择EPSandMinPts,基本方法是观察点到它的k个最近邻的距离（称为k-距离）的特性。计算所有点的k-距离，以递增次序将它们排序，然后绘制排序后的值，则我们预期会看到k-距离的急剧变化，对应于合适的Eps值。如果我们选取该距离为Eps参数，而取k的值为MinPts参数。,OriginalPoints,Pointtypes:core,borderandnoise,Eps=10,MinPts=4,变密度的簇,如果簇的密度变化很大，DBSCAN可能会有问题。考虑图8-24，它包含4个埋藏在噪声中的簇。簇和噪声区域的密度由它们的明暗度指出。较密的两个簇A和B周围的噪声的密度与簇C和D的密度相同。如果Eps域值足够低，使得DBSCAN可以发现簇C和D，则A、B和包围它们的点将变成单个簇。如果Eps域值足够高，使得DBSCAN可以发现A和B，并且将包围它们的点标记为噪声，则C、D和包围它们的点也将标记为噪声。,OriginalPoints,(MinPts=4,Eps=9.75).,(MinPts=4,Eps=9.92),VaryingdensitiesHigh-dimensionaldata,DBSCAN的优点与缺点,因为DBSCAN使用簇的基于密度的定义，因此它是相对抗噪声的，并且能够处理任意形状和大小的簇。这样，DBSCAN可以发现使用K均值不能发现的许多簇。然而，正如前面所指出的，当簇的密度变化太大时，DBSCAN就会有麻烦。对于高维数据，它也有问题，因为对于这样的数据，密度定义更困难。最后，当近邻计算需要计算所有的点对近邻度时，DBSCAN可能是开销很大的。,簇评估,如何评估聚类结果的好坏？为什么要评估聚类?ToavoidfindingpatternsinnoiseTocompareclusteringalgorithmsTocomparetwosetsofclustersTocomparetwoclusters,随机数据的聚类结果,RandomPoints,K-means,DBSCAN,CompleteLink,MeasuringClusterValidityViaCorrelation,CorrelationofincidenceandproximitymatricesfortheK-meansclusteringsofthef