第十講 聚類分析

第十講

聚類分析1聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法（自學(xué)）基于模型的方法（自學(xué)）高維數(shù)據(jù)聚類（自學(xué)）基于約束的聚類（自學(xué)）離群點分析（自學(xué)）小結(jié)2什么是聚類分析?簇(cluster):數(shù)據(jù)對象的集合同一簇中對象相似不同簇中對象相異聚類(clustering):將物理或抽象對象的集合分成相似的對象類的過程聚類分析在數(shù)據(jù)中按照數(shù)據(jù)的特征找出相似處，將相似的數(shù)據(jù)對象分組到一個聚類無指導(dǎo)學(xué)習(xí)(Unsupervisedlearning):沒有預(yù)定義的類典型應(yīng)用作為一個獨立的工具，用于觀察數(shù)據(jù)的分布作為其他算法的預(yù)處理步驟3聚類：多學(xué)科、廣泛的應(yīng)用模式識別(PatternRecognition)空間數(shù)據(jù)分析(SpatialDataAnalysis)在GIS中，通過聚類特征空間，創(chuàng)建主題地圖檢測空間聚類或其他空間挖掘任務(wù)圖象處理經(jīng)濟科學(xué)(特別是市場研究)WWW文檔分類聚類Weblog數(shù)據(jù)，發(fā)現(xiàn)類似的存取模式組4ExamplesofClusteringApplications市場:幫助市場分析員發(fā)現(xiàn)顧客的不同類別，并使用這些知識開發(fā)目標市場程序。國土利用:幫助識別地球觀測數(shù)據(jù)庫中國土利用相似的區(qū)域。保險:賠付較高保險金額的保險持有者城市計劃:根據(jù)房子的類型、價值和地理位置對城市中房屋的分組識別5Quality:WhatIsGoodClustering?好的聚類方法：高內(nèi)聚、低耦合聚類結(jié)果的質(zhì)量依賴于方法和實現(xiàn)中使用的相似度度量。聚類方法的質(zhì)量還可以由它所發(fā)現(xiàn)一些或全部隱藏模式的能力所衡量6MeasuretheQualityofClustering相異度/相似度矩陣:相似度表現(xiàn)為距離函數(shù)，矩陣

d(i,j)對于不同的數(shù)據(jù)類型，距離函數(shù)(distancefunctions)的定義可能有很大的差別：

區(qū)間標量變量、二元變量、分類變量、序數(shù)變量和向量變量權(quán)重的設(shè)置與應(yīng)用中的不同變量有關(guān)。很難定義怎樣是“足夠相似”或是“足夠好”，因為其答案是相當主觀的。7RequirementsofClusteringinDataMining可伸縮的處理不同類型屬性的能力處理動態(tài)數(shù)據(jù)的能力處理任意形狀的聚類輸入?yún)?shù)的確定需要盡量少的領(lǐng)域知識處理帶噪聲數(shù)據(jù)的能力對數(shù)據(jù)數(shù)據(jù)的順序不敏感高維性滿足用戶指定的約束可解釋性和可用性8聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類基于約束的聚類離群點分析小結(jié)9DataStructures數(shù)據(jù)矩陣N個對象，p個變量(雙模)相異度矩陣d(i,j):對象i和j間的相異度(單模)10TypeofdatainclusteringanalysisInterval-scaledvariables(區(qū)間標度變量)BinaryVariables(二元變量)Nominal,ordinal,andratiovariables(分類、序數(shù)和比例調(diào)度變量)混合類型變量11區(qū)間標度變量區(qū)間標度變量：粗略線性標度的連續(xù)度量。如重量、經(jīng)緯度、氣溫等數(shù)據(jù)標準化？單位不同對聚類結(jié)果影響大計算均值絕對偏差(meanabsolutedeviation)其中計算標準度量值(standardizedmeasurement)(z-score)使用均值絕對偏差比標準差對于離群點有更好的魯棒性。12對象間的相似度或相異度距離：通常用于衡量兩個對象之間的相似度或相異度閔可夫斯基距離(Minkowskidistance):其中，i=(xi1,xi2,…,xip)和

j=(xj1,xj2,…,xjp)是p維對象,q是非負整數(shù)如果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)(三角不等式)可對某些變量根據(jù)重要性賦予權(quán)重14二元變量二元變量只有兩個狀態(tài):0or1二元變量的相依表對稱二元變量(兩個狀態(tài)具有同等價值和相同的權(quán)值)的距離度量:非對稱二元變量的距離度量:(通常將出現(xiàn)幾率較小的結(jié)果編碼為1)

