第十講 聚類(lèi)分析

第十講

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

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

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

j=(xj1,xj2,…,xjp)是p維對(duì)象,q是非負(fù)整數(shù)如果q=1,d

是曼哈頓距離(Manhattandistance)13q=2時(shí),d是歐幾里德距離(Euclideandistance)特征d(i,j)

0d(i,i)

=0d(i,j)

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

d(i,k)

+d(k,j)(三角不等式)可對(duì)某些變量根據(jù)重要性賦予權(quán)重14二元變量二元變量只有兩個(gè)狀態(tài):0or1二元變量的相依表對(duì)稱(chēng)二元變量(兩個(gè)狀態(tài)具有同等價(jià)值和相同的權(quán)值)的距離度量:非對(duì)稱(chēng)二元變量的距離度量:(通常將出現(xiàn)幾率較小的結(jié)果編碼為1)

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

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

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

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

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

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

并且

將zif

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

EM,SOM,COBWEB基于頻繁模式基于頻繁模式的分析Typicalmethods:pCluster用戶(hù)指導(dǎo)的或基于約束的方法:考慮用戶(hù)指定或應(yīng)用指定的約束所作的聚類(lèi)Typicalmethods:COD(obstacles),constrainedclustering24典型的計(jì)算簇間距離的方法Singlelink:一個(gè)簇中元素與另一個(gè)簇中元素的最近距離,i.e.,dis(Ki,Kj)=min(tip,tjq)Completelink:一個(gè)簇中元素與另一個(gè)簇中元素的最遠(yuǎn)距離,i.e.,dis(Ki,Kj)=max(tip,tjq)Average:一個(gè)簇中元素與另一個(gè)簇中元素的平均距離,i.e.,dis(Ki,Kj)=avg(tip,tjq)Centroid:兩個(gè)簇的質(zhì)心距離,i.e.,dis(Ki,Kj)=dis(Ci,Cj)Medoid:兩個(gè)簇的中心點(diǎn)距離,i.e.,dis(Ki,Kj)=dis(Mi,Mj)Medoid:onechosen,centrallylocatedobjectinthecluster25Centroid,RadiusandDiameterofaCluster(fornumericaldatasets)Centroid:the“middle”ofaclusterRadius:squarerootofaveragedistancefromanypointoftheclustertoitscentroidDiameter:squarerootofaveragemeansquareddistancebetweenallpairsofpointsinthecluster26聚類(lèi)分析什么是聚類(lèi)分析?聚類(lèi)分析中的數(shù)據(jù)類(lèi)型主要聚類(lèi)方法的分類(lèi)劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類(lèi)基于約束的聚類(lèi)離群點(diǎn)分析小結(jié)27劃分算法：基本概念劃分方法:

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

與k-medoids

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

Example012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign30CommentsontheK-MeansMethodStrength:

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

表示位于簇最中心位置的一個(gè)對(duì)象。

01234567891001234567891001234567891001234567891033

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

