第八章聚類(lèi)分析8.1什么是聚類(lèi)分析?8.2

聚類(lèi)分析中的數(shù)據(jù)類(lèi)型8.3主要聚類(lèi)分析方法分類(lèi)8.4

劃分方法（PartitioningMethods）8.5

分層方法8.6

基于密度的方法8.7基于網(wǎng)格的方法8.8基于模型（Model-Based）的聚類(lèi)方法8.9孤立點(diǎn)分析8.10總結(jié)2023/3/101DataMining:ConceptsandTechniques8.1什么是聚類(lèi)分析?簇（Cluster）:一個(gè)數(shù)據(jù)對(duì)象的集合聚類(lèi)分析把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成不同的簇；在同一個(gè)簇（或類(lèi)）中，對(duì)象之間具有相似性；不同簇（或類(lèi)）的對(duì)象之間是相異的。聚類(lèi)是一種無(wú)監(jiān)督分類(lèi)法:沒(méi)有預(yù)先指定的類(lèi)別；典型的應(yīng)用作為一個(gè)獨(dú)立的分析工具，用于了解數(shù)據(jù)的分布；作為其它算法的一個(gè)數(shù)據(jù)預(yù)處理步驟；聚類(lèi)的常規(guī)應(yīng)用模式識(shí)別空間數(shù)據(jù)分析在GIS中，通過(guò)聚類(lèi)發(fā)現(xiàn)特征空間來(lái)建立主題索引；在空間數(shù)據(jù)挖掘中，檢測(cè)并解釋空間中的簇；圖象處理經(jīng)濟(jì)學(xué)(尤其是市場(chǎng)研究方面)WWW文檔分類(lèi)分析WEB日志數(shù)據(jù)來(lái)發(fā)現(xiàn)相似的訪(fǎng)問(wèn)模式2023/3/103DataMining:ConceptsandTechniques什么是一個(gè)好的聚類(lèi)方法?一個(gè)好的聚類(lèi)方法要能產(chǎn)生高質(zhì)量的聚類(lèi)結(jié)果——簇，這些簇要具備以下兩個(gè)特點(diǎn)：高的簇內(nèi)相似性低的簇間相似性聚類(lèi)結(jié)果的好壞取決于該聚類(lèi)方法采用的相似性評(píng)估方法以及該方法的具體實(shí)現(xiàn)；聚類(lèi)方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還是所有的隱含模式；2023/3/105DataMining:ConceptsandTechniques數(shù)據(jù)挖掘?qū)垲?lèi)的典型要求：可伸縮性能夠處理不同類(lèi)型的屬性能發(fā)現(xiàn)任意形狀的簇在決定輸入?yún)?shù)的時(shí)候，盡量不需要特定的領(lǐng)域知識(shí)；能夠處理噪聲和異常對(duì)輸入數(shù)據(jù)對(duì)象的順序不敏感能處理高維數(shù)據(jù)能產(chǎn)生一個(gè)好的、能滿(mǎn)足用戶(hù)指定約束的聚類(lèi)結(jié)果結(jié)果是可解釋的、可理解的和可用的2023/3/106DataMining:ConceptsandTechniques8.2聚類(lèi)分析中的數(shù)據(jù)類(lèi)型兩種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣(twomodes)差異度矩陣(onemode)2023/3/107DataMining:ConceptsandTechniques聚類(lèi)分析中的數(shù)據(jù)類(lèi)型區(qū)間標(biāo)度變量（Interval-scaledvariables）:二元變量（Binaryvariables）:標(biāo)稱(chēng)型，序數(shù)型和比例型變量（Nominal,ordinal,andratiovariables）:混合類(lèi)型變量（Variablesofmixedtypes）:2023/3/109DataMining:ConceptsandTechniques區(qū)間標(biāo)度變量數(shù)據(jù)標(biāo)準(zhǔn)化計(jì)算絕對(duì)偏差的平均值:其中計(jì)算標(biāo)準(zhǔn)度量值(z-score)使用絕對(duì)偏差的平均值比使用標(biāo)準(zhǔn)偏差更健壯（robust）2023/3/1010DataMining:ConceptsandTechniques計(jì)算對(duì)象之間的相異度通常使用距離來(lái)衡量?jī)蓚€(gè)對(duì)象之間的相異度。常用的距離度量方法有:

明考斯基距離（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和

j=(xj1,xj2,…,xjp)是兩個(gè)p維的數(shù)據(jù)對(duì)象,q是一個(gè)正整數(shù)。當(dāng)q=1時(shí),d

稱(chēng)為曼哈坦距離（Manhattandistance）2023/3/1011DataMining:ConceptsandTechniques二元變量二元變量的可能性表 其中每個(gè)對(duì)象有p個(gè)變量，且 p=q+r+s+tObjectiObjectj2023/3/1013DataMining:ConceptsandTechniques二元變量對(duì)稱(chēng)的 如果一個(gè)二元變量的兩個(gè)狀態(tài)是同等價(jià)值的，具有相同的權(quán)重。即可以任取其中一種狀態(tài)編碼為1或者0 對(duì)于對(duì)稱(chēng)的二員變量，采用簡(jiǎn)單匹配系數(shù)來(lái)評(píng)價(jià)兩個(gè)對(duì)象之間的相異度