Jaccard系數(shù)(非對稱二元變量的相似度):ObjectiObjectj15DissimilaritybetweenBinaryVariablesExamplegenderisasymmetricattributetheremainingattributesareasymmetricbinaryletthevaluesYandPbesetto1,andthevalueNbesetto016分類變量分類變量是二元變量的推廣，它可以取多于兩個狀態(tài)值。eg.,red,yellow,blue,greenm:匹配數(shù),p:全部變量數(shù)目，不匹配率：17序數(shù)變量序數(shù)變量可以是離散的也可以是連續(xù)的序數(shù)變量中，順序很重要,如，職稱在計算對象的相異度時，序數(shù)變量的處理與區(qū)間標度變量非常類似第i個對象的f值為xif

，變量f有Mf個有序的狀態(tài)，表示秩評定1，…,Mf,用對應(yīng)的秩代替xif

。將變量的值映射到[0,1]，將第i個對象的第f個變量表示為使用區(qū)間標量的相異度計算。18比例標度變量比例標度變量:在非線性的刻度取正的度量值，近似地遵循指數(shù)比例，如AeBtorAe-Bt

方法:采用與處理區(qū)間標度變量同樣的方法處理。(刻度可能被扭曲)應(yīng)用對數(shù)變換yif=log(xif)將它們看作連續(xù)的序數(shù)數(shù)據(jù)，將其秩作為區(qū)間值來對待。19混合類型變量數(shù)據(jù)庫可能包含下述六種類型變量對稱二元變量、不對稱二元變量、分類變量、序數(shù)變量、區(qū)間變量與比例標度變量f

是二元或分類變量:如果xif=xjf,dij(f)=0；否則dij(f)=1f

是區(qū)間變量:使用規(guī)范化后的距離f是序數(shù)或比例標度變量計算秩rif

并且

將zif

作為區(qū)間變量20VectorObjectsVectorobjects:keywordsindocuments,genefeaturesinmicro-arrays,etc.Broadapplications:informationretrieval,biologictaxonomy,etc.CosinemeasureAvariant:Tanimotocoefficient21聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類基于約束的聚類離群點分析小結(jié)22主要聚類方法的分類劃分方法:構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一簇。Typicalmethods:k-means,k-medoids,CLARANS層次方法:構(gòu)建給定數(shù)據(jù)對象集的層次分解Typicalmethods:Diana,Agnes,BIRCH,ROCK,CAMELEON基于密度的方法:基于連接和密度函數(shù)Typicalmethods:DBSACN,OPTICS,DenClue23主要聚類方法的分類(II)基于網(wǎng)格的方法:基于多層網(wǎng)格結(jié)構(gòu)Typicalmethods:STING,WaveCluster,CLIQUE基于建模的方法:為簇建立最合適的假設(shè)模型Typicalmethods:

EM,SOM,COBWEB基于頻繁模式基于頻繁模式的分析Typicalmethods:pCluster用戶指導(dǎo)的或基于約束的方法:考慮用戶指定或應(yīng)用指定的約束所作的聚類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:兩個簇的質(zhì)心距離,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聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類基于約束的聚類離群點分析小結(jié)27劃分算法：基本概念劃分方法:

構(gòu)建數(shù)據(jù)庫的一個劃分，將n個對象分到k個簇中,使得平方距離和最小給定k,找到k個簇的劃分全局優(yōu)化:列舉所有的劃分啟發(fā)式方法:k-means

與k-medoids

方法k-means(MacQueen’67):用簇中心表示簇k-medoidsPAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):用簇中的一個對象來表示簇28K-Means:k均值方法給定k表示簇的數(shù)目:從D中任意選擇k個對象作為初始簇中心。Repeat根據(jù)簇中對象的均值，將每個對象(再)指派到最相似的簇更新簇均值，即計算每個簇中對象的均值Until不再發(fā)生變化29TheK-MeansClusteringMethod

Example012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign30CommentsontheK-MeansMethodStrength:

計算復(fù)雜度:O(tkn),t表示迭代次數(shù).通常的,k,t<<n.Comparing:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k))Weakness只有均值有定義時才能使用需要指定k不能處理噪聲數(shù)據(jù)或離群點不適合發(fā)現(xiàn)非凸形狀的簇31VariationsoftheK-MeansMethodk-means方法的變種初始K個均值的選擇相異度的計算計算簇均值的策略處理分類數(shù)據(jù):k-modes(Huang’98)用modes(眾數(shù)：一組中出現(xiàn)最頻繁的數(shù)或數(shù)列)來代替簇均值用新的相異度度量處理分類對象采用基于頻率的方法更新簇眾數(shù)處理分類數(shù)據(jù)和數(shù)值形混合數(shù)據(jù)的方法:k-prototype32K-Means方法的難題k-means對離群點太敏感具有很大極端值的一個對象可能顯著地扭曲數(shù)據(jù)，平方誤差函數(shù)的使用更加惡化了這一影響K-Medoids:使用一個參考點而不是均值來代表簇,medoids

