第七章-聚类分析

05二月2023DataMining:ConceptsandTechniques1第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques2什么是聚类分析聚类：将数据对象集合成簇簇内相似最大化簇间相异最大化聚类分析将物理或抽象对象的集合分成相似的对象类的过程无监督学习:无欲先定义的类典型应用作为独立的工具来分析数据的分布情况作为其他程序的预处理过程05二月2023DataMining:ConceptsandTechniques3聚类在各学科间的应用

模式识别空间数据分析CreatethematicmapsinGISbyclusteringfeaturespacesDetectspatialclustersorforotherspatialminingtasks图像处理经济学(特别是市场分析)WWW文献分类聚类网络日志，ClusterWeblogdatatodiscovergroupsofsimilaraccesspatterns05二月2023DataMining:ConceptsandTechniques4聚类的应用举例市场学:帮助营销人员将其客户数据分成不同的组，以更好的开拓目标市场土地使用:对地球上相似地区土地的使用观察数据保险行业:将汽车保险分组从而使得投保人的平均花费最高城市规划:根据的房子类型，价值，和地理位置确定住房团体地震研究:

根据大陆断层的聚类观测震中05二月2023DataMining:ConceptsandTechniques5什么是好的聚类？一个好的聚类方法使聚类结果簇内相似最大化簇间相似最小化

好的聚类方法不仅取决于它产生结果的相似程度，而且还与其执行有关聚类方法的好坏也与他发现部分或全部潜在模式的能力有关05二月2023DataMining:ConceptsandTechniques6衡量聚类的质量相异/相似尺度:我们用距离函数d(i,j)来表示相似度。有独立的“质量”函数来衡量聚类的好坏对区间标度变量，布尔变量，分类变量，序数变量，向量的距离函数的定义方式是不同的.不同的应用或数据含义，其衡量方法应该不同很难定义“足够相似”或“足够好”

结果往往是高度主观的05二月2023DataMining:ConceptsandTechniques7数据挖掘中聚类的要求

可伸缩性具有处理不同类型属性的能力具有处理动态数据的能力发现任意形状的聚类对于决定输入的参数的领域知识需求最小可以处理噪声和离群点不依赖于对象的输入次序高维性基于约束的聚类可释性和可用性05二月2023DataMining:ConceptsandTechniques8第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques9数据结果数据矩阵(二模)相异度矩阵(单模)05二月2023DataMining:ConceptsandTechniques10聚类分析中的数据类型区间标度变量二元变量分类、序数、和比例表度变量混合类型的变量05二月2023DataMining:ConceptsandTechniques11区间标度变量数据标准化计算均值绝对误差其中计算标准度量值(z-score)使用均值绝对误差比使用标准度量值稳定05二月2023DataMining:ConceptsandTechniques12对象间的相似度和相异度通常用距离来描述对象间的相似度或相异度最常用的是闵可夫斯基距离其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维数据，q是一个正整数。当q=1时，d是曼哈顿距离05二月2023DataMining:ConceptsandTechniques13对象间的相似度和相异度当q=2时，d为欧氏距离:d应满足的要求d(i,j)

0d(i,i)

=0d(i,j)

=d(j,i)d(i,j)

d(i,k)

+d(k,j)当然，我们也可以用加权距离或是其他的相异度衡量方法05二月2023DataMining:ConceptsandTechniques14二元变量二元变量的相依表使用对称二元变量描述对象间的距离：使用非对称二元变量描述对象间的距离：Jaccard系数(非对称二元变量相似度):ObjectiObjectj05二月2023DataMining:ConceptsandTechniques15二元变量间的相异度例：性别是对称属性剩下的属性为非对称二元变量令，Y=P=1,N=005二月2023DataMining:ConceptsandTechniques16分类变量一般的变量都不是二元变量，是可以取多于两个状态值的。如：红色，黄色，蓝色，绿色。方法1:不匹配率m:匹配的数目，p:全部变量的数目方法2:使用多个二元变量为每个分类变量的状态创建一个新的二元变量05二月2023DataMining:ConceptsandTechniques17序数变量序数变量可以是离散的或是连续的序数是很重要的，如：等级。可以当做是区间标度变量来对待将

xif

替换成他的秩

