第七章 聚类分析

2020年2月9日星期日DataMining:ConceptsandTechniques1第七章聚类分析1.什么是聚类分析？2.聚类分析中的数据类型3.聚类分析的主要方法分类4.划分方法5.层次方法6.基于密度的方法7.基于网格的方法8.基于模型的方法9.聚类高维数据10.基于约束的聚类分析11.离群点分析12.小结2020年2月9日星期日DataMining:ConceptsandTechniques2什么是聚类分析聚类：将数据对象集合成簇簇内相似最大化簇间相异最大化聚类分析将物理或抽象对象的集合分成相似的对象类的过程无监督学习:无欲先定义的类典型应用作为独立的工具来分析数据的分布情况作为其他程序的预处理过程2020年2月9日星期日DataMining:ConceptsandTechniques3聚类在各学科间的应用模式识别空间数据分析CreatethematicmapsinGISbyclusteringfeaturespacesDetectspatialclustersorforotherspatialminingtasks图像处理经济学(特别是市场分析)文献分类聚类网络日志，ClusterWeblogdatatodiscovergroupsofsimilaraccesspatterns2020年2月9日星期日DataMining:ConceptsandTechniques4聚类的应用举例市场学:帮助营销人员将其客户数据分成不同的组，以更好的开拓目标市场土地使用:对地球上相似地区土地的使用观察数据保险行业:将汽车保险分组从而使得投保人的平均花费最高城市规划:根据的房子类型，价值，和地理位置确定住房团体地震研究:根据大陆断层的聚类观测震中2020年2月9日星期日DataMining:ConceptsandTechniques5什么是好的聚类？一个好的聚类方法使聚类结果簇内相似最大化簇间相似最小化好的聚类方法不仅取决于它产生结果的相似程度，而且还与其执行有关聚类方法的好坏也与他发现部分或全部潜在模式的能力有关2020年2月9日星期日DataMining:ConceptsandTechniques6衡量聚类的质量相异/相似尺度:我们用距离函数d(i,j)来表示相似度。有独立的“质量”函数来衡量聚类的好坏对区间标度变量，布尔变量，分类变量，序数变量，向量的距离函数的定义方式是不同的.不同的应用或数据含义，其衡量方法应该不同很难定义“足够相似”或“足够好”结果往往是高度主观的2020年2月9日星期日DataMining:ConceptsandTechniques7数据挖掘中聚类的要求可伸缩性具有处理不同类型属性的能力具有处理动态数据的能力发现任意形状的聚类对于决定输入的参数的领域知识需求最小可以处理噪声和离群点不依赖于对象的输入次序高维性基于约束的聚类可释性和可用性2020年2月9日星期日DataMining:ConceptsandTechniques8第七章聚类分析1.什么是聚类分析？2.聚类分析中的数据类型3.聚类分析的主要方法分类4.划分方法5.层次方法6.基于密度的方法7.基于网格的方法8.基于模型的方法9.聚类高维数据10.基于约束的聚类分析11.离群点分析12.小结2020年2月9日星期日DataMining:ConceptsandTechniques9数据结果数据矩阵(二模)相异度矩阵(单模)npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x0...)2,()1,(:::)2,3()...ndnd0dd(3,10d(2,1)02020年2月9日星期日DataMining:ConceptsandTechniques10聚类分析中的数据类型区间标度变量二元变量分类、序数、和比例表度变量混合类型的变量2020年2月9日星期日DataMining:ConceptsandTechniques11区间标度变量数据标准化计算均值绝对误差其中计算标准度量值(z-score)使用均值绝对误差比使用标准度量值稳定.)...211nffffxx(xnm|)|...|||(|121fnffffffmxmxmxnsffififsmxz2020年2月9日星期日DataMining:ConceptsandTechniques12对象间的相似度和相异度通常用距离来描述对象间的相似度或相异度最常用的是闵可夫斯基距离其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维数据，q是一个正整数。当q=1时，d是曼哈顿距离qqppqqjxixjxixjxixjid)||...|||(|),(2211||...||||),(2211ppjxixjxixjxixjid2020年2月9日星期日DataMining:ConceptsandTechniques13对象间的相似度和相异度当q=2时，d为欧氏距离:d应满足的要求d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)当然，我们也可以用加权距离或是其他的相异度衡量方法)||...|||(|),(2222211ppjxixjxixjxixjid2020年2月9日星期日DataMining:ConceptsandTechniques14二元变量二元变量的相依表使用对称二元变量描述对象间的距离：使用非对称二元变量描述对象间的距离：Jaccard系数(非对称二元变量相似度):dcbacbjid),(cbacbjid),(pdbcasumdcdcbabasum0101ObjectiObjectjcbaajisimJaccard),(2020年2月9日星期日DataMining:ConceptsandTechniques15二元变量间的相异度例：性别是对称属性剩下的属性为非对称二元变量令，Y=P=1,N=0NameGenderFeverCoughTest-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackd2020年2月9日星期日DataMining:ConceptsandTechniques16分类变量一般的变量都不是二元变量，是可以取多于两个状态值的。如：红色，黄色，蓝色，绿色。方法1:不匹配率m:匹配的数目，p:全部变量的数目方法2:使用多个二元变量为每个分类变量的状态创建一个新的二元变量pmpjid),(2020年2月9日星期日DataMining:ConceptsandTechniques17序数变量序数变量可以是离散的或是连续的序数是很重要的，如：等级。可以当做是区间标度变量来对待将xif替换成他的秩将每个变量的值映射到区间[0,1]内，这可以通过用代替第f个变量的第i个对象来实现利用求区间标度变量相异度的方法来计算序数变量的相异度ifz11fififMrz},...,1{fifMrifr2020年2月9日星期日DataMining:ConceptsandTechniques18比例标度变量比例表度变量:在非线性的刻度（例如指数刻度）取正的度量值，近似的遵循下面的公式：AeBt或Ae-Bt方法：采用处理区间标度变量的方法——并不是一个好的方法（比例可能被扭曲了）对比例标度进行对数变化yif=log(xif)将其看做连续的序数数据，将其秩看做区间标度变量2020年2月9日星期日DataMining:ConceptsandTechniques19混合类型的变量一个数据库可能含有所以以上六种类型的变量对称二元变量，非对称二元变量，分类变量，序数变量，区间标度变量和比例标度变量用有效的公式将他们一起处理f是二元变量或分类变量:dij(f)=0ifxif=xjf,ordij(f)=1否则f是区间标度变量:使用标准距离f是序数或比例标度变量计算秩rif和zif并将zif看做区间标度变量)(1)()(1),(fijpffijfijpfdjid11fifMrzif2020年2月9日星期日DataMining:ConceptsandTechniques20向量对象向量对象:文献中的关键词，微阵列中的基因特征等。广泛应用:信息检索,生物学分类等.余弦度量Tanimoto系数2020年2月9日星期日DataMining:ConceptsandTechniques21第七章聚类分析1.什么是聚类分析？2.聚类分析中的数据类型3.聚类分析的主要方法分类4.划分方法5.层次方法6.基于密度的方法7.基于网格的方法8.基于模型的方法9.聚类高维数据10.基于约束的聚类分析11.离群点分析12.小结2020年2月9日星期日DataMining:ConceptsandTechniques22主要的聚类分析方法（I）划分法:将给定的数据，按照一定的标准构建k划分。典型的有：k均值法，k中心点算法，CLARA(聚类大型应用)。层次方法：按照一定的标准，创建给定数据对象集的层次分解。典型的有：Diana,Agnes,BIRCH,ROCK,CAMELEON基于密度的方法：基于密度或链接函数典型的有：DBSACN,OPTICS,DenClue2020年2月9日星期日DataMining:ConceptsandTechniques23主要的聚类分析方法(II)基于网格的方法：基于多层粒度结构经典的方法:STING,WaveCluster,CLIQUE基于模型的方法:为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合。经典的有：EM,SOM,COBWEB基于频繁模式的方法:基于对频繁模式的分析。经典的方法:pCluster基于约束的方法:结合用户给定或面向应用的特殊约束进行聚类经典的方法:COD(含障碍物),基于约束的聚类2020年2月9日星期日DataMining:ConceptsandTechniques24常用的计算簇间距离的方法单链接:使用两个簇的元素间的最小距离作为簇间距离即：dis(Ki,Kj)=min(tip,tjq)完全链接:使用两个簇间的元素的最大距离作为簇间距离即：dis(Ki,Kj)=max(tip,tjq)平均值:使用两个簇的元素间距离的平均值作为簇间距离即：dis(Ki,Kj)=avg(tip,tjq)质心:使用两个簇的质心的距离作为簇间距离即：dis(Ki,Kj)=dis(Ci,Cj)中心点:使用两个簇的中心点的距离作为簇间距离即：dis(Ki,Kj)=dis(Mi,Mj)2020年2月9日星期日DataMining:ConceptsandTechniques25簇的质心，半径，直径(fornumericaldatasets)质心:簇的“中央”半径:簇中元素到其质心的距离的平均值的平方根直径:没对元素的距离的平均值的平方根NtNiipmC)(1NmciptNimR2)(1)1(2)(11NNiqtiptNiNimD2020年2月9日星期日DataMining:ConceptsandTechniques26第七章聚类分析1.什么是聚类分析？2.聚类分析中的数据类型3.聚类分析的主要方法分类4.划分方法5.层次方法6.基于密度的方法7.基于网格的方法8.基于