7第七章 聚类分析

第七章聚类分析张静（[e-mail]）主要内容ECUST--JingZhang2什么是聚类分析?聚类分析中的数据类型主要的聚类方法划分方法层次方法基于密度的方法基于网格的方法基于模型的方法离群点分析小结什么是聚类分析？聚类是无监督学习（unsupervisedlearning）没有预定义的类别观察式学习典型应用作为独立工具（stand-alonetool），可表征数据分布作为其他算法的预处理步骤（preprocessingstep）ECUST--JingZhang4聚类的应用场景5空间数据分析在GIS中，通过对特征空间聚类来创建主题地图。图像处理经济学(特别是市场研究)城市规划气候研究文档分类对Web日志进行聚类，从而发现相似的访问模式。离群点检测信用卡欺诈检测；监控电子商务中的犯罪活动等。6聚类作为预处理工具概括可以作为回归,PCA,分类,以及关联分析的预处理压缩图像处理:矢量量化找到K近邻局部搜索一个或少量的聚类ECUST--JingZhang什么是好的聚类方法？ECUST--JingZhang7一个好的聚类方法将会产生高质量的簇高簇内相似性：类内凝聚性低簇间相似性：类间区分性判定一个聚类方法质量好坏依赖于用于该聚类方法的相似度度量具体实现方法能否发现部分或者所有隐藏的模式数据挖掘对聚类的要求8可伸缩性处理不同类型属性的能力数值型、二元类型、分类/标称类型、序数型。发现任意形状的聚类基于欧几里德距离或曼哈顿距离，偏向于发现具有相近尺寸和密度的球状簇开发其他类型的其他度量对于决定输入参数的领域知识需求最小参数选择ECUST--JingZhang数据挖掘对聚类的要求处理噪声数据的能力离群点、空缺值、未知数据、错误数据增量聚类和对于输入纪录的顺序不敏感高维性基于约束的聚类可解释性和可用性ECUST--JingZhang9聚类方法研究的问题分割需求:单层vs.多层簇的分割:排他的vs.非排他的相似度度量:距离vs.基于密度或区域的连通性聚类空间:整个空间vs.子空间10主要内容ECUST--JingZhang11什么是聚类分析?聚类分析中的数据类型主要的聚类方法划分方法层次方法基于密度的方法基于网格的方法基于模型的方法离群点分析小结不同数据类型的距离度量区间标度变量:粗略线性标度的连续度量，如：重量，高度等MinkowskiDistance:Specialcases:Euclidean(L2-norm),Manhattan(L1-norm)1211,rrniiidXYxy1,niiidXYxy21,niiidXYxyECUST--JingZhang不同数据类型的距离度量二元变量:只有两种状态：0,1相异度计算：相异矩阵对称vs.非对称对称二元变量：两个状态具有同等价值和相同的权重。非对称二元变量：输出的状态不是同等重要的。标称变量（分类变量）:二元变量的推广，可以取多个状态值相异度计算：不匹配变量的数目（或不匹配率）ECUST--JingZhang13不同数据类型的距离度量序数变量:相异度计算：处理方法同区间标度变量比例标度变量:在非线性的刻度（例如指数刻度）取正的度量值相异度计算：首先进行对数变换矢量:相异度计算：cosinemeasure混合类型变量:相异度计算：按类型分组，对每种类型的变量进行单独的聚类分析将所有类型的变量一起处理，只进行一次聚类分析14簇之间的距离Singlelink:一个簇中的对象和另一个簇中对象的最小距离,i.e.,dist(Ki,Kj)=min(tip,tjq)Completelink:一个簇中的对象和另一个簇中对象的最大距离,i.e.,dist(Ki,Kj)=max(tip,tjq)Average:一个簇中的对象和另一个簇中对象的平均距离,i.e.,dist(Ki,Kj)=avg(tip,tjq)Centroid:两个簇质心之间的距离,i.e.,dist(Ki,Kj)=dist(Ci,Cj)Medoid:两个簇中心点之间的距离,i.e.,dist(Ki,Kj)=dist(Mi,Mj)Medoid:achosen,centrallylocatedobjectintheclusterXX15一个簇的质心（Centroid）,半径（Radius）和直径（Diameter）(对于数值数据集合)Centroid:the“middle”ofaclusterRadius:squarerootofaveragedistancefromanypointoftheclustertoitscentroidDiameter:squarerootofaveragemeansquareddistancebetweenallpairsofpointsintheclusterNtNiipmC)(1NmciptNimR2)(1)1(2)(11NNiqtiptNiNimD16主要内容ECUST--JingZhang17什么是聚类分析?聚类分析中的数据类型主要的聚类方法划分方法层次方法基于密度的方法基于网格的方法基于模型的方法离群点分析小结主要聚类方法的分类ECUST--JingZhang18划分算法构造各种各样的划分,并用一些标准来评估它们给定初始划分数目k，产生一个初始划分，然后采用迭代的重定位技术，直到找到一个好的划分。层次算法使用一些策略来进行数据(或对象)集的层次分解凝聚的和分裂的缺点：不能被撤销改进在每层划分中，仔细分析对象间的“联接”综合层次凝聚和迭代的重定位方法主要聚类方法的分类ECUST--JingZhang19基于密度的方法基于连续和密度函数只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类基于网格的方法基于多层粒度结构把对象量化为有限数目的单元，形成一个网格结构。聚类操作在网格结构（即量化的空间）上进行。处理时间独立于数据对象数目，只与量化空间中每一维的单元数目有关。基于模型的方法为每个簇假设一个模型,寻找数据对给定模型的最佳拟合主要聚类方法的分类其他类型的聚类聚类高维数据子空间聚类方法基于频繁模式的聚类基于约束的聚类存在障碍物的空间聚类用户指定约束下的聚类半监督聚类ECUST--JingZhang20主要内容ECUST--JingZhang21什么是聚类分析?聚类分析中的数据类型主要的聚类方法划分方法层次方法基于密度的方法基于网格的方法基于模型的方法离群点分析小结划分方法：基本概念22划分方法:基于一个n个对象或元组的数据库，构建数据的k个划分，每个划分表示一个簇，k=n给定一个k，找到一个划分方法，含k个簇，并且这个划分是最优的。全局最优:需要穷举所有可能的划分启发式方法:k-means和k-medoids算法k-means:每个簇用该簇中对象的平均值来表示k-medoidsorPAM(Partitionaroundmedoids):每个簇用接近聚类中心的一个对象来表示ECUST--JingZhang22K-Means聚类方法K均值的处理流程如下：随机选择k个对象，每个对象初始地代表了一个簇的平均值或中心对剩余每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。重新计算每个簇的平均值。这个过程不断重复，直到簇不再发生变化或准则函数收敛。平方误差准则P是空间中的点，mi是簇Ci的平均值kiCpiimp12||EECUST--JingZhang23K-Means聚类方法举例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2任意选择K个对象作为初始化类中心把每个对象归为最相似的中心更新簇的均值更新簇的均值重新指派重新指派24K-Means聚类方法ECUST--JingZhang25优点复杂度:O(nkt),其中n是对象的数目,k是簇的数目,t是迭代的次数.通常k,tn.相对可伸缩和高效。通常以局部最优结束。缺点只有在簇的平均值被定义的情况下才能使用，当涉及有分类属性的数据时无法处理需要事先给出k，簇的数目对噪声和离群点数据敏感不适合发现非凸形状的簇，或者大小差别很大的簇K-Means方法的变种ECUST--JingZhang26有许多k-means算法的变种，区别在于初始k个平均值的选择相异度的计算计算聚类平均值的策略处理分类数据:k-众数方法（k-modes(Huang’98)）用众数代替簇的平均值采用新的相异度度量采用基于频率的方法更新簇众数混合处理分类和数值数据:k-原型方法（k-prototype）将k-均值和k-众数方法综合起来K-Means方法存在的问题?k-means算法对离群点非常敏感!因为拥有极端值的对象将在很大程度上影响数据的分布。K-Medoids:用中心点（位于簇最中心位置的对象）而不是簇中对象的平均值作为参考点。01234567891001234567891001234567891001234567891027K-Medoids聚类算法ECUST--JingZhang28在各个簇中找到最有代表性的对象，即中心点（medoids）基本策略为每个簇随意选择一个代表对象剩余的对象按照它跟代表对象的距离分配给最近的一个簇然后反复地用非代表对象替代代表对象，以改进聚类质量。方法PAM(PartitioningAroundMedoids,1987)从一个初始的集合开始，循环利用non-medoids替换medoids，看看是否能够提高各个簇的性能PAM处理小数据集合时非常有效，但是处理大数据集合时却并不很有效CLARA(Kaufmann&Rousseeuw,1990)：基于抽样的PAMCLARANS(Ng&Han,1994):随机的样本PAM(PartitioningAroundMedoids)ECUST--JingZhang29PAM(PartitioningAroundMedoids,KaufmanandRousseeuw,1987)算法：随机选择k个对象作为初始的中心点Repeat指派每个剩余的对象给离它最近的中心点所代表的簇；随机地选择一个非中心点对象Oh；计算用Oh代替Oi的总代价(totalswappingcost)TCih；IfTCih0,thenOh替换Oi，形成新的k个中心点的集合；Until不发生变化k-Means与k-MedoidsECUST--JingZhang30当存在噪声或离群点数据时，k-Medoids方法比k-Means方法更健壮，因为中心点不象平均值那么容易被极端数据影响K-Medoids方法执行代价比k-Means高K-Medoids方法不具有良好的可伸缩性二者均要求指定结果簇的数目kCLARA(ClusteringLargeApplications)ECUST--JingZhang31基于抽样的方法抽取数据集合的多个样本，对每个样本应用PAM算法，返回最好的聚类结果作为输出优点能处理规模较大的数据集缺点有效性取决于样本的大小如果样本发生偏斜，基于样本的好的聚类不一定代表了整个数据集合的一个好的聚类CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch)将采样技术同PAM相结合，随机化的“CLARA”CLARAN