将每个变量的值映射到区间[0,1]内，这可以通过用代替第f个变量的第i个对象来实现利用求区间标度变量相异度的方法来计算序数变量的相异度05二月2023DataMining:ConceptsandTechniques18比例标度变量比例表度变量:在非线性的刻度（例如指数刻度）取正的度量值，近似的遵循下面的公式：

AeBt

或Ae-Bt

方法：采用处理区间标度变量的方法——并不是一个好的方法（比例可能被扭曲了）对比例标度进行对数变化yif=log(xif)将其看做连续的序数数据，将其秩看做区间标度变量05二月2023DataMining:ConceptsandTechniques19混合类型的变量一个数据库可能含有所以以上六种类型的变量对称二元变量，非对称二元变量，分类变量，序数变量，区间标度变量和比例标度变量用有效的公式将他们一起处理f

是二元变量或分类变量:dij(f)=0ifxif=xjf,ordij(f)=1否则f

是区间标度变量:使用标准距离f

是序数或比例标度变量计算秩rif

和zif

并将zif看做区间标度变量05二月2023DataMining:ConceptsandTechniques20向量对象向量对象:文献中的关键词，微阵列中的基因特征等。广泛应用:信息检索,生物学分类等.余弦度量Tanimoto系数05二月2023DataMining:ConceptsandTechniques21第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques22主要的聚类分析方法（I）划分法:将给定的数据，按照一定的标准构建k划分。典型的有：k均值法，k中心点算法，CLARA(聚类大型应用)。层次方法：

按照一定的标准，创建给定数据对象集的层次分解。典型的有：Diana,Agnes,BIRCH,ROCK,CAMELEON基于密度的方法：

基于密度或链接函数典型的有：DBSACN,OPTICS,DenClue05二月2023DataMining:ConceptsandTechniques23主要的聚类分析方法(II)基于网格的方法：

基于多层粒度结构经典的方法:STING,WaveCluster,CLIQUE基于模型的方法:为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合。经典的有：

EM,SOM,COBWEB基于频繁模式的方法:基于对频繁模式的分析。经典的方法:pCluster基于约束的方法:结合用户给定或面向应用的特殊约束进行聚类经典的方法:COD(含障碍物),基于约束的聚类05二月2023DataMining: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)05二月2023DataMining:ConceptsandTechniques25簇的质心，半径，直径

(fornumericaldatasets)质心:簇的“中央”半径:簇中元素到其质心的距离的平均值的平方根直径:没对元素的距离的平均值的平方根05二月2023DataMining:ConceptsandTechniques26第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques27划分算法：基本概念划分方法：

将给定n个对象的数据集D，划分成k个簇，使得：平方距离和最小给定k，找到一个k划分，找一个又划分标准来判断是最优的k划分全局最优:穷举法启发式的方法:k均值法和k中心点法K均值法

(MacQueen’67):每个簇由其中心来代替k-medoidsorPAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每个簇由其中的一个元素来代替05二月2023DataMining:ConceptsandTechniques28K均值聚类方法给定k，k均值算法的处理流程有以下四步组成：将数据集分成k个非空的子集计算当前每个簇的质心作为种子结点（质心是簇的中心点，或是平均值点）将每个对象指派到离他最近的种子结点的簇回到第二步，知道指派结果不再变动05二月2023DataMining:ConceptsandTechniques29K均值聚类方法例：012345678910012345678910012345678910012345678910K=2任意选择k个对象作为最初的簇的质心将每个对象指派到最相似的簇更新簇的质心更新簇的质心重新指派reassign05二月2023DataMining:ConceptsandTechniques30K均值法的优缺点优点:

效率很高:算法时间复杂度为O(tkn),其中，n为给定对象的数目，k是给定要划分的簇的个数，t是指反复迭代次数，通常k,t<<n.相比之下:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k))注:

常常会停留在局部最优处，而达不到全局最优。要找到全局最优往往要使用确定的退火算法或是遗传算法缺点：只适用于均值已被定义的情况，不能用于分类数据等。?需要预先指定要划分的簇的个数不能处理噪声或离群点不适于寻找图形不规则的簇05二月2023DataMining:ConceptsandTechniques31改进k均值算法改进的k均值算法的几个不同之处：挑选最初的k个均值计算相异度计算簇均值的算法可以处理分类数据的算法:k众数(Huang’98)用众数替代簇的均值使用新的相异度衡量方法来处理分类数据使用基于频率的方法来更新簇的众数处理数值数据和分类数据的混合类型:k-原型算法05二月2023DataMining:ConceptsandTechniques32K均值算法的问题Method?K均值算法对离群点非常敏感!因为一个对象如果具有很大的值，会对均值产生很大的影响，明显的扭曲数据的分布状态.K中心点法:用中心点来代替簇的均值，中心点就是簇的最中央的那个对象。01234567891001234567891001234567891001234567891005二月2023DataMining:ConceptsandTechniques33K中心点聚类算法找到簇的中心点作为簇的代表对象PAM(围绕中心点的划分，1987)在随机的选取k个代表对象做为中心点后，反复选择簇的更好的代表对象。当数据集很小时，PAM的效率是很高的，但是不适用于大的数据集CLARA

（聚类大型应用）(Kaufmann&Rousseeuw,1990)CLARANS

（基于随机搜索的聚类大型应用）(Ng&Han,1994):RandomizedsamplingFocusing+spatialdatastructure(Esteretal.,1995)05二月2023DataMining:ConceptsandTechniques34经典的k中心算法

(PAM)TotalCost=20012345678910012345678910K=2随机的选择k个对象作为代表对象将剩余的对象指派给离其最近的那个对象的簇随机的选取一个不是代表对象的对象Oramdom计算总的交换开销012345678910012345678910总开销

=26如果情况变好了就交换O和Oramdom循环，直至情况不再改变01234567891001234567891005二月2023DataMining:ConceptsandTechniques35PAM(围绕中心点的划分)(1987)PAM(KaufmanandRousseeuw,1987),builtinSplus使用实际的对象作为代表对象任选k个对象作为代表对象对任意一对没被选中的对象h和被选中的对象i计算总的交换开销TCih对任意一对

i

和

h,如果

TCih<0,h则用h来代替i然后将每个没被选中的对象指派到最近的代表对象的簇重复第2-3步，直至结果不在改变05二月2023DataMining:ConceptsandTechniques36PAM聚类:总的交换开销

TCih=jCjihjihttihjhitjtihj05二月2023DataMining:ConceptsandTechniques37PAM算法的问题在处理有离群点或噪声的数据时PAM算法要比k均值算法稳定，因为离群点或其他具有极端值的点对中心点的影响要小于对均值的影响PAM算法在处理小数据集的对象是效率很高的，但不适用于数据集很大的情况.每次迭代需要进行O(k(n-k)2

步

其中，n是对象的个数，k是划分成的簇的个数基于取样的方法,

CLARA(聚类大型应用)05二月2023DataMining:ConceptsandTechniques38CLARA(聚类大型应用)(1990)CLARA(KaufmannandRousseeuwin1990)用于统计学数据包分析，如S+对数据进行多重抽样，对每个抽样的样本用PAM算法聚类优点:可以处理比PAM算法能处理的大的数据集缺陷:有效性取决于抽样大小如果取样偏执了，那么对取样的一个好的聚类并不能代表对整个数据的好的聚类05二月2023DataMining:ConceptsandTechniques39CLARANS(基于随机搜索的CLARA)(1994)CLARANS(基于随机搜索的聚类算法)(NgandHan’94)CLARANS动态的抽取紧邻的随机样本聚类的过程可以看做搜素一个图，图中的每个结点是一个潜在解。当达到局部最优时，CLARANS会随机的选择一个新的结点开始，寻找新的局部最优他比PAM和CLARA算法更有效。通过利用空间数据结构的聚焦技术，可以进一步提高该算法的能力(Esteretal.’95)05二月2023DataMining:ConceptsandTechniques40第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques41层次方法使用距离矩阵作为聚类标准。此方法不需要输入簇的个数k，但是需要终止条件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚层次聚类法(AGNES)分裂层次聚类法(DIANA)05二月2023DataMining:ConceptsandTechniques42AGNES(凝聚层次聚类法)IntroducedinKaufmannandRousseeuw(1990)执行统计数据分析，

如：Splus使用单连接方法，和相异度矩阵

合并相异度最小的结点采用非递减模式进行最终，所有的结点都凝聚成一个簇05二月2023DataMining:ConceptsandTechniques43树状图:

簇是如何合并的Decomposedataobjectsintoaseverallevelsofnestedpartitioning(treeofclusters),calledadendrogram.Aclusteringofthedataobjectsisobtainedbycuttingthedendrogramatthedesiredlevel,theneachconnectedcomponentformsacluster.05二月2023DataMining:ConceptsandTechniques44DIANA(分裂层次聚类)IntroducedinKaufmannandRousseeuw(1990)执行统计数据分析如：SplusAGNES的逆序过程最终每个结点构成一个簇05二月2023DataMining:ConceptsandTechniques45最新的层次聚类分析法凝聚算法的主要缺陷不可伸缩型:时间复杂度至少是O(n2)不能取消以前的工作结合层次法和基于距离的方法的聚类BIRCH(1996):使用CF树，对对象的增量和动态聚类也非常有效ROCK(1999):对分类属性数据使用了链接，通过考虑成对点邻域情况进行聚类CHAMELEON(1999):使用动态建模的层次聚类算法05二月2023DataMining:ConceptsandTechniques46BIRCH(1996)Birch:利用层次方法的平衡迭代规约和聚类IncrementallyconstructaCF(ClusteringFeature)tree,ahierarchicaldatastructureformultiphaseclustering阶段1：扫描DB在内存中创建初始的CFtree阶段2：使用任意聚类算法聚类CFtree的叶节点

线性增长:扫描一次就可以的到较好的聚类，如果增加扫描次数就可以提高聚类质量缺陷：

只能处理数值数据,而且对数据的输入次序敏感05二月2023DataMining:ConceptsandTechniques47用BIRCH聚类特征向量聚类特征:

CF=(N,LS,SS)N:数据点个数LS:Ni=1=XiSS:Ni=1=Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)05二月2023DataMining:ConceptsandTechniques48BIRCH中的CF-Tree聚类特征:给定簇的统计汇总，他是簇的0阶矩，一阶矩，二阶矩汇总对象簇的主要信息，避免存储所有对象，有效地利用了存储空间CFtree是一个高度平衡树，他储存了层次聚类的聚类特征

