第十讲 聚类分析

第十讲

聚类分析1聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法（自学）基于模型的方法（自学）高维数据聚类（自学）基于约束的聚类（自学）离群点分析（自学）小结2什么是聚类分析?簇(cluster):数据对象的集合同一簇中对象相似不同簇中对象相异聚类(clustering):将物理或抽象对象的集合分成相似的对象类的过程聚类分析在数据中按照数据的特征找出相似处，将相似的数据对象分组到一个聚类无指导学习(Unsupervisedlearning):没有预定义的类典型应用作为一个独立的工具，用于观察数据的分布作为其他算法的预处理步骤3聚类：多学科、广泛的应用模式识别(PatternRecognition)空间数据分析(SpatialDataAnalysis)在GIS中，通过聚类特征空间，创建主题地图检测空间聚类或其他空间挖掘任务图象处理经济科学(特别是市场研究)WWW文档分类聚类Weblog数据，发现类似的存取模式组4ExamplesofClusteringApplications市场:帮助市场分析员发现顾客的不同类别，并使用这些知识开发目标市场程序。国土利用:帮助识别地球观测数据库中国土利用相似的区域。保险:赔付较高保险金额的保险持有者城市计划:根据房子的类型、价值和地理位置对城市中房屋的分组识别5Quality:WhatIsGoodClustering?好的聚类方法：高内聚、低耦合聚类结果的质量依赖于方法和实现中使用的相似度度量。聚类方法的质量还可以由它所发现一些或全部隐藏模式的能力所衡量6MeasuretheQualityofClustering相异度/相似度矩阵:相似度表现为距离函数，矩阵

d(i,j)对于不同的数据类型，距离函数(distancefunctions)的定义可能有很大的差别：

区间标量变量、二元变量、分类变量、序数变量和向量变量权重的设置与应用中的不同变量有关。很难定义怎样是“足够相似”或是“足够好”，因为其答案是相当主观的。7RequirementsofClusteringinDataMining可伸缩的处理不同类型属性的能力处理动态数据的能力处理任意形状的聚类输入参数的确定需要尽量少的领域知识处理带噪声数据的能力对数据数据的顺序不敏感高维性满足用户指定的约束可解释性和可用性8聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法高维数据聚类基于约束的聚类离群点分析小结9DataStructures数据矩阵N个对象，p个变量(双模)相异度矩阵d(i,j):对象i和j间的相异度(单模)10TypeofdatainclusteringanalysisInterval-scaledvariables(区间标度变量)BinaryVariables(二元变量)Nominal,ordinal,andratiovariables(分类、序数和比例调度变量)混合类型变量11区间标度变量区间标度变量：粗略线性标度的连续度量。如重量、经纬度、气温等数据标准化？单位不同对聚类结果影响大计算均值绝对偏差(meanabsolutedeviation)其中计算标准度量值(standardizedmeasurement)(z-score)使用均值绝对偏差比标准差对于离群点有更好的鲁棒性。12对象间的相似度或相异度距离：通常用于衡量两个对象之间的相似度或相异度闵可夫斯基距离(Minkowskidistance):其中，i=(xi1,xi2,…,xip)和

j=(xj1,xj2,…,xjp)是p维对象,q是非负整数如果q=1,d

是曼哈顿距离(Manhattandistance)13q=2时,d是欧几里德距离(Euclideandistance)特征d(i,j)

0d(i,i)

=0d(i,j)

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

d(i,k)

+d(k,j)(三角不等式)可对某些变量根据重要性赋予权重14二元变量二元变量只有两个状态:0or1二元变量的相依表对称二元变量(两个状态具有同等价值和相同的权值)的距离度量:非对称二元变量的距离度量:(通常将出现几率较小的结果编码为1)

Jaccard系数(非对称二元变量的相似度):ObjectiObjectj15DissimilaritybetweenBinaryVariablesExamplegenderisasymmetricattributetheremainingattributesareasymmetricbinaryletthevaluesYandPbesetto1,andthevalueNbesetto016分类变量分类变量是二元变量的推广，它可以取多于两个状态值。eg.,red,yellow,blue,greenm:匹配数,p:全部变量数目，不匹配率：17序数变量序数变量可以是离散的也可以是连续的序数变量中，顺序很重要,如，职称在计算对象的相异度时，序数变量的处理与区间标度变量非常类似第i个对象的f值为xif