表示位于簇最中心位置的一個對象。

01234567891001234567891001234567891001234567891033

K中心點方法(K-Medoids)Findrepresentativeobjects,calledmedoids,inclustersPAM(圍繞中心點的劃分PartitioningAroundMedoids,1987)startsfromaninitialsetofmedoidsanditerativelyreplacesoneofthemedoidsbyoneofthenon-medoidsifitimprovesthetotaldistanceoftheresultingclusteringPAM

對小規(guī)模數(shù)據(jù)性能良好，但不善于處理大規(guī)模數(shù)據(jù)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，計算總的轉(zhuǎn)換代價TCih；聚類結(jié)果的質(zhì)量用代價函數(shù)來評估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聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類基于約束的聚類離群點分析小結(jié)41HierarchicalClusteringUsedistancematrixasclusteringcriteria.Thismethoddoesnotrequirethenumberofclusterskasaninput,butneedsaterminationconditionStep0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)42AGNES(AgglomerativeNesting)IntroducedinKaufmannandRousseeuw(1990)Implementedinstatisticalanalysispackages,e.g.,SplusUsetheSingle-Linkmethodandthedissimilaritymatrix.MergenodesthathavetheleastdissimilarityGooninanon-descendingfashionEventuallyallnodesbelongtothesamecluster43Dendrogram:ShowsHowtheClustersareMerged通常，使用樹狀圖（dendrogram.）的樹形結(jié)構(gòu)表示層次聚類的過程，它展示出對象是如何一步步分組的。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:給定子簇的統(tǒng)計匯總:從統(tǒng)計學(xué)角度看，它是簇的零階矩，一階矩和二階矩。使用聚類特征來匯總對象簇的信息，從而避免存儲所有對象。CF樹是高度平衡的樹，它存儲了層次結(jié)構(gòu)的聚類特征。

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傳統(tǒng)聚類算法使用的距離函數(shù)對分類數(shù)據(jù)不能產(chǎn)生高質(zhì)量的簇。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聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類基于約束的聚類離群點分析小結(jié)57Density-BasedClusteringMethods基于密度的聚類，將簇看作是數(shù)據(jù)空間中被低密度區(qū)域(代表噪聲)分割的稠密對象區(qū)域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:給定對象半徑ε內(nèi)的鄰域稱為該對象的ε鄰域如果對象的ε鄰域至少包含最小數(shù)目MinPts的對象，則稱該對象為核心對象直接密度可達(Directlydensity-reachable):給定一個對象集合D，如果p在q的鄰域內(nèi)，q是一個核心對象，則稱對象p從對象q出發(fā)是直接密度可達。pqMinPts=5Eps=1cm59密度可達與密度相連密度可達(Density-reachable)如果存在一個對象鏈，p1,…,pn,p1=q,pn=p

；pi+1