非叶节点有子女或后裔非叶节点存储其子女的CF总和CFtree有两个参数分支因子：定义了每个非叶结点的子女的最大数目.阈值:存储在树的叶节点中子簇的最大直径05二月2023DataMining:ConceptsandTechniques49CFTree的结构CF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=7L=6RootNon-leafnodeLeafnodeLeafnode05二月2023DataMining:ConceptsandTechniques50聚类分类数据:ROCK算法ROCK:RObustClusteringusinglinKsS.Guha,R.Rastogi&K.Shim,ICDE’99主要思想使用链接来衡量相似度/相异度不急于距离计算复杂度:算法:基于取样的聚类随机取样采用链接聚类在磁盘中标号数据实验议会选举,迅速增长的数据05二月2023DataMining:ConceptsandTechniques51ROCK中的相似度衡量传统的方法无法很好的衡量分类数据的相似度，如，Jaccard系数例如：两个事务簇C1.<a,b,c,d,e>:{a,b,c},{a,b,d},{a,b,e},{a,c,d},{a,c,e},{a,d,e},{b,c,d},{b,c,e},{b,d,e},{c,d,e}C2.<a,b,f,g>:{a,b,f},{a,b,g},{a,f,g},{b,f,g}Jaccard系数会得到错误的聚类结果C1:0.2({a,b,c},{b,d,e}}to0.5({a,b,c},{a,b,d})C1&C2:couldbeashighas0.5({a,b,c},{a,b,f})基于Jaccard系数的相似度: 例.令

T1={a,b,c},T2={c,d,e}05二月2023DataMining:ConceptsandTechniques52ROCK中的链接方法链接：公共紧邻C1<a,b,c,d,e>:{a,b,c},

{a,b,d},{a,b,e},

{a,c,d},{a,c,e},{a,d,e},{b,c,d},

{b,c,e},{b,d,e},{c,d,e}C2<a,b,f,g>:{a,b,f},

{a,b,g},{a,f,g},{b,f,g}LetT1={a,b,c},T2={c,d,e},T3={a,b,f}link(T1,T2)=4,因为他们有四个公共近邻{a,c,d},{a,c,e},{b,c,d},{b,c,e}link(T1,T3)=3,他们有3个公共近邻{a,b,d},{a,b,e},{a,b,g}所以链接法比Jaccard系数更为有效05二月2023DataMining:ConceptsandTechniques53CHAMELEON:利用动态建模的层次聚类法CHAMELEON:byG.Karypis,E.H.Han,andV.Kumar’99基于动态建模来衡量相似度如果两个簇的互联性都很高并且它们又靠的很近就将其合并

