第十講

聚類分析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