是從Pi對于ε和MinPts是直接密度可達，則對象p是從對象q關(guān)于ε和MinPts密度可達的。密度連接(Density-connected)如果存在對象o∈D，使對象p和q都是從o關(guān)于ε和MinPts密度可達，則對象p到q是關(guān)于ε和MinPts密度相連的。pqp1pqo60DBSCAN:DensityBasedSpatialClusteringofApplicationswithNoise簇被定義為密度連接點的最大集合能在帶有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇CoreBorderOutlierEps=1cmMinPts=561DBSCAN:TheAlgorithm隨機選擇點p檢索從p開始的所有密度可達點。如果p是核心點，則形成一個簇如果p是邊緣點，則沒有從p密度可達的點；DBSCAN訪問數(shù)據(jù)庫中其他點繼續(xù)處理，直到所有點都被處理62X5X2X3X4X6X7X8X1X9X102ε＝2Minpts＝2222222222ExampleofDBSCAN63DBSCAN:SensitivetoParameters64CHAMELEON(ClusteringComplexObjects)65OPTICS:ACluster-OrderingMethod(1999)OPTICS:OrderingPointsToIdentifytheClusteringStructure(通過點排序識別聚類結(jié)構(gòu))Ankerst,Breunig,Kriegel,andSander(SIGMOD’99)產(chǎn)生基于密度聚類結(jié)構(gòu)的數(shù)據(jù)庫的特定順序它包含的信息等價于從一個廣泛的參數(shù)設(shè)置所獲得的基于密度的聚類?？梢杂脠D形化或可視化技術(shù)來表示66OPTICS:SomeExtensionfromDBSCAN核心距離使{P}成為核心對象的最小ε’可達距離p2MinPts=5e=3cmp的核心距離和p與q之間歐幾里德距離的較大值r(p1,o)=2.8cm.r(p2,o)=4cmoop167DENCLUE:UsingStatisticalDensityFunctionsDENsity-basedCLUstEringbyHinneburg&Keim(KDD’98)使用統(tǒng)計密度函數(shù):Majorfeatures有著堅實的數(shù)學(xué)基礎(chǔ)對具有大量噪聲的數(shù)據(jù)集的分析很有好處能對高維數(shù)據(jù)集的任意形狀的聚類做復(fù)雜的數(shù)學(xué)描述比現(xiàn)存算法快得多(e.g.,DBSCAN)需要大量參數(shù)68Usesgridcellsbutonlykeepsinformationaboutgridcellsthatdoactuallycontaindatapointsandmanagesthesecellsinatree-basedaccessstructure影響函數(shù):每個數(shù)據(jù)點的影響可以用影響函數(shù)來建模，描述數(shù)據(jù)點在其鄰域內(nèi)的影響數(shù)據(jù)空間的整體密度可以用所有數(shù)據(jù)點的影響函數(shù)的和建模。簇可以通過識別密度吸引點數(shù)學(xué)確定。密度吸引點是全局密度函數(shù)的局部極大值。Denclue:TechnicalEssence69聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類基于約束的聚類離群點分析小結(jié)70Grid-BasedClusteringMethod多分辨率網(wǎng)格數(shù)據(jù)結(jié)構(gòu)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高層的每個單元被劃分成一定數(shù)量的底層的較小單元每個單元的統(tǒng)計信息被預(yù)先計算并存儲，并用于回答查詢。高層的參數(shù)可從底層參數(shù)簡單計算而得count,mean,s,min,max

分布—normal,uniform,etc.使用自頂向下方法回答數(shù)據(jù)查詢從一個預(yù)選擇的層開始—typicallywithasmallnumberofcells

73CommentsonSTINGRemovetheirrelevantcellsfromfurtherconsiderationWhenfinishexaminingthecurrentlayer,proceedtothenextlowerlevelRepeatthisprocessuntilthebottomlayerisreachedAdvantages:Query-independent,easytoparallelize,incrementalupdateO(K),whereKisthenumberofgridcellsatthelowestlevelDisadvantages:Alltheclusterboundariesareeitherhorizontalorvertical,andnodiagonalboundaryisdetected74WaveCluster:ClusteringbyWaveletAnalysis(1998)Sheikholeslami,Chatterjee,andZhang(VLDB’98)首先通過在數(shù)據(jù)空間強加一個多維網(wǎng)格結(jié)構(gòu)來匯總數(shù)據(jù)，然后采用小波變換來變換原特征空間，在變換后的空間中發(fā)現(xiàn)密集區(qū)域。Howtoapplywavelettransformtofindclusters強加一個多維網(wǎng)格結(jié)構(gòu)來匯總數(shù)據(jù)這種多維空間數(shù)據(jù)被表示為n維特征空間在特征空間上采用小波變換，以發(fā)現(xiàn)特征空間的稠密區(qū)域75WaveletTransformWavelettransform:一種信號處理技術(shù)，它將一個信號分解為不同頻率的子波段。通過應(yīng)用一維小波變換d次，小波模型可以應(yīng)用于d維信號在進行小波變化時，數(shù)據(jù)變化以便在不同的分辨率水平保留對象間的相對距離。使得數(shù)據(jù)的自然簇變得更加容易區(qū)別。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聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類基于約束的聚類離群點分析小結(jié)79Model-BasedClusteringWhatismodel-basedclustering?嘗試優(yōu)化給定數(shù)據(jù)和某數(shù)學(xué)模型之間的擬合?；诘募俣?數(shù)據(jù)根據(jù)潛在的混合概率分布生成。TypicalmethodsStatisticalapproachEM(Expectationmaximization：),AutoClassMachinelearningapproachCOBWEB,CLASSITNeuralnetworkapproachSOM(Self-OrganizingFeatureMap)80EM—ExpectationMaximizationEM—Apopulariterativerefinementalgorithm期望最大化Anextensiontok-meansAssigneachobjecttoaclusteraccordingtoaweight(prob.distribution)NewmeansarecomputedbasedonweightedmeasuresGeneralideaStartswithaninitialestimateoftheparametervectorIterativelyrescoresthepatternsagainstthemixturedensityproducedbytheparametervectorTherescoredpatternsareusedtoupdatetheparameterupdatesPatternsbelongingtothesamecluster,iftheyareplacedbytheirscoresinaparticularcomponentAlgorithmconvergesfastbutmaynotbeinglobaloptima81TheEM(ExpectationMaximization)AlgorithmInitially,randomlyassignkclustercentersIterativelyrefinetheclustersbasedontwostepsExpectationstep:assigneachdatapointXitoclusterCiwiththefollowingprobabilityMaximizationstep:Estimationofmodelparameters82ConceptualClusteringConceptualclustering一種機器學(xué)習(xí)聚類方法給定一組未標記的對象，產(chǎn)生對象的分類模式確定相似的對象分組并找出每組對象的特征描述COBWEB(Fisher’87)