Cure

忽略了簇的互联性，Rock

忽略了关于簇的邻近度信息算法分为两个阶段使用图划分算法：将对象划分为相对较小的字簇使用凝聚层次聚类算法：通过反复合并子簇来找到最终的簇05二月2023DataMining:ConceptsandTechniques54CHAMELEON的工作框架构造稀疏图划分图合并划分最终的簇数据集05二月2023DataMining:ConceptsandTechniques55CHAMELEON(聚类复杂对象)05二月2023DataMining:ConceptsandTechniques56第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques57基于密度的聚类方法Clusteringbasedondensity(localclustercriterion),suchasdensity-connectedpoints主要特征:可以发现任意形状的簇可以处理喊噪声的数据一次扫描需要给出密度参数的终止条件典型算法DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)(moregrid-based)05二月2023DataMining:ConceptsandTechniques58基于密度聚类的基本概念两个参数:Eps:邻域的最大半径MinPts:对象邻域内最少点数NEps(p): {q属于D|dist(p,q)<=Eps}直接密度可达:对象p从对象q出发时直接密度可达的，如果

P属于

NEps(q)核心对象条件:|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm05二月2023DataMining:ConceptsandTechniques59密度可达和密度相连密度可达:P是从q密度可达的，如果存在一连串的对象p1,…,pn,p1=q,pn=p

使得pi+1从

pi

出发直接密度可达密度相连P和q是密度互连的，如果存在o使得p和q都是从o出发密度可达的pqp1pqo05二月2023DataMining:ConceptsandTechniques60DBSCAN:基于高密度连同区域的基于密度的聚类方法依赖基于密度理论的分类：密度互连的对象组成的最大集合为一个簇在有噪声的空间数据库中可以发现任意形状的簇CoreBorderOutlierEps=1cmMinPts=505二月2023DataMining:ConceptsandTechniques61DBSCAN:算法任选一个对象p找到所有从p出发密度可达的对象（给定Eps和MinPts）如果p是核心对象，则形成一个簇如果p是边界对象，则没有对象从p出发直接密度可达，DBSCAN则会选择数据库中的另外一个对象重复上述步骤，直至所有的对象都被处理过05二月2023DataMining:ConceptsandTechniques62DBSCAN:对参数的敏感性05二月2023DataMining:ConceptsandTechniques63CHAMELEON(聚类复杂对象)05二月2023DataMining:ConceptsandTechniques64OPTICS:排序聚类方法(1999)OPTICS:通过点排序识别聚类结构Ankerst,Breunig,Kriegel,andSander(SIGMOD’99)根据基于密度的分类结构产生簇排序

该簇排序包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类有利于自动或交互式聚类分析，并能提供内在的聚类结构可以用图表示，或者其他的可视化工具05二月2023DataMining:ConceptsandTechniques65OPTICS:对DBSCAN一些扩展基于索引:

k=维数N=20p=75%M=N(1-p)=5Complexity:O(kN2)核心距离可达距离Dp2MinPts=5e=3cmMax(core-distance(o),d(o,p))r(p1,o)=2.8cm.r(p2,o)=4cmoop105二月2023DataMining:ConceptsandTechniques66可达距离Cluster-orderoftheobjects无定义‘05二月2023DataMining:ConceptsandTechniques67基于密度聚类:OPTICS及其应用05二月2023DataMining:ConceptsandTechniques68DENCLUE:使用密度分布函数DENsity-basedCLUstEringbyHinneburg&Keim(KDD’98)使用密度分布函数:主要特征固定的数学基础可以处理含有大量噪声的数据可以对高维数据集中任意形状的簇做简洁的数学描述比现有的其他算法要快得多(e.g.,DBSCAN)但是需要大量的参数05二月2023DataMining:ConceptsandTechniques69使用网格单元，但是只保存网格单元中实际包含的数据点的个数信息，并用树结构来管理这些网格影响函数:描述数据点在其邻域内的影响数据空间的整体密度可以用所有数据点的影响函数计算出簇可以通过识别密度吸引点数学确定密度吸引点是全局密度函数的局部极大值Denclue:基本技术05二月2023DataMining:ConceptsandTechniques70密度吸引点05二月2023DataMining:ConceptsandTechniques71Center-DefinedandArbitrary05二月2023DataMining:ConceptsandTechniques72第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques73基于网格的聚类方法使用多分辨率的网格数据结构相关的方法STING(aSTatisticalINformationGridapproach)byWang,YangandMuntz(1997)WaveClusterbySheikholeslami,Chatterjee,andZhang(VLDB’98)利用小波变换的多分辨率聚类方法CLIQUE:Agrawal,etal.(SIGMOD’98)处理高维数据05二月2023DataMining:ConceptsandTechniques74STING:统计信息网格法Wang,YangandMuntz(VLDB’97)将空间区域分成矩形单元存在多级矩形单元对应不同级别的分辨率05二月2023DataMining:ConceptsandTechniques75STING聚类方法每个高层单元划分成多个低一层的单元将每个单元的统计信息都计算并存储起来，用于查询处理高层单元的统计参数可以很容易的从低层单元的参数计算得到计数，均值，标准差，最大值，最小值分布类型—正态的，均匀的等.使用从顶向下方法回答空间数据查询从预先选定的一层开始，通常该层含有较少量的单元对当前层的每个单元计算器相关的置信度区间