，变量f有Mf个有序的状态，表示秩评定1，…,Mf,用对应的秩代替xif

。将变量的值映射到[0,1]，将第i个对象的第f个变量表示为使用区间标量的相异度计算。18比例标度变量比例标度变量:在非线性的刻度取正的度量值，近似地遵循指数比例，如AeBtorAe-Bt

方法:采用与处理区间标度变量同样的方法处理。(刻度可能被扭曲)应用对数变换yif=log(xif)将它们看作连续的序数数据，将其秩作为区间值来对待。19混合类型变量数据库可能包含下述六种类型变量对称二元变量、不对称二元变量、分类变量、序数变量、区间变量与比例标度变量f

是二元或分类变量:如果xif=xjf,dij(f)=0；否则dij(f)=1f

是区间变量:使用规范化后的距离f是序数或比例标度变量计算秩rif

并且

将zif

作为区间变量20VectorObjectsVectorobjects:keywordsindocuments,genefeaturesinmicro-arrays,etc.Broadapplications:informationretrieval,biologictaxonomy,etc.CosinemeasureAvariant:Tanimotocoefficient21聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法高维数据聚类基于约束的聚类离群点分析小结22主要聚类方法的分类划分方法:构建数据的k个划分，每个划分表示一簇。Typicalmethods:k-means,k-medoids,CLARANS层次方法:构建给定数据对象集的层次分解Typicalmethods:Diana,Agnes,BIRCH,ROCK,CAMELEON基于密度的方法:基于连接和密度函数Typicalmethods:DBSACN,OPTICS,DenClue23主要聚类方法的分类(II)基于网格的方法:基于多层网格结构Typicalmethods:STING,WaveCluster,CLIQUE基于建模的方法:为簇建立最合适的假设模型Typicalmethods:

EM,SOM,COBWEB基于频繁模式基于频繁模式的分析Typicalmethods:pCluster用户指导的或基于约束的方法:考虑用户指定或应用指定的约束所作的聚类Typicalmethods:COD(obstacles),constrainedclustering24典型的计算簇间距离的方法Singlelink:一个簇中元素与另一个簇中元素的最近距离,i.e.,dis(Ki,Kj)=min(tip,tjq)Completelink:一个簇中元素与另一个簇中元素的最远距离,i.e.,dis(Ki,Kj)=max(tip,tjq)Average:一个簇中元素与另一个簇中元素的平均距离,i.e.,dis(Ki,Kj)=avg(tip,tjq)Centroid:两个簇的质心距离,i.e.,dis(Ki,Kj)=dis(Ci,Cj)Medoid:两个簇的中心点距离,i.e.,dis(Ki,Kj)=dis(Mi,Mj)Medoid:onechosen,centrallylocatedobjectinthecluster25Centroid,RadiusandDiameterofaCluster(fornumericaldatasets)Centroid:the“middle”ofaclusterRadius:squarerootofaveragedistancefromanypointoftheclustertoitscentroidDiameter:squarerootofaveragemeansquareddistancebetweenallpairsofpointsinthecluster26聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法高维数据聚类基于约束的聚类离群点分析小结27划分算法：基本概念划分方法:

构建数据库的一个划分，将n个对象分到k个簇中,使得平方距离和最小给定k,找到k个簇的划分全局优化:列举所有的划分启发式方法:k-means

与k-medoids

方法k-means(MacQueen’67):用簇中心表示簇k-medoidsPAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):用簇中的一个对象来表示簇28K-Means:k均值方法给定k表示簇的数目:从D中任意选择k个对象作为初始簇中心。Repeat根据簇中对象的均值，将每个对象(再)指派到最相似的簇更新簇均值，即计算每个簇中对象的均值Until不再发生变化29TheK-MeansClusteringMethod

Example012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign30CommentsontheK-MeansMethodStrength:

计算复杂度:O(tkn),t表示迭代次数.通常的,k,t<<n.Comparing:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k))Weakness只有均值有定义时才能使用需要指定k不能处理噪声数据或离群点不适合发现非凸形状的簇31VariationsoftheK-MeansMethodk-means方法的变种初始K个均值的选择相异度的计算计算簇均值的策略处理分类数据:k-modes(Huang’98)用modes(众数：一组中出现最频繁的数或数列)来代替簇均值用新的相异度度量处理分类对象采用基于频率的方法更新簇众数处理分类数据和数值形混合数据的方法:k-prototype32K-Means方法的难题k-means对离群点太敏感具有很大极端值的一个对象可能显著地扭曲数据，平方误差函数的使用更加恶化了这一影响K-Medoids:使用一个参考点而不是均值来代表簇,medoids

表示位于簇最中心位置的一个对象。

01234567891001234567891001234567891001234567891033

K中心点方法(K-Medoids)Findrepresentativeobjects,calledmedoids,inclustersPAM(围绕中心点的划分PartitioningAroundMedoids,1987)startsfromaninitialsetofmedoidsanditerativelyreplacesoneofthemedoidsbyoneofthenon-medoidsifitimprovesthetotaldistanceoftheresultingclusteringPAM

对小规模数据性能良好，但不善于处理大规模数据CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):RandomizedsamplingFocusing+spatialdatastructure(Esteretal.,1995)34ATypicalK-MedoidsAlgorithm(PAM)TotalCost=20012345678910012345678910K=2ArbitrarychoosekobjectasinitialmedoidsAssigneachremainingobjecttonearestmedoidsRandomlyselectanonmedoidobject,OramdomComputetotalcostofswapping012345678910012345678910TotalCost=26SwappingOandOramdomIfqualityisimproved.DoloopUntilnochange01234567891001234567891035PAM(PartitioningAroundMedoids)(1987)PAM(KaufmanandRousseeuw,1987),builtinSplus使用实际对象表示簇随机选择k个代表点对于每个未被选择对象h和被选择对象i，计算总的转换代价TCih；聚类结果的质量用代价函数来评估Foreachpairofiandh,IfTCih<0,iisreplacedbyh将每个未被选择对象赋值给最靠近的代表对象所在的簇repeatsteps2-3untilthereisnochange36PAMClustering:TotalswappingcostTCih=jCjihjihttihjhitjtihjh代替i吗？j当前属于i所代表的簇,并且j离h比t近,即d(j,h)<=d(j,t

),此处t是j的第二接近中心点。这样,如果i被h替换作为中心点,j将属于h所代表的簇j当前属于i所代表的簇,并且j离t比h近,即d(j,h)>=d(j,t),此处t是j的第二接近中心点。这样,如果i被h替换作为中心点,j将属于t所代表的簇.j当前属于另一个非i所代表的簇,t是j所属簇的代表对象,并且j离h比t近,即d(j,h)<d(j,t)。这样,如果i被h替换作为中心点,j将从t所代表的簇中跳入h所代表的簇中37WhatIstheProblemwithPAM?Pamismorerobustthank-meansinthepresenceofnoiseandoutliersbecauseamedoidislessinfluencedbyoutliersorotherextremevaluesthanameanPamworksefficientlyforsmalldatasetsbutdoesnotscalewellforlargedatasets.O(k(n-k)2)foreachiteration wherenis#ofdata,kis#ofclustersSamplingbasedmethod, CLARA(ClusteringLARgeApplications)38CLARA(ClusteringLargeApplications)(1990)CLARA(KaufmannandRousseeuwin1990)Builtinstatisticalanalysispackages,suchasS+Itdrawsmultiplesamplesofthedataset,appliesPAMoneachsample,andgivesthebestclusteringastheoutputStrength:dealswithlargerdatasetsthanPAMWeakness:EfficiencydependsonthesamplesizeAgoodclusteringbasedonsampleswillnotnecessarilyrepresentagoodclusteringofthewholedatasetifthesampleisbiased39CLARANS(“Randomized”CLARA)(1994)CLARANS(AClusteringAlgorithmbasedonRandomizedSearch)(NgandHan’94)CLARANSdrawssampleofneighborsdynamicallyTheclusteringprocesscanbepresentedassearchingagraphwhereeverynodeisapotentialsolution,thatis,asetofkmedoidsIfthelocaloptimumisfound,CLARANSstartswithnewrandomlyselectednodeinsearchforanewlocaloptimumItismoreefficientandscalablethanbothPAMandCLARAFocusingtechniquesandspatialaccessstructuresmayfurtherimproveitsperformance(Esteretal.’95)40聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法高维数据聚类基于约束的聚类离群点分析小结41HierarchicalClusteringUsedistancematrixasclusteringcriteria.Thismethoddoesnotrequirethenumberofclusterskasaninput,butneedsaterminationconditionStep0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)42AGNES(AgglomerativeNesting)IntroducedinKaufmannandRousseeuw(1990)Implementedinstatisticalanalysispackages,e.g.,SplusUsetheSingle-Linkmethodandthedissimilaritymatrix.MergenodesthathavetheleastdissimilarityGooninanon-descendingfashionEventuallyallnodesbelongtothesamecluster43Dendrogram:ShowsHowtheClustersareMerged通常，使用树状图（dendrogram.）的树形结构表示层次聚类的过程，它展示出对象是如何一步步分组的。44DIANA(DivisiveAnalysis)IntroducedinKaufmannandRousseeuw(1990)Implementedinstatisticalanalysispackages,e.g.,SplusInverseorderofAGNESEventuallyeachnodeformsaclusteronitsown45RecentHierarchicalClusteringMethodsMajorweaknessofagglomerativeclusteringmethodsdonotscalewell:timecomplexityofatleastO(n2),wherenisthenumberoftotalobjectscanneverundowhatwasdonepreviouslyIntegrationofhierarchicalwithdistance-basedclusteringBIRCH(1996):usesCF-treeandincrementallyadjuststhequalityofsub-clustersROCK(1999):clusteringcategoricaldatabyneighborandlinkanalysisCHAMELEON(1999):hierarchicalclusteringusingdynamicmodeling46BIRCH(1996)Birch:BalancedIterativeReducingandClusteringusingHierarchies(Zhang,Ramakrishnan&Livny,SIGMOD’96)IncrementallyconstructaCF(ClusteringFeature)tree,ahierarchicaldatastructureformultiphaseclusteringPhase1:scanDBtobuildaninitialin-memoryCFtree(amulti-levelcompressionofthedatathattriestopreservetheinherentclusteringstructureofthedata)Phase2:useanarbitraryclusteringalgorithmtoclustertheleafnodesoftheCF-treeScaleslinearly:findsagoodclusteringwithasinglescanandimprovesthequalitywithafewadditionalscansWeakness:handlesonlynumericdata,andsensitivetotheorderofthedatarecord.47ClusteringFeatureVectorinBIRCHClusteringFeature:

CF=(N,LS,SS)N:NumberofdatapointsLS:Ni=1=XiSS:Ni=1=Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)48CF-TreeinBIRCHClusteringfeature:给定子簇的统计汇总:从统计学角度看，它是簇的零阶矩，一阶矩和二阶矩。使用聚类特征来汇总对象簇的信息，从而避免存储所有对象。CF树是高度平衡的树，它存储了层次结构的聚类特征。

Anonleafnodeinatreehasdescendantsor“children”ThenonleafnodesstoresumsoftheCFsoftheirchildrenACFtreehastwoparameters分支因子(Branchingfactor):specifythemaximumnumberofchildren.阈值（threshold）:maxdiameterofsub-clustersstoredattheleafnodes49TheCFTreeStructureCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=7L=6RootNon-leafnodeLeafnodeLeafnode50ClusteringCategoricalData:TheROCKAlgorithmROCK:RObustClusteringusinglinKs

S.Guha,R.Rastogi&K.Shim,ICDE’99MajorideasUselinkstomeasuresimilarity/proximityNotdistance-basedComputationalcomplexity:Algorithm:sampling-basedclusteringDrawrandomsampleClusterwithlinksLabeldataindiskExperimentsCongressionalvoting,mushroomdata51SimilarityMeasureinROCK传统聚类算法使用的距离函数对分类数据不能产生高质量的簇。JaccardcoefficientExample:Twogroups(clusters)oftransactionsC1.<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}Jaccardco-efficientmayleadtowrongclusteringresultC1: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})Jaccardco-efficient-basedsimilarityfunction: Ex.LetT1={a,b,c},T2={c,d,e}52LinkMeasureinROCKLinks:#ofcommonneighborsC1<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,sincetheyhave4commonneighbors{a,c,d},{a,c,e},{b,c,d},{b,c,e}link(T1,T3)=3,sincetheyhave3commonneighbors{a,b,d},{a,b,e},{a,b,g}ThuslinkisabettermeasurethanJaccardcoefficient53CHAMELEON:HierarchicalClusteringUsingDynamicModeling(1999)CHAMELEON:byG.Karypis,E.H.Han,andV.Kumar’99MeasuresthesimilaritybasedonadynamicmodelTwoclustersaremergedonlyiftheinterconnectivity