2023/3/1014DataMining:ConceptsandTechniques二元變量非對(duì)稱(chēng)的 如果變量的兩個(gè)狀態(tài)不是同樣重要的，則稱(chēng)該變量是不對(duì)稱(chēng)的。 根據(jù)慣例，將比較重要通常也是出現(xiàn)概率比較小的狀態(tài)編碼為1，將另一中狀態(tài)編碼為0。 對(duì)于非對(duì)稱(chēng)的二員變量，采用Jaccard系數(shù)來(lái)評(píng)價(jià)兩個(gè)對(duì)象之間的相異度2023/3/1015DataMining:ConceptsandTechniques標(biāo)稱(chēng)變量（NominalVariables）標(biāo)稱(chēng)變量是二元變量的推廣，它可以具有多于兩個(gè)的狀態(tài)，比如變量map_color可以有red,yellow,blue,green四種狀態(tài)。有兩種計(jì)算相異度的方法：方法1:簡(jiǎn)單匹配方法M是匹配的數(shù)目,

p是全部變量的數(shù)目方法2:使用二元變量為每一個(gè)狀態(tài)創(chuàng)建一個(gè)新的二元變量，可以用非對(duì)稱(chēng)的二元變量來(lái)編碼標(biāo)稱(chēng)變量。2023/3/1017DataMining:ConceptsandTechniques序數(shù)型變量一個(gè)序數(shù)型變量可以是離散的也可以是連續(xù)的離散的序數(shù)型變量類(lèi)似于標(biāo)稱(chēng)變量，除了它的M個(gè)狀態(tài)是以有意義的序列排序的，比如職稱(chēng)連續(xù)的序數(shù)型變量類(lèi)似于區(qū)間標(biāo)度變量，但是它沒(méi)有單位，值的相對(duì)順序是必要的，而其實(shí)際大小并不重要。2023/3/1018DataMining:ConceptsandTechniques序數(shù)型變量相異度的計(jì)算 與區(qū)間標(biāo)度變量的計(jì)算方法相類(lèi)似將xif

用它對(duì)應(yīng)的秩代替將每個(gè)變量的值域映射到[0.0，1.0]上，使得每個(gè)變量都有相同的權(quán)重。這通過(guò)用zif來(lái)替代rif來(lái)實(shí)現(xiàn)用前面所述的區(qū)間標(biāo)度變量的任一種距離計(jì)算方法來(lái)計(jì)算2023/3/1019DataMining:ConceptsandTechniques混合類(lèi)型的變量(230頁(yè))一個(gè)數(shù)據(jù)庫(kù)可能包含了所有這6中類(lèi)型的變量 用以下公式計(jì)算對(duì)象i，j之間的相異度. 其中，p為對(duì)象中的變量個(gè)數(shù) 如果xif或xjf

缺失（即對(duì)象i或?qū)ο骿沒(méi)有變量f的值），或者xif=xjf=0，且變量f是不對(duì)稱(chēng)的二元變量，則指示項(xiàng)δij(f)=0；否則δij(f)=12023/3/1021DataMining:ConceptsandTechniques混合類(lèi)型的變量f

是二元變量或標(biāo)稱(chēng)變量:ifxif=xjfdij(f)=0,elsedij(f)=1f

是區(qū)間標(biāo)度變量: dij(f)=|xif-xjf|/（maxhxhf-minhxhf）

其中h遍取變量f的所有非空缺對(duì)象f

是序數(shù)型或比例標(biāo)度型計(jì)算秩rif

計(jì)算zif并將其作為區(qū)間標(biāo)度變量值對(duì)待2023/3/1022DataMining:ConceptsandTechniques8.3主要聚類(lèi)分析方法分類(lèi)Partitioningalgorithms:ConstructvariouspartitionsandthenevaluatethembysomecriterionHierarchyalgorithms:Createahierarchicaldecompositionofthesetofdata(orobjects)usingsomecriterionDensity-based:basedonconnectivityanddensityfunctionsGrid-based:basedonamultiple-levelgranularitystructureModel-based:Amodelishypothesizedforeachoftheclustersandtheideaistofindthebestfitofthatmodeltoeachother2023/3/1023DataMining:ConceptsandTechniquesK-平均算法給定k，算法的處理流程如下:1.隨機(jī)的把所有對(duì)象分配到k個(gè)非空的簇中；2.計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的簇；3.將每個(gè)對(duì)象根據(jù)其與各個(gè)簇中心的距離，重新分配到與它最近的簇中；4.回到第二步，直到不再有新的分配發(fā)生。2023/3/1025DataMining:ConceptsandTechniquesK-平均算法例8.22023/3/1026DataMining:ConceptsandTechniquesK-中心點(diǎn)算法找出簇中位置最中心的對(duì)象，即中心點(diǎn)來(lái)代表簇PAM(PartitioningAroundMedoids,1987)設(shè)定一個(gè)中心點(diǎn)的初始集合，然后反復(fù)的用非中心點(diǎn)對(duì)象來(lái)替代中心點(diǎn)對(duì)象，以改進(jìn)聚類(lèi)的質(zhì)量；PAM