05二月2023DataMining:ConceptsandTechniques76STING删除不相关的单元，不再进一步考虑处理完当前层后处理下一个较低层

重复此过程，直至达到最低层优点:不依赖于查询信息，有利于并行处理和增量更新时间复杂度为：O(K),其中k是最低层网格单元的数量缺点:所有簇的边界不是水平的就是竖直的，没有斜的分界线05二月2023DataMining:ConceptsandTechniques77WaveCluster:利用小波分析聚类(1998)Sheikholeslami,Chatterjee,andZhang(VLDB’98)对特征空间进行小波变换的多分辨率聚类方法如何应用小波变换来找到簇通过在数据空间强加一个多维网格结构来汇总数据用一个n为特征空间来代替这些多维空间数据对特征空间进行小波变换，在变换后的空间中发现密集区域多次应用小波变换05二月2023DataMining:ConceptsandTechniques78小波变换小波变换:一种信号处理技术，它将一个信号分解成不同频率的子波段数据变换，以便在不同的分辨率水平保留对象间的相对距离使得数据的自然簇变得更加容易分辨05二月2023DataMining:ConceptsandTechniques79WaveCluster算法输入参数#ofgridcellsforeachdimensionthewavelet,andthe#ofapplicationsofwavelettransform在聚类中为什么可以用小波变换?使用帽子形状的过滤器来强调尖端簇区域，同时弱化其边界的信息

有效地去除离群点，多分辨率，开销低主要特征:复杂度O(N)可以发现任意形状的簇对噪声和数据的输入顺序不敏感仅适用于低维数据基于网格与基于密度相结合05二月2023DataMining:ConceptsandTechniques80分层与变换首先将数据分成m维网格结构，然后应用小波变换a)scale1:高分辨率b)scale2:中等分辨率c)scale3:低分辨率05二月2023DataMining:ConceptsandTechniques81第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques82基于模型的聚类什么是基于模型的聚类?优化给定数据与某个数学模型间的拟合

基于这个假设，数据根据潜在的混合概率分布生成典型方法统计方法EM(Expectationmaximization),AutoClass机器学习法MachinelearningapproachCOBWEB,CLASSIT神经网络法NeuralnetworkapproachSOM(Self-OrganizingFeatureMap)05二月2023DataMining:ConceptsandTechniques83EM—期望最大化EM—一种流行的迭代求精算法可以看做是k均值法的扩展根据一个代表隶属度概率的权重将对象指派到簇(prob.distribution)新的均值基于加权的重量来计算主要思想对参数进行初始猜测反复估计参数来产生的混合密度对每个对象重新打分重新打分后的对象又用来更新参数估计每个对象赋予一个概率，假定它是给定簇的成员，具有一定属性值集合的可能性。算法收敛很快，但可能达不到全局最优05二月2023DataMining:ConceptsandTechniques84EM算法随机的选取k个对象代表簇的均值或中心按如下两个步骤反复求精参数

期望步：用以下概率将每个对象XiXi

指派到簇Ck最大化步:估计模型参数05二月2023DataMining:ConceptsandTechniques85给定一些观察数据x，假设x符合如下高斯分布：求混合高斯分布的三组参数05二月2023DataMining:ConceptsandTechniques86该混合高斯分布一共有K个分布，并且对于每个观察