andcloseness(proximity)betweentwoclustersarehighrelativetotheinternalinterconnectivityoftheclustersandclosenessofitemswithintheclustersCureignoresinformationaboutinterconnectivityoftheobjects,RockignoresinformationabouttheclosenessoftwoclustersAtwo-phasealgorithmUseagraphpartitioningalgorithm:clusterobjectsintoalargenumberofrelativelysmallsub-clustersUseanagglomerativehierarchicalclusteringalgorithm:findthegenuineclustersbyrepeatedlycombiningthesesub-clusters54OverallFrameworkofCHAMELEONConstructSparseGraphPartitiontheGraphMergePartitionFinalClustersDataSet55CHAMELEON(ClusteringComplexObjects)56聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法高维数据聚类基于约束的聚类离群点分析小结57Density-BasedClusteringMethods基于密度的聚类，将簇看作是数据空间中被低密度区域(代表噪声)分割的稠密对象区域Majorfeatures:DiscoverclustersofarbitraryshapeHandlenoiseOnescanNeeddensityparametersasterminationconditionSeveralinterestingstudies:DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)(moregrid-based)58Density-BasedClustering:BasicConceptsTwoparameters:给定对象半径ε内的邻域称为该对象的ε邻域如果对象的ε邻域至少包含最小数目MinPts的对象，则称该对象为核心对象直接密度可达(Directlydensity-reachable):给定一个对象集合D，如果p在q的邻域内，q是一个核心对象，则称对象p从对象q出发是直接密度可达。pqMinPts=5Eps=1cm59密度可达与密度相连密度可达(Density-reachable)如果存在一个对象链，p1,…,pn,p1=q,pn=p

；pi+1

