聚类分析基本概念和算法.ppt
聚类分析：基本概念和算法第8 章 聚类分析：基本概念和算法什么是聚类分析?l 聚类分析将数据划分成有意义或有用的组（簇）。l 聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。Inter-cluster distances are maximizedIntra-cluster distances are minimized什么是一个好的聚类方法?l 一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性 低的簇间相似性 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 完全聚类（complete clustering）l 部分聚类（partial clustering）划分聚类（Partitional Clustering）Original Points A Partitional Clusteringl 划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。层次聚类（Hierarchical Clustering）Traditional Hierarchical ClusteringNon-traditional Hierarchical Clustering Non-traditional DendrogramTraditional Dendrograml 层次聚类是嵌套簇的集族，组织成一棵树。互斥的、重叠的、模糊的l 互斥的（Exclusive）每个对象都指派到单个簇.l 重叠的（overlapping）或非互斥的（non-exclusive）聚类用来反映一个对象.同时属于多个组（类）这一事实。例如：在大学里，一个人可能既是学生，又是雇员l 模糊聚类（Fuzzy clustering）每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。l 部分的（Partial）部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。l 完全的（complete）完全聚类将每个对象指派到一个簇。不同的簇类型l 明显分离的l 基于原型的l 基于图的l 基于密度的l 概念簇簇类型:明显分离的（Well-Separated）l 每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。3 well-separated clusters簇类型:基于原型的l 每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。l 基于中心的（Center-Based）的簇：每个点到其簇中心的距离比到任何其他簇中心的距离更近。4 center-based clusters簇类型:基于图的l 如果数据用图表示，其中节点是对象，而边代表对象之间的联系。l 簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通的对象组。l 基于近邻的（Contiguity-Based）：其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8 contiguous clusters簇类型:基于密度的（Density-Based）l 簇是对象的稠密区域，被低密度的区域环绕。6 density-based clusters簇类型:概念簇（Conceptual Clusters）l 可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。.2 Overlapping CirclesK 均值聚类基本K 均值算法l 1.选择k个点作为初始的质心l 2.repeatl 3.将每个点指派到最近的质心，形成k个簇l 4.重新计算每个簇的质心l 5.until 质心不发生变化数据对象之间的相异度l Euclidean Distance 明可夫斯基距离（Minkowski Distance）l Minkowski Distancel r=1.城市块(曼哈顿,出租车,L1 范数)距离.l r=2.欧氏距离（L2 范数）l r.上确界(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+f00)l Jaccard(雅卡尔)系数（非对称二元属性）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|=(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）时，使簇的L1 绝对误差和（SAE）最小的质心是中位数l 当紧邻函数是欧式距离时，可对SSE 求导选择初始的质心l 随机选择l 从层次聚类中提取K 个簇，并用这些簇的质心作为初始质心l 随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点l 二分K 均值二分k 均值l 二分k均值算法是基本k均值算法的直接k个簇。l 它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇二分k 均值算法l 初始化簇表，使之包含由所有的点组成的簇。l Repeatl 从簇表中取出一个簇。l for i=1 to 实验次数 dol 使用基本k均值，二分选定的簇。l end forl 从二分实验中选择具有最小总sse 的两个簇。l 将这两个簇添加到簇表中。l Until 簇表中包含k个簇。K means 的优点与缺点l 优点：l 算法简单l 适用于球形簇l 二分k均值等变种算法运行良好，不受初始化问题的影响。l 缺点：l 不能处理非球形簇、不同尺寸和不同密度的簇l 对离群点、噪声敏感K-means 的局限性l K-means has problems when clusters are of differing Sizes 大小 Densities 密度 Non-globular shapes 非球形Limitations 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 Points K-means ClustersOne solution is to use many clusters.Find parts of clusters,but need to put together.Overcoming K-means LimitationsOriginal Points K-means ClustersOvercoming K-means LimitationsOriginal Points K-means Clusters层次聚类l 层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。l 按自底向上层次分解，则称为凝聚的层次聚类。l 按自顶向下层次分解，就称为分裂的层次聚类。凝聚的和分裂的层次聚类 l 凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。l 分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。l 传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。凝聚的和分裂的层次聚类