到的x，如果我们同时还知道它属于K中的哪一个分布，则我们可以根据最大似然估计求出每个参数。结论：特别注意是个向量，而是个数值。表示属于第k个高斯分布的观察数据x。05二月2023DataMining:ConceptsandTechniques87实际问题观察数据x属于哪个高斯分布是未知的，所以要用

EM算法来解决这种实际问题。05二月2023DataMining:ConceptsandTechniques88EM算法过程：1、用随机函数初始化K个高斯分布的参数，同时保证Expectation2、依次取观察数据x，比较x在K个高斯函数中概率的大小，把x归类到这K个高斯中概率最大的一个。05二月2023DataMining:ConceptsandTechniques89Maximum3、用最大似然估计，使观察数据是x的概率最大，因为已经在第2步中分好类了，所以，即简单问题的求法。4、返回第2步用第3步新得到的参数来对观察数据x

重新分类。直到下式概率（最大似然函数）达到最大。05二月2023DataMining:ConceptsandTechniques90问题求解过程：05二月2023DataMining:ConceptsandTechniques91概念分类概念分类一种机器学习聚类方法给定一组为标记的对象，产生对象的模式分类找出每组对象的特征描述，其中每组对象代表一个概念或类COBWEB(Fisher’87)

一种流行的、简单的、增量概念分类以分类树的形式创建层次聚类每个结点代表一个概念，包含对该概念的概率描述05二月2023DataMining:ConceptsandTechniques92COBWEB聚类方法分类树05二月2023DataMining:ConceptsandTechniques93概念分类COBWEB的缺陷它基于这样一个假设，各个属性的概念分布是彼此统计独立的。但属性之间常常存在相关不适用于聚类大型的数据库Notsuitableforclusteringlargedatabasedata–skewedtreeandexpensiveprobabilitydistributionsCLASSIT是对COBWEB的扩展，用以处理连续性数据的增量聚类与COBWEB算法存在类似的问题

AutoClass(CheesemanandStutz,1996)使用贝叶斯统计分析法来估计簇的数目在工业中非常流行05二月2023DataMining:ConceptsandTechniques94神经网络方法神经网络方法将每个簇看成是一个标本，作为簇的原型新的对象可以根据某种距离度量分布到其标本最相似的簇经典的方法SOM(自组织特征映射)竞争学习法Involvesahierarchicalarchitectureofseveralunits(neurons)神经元按照Neuronscompeteina“winner-takes-all”fashionfortheobjectcurrentlybeingpresented05二月2023DataMining:ConceptsandTechniques95自组织特征映射(SOM)SOMs,也称之为拓扑有序映射或Kohonen自组织特征映射(KSOMs)目标是用低维（通常是2维到3维）目标空间的点来表示高维源空间中的所有点，尽可能的保持点见得距离和邻近关系类似于k均值算法:簇的中心往往处于特征或属性空间的一个低维流形中聚类通过若干单元竞争当前对象来进行权重向量最接近当前对象的单元成为赢家或活跃点调整获胜单元及其最近邻的权重SOM被认为类似于大脑的处理过程对用2维或3维的方式观察高维数据时很有效的05二月2023DataMining:ConceptsandTechniques96使用SOM聚类的web文档用SOM算法对12088篇web、文章聚类的结果右边的图片：对关键词“mining”进行下钻的结果05二月2023DataMining:ConceptsandTechniques97第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques98聚类高维数据聚类高维数据应用：文本文档，DNA微序列数据主要挑战:很多不相关的维可能屏蔽真实的簇距离度量变得无意义了——数据特别稀疏时位于不同维的数据点可以认为是等距的簇可能仅存在于某些子空间内方法特征变换:仅适用于大部分维都是相关的情况下如：PCA（主成分分析）和SVD（支撑向量机）仅适用于特征是高度相关的/冗余的特征选择:wrapperorfilterapproachesusefultofindasubspacewherethedatahaveniceclusters子空间聚类：

在所有可能的子空间中寻找簇CLIQUE,ProClus,基于频繁模式的聚类05二月2023DataMining:ConceptsandTechniques99维灾难

(graphsadaptedfromParsonsetal.KDDExplorations2004)一维的数据通常是在一个相关的区域内的增加一个维，是数据点沿这个维延伸，则会使数据变得分离增加更多的维，会使得数据点之间更加分离，高维数据是极端稀疏的数据度量变得没有意义了—当数据特别稀疏时我们可以认为位于不同维的数据点是距离相等的05二月2023DataMining:ConceptsandTechniques100为什么要对子空间聚类?