是从Pi对于ε和MinPts是直接密度可达，则对象p是从对象q关于ε和MinPts密度可达的。密度连接(Density-connected)如果存在对象o∈D，使对象p和q都是从o关于ε和MinPts密度可达，则对象p到q是关于ε和MinPts密度相连的。pqp1pqo60DBSCAN:DensityBasedSpatialClusteringofApplicationswithNoise簇被定义为密度连接点的最大集合能在带有噪声的空间数据库中发现任意形状的簇CoreBorderOutlierEps=1cmMinPts=561DBSCAN:TheAlgorithm随机选择点p检索从p开始的所有密度可达点。如果p是核心点，则形成一个簇如果p是边缘点，则没有从p密度可达的点；DBSCAN访问数据库中其他点继续处理，直到所有点都被处理62X5X2X3X4X6X7X8X1X9X102ε＝2Minpts＝2222222222ExampleofDBSCAN63DBSCAN:SensitivetoParameters64CHAMELEON(ClusteringComplexObjects)65OPTICS:ACluster-OrderingMethod(1999)OPTICS:OrderingPointsToIdentifytheClusteringStructure(通过点排序识别聚类结构)Ankerst,Breunig,Kriegel,andSander(SIGMOD’99)产生基于密度聚类结构的数据库的特定顺序它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类。可以用图形化或可视化技术来表示66OPTICS:SomeExtensionfromDBSCAN核心距离使{P}成为核心对象的最小ε’可达距离p2MinPts=5e=3cmp的核心距离和p与q之间欧几里德距离的较大值r(p1,o)=2.8cm.r(p2,o)=4cmoop167DENCLUE:UsingStatisticalDensityFunctionsDENsity-basedCLUstEringbyHinneburg&Keim(KDD’98)使用统计密度函数:Majorfeatures有着坚实的数学基础对具有大量噪声的数据集的分析很有好处能对高维数据集的任意形状的聚类做复杂的数学描述比现存算法快得多(e.g.,DBSCAN)需要大量参数68Usesgridcellsbutonlykeepsinformationaboutgridcellsthatdoactuallycontaindatapointsandmanagesthesecellsinatree-basedaccessstructure影响函数:每个数据点的影响可以用影响函数来建模，描述数据点在其邻域内的影响数据空间的整体密度可以用所有数据点的影响函数的和建模。簇可以通过识别密度吸引点数学确定。密度吸引点是全局密度函数的局部极大值。Denclue:TechnicalEssence69聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法高维数据聚类基于约束的聚类离群点分析小结70Grid-BasedClusteringMethod多分辨率网格数据结构SeveralinterestingmethodsSTING(aSTatisticalINformationGridapproach)byWang,YangandMuntz(1997)WaveClusterbySheikholeslami,Chatterjee,andZhang(VLDB’98)Amulti-resolutionclusteringapproachusingwaveletmethodCLIQUE:Agrawal,etal.(SIGMOD’98)Onhigh-dimensionaldata(thusputinthesectionofclusteringhigh-dimensionaldata71STING:AStatisticalInformationGridApproachWang,YangandMuntz(VLDB’97)ThespatialareaisdividedintorectangularcellsThereareseverallevelsofcellscorrespondingtodifferentlevelsofresolution72TheSTINGClusteringMethod高层的每个单元被划分成一定数量的底层的较小单元每个单元的统计信息被预先计算并存储，并用于回答查询。高层的参数可从底层参数简单计算而得count,mean,s,min,max

分布—normal,uniform,etc.使用自顶向下方法回答数据查询从一个预选择的层开始—typicallywithasmallnumberofcells

73CommentsonSTINGRemovetheirrelevantcellsfromfurtherconsiderationWhenfinishexaminingthecurrentlayer,proceedtothenextlowerlevelRepeatthisprocessuntilthebottomlayerisreachedAdvantages:Query-independent,easytoparallelize,incrementalupdateO(K),whereKisthenumberofgridcellsatthelowestlevelDisadvantages:Alltheclusterboundariesareeitherhorizontalorvertical,andnodiagonalboundaryisdetected74WaveCluster:ClusteringbyWaveletAnalysis(1998)Sheikholeslami,Chatterjee,andZhang(VLDB’98)首先通过在数据空间强加一个多维网格结构来汇总数据，然后采用小波变换来变换原特征空间，在变换后的空间中发现密集区域。Howtoapplywavelettransformtofindclusters强加一个多维网格结构来汇总数据这种多维空间数据被表示为n维特征空间在特征空间上采用小波变换，以发现特征空间的稠密区域75WaveletTransformWavelettransform:一种信号处理技术，它将一个信号分解为不同频率的子波段。通过应用一维小波变换d次，小波模型可以应用于d维信号在进行小波变化时，数据变化以便在不同的分辨率水平保留对象间的相对距离。使得数据的自然簇变得更加容易区别。76TheWaveClusterAlgorithmInputparameters#ofgridcellsforeachdimensionthewavelet,andthe#ofapplicationsofwavelettransformWhyiswavelettransformationusefulforclustering?Usehat-shapefilterstoemphasizeregionwherepointscluster,butsimultaneouslysuppressweakerinformationintheirboundaryEffectiveremovalofoutliers,multi-resolution,costeffectiveMajorfeatures:ComplexityO(N)DetectarbitraryshapedclustersatdifferentscalesNotsensitivetonoise,notsensitivetoinputorderOnlyapplicabletolowdimensionaldataBothgrid-basedanddensity-based77Quantization

&TransformationFirst,quantizedataintom-Dgridstructure,thenwavelettransforma)scale1:highresolutionb)scale2:mediumresolutionc)scale3:lowresolution78聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法高维数据聚类基于约束的聚类离群点分析小结79Model-BasedClusteringWhatismodel-basedclustering?尝试优化给定数据和某数学模型之间的拟合。基于的假定:数据根据潜在的混合概率分布生成。TypicalmethodsStatisticalapproachEM(Expectationmaximization：),AutoClassMachinelearningapproachCOBWEB,CLASSITNeuralnetworkapproachSOM(Self-OrganizingFeatureMap)80EM—ExpectationMaximizationEM—Apopulariterativerefinementalgorithm期望最大化Anextensiontok-meansAssigneachobjecttoaclusteraccordingtoaweight(prob.distribution)NewmeansarecomputedbasedonweightedmeasuresGeneralideaStartswithaninitialestimateoftheparametervectorIterativelyrescoresthepatternsagainstthemixturedensityproducedbytheparametervectorTherescoredpatternsareusedtoupdatetheparameterupdatesPatternsbelongingtothesamecluster,iftheyareplacedbytheirscoresinaparticularcomponentAlgorithmconvergesfastbutmaynotbeinglobaloptima81TheEM(ExpectationMaximization)AlgorithmInitially,randomlyassignkclustercentersIterativelyrefinetheclustersbasedontwostepsExpectationstep:assigneachdatapointXitoclusterCiwiththefollowingprobabilityMaximizationstep:Estimationofmodelparameters82ConceptualClusteringConceptualclustering一种机器学习聚类方法给定一组未标记的对象，产生对象的分类模式确定相似的对象分组并找出每组对象的特征描述COBWEB(Fisher’87)