算法在大數(shù)據(jù)集上效率較低，沒(méi)有良好的可伸縮性；CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):Randomizedsampling2023/3/1029DataMining:ConceptsandTechniquesPAM(PartitioningAroundMedoids)(1987)PAM(KaufmanandRousseeuw,1987）用真實(shí)的數(shù)據(jù)對(duì)象來(lái)代表簇隨機(jī)選擇k個(gè)對(duì)象作為初始的中心點(diǎn)；Repeat對(duì)每一個(gè)由非中心對(duì)象h

和中心對(duì)象i,計(jì)算i被h替代的總代價(jià)Tcih對(duì)每一個(gè)有h和I組成的對(duì)象對(duì)IfTCih<0,i

被h替換然后將每一個(gè)非中心點(diǎn)對(duì)象根據(jù)與中心點(diǎn)的距離分配給離它最近的中心點(diǎn)Until不發(fā)生變化。2023/3/1030DataMining:ConceptsandTechniquesPAMClustering:TotalscostTCih=jCjihjihttihjhitjtihj2023/3/1031DataMining:ConceptsandTechniquesCLARA(ClusteringLargeApplications)(1990)CLARA(KaufmannandRousseeuwin1990)

該算法首先獲得數(shù)據(jù)集的多個(gè)采樣，然后在每個(gè)采樣上使用PAM算法，最后返回最好的聚類(lèi)結(jié)果作為輸出。優(yōu)點(diǎn):能夠處理大數(shù)據(jù)集。缺點(diǎn):效率依賴(lài)于采樣的大?。蝗绻麡颖景l(fā)生偏斜，基于樣本的一個(gè)好的聚類(lèi)不一定代表得了整個(gè)數(shù)據(jù)集合的一個(gè)好的聚類(lèi)；2023/3/1032DataMining:ConceptsandTechniquesCLARANS(“Randomized”CLARA)(1994)CLARANS(AClusteringAlgorithmbasedonRandomizedSearch)(NgandHan’94)CLARANS在搜索的每一步動(dòng)態(tài)的抽取一個(gè)樣本；聚類(lèi)過(guò)程可以被描述為對(duì)一個(gè)圖的搜索，圖中的每個(gè)節(jié)點(diǎn)是一個(gè)潛在的解，即k個(gè)中心點(diǎn)的集合；在替換了一個(gè)中心點(diǎn)后的結(jié)果被稱(chēng)為當(dāng)前結(jié)果的鄰居。如果找到了一個(gè)局部最優(yōu)，算法從隨即選擇的節(jié)點(diǎn)開(kāi)始尋找新的局部最優(yōu)；比PAM

和CLARA更有效和有更好的伸縮性；采用聚焦技術(shù)和空間數(shù)據(jù)結(jié)構(gòu)等能進(jìn)一步提高性能(Esteretal.’95)2023/3/1033DataMining:ConceptsandTechniques8.5分層方法采用距離作為衡量聚類(lèi)的標(biāo)準(zhǔn)。該方法不在需要指定聚類(lèi)的個(gè)數(shù)，但用戶(hù)可以指定希望得到的簇的數(shù)目作為一個(gè)結(jié)束條件。Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)2023/3/1034DataMining:ConceptsandTechniquesAGNES(AgglomerativeNesting)由Kaufmann和Rousseeuw提出；(1990)使用單鏈接方法和差異度矩陣；合并那些具有最小差異度的節(jié)點(diǎn)；Gooninanon-descendingfashion最后所有的對(duì)象合并形成一個(gè)簇。2023/3/1035DataMining:ConceptsandTechniquesADendrogramShowsHowtheClustersareMergedHierarchicallyDecomposedataobjectsintoaseverallevelsofnestedpartitioning(treeofclusters),calledadendrogram.Aclusteringofthedataobjectsisobtainedbycuttingthedendrogramatthedesiredlevel,theneachconnectedcomponentformsacluster.2023/3/1036DataMining:ConceptsandTechniquesDIANA(DivisiveAnalysis)由Kaufmann和Rousseeuw提出(1990)AGNES算法的逆過(guò)程；最終每個(gè)新的簇只包含一個(gè)對(duì)象；2023/3/1037DataMining:ConceptsandTechniques層次方法的主要缺點(diǎn)：沒(méi)有良好的伸縮性:時(shí)間復(fù)雜度至少是O(n2)一旦一個(gè)合并或分裂被執(zhí)行，就不能修復(fù)；綜合層次聚類(lèi)和其它的聚類(lèi)技術(shù)：BIRCH(1996):usesCF-treeandincrementallyadjuststhequalityofsub-clustersCURE(1998):selectswell-scatteredpointsfromtheclusterandthenshrinksthemtowardsthecenteroftheclusterbyaspecifiedfractionCHAMELEON(1999):hierarchicalclusteringusingdynamicmodeling2023/3/1038DataMining:ConceptsandTechniquesBIRCH(1996)Birch:BalancedIterativeReducingandClusteringusingHierarchies,byZhang,Ramakrishnan,Livny(SIGMOD’96)增量的構(gòu)造一個(gè)CF樹(shù)Phase1:掃描數(shù)據(jù)庫(kù)，建立一個(gè)初始存放于內(nèi)存的CF樹(shù)，它可以被看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類(lèi)結(jié)構(gòu)；Phase2:采用某個(gè)聚類(lèi)算法對(duì)CF樹(shù)的葉子節(jié)點(diǎn)進(jìn)行聚類(lèi)；可伸縮性:數(shù)據(jù)集合的單邊掃描產(chǎn)生了一個(gè)基本的聚類(lèi)，額外的掃描可以進(jìn)一步的改進(jìn)聚類(lèi)的質(zhì)量。缺點(diǎn):