(adaptedfromParsonsetal.SIGKDDExplorations2004)簇可能仅仅是存在于某个子空间中子空间聚类:找出所有可能的子空间内的簇05二月2023DataMining:ConceptsandTechniques101CLIQUE(维增长子空间聚类方法)

Agrawal,Gehrke,Gunopulos,Raghavan(SIGMOD’98)自动的将高维数据空间划分成子空间以便更好的聚类

CLIQUE可以看做是基于密度的也可以看做是基于网格的他将每一维划分成相同数目的等距的区域将一个m维的数据空间划分成互不重叠的矩形单元如果一个单元中包含的数据点的个数超过了输入的参数则这个单元为稠密单元同一子空间中彼此相连的稠密单元构成的最大集合为一个簇05二月2023DataMining:ConceptsandTechniques102CLIQUE:主要步骤将数据空间划分，并找到每个划分单元中的数据点的个数.找出含有簇的子空间，使用Apriori规则剪枝确定簇找出所有相关子空间中的稠密单元找出相关子空间中的所有相连的稠密单元.生成簇的最小覆盖（逻辑描述）为每个簇确定覆盖所有相连的稠密单元的最大区域为每个簇确定一个最小覆盖05二月2023DataMining:ConceptsandTechniques103Salary(10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050

=305二月2023DataMining:ConceptsandTechniques104CLIQUE的优缺点优点自动的找出高维数据的簇存在的子空间对数据的输入顺序不敏感，不需要假定数据的规范分布

它随着输入规模线性的伸缩，当数据维数增加时具有良好的伸缩性缺点作为算法简洁的代价，聚类结果的精度可能会降低05二月2023DataMining:ConceptsandTechniques105基于频繁模式的方法适合用于高维数据(如：聚类文本文档，微阵列数据)Projectedsubspace-clustering:whichdimensionstobeprojectedon?CLIQUE,ProClusFeatureextraction:开销大，效率低？使用频繁模式是因为其具有下列性质频繁度是固有的性质挖掘频繁模式的开销不是很大经典方法基于频繁项的文件聚类通过微阵列数据分析中的模式相似性聚类(pClustering)05二月2023DataMining:ConceptsandTechniques106基于相似模式的聚类(p-Clustering)右图：只包含3个对象的多维微阵列原始数据很难发现其中的模式下图：选择属性的子集后的平移和缩放模式05二月2023DataMining:ConceptsandTechniques107p-Clustering产生的原因?微阵列数据分析需要聚类具有上千属性的数据发现平移和缩放模式使用欧氏距离聚类？——不能发现平移模式

对数据变换后得到新的属性如Aij=ai–aj再对其聚类?—将引入

N(N-1)个属性Bi-cluster使用均方差得分矩阵变换matrix(I,J)其中子矩阵称为称为δ-双簇，如果对于某个δ>0有H(I,J)≤δδ双簇的问题δ双簇的子矩阵不一定是δ双簇由于取平均的影响，双簇可能包含一些不符合要求的离群点，但仍满足一个非常小的

δ阈值05二月2023DataMining:ConceptsandTechniques108p-Clustering:基于相似模式的聚类给定对象x,y属于O，属性a,b属于T,pScore（X）是一个2*2阶矩阵如果（O,T）中任意的2*2阶矩阵X都有pScore(X)≤δ（δ>0）则（O,T）对形成pclusterδ-pCluster的性质向下闭包性产生的簇比双簇方法产生的更同源(thusthename:pair-wiseCluster)为了有效的挖掘引入模式增长算法

用比例模式，取对数可以得到pScore的形式为05二月2023DataMining:ConceptsandTechniques109第七章聚类分析什么是聚类分析？聚类分析中的数据类型聚类分析的主要方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类高维数据基于约束的聚类分析

离群点分析小结05二月2023DataMining:ConceptsandTechniques110为什么要有机遇约束的聚类分析?需要用户反馈:用户最了解他们的需求参数少，但是用户定义的约束多，05二月2023DataMining:ConceptsandTechniques111基于约束聚类分析的分类聚类应用:设计有用户知道的聚类分析聚类分析中的不同约束:对个体对象的约束(应首先选择)聚类价值在