一种流行的、简单的、增量概念的聚类方法以分类树（classificationtree）的形式创建层次聚类每个节点对应一个概念并包含该概念的概率描述83COBWEBClusteringMethodAclassificationtree84MoreonConceptualClusteringLimitationsofCOBWEBTheassumptionthattheattributesare

independentofeachotherisoftentoostrongbecausecorrelationmayexistNotsuitableforclusteringlargedatabasedata–skewedtreeandexpensiveprobabilitydistributionsCLASSITanextensionofCOBWEBforincrementalclusteringofcontinuousdatasufferssimilarproblemsasCOBWEBAutoClass(CheesemanandStutz,1996)UsesBayesianstatisticalanalysistoestimatethenumberofclustersPopularinindustry85NeuralNetworkApproachNeuralnetworkapproaches将每个簇描述未一个标本(exemplar)，标本充当簇的“原型”，不一定对应一个特定的数据实例或对象。NewobjectsaredistributedtotheclusterwhoseexemplaristhemostsimilaraccordingtosomedistancemeasureTypicalmethodsSOM(Soft-OrganizingfeatureMap)：自组织特征映射CompetitivelearningInvolvesahierarchicalarchitectureofseveralunits(neurons)Neuronscompeteina“winner-takes-all”fashionfortheobjectcurrentlybeingpresented86Self-OrganizingFeatureMap(SOM)SOMs,alsocalledtopologicalorderedmaps（拓扑有序映射）,orKohonenSelf-OrganizingFeatureMap(KSOMs)用低维(2to3-d)的目标空间的点来表示高维源空间中的所有点，尽可能地保留点间的距离和邻近关系Similartok-means:clustercenterstendtolieinalow-dimensionalmanifoldinthefeaturespace聚类对于若干单元竞争当前对象来进行权重向量最接近当前对象的单元称为赢家赢家及其邻居调整权重，以便更接近输入对象。SOMsarebelievedtoresembleprocessingthatcanoccurinthebrainUsefulforvisualizinghigh-dimensionaldatain2-or3-Dspace87WebDocumentClusteringUsingSOMTheresultofSOMclusteringof12088WebarticlesThepictureontheright:drillingdownonthekeyword“mining”Basedonwebsom.hut.fiWebpage88聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类方法的分类划分方法层次方法基于密度的方法基于网格的方法（自学）基于模型的方法（自学）高维数据聚类（自学）基于约束的聚类（自学）离群点分析（自学）小结89ClusteringHigh-DimensionalDataClusteringhigh-dimensionaldataManyapplications:textdocuments,DNAmicro-arraydataMajorchallenges:ManyirrelevantdimensionsmaymaskclustersDistancemeasurebecomesmeaningless—duetoequi-distanceClustersmayexistonlyinsomesubspacesMethods特征变换:onlyeffectiveifmostdimensionsarerelevantPCA&SVDusefulonlywhenfeaturesarehighlycorrelated/redundant特征选择:wrapperorfilterapproachesusefultofindasubspacewherethedatahaveniceclustersSubspace-clustering:findclustersinallthepossiblesubspacesCLIQUE,ProClus,andfrequentpattern-basedclustering90TheCurseofDimensionality