對(duì)小規(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使用實(shí)際對(duì)象表示簇隨機(jī)選擇k個(gè)代表點(diǎn)對(duì)于每個(gè)未被選擇對(duì)象h和被選擇對(duì)象i，計(jì)算總的轉(zhuǎn)換代價(jià)TCih；聚類(lèi)結(jié)果的質(zhì)量用代價(jià)函數(shù)來(lái)評(píng)估Foreachpairofiandh,IfTCih<0,iisreplacedbyh將每個(gè)未被選擇對(duì)象賦值給最靠近的代表對(duì)象所在的簇repeatsteps2-3untilthereisnochange36PAMClustering:TotalswappingcostTCih=jCjihjihttihjhitjtihjh代替i嗎？j當(dāng)前屬于i所代表的簇,并且j離h比t近,即d(j,h)<=d(j,t

),此處t是j的第二接近中心點(diǎn)。這樣,如果i被h替換作為中心點(diǎn),j將屬于h所代表的簇j當(dāng)前屬于i所代表的簇,并且j離t比h近,即d(j,h)>=d(j,t),此處t是j的第二接近中心點(diǎn)。這樣,如果i被h替換作為中心點(diǎn),j將屬于t所代表的簇.j當(dāng)前屬于另一個(gè)非i所代表的簇,t是j所屬簇的代表對(duì)象,并且j離h比t近,即d(j,h)<d(j,t)。這樣,如果i被h替換作為中心點(diǎn),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聚類(lèi)分析什么是聚類(lèi)分析?聚類(lèi)分析中的數(shù)據(jù)類(lèi)型主要聚類(lèi)方法的分類(lèi)劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類(lèi)基于約束的聚類(lèi)離群點(diǎn)分析小結(jié)41HierarchicalClusteringUsedistancematrixasclusteringcriteria.Thismethoddoesnotrequirethenumberofclusterskasaninput,butneedsaterminationconditionStep0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)42AGNES(AgglomerativeNesting)IntroducedinKaufmannandRousseeuw(1990)Implementedinstatisticalanalysispackages,e.g.,SplusUsetheSingle-Linkmethodandthedissimilaritymatrix.MergenodesthathavetheleastdissimilarityGooninanon-descendingfashionEventuallyallnodesbelongtothesamecluster43Dendrogram:ShowsHowtheClustersareMerged通常，使用樹(shù)狀圖（dendrogram.）的樹(shù)形結(jié)構(gòu)表示層次聚類(lèi)的過(guò)程，它展示出對(duì)象是如何一步步分組的。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)計(jì)匯總:從統(tǒng)計(jì)學(xué)角度看，它是簇的零階矩，一階矩和二階矩。使用聚類(lèi)特征來(lái)匯總對(duì)象簇的信息，從而避免存儲(chǔ)所有對(duì)象。CF樹(shù)是高度平衡的樹(shù)，它存儲(chǔ)了層次結(jié)構(gòu)的聚類(lèi)特征。

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

；pi+1

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

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

73CommentsonSTINGRemovetheirrelevantcellsfromfurtherconsiderationWhenfinishexaminingthecurrentlayer,proceedtothenextlowerlevelRepeatthisprocessuntilthebottomlayerisreachedAdvantages:Query-independent,easytoparallelize,incrementalupdateO(K),whereKisthenumberofgridcellsatthelowestlevelDisadvantages:Alltheclusterboundariesareeitherhorizontalorvertical,andnodiagonalboundaryisdetected74WaveCluster:ClusteringbyWaveletAnalysis(1998)Sheikholeslami,Chatterjee,andZhang(VLDB’98)首先通過(guò)在數(shù)據(jù)空間強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)來(lái)匯總數(shù)據(jù)，然后采用小波變換來(lái)變換原特征空間，在變換后的空間中發(fā)現(xiàn)密集區(qū)域。Howtoapplywavelettransformtofindclusters強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)來(lái)匯總數(shù)據(jù)這種多維空間數(shù)據(jù)被表示為n維特征空間在特征空間上采用小波變換，以發(fā)現(xiàn)特征空間的稠密區(qū)域75WaveletTransformWavelettransform:一種信號(hào)處理技術(shù)，它將一個(gè)信號(hào)分解為不同頻率的子波段。通過(guò)應(yīng)用一維小波變換d次，小波模型可以應(yīng)用于d維信號(hào)在進(jìn)行小波變化時(shí)，數(shù)據(jù)變化以便在不同的分辨率水平保留對(duì)象間的相對(duì)距離。使得數(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聚類(lèi)分析什么是聚類(lèi)分析?聚類(lèi)分析中的數(shù)據(jù)類(lèi)型主要聚類(lèi)方法的分類(lèi)劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法高維數(shù)據(jù)聚類(lèi)基于約束的聚類(lèi)離群點(diǎn)分析小結(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一種機(jī)器學(xué)習(xí)聚類(lèi)方法給定一組未標(biāo)記的對(duì)象，產(chǎn)生對(duì)象的分類(lèi)模式確定相似的對(duì)象分組并找出每組對(duì)象的特征描述COBWEB(Fisher’87)

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

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

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