一種流行的、簡單的、增量概念的聚類方法以分類樹（classificationtree）的形式創(chuàng)建層次聚類每個節(jié)點對應(yīng)一個概念并包含該概念的概率描述83COBWEBClusteringMethodAclassificationtree84MoreonConceptualClusteringLimitationsofCOBWEBTheassumptionthattheattributesare

independentofeachotherisoftentoostrongbecausecorrelationmayexistNotsuitableforclusteringlargedatabasedata–skewedtreeandexpensiveprobabilitydistributionsCLASSITanextensionofCOBWEBforincrementalclusteringofcontinuousdatasufferssimilarproblemsasCOBWEBAutoClass(CheesemanandStutz,1996)UsesBayesianstatisticalanalysistoestimatethenumberofclustersPopularinindustry85NeuralNetworkApproachNeuralnetworkapproaches將每個簇描述未一個標本(exemplar)，標本充當簇的“原型”，不一定對應(yīng)一個特定的數(shù)據(jù)實例或?qū)ο?。NewobjectsaredistributedtotheclusterwhoseexemplaristhemostsimilaraccordingtosomedistancemeasureTypicalmethodsSOM(Soft-OrganizingfeatureMap)：自組織特征映射CompetitivelearningInvolvesahierarchicalarchitectureofseveralunits(neurons)Neuronscompeteina“winner-takes-all”fashionfortheobjectcurrentlybeingpresented86Self-OrganizingFeatureMap(SOM)SOMs,alsocalledtopologicalorderedmaps（拓撲有序映射）,orKohonenSelf-OrganizingFeatureMap(KSOMs)用低維(2to3-d)的目標空間的點來表示高維源空間中的所有點，盡可能地保留點間的距離和鄰近關(guān)系Similartok-means:clustercenterstendtolieinalow-dimensionalmanifoldinthefeaturespace聚類對于若干單元競爭當前對象來進行權(quán)重向量最接近當前對象的單元稱為贏家贏家及其鄰居調(diào)整權(quán)重，以便更接近輸入對象。SOMsarebelievedtoresembleprocessingthatcanoccurinthebrainUsefulforvisualizinghigh-dimensionaldatain2-or3-Dspace87WebDocumentClusteringUsingSOMTheresultofSOMclusteringof12088WebarticlesThepictureontheright:drillingdownonthekeyword“mining”Basedonwebsom.hut.fiWebpage88聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類方法的分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法（自學(xué)）基于模型的方法（自學(xué)）高維數(shù)據(jù)聚類（自學(xué)）基于約束的聚類（自學(xué)）離群點分析（自學(xué)）小結(jié)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將每一維劃分成網(wǎng)格狀結(jié)構(gòu)將d維數(shù)據(jù)空間劃分成若干互不重疊的矩形單元，從中識別稠密單元Aunitisdense:如果包含的數(shù)據(jù)點個數(shù)超過某個輸入的模型參數(shù)值A(chǔ)clusterisamaximalsetofconnecteddenseunitswithinasubspace93CLIQUE:TheMajorStepsPartitionthedataspaceandfindthenumberofpointsthatlieinsideeachcellofthepartition.IdentifythesubspacesthatcontainclustersusingtheAprioriprincipleIdentifyclustersDeterminedenseunitsinallsubspacesofinterestsDetermineconnecteddenseunitsinallsubspacesofinterests.生成簇的最小描述對于每個簇，確定覆蓋聯(lián)通稠密單元簇的最大區(qū)域為每個簇確定最小覆蓋（邏輯覆蓋）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