只能處理數(shù)值型數(shù)據(jù)；對(duì)于非球狀的簇不能很好的工作。2023/3/1039DataMining:ConceptsandTechniquesClusteringFeatureVectorClusteringFeature:

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)2023/3/1040DataMining:ConceptsandTechniquesCFTreeCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=7L=6RootNon-leafnodeLeafnodeLeafnode2023/3/1041DataMining:ConceptsandTechniquesCURE(ClusteringUsingREpresentatives)CURE:proposedbyGuha,Rastogi&Shim,1998StopsthecreationofaclusterhierarchyifalevelconsistsofkclustersUsesmultiplerepresentativepointstoevaluatethedistancebetweenclusters,adjustswelltoarbitraryshapedclustersandavoidssingle-linkeffect2023/3/1042DataMining:ConceptsandTechniquesDrawbacksofDistance-BasedMethodDrawbacksofsquare-errorbasedclusteringmethodConsideronlyonepointasrepresentativeofaclusterGoodonlyforconvexshaped,similarsizeanddensity,andifkcanbereasonablyestimated2023/3/1043DataMining:ConceptsandTechniquesCure:TheAlgorithmDrawrandomsamples.Partitionsampletoppartitionswithsizes/pPartiallyclusterpartitionsintos/pqclustersEliminateoutliersByrandomsamplingIfaclustergrowstooslow,eliminateit.Clusterpartialclusters.Labeldataindisk2023/3/1044DataMining:ConceptsandTechniquesDataPartitioningandClusterings=50p=2s/p=25xxxyyyyxyxs/pq=52023/3/1045DataMining:ConceptsandTechniquesCure:ShrinkingRepresentativePointsShrinkthemultiplerepresentativepointstowardsthegravitycenterbyafractionof.Multiplerepresentativescapturetheshapeoftheclusterxyxy2023/3/1046DataMining:ConceptsandTechniquesK-modes(補(bǔ)充）AFastClusteringAlgorithmtoClusterVeryLargeCategoricalDataSetsinDataMining,ZhexueHuang,1997K-模，對(duì)k-平均方法的改進(jìn)，k-原型的簡(jiǎn)化處理分類(lèi)屬性分類(lèi)屬性：A1,A2,…,Am為空間的m個(gè)屬性，DOM(Ai)為屬性的值域，如果DOM(Ai)是確定和無(wú)序的，即對(duì)任何a，bA,只有a=b或者ab,則稱(chēng)Ai為分類(lèi)屬性如果A1,A2,…,Am都為分類(lèi)屬性，則屬性為分類(lèi)空間2023/3/1047DataMining:ConceptsandTechniques相異度度量設(shè)X，Y為m個(gè)分類(lèi)屬性的分類(lèi)對(duì)象，它們之間的相異度定義為：d(x,y)對(duì)一個(gè)屬性上的每個(gè)類(lèi)賦予了相同的權(quán)重考慮屬性出現(xiàn)的頻率對(duì)出現(xiàn)頻率較低的類(lèi)給予了更大的權(quán)重nxj為數(shù)據(jù)集中屬性j上的值為xj的對(duì)象數(shù)2023/3/1048DataMining:ConceptsandTechniques數(shù)據(jù)集的模（mode）設(shè)X為一組分類(lèi)對(duì)象，分類(lèi)屬性包括A1,A2,…,AMX={X1,X2,…Xn}的模:向量Q=[q1,q2,…,qm],使得最小定理：函數(shù)D(Q,X)為最小，當(dāng)且僅當(dāng)對(duì)所有的j=1,…,m有Nck,j是在屬性上Ai值為ck,j的對(duì)象數(shù)2023/3/1049DataMining:ConceptsandTechniquesK模算法1.為每個(gè)簇選擇初始模，共k個(gè)2.根據(jù)d，把對(duì)象分配給最近的簇。根據(jù)定理重新計(jì)算簇的模3.計(jì)算每個(gè)對(duì)象對(duì)當(dāng)前模的相異度，重新分配對(duì)象到簇4.重復(fù)上述2，3過(guò)程，直到簇中的對(duì)象不再發(fā)生變化2023/3/1050DataMining:ConceptsandTechniques8.6基于密度的方法將簇看作是數(shù)據(jù)空間中被低密度區(qū)域分割開(kāi)的高密度區(qū)域。優(yōu)點(diǎn)：可發(fā)現(xiàn)任意形狀的聚基于密度的方法：DBSCAN基于高密度連接區(qū)域的密度聚類(lèi)方法OPTICS通過(guò)對(duì)象排序識(shí)別聚類(lèi)結(jié)構(gòu)DENCLUE基于密度分布函數(shù)的聚類(lèi)2023/3/1051DataMining:ConceptsandTechniquesDBSCAN(基于高密度連接區(qū)域的密度聚類(lèi)方法）Density-BasedSpatialClusteringofApplicationswithNoiseADensity-BasedAlgorithmforDiscoveringClustersinLargeSpatialDatabaseswithNoiseMartinEster,KDD-96

2023/3/1052DataMining:ConceptsandTechniques定義給定半徑和MinPts，每個(gè)聚類(lèi)中的對(duì)象的-鄰域中至少包含MinPts個(gè)對(duì)象給定對(duì)象集合D

鄰域N(q):給定對(duì)象半徑內(nèi)的區(qū)域，即{qD|dist(p,q)<=}核心對(duì)象：qD，|N(q)|MinPts對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)：pN(q)且|N(q)|MinPtspqMinPts=5=1cm2023/3/1053DataMining:ConceptsandTechniques定義（續(xù)）對(duì)象p從對(duì)象q關(guān)于和MinPts密度可達(dá)：存在對(duì)象鏈p1，p2，…，pn，p1=q，pn=p，piD，pi+1是從pi關(guān)于和MinPts直接密度可達(dá)的（非對(duì)稱(chēng)）對(duì)象p和q關(guān)于和MinPts密度相連：存在對(duì)象oD，使得對(duì)象p和q從o關(guān)于和MinPts密度可達(dá)（對(duì)稱(chēng)）pqopqp12023/3/1054DataMining:ConceptsandTechniquesDBSCAN基本思想簇：基于密度可達(dá)性的最大的密度相連對(duì)象的集合噪音：不在任何簇中的對(duì)象邊界對(duì)象：不是核心對(duì)象，但在簇中，即至少?gòu)囊粋€(gè)核心對(duì)象直接可達(dá)核心對(duì)象邊界點(diǎn)噪音=1cmMinPts=52023/3/1055DataMining:ConceptsandTechniquesDBSCAN算法1）任意選擇沒(méi)有加簇標(biāo)簽的點(diǎn)p2）找到從p關(guān)于