(graphsadaptedfromParsonsetal.KDDExplorations2004)DatainonlyonedimensionisrelativelypackedAddingadimension“stretch”thepointsacrossthatdimension,makingthemfurtherapartAddingmoredimensionswillmakethepointsfurtherapart—highdimensionaldataisextremelysparseDistancemeasurebecomesmeaningless—duetoequi-distance91WhySubspaceClustering?

(adaptedfromParsonsetal.SIGKDDExplorations2004)ClustersmayexistonlyinsomesubspacesSubspace-clustering:findclustersinallthesubspaces92CLIQUE(ClusteringInQUEst)

Agrawal,Gehrke,Gunopulos,Raghavan(SIGMOD’98)AutomaticallyidentifyingsubspacesofahighdimensionaldataspacethatallowbetterclusteringthanoriginalspaceCLIQUEcanbeconsideredasbothdensity-basedandgrid-based将每一维划分成网格状结构将d维数据空间划分成若干互不重叠的矩形单元，从中识别稠密单元Aunitisdense:如果包含的数据点个数超过某个输入的模型参数值Aclusterisamaximalsetofconnecteddenseunitswithinasubspace93CLIQUE:TheMajorStepsPartitionthedataspaceandfindthenumberofpointsthatlieinsideeachcellofthepartition.IdentifythesubspacesthatcontainclustersusingtheAprioriprincipleIdentifyclustersDeterminedenseunitsinallsubspacesofinterestsDetermineconnecteddenseunitsinallsubspacesofinterests.生成簇的最小描述对于每个簇，确定覆盖联通稠密单元簇的最大区域为每个簇确定最小覆盖（逻辑覆盖）94Salary(10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050

=395StrengthandWeaknessofCLIQUEStrength

automaticallyfindssubspacesofthe

highestdimensionalitysuchthathighdensityclustersexistinthosesubspacesinsensitivetotheorderofrecordsininputanddoesnotpresumesomecanonicaldatadistributionscaleslinearlywiththesizeofinputandhasgoodscalabilityasthenumberofdimensionsinthedataincreasesWeaknessTheaccuracyoftheclusteringresultmaybedegradedattheexpenseofsimplicityofthemethod96FrequentPattern-BasedApproachClusteringhigh-dimensionalspace(e.g.,clusteringtextdocuments,microarraydata：微阵列)Projectedsubspace-clustering:whichdimensionstobeprojectedon?CLIQUE,ProClusFeatureextraction:costlyandmaynotbeeffective?Usingfrequentpatternsas“features”“Frequent”areinherentfeaturesMiningfreq.patternsmaynotbesoexpensiveTypicalmethodsFrequent-term-baseddocumentclusteringClusteringbypatternsimilarityinmicro-arraydata(pClustering)97ClusteringbyPatternSimilarity(p-Clustering)Right:Themicro-array“raw”datashows3genesandtheirvaluesinamulti-dimensionalspaceDifficulttofindtheirpatternsBottom:Somesubsetsofdimensionsformniceshiftandscalingpatterns98Whyp-Clustering?MicroarraydataanalysismayneedtoClusteringonthousandsofdimensions(attributes)DiscoveryofbothshiftandscalingpatternsClusteringwithEuclideandistancemeasure?—cannotfindshiftpatternsClusteringonderivedattributeAij=ai–aj?—introducesN(N-1)/2dimensionsBi-cluster(双聚类)

usingtransformedmean-squaredresiduescore均方残差得分matrix(I,J)WhereAsubmatrixisaδ-clusterifH(I,J)≤δforsomeδ>0Problemswithbi-cluste