《第8章_聚类分析：基本概念和算法课件》由会员分享，可在线阅读，更多相关《第8章_聚类分析：基本概念和算法课件（84页珍藏版）》请在金锄头文库上搜索。
1、聚类分析：基本概念和算法,第8章 聚类分析：基本概念和算法,什么是聚类分析?,聚类分析将数据划分成有意义或有用的组（簇）。 聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。,什么是一个好的聚类方法?,一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点： 高的簇内相似性 低的簇间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现； 聚类方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式；,聚类的复杂性,不同的聚类类型,划分聚类（Partitional Clust
2、ering） 层次聚类（Hierarchical Clustering） 互斥（重叠）聚类（exclusive clustering） 非互斥聚类（non-exclusive） 模糊聚类（fuzzy clustering） 完全聚类（complete clustering） 部分聚类（partial clustering）,划分聚类（Partitional Clustering）,Original Points,A Partitional Clustering,划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。,层次聚类（Hierarchical Clustering
3、）,Traditional Hierarchical Clustering,Non-traditional Hierarchical Clustering,Non-traditional Dendrogram,Traditional Dendrogram,层次聚类是嵌套簇的集族，组织成一棵树。,互斥的、重叠的、模糊的,互斥的（Exclusive） 每个对象都指派到单个簇. 重叠的（overlapping）或非互斥的（non-exclusive） 聚类用来反映一个对象.同时属于多个组（类）这一事实。 例如：在大学里，一个人可能既是学生，又是雇员 模糊聚类（Fuzzy clustering ） 每
4、个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。 部分的（Partial） 部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。 完全的（complete） 完全聚类将每个对象指派到一个簇。,不同的簇类型,明显分离的 基于原型的 基于图的 基于密度的 概念簇,簇类型: 明显分离的（Well-Separated）,每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。,3 well-separated clusters,簇类型:基于原型的,每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，
5、簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。 基于中心的（ Center-Based）的簇：每个点到其簇中心的距离比到任何其他簇中心的距离更近。,4 center-based clusters,簇类型:基于图的,如果数据用图表示，其中节点是对象，而边代表对象之间的联系。 簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通的对象组。 基于近邻的（ Contiguity-Based）：其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。
6、,8 contiguous clusters,簇类型: 基于密度的（Density-Based）,簇是对象的稠密区域，被低密度的区域环绕。,6 density-based clusters,簇类型: 概念簇（Conceptual Clusters）,可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。 .,2 Overlapping Circles,K均值聚类,基本K均值算法,1.选择k个点作为初始的质心 2.repeat 3. 将每个点指派到最近的质心，形成k个簇 4. 重新计算每个簇的质心 5.until 质心不发生变化,数据对
7、象之间的相异度,Euclidean Distance,明可夫斯基距离（Minkowski Distance）,Minkowski Distance r = 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 = 值匹配的属
8、性个数 / 属性个数 = (f11 +f00) / (f01 + f10 + f11 + f00) Jaccard(雅卡尔 ) 系数 （非对称二元属性） J = 匹配的个数 / 不涉及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
9、 + 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.245 cos( d1, d2 ) = 0.3150,误差平方和（sum of the squared error，SSE）,误差平方和 它可以度量聚类的质量。误差平方和越小，意味着质心是簇中点的更好代表。 可以证明：当紧邻函数是欧式距离（L2）时，使簇的S
10、SE最小的质心是均值，即 可以证明：当紧邻函数是曼哈顿距离（L1）时，使簇的L1绝对误差和（SAE）最小的质心是中位数,当紧邻函数是欧式距离时，可对SSE求导,选择初始的质心,随机选择 从层次聚类中提取K个簇，并用这些簇的质心作为初始质心 随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点 二分K均值,二分k均值,二分k均值算法是基本k均值算法的直接k个簇。 它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇,二分k均值算法,初始化簇表，使之包含由所有的点组成的簇。 Repeat 从簇表中取出一个簇。
11、for i=1 to 实验次数 do 使用基本k均值，二分选定的簇。 end for 从二分实验中选择具有最小总sse的两个簇。 将这两个簇添加到簇表中。 Until 簇表中包含k个簇。,K means 的优点与缺点,优点： 算法简单 适用于球形簇 二分k均值等变种算法运行良好，不受初始化问题的影响。 缺点： 不能处理非球形簇、不同尺寸和不同密度的簇 对离群点、噪声敏感,K-means 的局限性,K-means has problems when clusters are of differing Sizes大小 Densities密度 Non-globular shapes非球形,Limit
12、ations of K-means: Differing Sizes,Original Points,K-means (3 Clusters),Limitations of K-means: Differing Density,Original Points,K-means (3 Clusters),Limitations of K-means: Non-globular Shapes,Original Points,K-means (2 Clusters),K-means 局限性的克服,Original PointsK-means Clusters,One solution is to us
13、e many clusters. Find parts of clusters, but need to put together.,Overcoming K-means Limitations,Original PointsK-means Clusters,Overcoming K-means Limitations,Original PointsK-means Clusters,层次聚类,层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。 按自底向上层次分解，则称为凝聚的层次聚类。 按自顶向下层次分解，就称为分裂的层次聚类。,凝聚的和分裂的层次聚类,凝聚的层次聚类采用自底向上的
14、策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。 分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。 传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。,凝聚的和分裂的层次聚类,基本凝聚层次聚类方法,凝聚层次聚类算法 计算临近度矩阵 让每个点作为一个cluster Repeat 合并最近的两个类 更新临近度矩阵，以反映新的簇与原来的簇之间的临近性 Until 仅剩下一个簇 关键的操作是two clusters的邻近度计算 不同的邻近度的定义区分了
15、各种不同的凝聚层次技术,起始步骤,Start with clusters of individual points and a proximity matrix,Proximity Matrix,中间步骤,经过部分融合之后 ，我们得到一些cluster,C1,C4,C2,C5,C3,Proximity Matrix,中间步骤,我们希望合并两个最邻近的cluster (C2 and C5) 并更新临近度矩阵,C1,C4,C2,C5,C3,Proximity Matrix,最终合并,如何更新临近度矩阵？,C1,C4,C2 U C5,C3,? ? ? ?,?,?,?,C2 U C5,C1,C1,C3
16、,C4,C2 U C5,C3,C4,Proximity Matrix,如何定义cluster间的相似性,Similarity?,MIN MAX Group Average Distance Between Centroids Other methods driven by an objective function Wards Method uses squared error,Proximity Matrix,Proximity Matrix,MIN MAX Group Average Distance Between Centroids Other methods driven by an objective function Wards Method uses squared error,如何定义cluster间的相似性,