andMinPts密度可達(dá)的所有點(diǎn)

3）如果|N(q)|MinPts，則p是核心對(duì)象,形成一個(gè)新的簇，給簇內(nèi)所有的對(duì)象點(diǎn)加簇標(biāo)簽4）如果p

是邊界點(diǎn),則處理數(shù)據(jù)庫(kù)的下一點(diǎn)5）重復(fù)上述過(guò)程，直到所有的點(diǎn)處理完畢=1cmMinPts=52023/3/1056DataMining:ConceptsandTechniques不足和改進(jìn)只能發(fā)現(xiàn)密度相仿的簇對(duì)用戶(hù)定義的參數(shù)（

andMinPts）敏感計(jì)算復(fù)雜度為O(n2)采用R-樹(shù)等空間索引技術(shù)，計(jì)算復(fù)雜度為o(nlogn)2023/3/1057DataMining:ConceptsandTechniques圖示A和B被認(rèn)為是噪音C1和C2兩個(gè)簇合并了2023/3/1058DataMining:ConceptsandTechniquesOPTICSOPTICS:OrderingPointsToIdentifytheClusteringStructure（通過(guò)對(duì)象排序識(shí)別聚類(lèi)結(jié)構(gòu)）MihaelAnkerst.ACMSIGMOD’99Int.Conf,1999對(duì)DBSCAN的改進(jìn)對(duì)輸入?yún)?shù)不敏感可以發(fā)現(xiàn)不同密度的簇用圖表等可視化的方式來(lái)表示按可達(dá)距離排序可自動(dòng)開(kāi)采，也可與用戶(hù)交互2023/3/1059DataMining:ConceptsandTechniques引入兩個(gè)新概念P為對(duì)象，數(shù)據(jù)集D，為距離值，N(q)為鄰域，MinPtsP的核心距離：使得P成為核心對(duì)象的最小若|（N(q)|MinPts，即P不是核心對(duì)象，則無(wú)定義，即無(wú)窮大否則，定義為使P成為核心對(duì)象的的最小值P關(guān)于對(duì)象q的可達(dá)距離：p的核心距離和p,q的歐幾里得距離之間的較大值若|N(q)|MinPts，即P不是核心對(duì)象，則無(wú)定義否則，定義為Max（核心距離，|（p,q）|）2023/3/1060DataMining:ConceptsandTechniques圖示核心距離可達(dá)距離2023/3/1061DataMining:ConceptsandTechniquesOPTICS算法1.計(jì)算數(shù)據(jù)點(diǎn)p的核心距離和可達(dá)距離2.如果p為核心對(duì)象，找到所有它的關(guān)于和MinPts的直接密度可達(dá)點(diǎn)，按可達(dá)距離排序并插入隊(duì)列。3.處理下一個(gè)數(shù)據(jù)點(diǎn)2023/3/1062DataMining:ConceptsandTechniques尋找簇Reachability-distanceundefined‘Cluster-orderoftheobjects2023/3/1063DataMining:ConceptsandTechniques不同密度、形狀、大小的簇2023/3/1064DataMining:ConceptsandTechniques參數(shù)的影響減小，則可達(dá)距離為無(wú)窮大的點(diǎn)增多；

MinPts減小，核心對(duì)象增多，圖象更尖銳2023/3/1065DataMining:ConceptsandTechniques確定參數(shù)MinPts經(jīng)驗(yàn)值：10-202023/3/1066DataMining:ConceptsandTechniquesDENCLUEDENsity-basedCLUsteringAnEfficientApplicationtoClusteringinLargeMultimediaDatabaseswithNoise（在帶噪音的大型多維數(shù)據(jù)庫(kù)上的高效的聚類(lèi)方法）AlexanderHinnebug,19982023/3/1067DataMining:ConceptsandTechniques數(shù)學(xué)基礎(chǔ)1.影響函數(shù)描述了一個(gè)數(shù)據(jù)點(diǎn)在鄰域的影響2.數(shù)據(jù)空間的整體密度函數(shù)為所有數(shù)據(jù)點(diǎn)的影響函數(shù)之和3.聚類(lèi)可以通過(guò)確定密度吸引點(diǎn)來(lái)得到，密度吸引點(diǎn)為密度函數(shù)的局部最大2023/3/1068DataMining:ConceptsandTechniques影響函數(shù)假設(shè)x和y是特征空間中的對(duì)象。數(shù)據(jù)對(duì)象y對(duì)x的影響函數(shù)為原則上影響函數(shù)可以是任意的函數(shù)，它由鄰域內(nèi)的兩個(gè)對(duì)象之間的距離決定方波影響函數(shù)高斯函數(shù)一個(gè)點(diǎn)x是被一個(gè)密度吸引點(diǎn)y密度吸引的:如果存在一組點(diǎn)x0,…,xk,x0=x,xk=y,對(duì)0<i<k,xi-1的梯度是在xi的方向上的一個(gè)梯度指導(dǎo)的爬山算法可用來(lái)計(jì)算一組數(shù)據(jù)點(diǎn)的密度吸引點(diǎn)2023/3/1069DataMining:ConceptsandTechniques梯度和密度吸引點(diǎn)2023/3/1070DataMining:ConceptsandTechniques爬山算法1.在收縮空間隨機(jī)選擇一點(diǎn).2.考慮當(dāng)前狀態(tài)的所有鄰域3.選擇最佳的鄰域，當(dāng)前狀態(tài)轉(zhuǎn)向它4.重復(fù)過(guò)程2，3，直到當(dāng)前狀態(tài)為鄰域中最佳5.返回當(dāng)前狀態(tài)作為結(jié)果2023/3/1071DataMining:ConceptsandTechniques對(duì)一個(gè)2維數(shù)據(jù)集的可能的密度函數(shù)2023/3/1072DataMining:ConceptsandTechniques簇密度吸引點(diǎn)x的中心定義的簇是一個(gè)被x密度吸引的子集C，在x的密度函數(shù)不小于閾值；否則它被認(rèn)為是孤立點(diǎn)一個(gè)任意形狀的簇是子集C的集合，每一個(gè)都是密度吸引的，有不小于閾值的密度函數(shù)值；并從每個(gè)區(qū)域到另一個(gè)都存在一條路徑p，路徑上的每個(gè)點(diǎn)的密度函數(shù)值都不小于2023/3/1073DataMining:ConceptsandTechniquesChapter8.ClusterAnalysis

