CHAPTER10-聚类分析：基本概念和方法

费高雷通信与信息工程学院2015年春季第10章聚类分析：基本概念和方法2第10章：聚类分析：基本概念和方法聚类分析划分方法层次方法基于密度的方法基于网格的方法聚类评估小结什么是聚类分析?聚类:数据对象的集合/簇(cluster)同一簇中的对象彼此相似不同簇中的对象彼此相异聚类分析将数据对象分组成为多个类或簇聚类是无监督的分类：没有预先定义的类典型应用作为洞察数据内部分布的独一无二的工具作为其它算法的预处理步骤聚类的一般应用模式识别空间数据分析聚类产生GIS(地理信息系统)的专题地图thematicmaps在空间数据挖掘中检测空间聚类并解释它们图象处理经济科学(特别是市场研究)文本分类Web日志数据聚类，发现类似访问模式群聚类应用的例子市场营销:帮助市场营销者发现他们的基本顾客的不同组群，然后利用这一知识制定有针对性的营销计划国土利用在地球观测数据库中识别类似的国土使用区域保险对汽车保险持有者的分组城市规划根据房子的类型，价值，和地理位置对一个城市中房屋的分组地震研究应当将观测到的地震震中沿大陆板块断裂进行聚类聚类分析的主要步骤特征选择选择与任务密切相关的信息尽可能减少信息冗余相似度评价两个特征向量的相似性聚类的评价准则通过代价函数或某些规则聚类算法k-均值、极大似然、…结果验证验证聚类结果的有效性结果解释根据实际应用解释聚类结果6什么是好的聚类方法?一个好的聚类方法应当产生高质量的聚类类内相似性高类间相似性低聚类结果的质量依赖于方法所使用的相似性度量和它的实现.聚类方法的质量也用它发现某些或全部隐藏的模式的能力来度量数据挖掘对聚类的要求可伸缩性有的算法当数据对象少于200时处理很好,但对大量数据对象偏差较大大型数据库包含数百万个对象处理不同属性类型的能力许多算法专门用于数值类型的数据实际应用涉及不同数据类型（数值和分类数据混合）发现任意形状的聚类基于距离的聚类趋向于发现具有相近尺度和密度的球状簇一个簇可能是任意形状的数据挖掘对聚类的要求(续)用于决定输入参数的领域知识最小化许多聚类算法要求用户输入一定的参数，如希望产生的簇的数目。参数难以确定，增加用户负担，使聚类质量难以控制处理噪声数据和孤立点的能力一些聚类算法对于噪音数据敏感,可能导致低质量的聚类结果现实世界中的数据库大都包含了孤立点,空缺,或者错误的数据对于输入记录的顺序不敏感一些聚类算法对于输入数据的顺序是敏感的,以不同的次序输入会导致不同的聚类数据挖掘对聚类的要求(续)高维性（highdimensionality）许多聚类算法擅长处理低维的数据,可能只涉及两到三维数据库或者数据仓库可能包含若干维或者属性,数据可能非常稀疏,而且高度偏斜整合用户指定的约束现实世界的应用可能需要在各种约束条件下进行聚类要找到既满足特定的约束,又具有良好聚类特性的数据分组是一项具有挑战性的任务可解释性和可用性用户希望聚类结果是可解释的,可理解的,和可用的聚类可能需要和特定的语义解释和应用相联系聚类分析的方法划分方法:Constructvariouspartitionsandthenevaluatethembysomecriterion,e.g.,minimizingthesumofsquareerrorsTypicalmethods:k-means,k-medoids,CLARANS层次方法:Createahierarchicaldecompositionofthesetofdata(orobjects)usingsomecriterionTypicalmethods:Diana,Agnes,BIRCH,CAMELEON基于密度的方法:BasedonconnectivityanddensityfunctionsTypicalmethods:DBSACN,OPTICS,DenClue基于网格的方法:basedonamultiple-levelgranularitystructureTypicalmethods:STING,WaveCluster,CLIQUE11聚类分析的方法基于模型的方法:AmodelishypothesizedforeachoftheclustersandtriestofindthebestfitofthatmodeltoeachotherTypicalmethods:EM,SOM,COBWEB基于频繁模式的方法:BasedontheanalysisoffrequentpatternsTypicalmethods:p-Cluster基于约束的方法:Clusteringbyconsideringuser-specifiedorapplication-specificconstraintsTypicalmethods:COD(obstacles),constrainedclustering基于链接的方法:ObjectsareoftenlinkedtogetherinvariouswaysMassivelinkscanbeusedtoclusterobjects:SimRank,LinkClus1213第10章：聚类分析：基本概念和方法聚类分析划分方法层次方法基于密度的方法基于网格的方法聚类评估小结划分方法划分方法:构造n个对象数据库D的划分,将其划分成k个聚类给定k,找k个clusters对于选定的划分标准它是最优的全局最优(Globaloptimal):枚举所有的划分启发式方法(Heuristicmethods):k-平均(k-means)和k-中心点(k-medoids)算法k-平均(MacQueen’67):每个簇用簇的重心(簇的平均值)表示k-中心点或PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每个簇用接近聚类中心的一个对象来表示k-平均聚类算法算法：k-平均(1)任意选择k个对象作为初始的簇中心；(2)repeat(3)根据簇中对象的平均值,将每个对象(重新)赋给最类似的簇；(4)更新簇的平均值,即重新计算每个簇中对象的平均值；(5)until不再发生变化通常,采用平方误差准则作为收敛函数,其定义如下其中,mi是簇Ci的平均值该准则试图使生成的结果簇尽可能紧凑,独立21||kiCpiimpEk-平均聚类算法(续)例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2任意选择K个对象作为初始聚类中心将每个对象赋给最相似中心更新簇平均值重新赋值更新簇平均值重新赋值k-平均聚类算法(续)优点:相对有效性:O(tkn),其中，n是对象数目，k是簇数目，t是迭代次数;通常：k，tn比较:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k))当结果簇是密集的，簇与簇之间区别明显，效果较好Comment:常常终止于局部最优全局最优可以使用诸如确定性的退火（deterministicannealing）和遗传算法（geneticalgorithms）等技术得到k-平均聚类算法(续)弱点只有在簇的平均值(mean)被定义的情况下才能使用可能不适用于某些应用，例如涉及有分类属性的数据需要预先指顶簇的数目k不能处理噪音数据和孤立点(outliers)不适合用来发现非凸形状(non-convexshapes)的簇k-中心点聚类方法k-平均值算法对孤立点很敏感因为具有特别大的值的对象可能显著地影响数据的分布{1,2,3,8,9,10,25}—{1,2,3}{8,9,10,25}{1,2,3,8}{9,10,25}k-中心点(k-Medoids):不采用簇中对象的平均值作为参照点,而是选用簇中位置最中心的对象,即中心点(medoid)作为参照点012345678910012345678910012345678910012345678910k-中心点聚类方法(续)找聚类中的代表对象(中心点)PAM（PartitioningAroundMedoids,1987）首先为每个簇随意选择一个代表对象,剩余的对象根据其与代表对象的距离分配给最近的一个簇反复地用非代表对象替代代表对象，以改进聚类的质量PAM对于较小的数据集非常有效,但不能很好地扩展到大型数据集CLARA(Kaufmann&Rousseeuw,1990)抽样CLARANS(Ng&Han,1994):随机选样算法:k-中心点(1)随机选择k个对象作为初始的代表对象；(2)repeat(3)指派每个剩余的对象给离它最近的代表对象所代表的簇；(4)随意地选择一个非代表对象Orandom；(5)计算用Orandom代替Oj的总代价S；(6)若S0，用Orandom替换Oj，形成新的k个代表对象的集合；(7)until不发生变化k-中心点聚类方法(续)O1O2O3。。。Oj。。。OkOrandom012345678910012345678910TotalCost=20012345678910012345678910k=2任意选择k个数据对象作为初始类中心点012345678910012345678910将每个剩余的数据对象安排对最近的类随机选择一个非类中心数据对象Oramdom计算交换的代价012345678910012345678910TotalCost=26若聚类质量上升，交换O与Oramdom.执行循环直至类不在发生变化012345678910012345678910k-中心点聚类方法(续)k-中心点聚类方法(续)为了判定一个非代表对象Orandom是否是当前一个代表对象Oj的好的替代，对于每一个非代表对象，考虑下面四种情况：第一种情况：p当前隶属于代表对象Oj.如果Oj被Orandom所代替,且p离Oi最近,i≠j,那么p被重新分配给Oi第二种情况：p当前隶属于代表对象Oj.如果Oj被Orandom代替,且p离Orandom最近,那么p被重新分配给Orandom第三种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，而p仍然离Oi最近，那么对象的隶属不发生变化第四种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，且p离Orandom最近，那么p被重新分配给Orandom1.重新分配给Oi2.重新分配给Orandom3.不发生变化4.重新分配给Orandom●数据对象+簇中心替代前替代后k-中心点聚类代价函数的四种情况+++●OrandomOiOjp+++●OrandomOiOjp+++●OrandomOiOjp+++●OrandomOiOjpk-中心点聚类方法(续)当存在噪音和孤立点时，PAM比k-平均方法更健壮，其原因是中心点不象平均值那么容易被极端数据影响PAM对于小数据集工作得很好，但不能很好地用于大数据集每次迭代O(k(n-k)2)k-平均：O(tkn)其中，n是数据对象数目，k是聚类数基于抽样的方法：CLARA(ClusteringLARgeApplications)k-中心点聚类方法(续)26第10章：聚类分析：基本概念和方法聚类分析划分方法层次方法基于密度的方法基于网格的方法聚类评估小结层次方法层次的聚类方法将数据对象组成一棵聚类的树根据层次分解是自底向上,还是自顶向下形成,层次的聚类方法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类使用距离矩阵作为聚类标准.该方法不需要输入聚类数目k,但需要终止条件凝聚的(agglomerative)和分裂的(divisiv