基于密度的方法DBSCANOPTICSDENCLUE基于網(wǎng)格的方法STINGWaveClusterCLIQUE基于模型的方法統(tǒng)計(jì)學(xué)方法神經(jīng)網(wǎng)絡(luò)方法孤立點(diǎn)分析小結(jié)2023/3/1074DataMining:ConceptsandTechniques8.7基于網(wǎng)格的方法

采用一個(gè)多分辨率的網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)。將空間化為有限數(shù)目的單元，這些單元形成了網(wǎng)格結(jié)構(gòu)，聚類(lèi)在網(wǎng)格上進(jìn)行。優(yōu)點(diǎn)：處理速度快，處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，僅依賴(lài)于量化空間中每一維上的單元數(shù)目?；诰W(wǎng)格的方法STING利用存儲(chǔ)在網(wǎng)格單元中的統(tǒng)計(jì)信息；

WaveCluster

用一種小波轉(zhuǎn)換方法來(lái)聚類(lèi)對(duì)象；CLIQUE在高維數(shù)據(jù)空間中基于網(wǎng)格和密度的聚類(lèi)方法。2023/3/1075DataMining:ConceptsandTechniquesSTINGSTatisticalInformationGrid(統(tǒng)計(jì)信息網(wǎng)格方法）STING:AStatisticalInformationGridApproachtoSpatialDataMiningWeiWang,LosAngeles,19972023/3/1076DataMining:ConceptsandTechniques主要思想數(shù)據(jù)空間區(qū)域被劃分為有限數(shù)目矩形單元對(duì)應(yīng)于不同級(jí)別的分辨率，存在著不同級(jí)別的矩形單元：高層的每個(gè)單元被分為多個(gè)低一層的單元。每個(gè)網(wǎng)格單元的統(tǒng)計(jì)信息被預(yù)先計(jì)算和存儲(chǔ)，以供處理查詢(xún)之用2023/3/1077DataMining:ConceptsandTechniques統(tǒng)計(jì)信息（1）n（網(wǎng)格中的對(duì)象數(shù)），m（平均值），s（標(biāo)準(zhǔn)偏差），min（最小值），max（最大值）2023/3/1078DataMining:ConceptsandTechniques統(tǒng)計(jì)信息（2）分布類(lèi)型（typeofdistribution)假設(shè)dist為大多數(shù)數(shù)據(jù)點(diǎn)的分布類(lèi)型，confl為分布類(lèi)型不同的數(shù)據(jù)點(diǎn)的個(gè)數(shù)1.distidist，mim，sis，則conflconfl+ni3.distidist，mim，sis，則conflconfl4.mim，sis中有某個(gè)不成立，則confln如果,（t為一個(gè)指定域值），則dist為NONE.否則，dist不變.2023/3/1079DataMining:ConceptsandTechniques統(tǒng)計(jì)信息（3）n=220dist4distm=20.27confl=10s=2.37confl/n=0.045<0.05min=3.8max=40dist=normal2023/3/1080DataMining:ConceptsandTechniques自頂向下地回答查詢(xún)1.從層次中選定一層（包含較少的單元）作為查詢(xún)處理的開(kāi)始。2.對(duì)當(dāng)前層次的每個(gè)單元，計(jì)算置信度區(qū)間，用以反映該網(wǎng)格單元與給定查詢(xún)的關(guān)聯(lián)程度3.當(dāng)前層次處理完畢，轉(zhuǎn)低一層，直至底層2023/3/1081DataMining:ConceptsandTechniques優(yōu)缺點(diǎn)獨(dú)立于查詢(xún)有利于并行處理和增量更新計(jì)算統(tǒng)計(jì)信息的復(fù)雜度為o(n),n為對(duì)象數(shù)，查詢(xún)處理事件的復(fù)雜度為o(g),g為最低層的網(wǎng)格數(shù)，g<<n聚類(lèi)的質(zhì)量取決于網(wǎng)格最低層的粒度所有聚類(lèi)邊界為水平或垂直的降低了簇的質(zhì)量和精確性2023/3/1082DataMining:ConceptsandTechniquesWavecluster(小波變換）Wavecluster：基于大型空間數(shù)據(jù)庫(kù)的多分辨率的聚類(lèi)方法（the24thVLDBConference,NewYork,USA,1998)基于網(wǎng)格和密度的多維空間數(shù)據(jù)對(duì)象可以用多維特征空間來(lái)表示。從信號(hào)處理的角度來(lái)看，n維特征空間的對(duì)象就是n維的信號(hào)。信號(hào)的高頻率區(qū)：對(duì)象分布情況變化劇烈的區(qū)域，即孤立點(diǎn)信號(hào)的低頻率高振幅區(qū)：對(duì)象分布密集區(qū)，即簇n維信號(hào)的變換用多次的一維小波變換來(lái)實(shí)現(xiàn)2023/3/1083DataMining:ConceptsandTechniques小波變換的原理通過(guò)過(guò)濾，可以給出信號(hào)的瞬間頻率值一維信號(hào)S與過(guò)濾系數(shù)Ck卷積M:過(guò)濾系數(shù)的個(gè)數(shù)Ck：過(guò)濾系數(shù)S：輸入信號(hào)2023/3/1084DataMining:ConceptsandTechniquesWavecluster分類(lèi)算法輸入：多維數(shù)據(jù)對(duì)象的特征向量輸出：聚類(lèi)的對(duì)象1.量化特征空間，把對(duì)象分配到各個(gè)單元2.對(duì)各個(gè)單元做小波變換3.按照不同的分辨率，在變換后的子波帶中找到簇4.給簇加類(lèi)標(biāo)簽5.生成查找表6.給對(duì)象加類(lèi)標(biāo)簽2023/3/1085DataMining:ConceptsandTechniques量化有d維的特征空間，每一維分成m個(gè)間隔，設(shè)每一維的m是相等的，且mi=m，則共有單元md個(gè)。Fk=（f1，f2，…，fd）是對(duì)象o的原始特征向量，Mj=（v1，v2，…，vd）是一個(gè)在原始特征空間的單元，1vimi，1id，是單元Mi在向量軸上的位置若i（vi-1）*sifivi*si，1id，則對(duì)象ok在單元Mj中2023/3/1086DataMining:ConceptsandTechniques圖示A0為輸入信號(hào)，為低通過(guò)濾器，為高通過(guò)濾器Dj為詳細(xì)信號(hào)（detailsignal），反映孤立點(diǎn)信息Ai為平均信號(hào)（averagesignal），反映簇的信息Ai的分辨率比Ai+1要高2023/3/1087DataMining:ConceptsandTechniques加類(lèi)標(biāo)簽，查找表cTk，TkclTk=cn，ccrlTk為經(jīng)小波變換后的單元Tk的類(lèi)標(biāo)簽簇的標(biāo)簽不能直接用于原始空間LT表：變換前后的單元對(duì)應(yīng)cMj，oiMj，loi=cn，ccr，1iNloi是對(duì)象oi的類(lèi)標(biāo)簽2023/3/1088DataMining:ConceptsandTechniques特性時(shí)間復(fù)雜度（NK）1）掃描數(shù)據(jù)庫(kù)，分配空間：O（N）2）設(shè)K=md，做小波變換：O（K）3）標(biāo)簽：O（K），LT表：O（K）4）加類(lèi)標(biāo)簽：O（N）2023/3/1089DataMining:ConceptsandTechniques多分辨率強(qiáng)調(diào)水平邊強(qiáng)調(diào)垂直邊強(qiáng)調(diào)轉(zhuǎn)角強(qiáng)調(diào)平均領(lǐng)域2023/3/1090DataMining:ConceptsandTechniques任意形狀的簇的發(fā)現(xiàn)2023/3/1091DataMining:ConceptsandTechniques小波變換的優(yōu)點(diǎn)無(wú)監(jiān)督分類(lèi)：hat-shape過(guò)濾，沒(méi)有事先假定的聚類(lèi)形狀，邊界的弱信息不會(huì)屏蔽剔除孤立點(diǎn)：采用低通過(guò)濾，對(duì)信號(hào)中的高低頻分量通低不通高多分辨率：不同的變換次數(shù)產(chǎn)生不同的分辨率高效率：本身運(yùn)算開(kāi)銷(xiāo)不大，并可以采用并行處理處理高維數(shù)據(jù)，多達(dá)20維2023/3/1092DataMining:ConceptsandTechniquesCLIQUECLIQUE:ClusteringInQUEst,1998給定多維數(shù)據(jù)集合，數(shù)據(jù)點(diǎn)在數(shù)據(jù)空間中不是均衡分布的。如果一個(gè)單元中的包含數(shù)據(jù)點(diǎn)超過(guò)了某個(gè)輸入模型參數(shù)，則該單元是密集的。簇：相連的密集單元的最大集合2023/3/1093DataMining:ConceptsandTechniques主要步驟1.將數(shù)據(jù)空間劃分為互不相交的長(zhǎng)方形單元，記錄每個(gè)單元里的對(duì)象數(shù)2.用先驗(yàn)性質(zhì)識(shí)別包含簇的子空間3.識(shí)別簇：在符合興趣度的子空間中找出密集單元在符合興趣度的子空間中找出相連的密集單元4.為每個(gè)簇生成最小化的描述先驗(yàn)性質(zhì)：如果一個(gè)K維單元是密集的，那么它在k-1空間上的投影也是密集的。即給定一個(gè)k維的侯選密集單元，如果檢查它的k-1維投影空間，發(fā)現(xiàn)任何一個(gè)不是密集的，那么知道第k維的單元也不可能是密集的。2023/3/1094DataMining:ConceptsandTechniquesSalary(10,000)Vacation(week)2030405060age543126702030405060age54312670ageVacationSalary3050=3關(guān)于age對(duì)salary和vocation維的密集單元，這些密集單元相交形成更高維度密集單元的一個(gè)侯選搜索空間2023/3/1095DataMining:ConceptsandTechniques有效性和缺點(diǎn)自動(dòng)地發(fā)現(xiàn)最高維的子空間，高密度聚類(lèi)存在于這些子空間中。對(duì)元組的輸入順序不敏感，無(wú)需假設(shè)任何規(guī)范的數(shù)據(jù)分布隨輸入數(shù)據(jù)的大小線(xiàn)形地?cái)U(kuò)展，當(dāng)數(shù)據(jù)的維數(shù)增加時(shí)具有良好的可伸縮性聚類(lèi)結(jié)果的精確度降低2023/3/1096DataMining:ConceptsandTechniquesChapter8.ClusterAnalysis

基于密度的方法DBSCANOPTICSDENCLUE基于網(wǎng)格的方法STINGWaveClusterCLIQUE基于模型的方法統(tǒng)計(jì)學(xué)方法神經(jīng)網(wǎng)絡(luò)方法孤立點(diǎn)分析小結(jié)2023/3/1097DataMining:ConceptsandTechniques8.8基于模型的聚類(lèi)方法試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性假設(shè)：數(shù)據(jù)是根據(jù)潛在的概率分布生成的統(tǒng)計(jì)學(xué)方法神經(jīng)網(wǎng)絡(luò)方法2023/3/1098DataMining:ConceptsandTechniques統(tǒng)計(jì)學(xué)方法概念聚類(lèi)機(jī)器學(xué)習(xí)中的一種聚類(lèi)方法，給出一組未標(biāo)記的對(duì)象。產(chǎn)生對(duì)象的一個(gè)分類(lèi)模式為每組對(duì)象發(fā)現(xiàn)了特征描述（分類(lèi)）COBWEB簡(jiǎn)單增量概念聚類(lèi)算法以分類(lèi)樹(shù)的形式創(chuàng)建層次聚類(lèi)每個(gè)節(jié)點(diǎn)代表一個(gè)概念，包含對(duì)概念的概率描述2023/3/1099DataMining:ConceptsandTechniques分類(lèi)效用(CategoryUtility)概率表示類(lèi)內(nèi)相似性。該值越大，共享該屬性-值對(duì)的類(lèi)成員比例就更大。概率表示類(lèi)間相異性。該值越大，在對(duì)照類(lèi)中共享該屬性-值對(duì)的類(lèi)成員比例就更大。分類(lèi)效用：N是在樹(shù)的某個(gè)層次上形成的一個(gè)劃分{C1,C2,…,Ck}的節(jié)點(diǎn)、概念或“種類(lèi)”的數(shù)目。在給定的劃分中能夠正確猜測(cè)期望的屬性值的數(shù)目中，分類(lèi)效用是隨沒(méi)有此種知識(shí)時(shí)期望的正確猜測(cè)的樹(shù)木而增加的。2023/3/10100DataMining:ConceptsandTechniquesCOBWEB：分類(lèi)樹(shù)2023/3/10101DataMining:ConceptsandTechniques分類(lèi)樹(shù)的節(jié)點(diǎn)插入將對(duì)象臨時(shí)置于每個(gè)節(jié)點(diǎn)，并計(jì)算結(jié)果劃分的分類(lèi)效用。產(chǎn)生最高分類(lèi)效用的位置是對(duì)象節(jié)點(diǎn)的好的選擇計(jì)算為給定對(duì)象創(chuàng)建一個(gè)新的節(jié)點(diǎn)所產(chǎn)生的分類(lèi)效用，與基于現(xiàn)存節(jié)點(diǎn)的計(jì)算相比較。根據(jù)產(chǎn)生最高效用的劃分，對(duì)象被置于一個(gè)已存在的類(lèi)，或者為它創(chuàng)建一個(gè)新類(lèi)。2023/3/10102DataMining:ConceptsandTechniques優(yōu)缺點(diǎn)假設(shè)每個(gè)屬性上的概率分布是彼此獨(dú)立的。聚類(lèi)的概率分布表示使得更新和存儲(chǔ)聚類(lèi)相當(dāng)昂貴時(shí)間和空間復(fù)雜度取決于屬性的數(shù)目、每個(gè)屬性的值的數(shù)目對(duì)偏斜的數(shù)據(jù)輸入不是高度平衡的，可能導(dǎo)致空間和時(shí)間復(fù)雜性的劇烈變化不適合大數(shù)據(jù)庫(kù)2023/3/10103DataMining:ConceptsandTechniques神經(jīng)網(wǎng)絡(luò)方法將每個(gè)簇描述為一個(gè)標(biāo)本（examplar），作為聚類(lèi)的原型根據(jù)某些距離度量，新的對(duì)象被分配給標(biāo)本與其最相似的簇競(jìng)爭(zhēng)學(xué)習(xí)(competitivelearning)自組織特征映射2023/3/10104DataMining:ConceptsandTechniques競(jìng)爭(zhēng)學(xué)習(xí)采用了若干個(gè)單元的層次結(jié)構(gòu)（神經(jīng)元）神經(jīng)元以一種“勝者全取”的方式對(duì)系統(tǒng)當(dāng)前處理的對(duì)象進(jìn)行競(jìng)爭(zhēng)1.激發(fā)式的連接（excitatory）：在某個(gè)給定層次中的單元可以接收來(lái)自低一層次所有單元的輸入。2.每一層中活動(dòng)單元的布局代表了高一層的輸入模式3.一個(gè)層次內(nèi)的聯(lián)系是抑制式（inhibitory）的，在某個(gè)給定的層次中，一個(gè)簇中的單元彼此競(jìng)爭(zhēng)，對(duì)低一層的輸入模式做出反應(yīng)4.獲勝的單元修正它與簇中其他單元連接上的權(quán)重，以便它能夠?qū)?/p>