bigdata數(shù)據(jù)挖掘培訓(xùn)課件

數(shù)據(jù)挖掘

DataMining閆雷鳴2022/12/9數(shù)據(jù)挖掘

DataMining閆雷鳴四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類2.聚類分析四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類4.1貝葉斯分類:為什么?可能性學(xué)習(xí)可能性預(yù)測4.1貝葉斯分類:為什么?貝葉斯定理給定訓(xùn)練數(shù)據(jù)

D,條件h的后驗概率MAP假設(shè)貝葉斯定理MAP極大后驗假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時可能性最大的假設(shè)h，h被稱為極大后驗假設(shè)（MAP）確定MAP的方法是用貝葉斯公式計算每個候選假設(shè)的后驗概率，計算式如下 最后一步，去掉了P(D)，因為它是不依賴于h的常量MAP極大后驗假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時可樸素貝葉斯分類樸素假定:屬性獨立P(x1,…,xk|C)=P(x1|C)·…·P(xk|C)假如i-th是分類屬性:

P(xi|C)類C中屬性i-th具有值xi假如i-th屬性連續(xù)的:

P(xi|C)通過高斯密度函數(shù)來估計兩種情況下計算容易樸素貝葉斯分類樸素假定:屬性獨立樸素貝葉斯分類(I)樸素假定:屬性類條件獨立:大大降低計算開銷,只計算類的分布.樸素貝葉斯分類(I)樸素假定:屬性類條件獨立:樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計算出概率（出去打網(wǎng)球）樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計算出概率（出去打網(wǎng)打網(wǎng)球?qū)嵗?估計P(xi|C)outlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(true|p)=3/9P(true|n)=3/5P(false|p)=6/9P(false|n)=2/5P(p)=9/14P(n)=5/14打網(wǎng)球?qū)嵗?估計P(xi|C)outlookP(sunn打網(wǎng)球?qū)嵗?分類XX=<rain,hot,high,false>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286樣本X通過類

n(don’tplay)來分類打網(wǎng)球?qū)嵗?分類X貝葉斯信念網(wǎng)絡(luò)(I)貝葉斯信念網(wǎng)絡(luò)允許在變量的子集間定義類條件獨立性提供一種因果關(guān)系的圖形學(xué)習(xí)貝葉斯信念網(wǎng)絡(luò)的幾種情況網(wǎng)絡(luò)結(jié)構(gòu)和變量均給出，容易給出網(wǎng)絡(luò)結(jié)構(gòu)和部分變量網(wǎng)絡(luò)結(jié)構(gòu)預(yù)先不知道貝葉斯信念網(wǎng)絡(luò)(I)貝葉斯信念網(wǎng)絡(luò)允許在變量的子集間定義類貝葉斯信念網(wǎng)絡(luò)(II)FamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.10.9貝葉斯信念網(wǎng)絡(luò)肺癌的條件概率表貝葉斯信念網(wǎng)絡(luò)(II)FamilyLungCancerPo國家政策（C）單位政策（U）身體狀況差（B）過勞死（D）工作壓力大（W）WBP(A)tttfftff0.3350.300.050.00UP(W)tf0.900.05CP(U)tf0.950.01P(C)0.50UP(B)tf0.300.01已知：一個事件e={單位政策U=true,and工作壓力大=true}，請近似計算出現(xiàn)過勞死的概率?！癗oonecanservetwomasters.Eitherhewillhatetheoneandlovetheother,orhewillbedevotedtotheoneanddespisetheother.YoucannotservebothGodandMoney.”

FromMatthew6:24NIV國家政策單位政策身體狀況過勞死工作壓力WBP(A)四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類2.聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法基于密度的方法孤立點分析四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類什么是聚類分析?聚類:數(shù)據(jù)對象的集合同一簇中的對象彼此相似與其他簇中的對象彼此相異Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以類聚人以群分什么是聚類分析?聚類:數(shù)據(jù)對象的集合Inter-cluste聚類分析將數(shù)據(jù)對象的集合分成由相似對象組成的多個類聚類分析中要劃分的類是未知的典型的應(yīng)用作為獨立的工具來獲得數(shù)據(jù)分布的情況也可以作為其他算法的預(yù)處理步驟

聚類分析同一數(shù)據(jù)的不同聚類結(jié)果Howmanyclusters?SixClusters

同一數(shù)據(jù)的不同聚類結(jié)果Howmanyclusters?SFourClusters

TwoClusters

FourClustersTwoClusters典型的聚類分析應(yīng)用模式識別數(shù)據(jù)分析圖象處理經(jīng)濟學(xué)（特別是在市場分析中）互聯(lián)網(wǎng)典型的聚類分析應(yīng)用對聚類算法的要求良好的聚類算法首先應(yīng)該保證簇內(nèi)對象的良好的相似性簇間對象的良好的相異性聚類算法的質(zhì)量取決于算法對相似性的判別標(biāo)準(zhǔn)以及算法的具體實現(xiàn)算法的質(zhì)量還取決于算法發(fā)現(xiàn)隱藏著的模式的能力對聚類算法的要求良好的聚類算法首先應(yīng)該保證數(shù)據(jù)挖掘?qū)垲惖牡湫鸵罂缮炜s性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀的聚類用于決定輸入?yún)?shù)的領(lǐng)域知識的最小化處理噪聲數(shù)據(jù)的能力對輸入記錄的順序不敏感高維性基于約束的聚類可解釋性和可用性數(shù)據(jù)挖掘?qū)垲惖牡湫鸵罂缮炜s性4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型4.2聚類分析什么是聚類分析?數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣(二模)相異度矩陣(單模)對象對的相異度數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣對象對的相異度聚類分析中的數(shù)據(jù)類型（1）區(qū)間標(biāo)度變量:重量、高度、經(jīng)緯度、氣溫二元變量:只有兩種狀態(tài)得病、未得病；0,1聚類分析中的數(shù)據(jù)類型（1）區(qū)間標(biāo)度變量:聚類分析中的數(shù)據(jù)類型（2）分類、序數(shù)型和比例標(biāo)度型變量:分類：紅、黃、藍、綠序數(shù)：講師、副教授、教授混合類型變量:聚類分析中的數(shù)據(jù)類型（2）分類、序數(shù)型和比例標(biāo)度型變量:如何計算對象間的相異度？兩個對象間的相異度是基于對象間距離來計算的常用的方法包括:明考斯基距離Minkowski:這里i=(xi1,xi2,…,xip)andj=(xj1,xj2,…,xjp)是兩個p維的數(shù)據(jù)對象如果q＝1，那么這個就是曼哈坦距離如何計算對象間的相異度？兩個對象間的相異度是基于對象間距離來SimilarityandDissimilarityBetweenObjects(Cont.)如果q＝2，那么就是歐幾里的距離:對于距離函數(shù)滿足如下要求d(i,j)

0d(i,i)

=0d(i,j)

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

d(i,k)

+d(k,j)加權(quán)也可以用于曼哈坦距離和明考斯基距離SimilarityandDissimilarityB4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類4.2聚類分析什么是聚類分析?主要的聚類方法劃分方法:構(gòu)建數(shù)據(jù)的若干個劃分層次方法:按某種標(biāo)準(zhǔn)將給定數(shù)據(jù)對象集合進行層次的分解基于密度的方法:基于連接和密度函數(shù)基于網(wǎng)格的方法:基于多層粒度結(jié)構(gòu)基于模型的方法:為每個簇假定一個模型，尋找數(shù)據(jù)對模型進行最佳擬和主要的聚類方法劃分方法:構(gòu)建數(shù)據(jù)的若干個劃分劃分聚類OriginalPointsAPartitionalClustering簇劃分聚類OriginalPointsAPartition層次聚類TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram層次聚類TraditionalHierarchicalC簇（Clusters）的類型

明顯分離的簇基于中心的簇基于鄰近的簇基于密度的簇概念簇簇（Clusters）的類型明顯分離的簇明顯分離的簇3well-separatedclusters明顯分離的簇3well-separatedcluster基于中心的簇Center-based

每個點到簇中心的距離，比到其他簇中心的距離更近4center-basedclusters基于中心的簇Center-based4center-bas基于鄰近的簇NearestneighborAclusterisasetofpointssuchthatapointinaclusteriscloser(ormoresimilar)tooneormoreotherpointsintheclusterthantoanypointnotinthecluster.8contiguousclusters基于鄰近的簇Nearestneighbor8contig基于密度的簇Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.6density-basedclusters基于密度的簇Density-based6density-b概念簇SharedPropertyorConceptualClustersFindsclustersthatsharesomecommonpropertyorrepresentaparticularconcept..2OverlappingCircles概念簇SharedPropertyorConceptu4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法4.2聚類分析什么是聚類分析?劃分方法:基本概念劃分方法:為包含n個數(shù)據(jù)對象的數(shù)據(jù)庫生成k個簇給定k值，采用一個劃分規(guī)則將對象組織成k個劃分全局優(yōu)化:盡可能枚舉所有劃分啟發(fā)式方法:k-均值和k-中心點算法k-均值

(MacQueen’67):每個簇以其對象平均值作為代表（簇中心，或質(zhì)心）k-中心點或

PAM(Kaufman&Rousseeuw’87):每個簇以其中的某一點代表劃分方法:基本概念劃分方法:為包含n個數(shù)據(jù)對象的數(shù)據(jù)庫生成K-均值方法給定k:1.任意選擇k個點作為初始的質(zhì)心2.repeat3.將每個點指派到最近（相似）的簇集4.重新計算每個簇的均值，即更新質(zhì)心5.until不再發(fā)生變化.K-均值方法給定k:K-均值方法例K-均值方法例最優(yōu)與次優(yōu)聚類結(jié)果Sub-optimalClusteringOptimalClusteringOriginalPoints最優(yōu)與次優(yōu)聚類結(jié)果Sub-optimalClusterin隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例2）但是，隨機選擇的初始質(zhì)心，未必能得到最優(yōu)的結(jié)果隨機選擇初始質(zhì)心（例2）但是，隨機選擇的初始質(zhì)心，未必能得到隨機選擇初始質(zhì)心（例2）隨機選擇初始質(zhì)心（例2）k-均值的優(yōu)點簡單、有效可用于各種數(shù)據(jù)類型（但并非適合所有數(shù)據(jù)類型）k-均值的優(yōu)點簡單、有效k-均值的局限（缺點）不能處理：不同尺寸的簇不同密度的簇非球形的簇對含離群點的數(shù)據(jù)聚類時也有問題k-均值的局限（缺點）不能處理：不同尺寸的簇OriginalPointsK-means(3Clusters)不同尺寸的簇OriginalPointsK-means(不同密度的簇OriginalPointsK-means(3Clusters)不同密度的簇OriginalPointsK-means(非球形的簇OriginalPointsK-means(2Clusters)非球形的簇OriginalPointsK-means(2克服K-means的局限OriginalPoints K-meansClusters一種方法是使用更多的簇（較小的簇集）.發(fā)現(xiàn)簇集的子簇,但是需要將子簇合并.克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints K中心點方法在簇集中找到簇中最中心位置的點，也就是中心點PAM(圍繞中心點的劃分,1987)最初隨機選定k個中心點后，反復(fù)試圖尋找更好的中心點，分析所有可能的對象對。PAM

適合于小數(shù)據(jù)集，但是在大數(shù)據(jù)集上效果不佳CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):隨即抽樣K中心點方法在簇集中找到簇中最中心位置的點，也就是中心點對比k-中心與k-均值當(dāng)存在噪聲和離群點時，k-中心法更魯棒k-中心法的執(zhí)行代價高于k-均值法對比k-中心與k-均值當(dāng)存在噪聲和離群點時，k-中心法更魯棒小結(jié)與回顧聚類分析同一數(shù)據(jù)，不同聚類方法可導(dǎo)致不同結(jié)果距離的度量基于劃分的聚類k-均值法小結(jié)與回顧聚類分析K-均值方法給定k:1.任意選擇k個點作為初始的質(zhì)心2.repeat3.將每個點指派到最近（相似）的簇集4.重新計算每個簇的均值，即更新質(zhì)心5.until不再發(fā)生變化.K-均值方法給定k:K-均值方法例K-均值方法例k-均值的優(yōu)點簡單、有效可用于各種數(shù)據(jù)類型（但并非適合所有數(shù)據(jù)類型）k-均值的優(yōu)點簡單、有效k-均值的局限（缺點）不能處理：不同尺寸的簇不同密度的簇非球形的簇對含離群點的數(shù)據(jù)聚類時也有問題k-均值的局限（缺點）不能處理：4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法4.2聚類分析什么是聚類分析?層次聚類HierarchicalClustering:NestedClustersDendrogram樹狀圖12345612345層次聚類HierarchicalClustering:Ne層次方法將嵌套定義的簇集組成一棵層次形式的樹按照分裂方式可分為：凝聚的把每個點都作為一個簇，開始聚類每一步合并兩個最近的簇，直到只剩下一個簇分裂的所有的點看做一個簇每一步，分裂一個簇，直到每個點都是一個簇層次方法將嵌套定義的簇集組成一棵層次形式的樹層次聚類方法利用相似度或距離矩陣作為聚類標(biāo)準(zhǔn).這種方法不需要提供k值，但是必須提供中止條件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚的(AGNES)分裂的(DIANA)層次聚類方法利用相似度或距離矩陣作為聚類標(biāo)準(zhǔn).這種方法不需AGNES(凝聚的層次聚類)KaufmannandRousseeuw(1990)將具有最少相異性的點合并將這些簇合并成越來越大的簇直到所有終結(jié)條件被滿足AGNES(凝聚的層次聚類)KaufmannandRoDIANA(分裂的層次聚類)KaufmannandRousseeuw(1990)與AGNES剛好相反直到每個對象自成一簇DIANA(分裂的層次聚類)KaufmannandRo基本層次凝聚聚類基本算法簡單直接：計算相似度矩陣（或鄰近矩陣）以每個點為一個簇Repeat

合并最近的兩個簇 更新相似度矩陣Until

僅剩下一個簇

關(guān)鍵操作:計算兩個簇間的相似度有多種方法度量距離或者相似度基本層次凝聚聚類基本算法簡單直接：簡單直接的凝聚聚類初始，每個點都為一個簇集，計算鄰近矩陣p1p3p5p4p2p1p2p3p4p5......ProximityMatrix簡單直接的凝聚聚類初始，每個點都為一個簇集，計算鄰近矩陣p中間過程經(jīng)若干次合并后C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中間過程經(jīng)若干次合并后C1C4C2C5C3C2C1C1C3C中間過程合并C2與C5，更新矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中間過程合并C2與C5，更新矩陣C1C4C2C5C3C2C合并后問題：“如何更新矩陣?”C1C4C2UC5C3???? ???C2UC5C1C1C3C4C2UC5C3C4ProximityMatrix合并后問題：“如何更新矩陣?”C1C4C2UC5C3如何度量簇間距離（相似性）

p1p3p5p4p2p1p2p3p4p5......Similarity?最小距離最大距離均值距離中心點間距離其他ProximityMatrix如何度量簇間距離（相似性）p1p3p5p4p2p1p2p3HowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他兩個極端折中HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他HowtoDefineInter-ClusterSi最近鄰聚類與單連接算法最近鄰：以最小距離度量簇間距離單連接：最近的簇間距離超過某個閾值聚類就會終止12345最近鄰聚類與單連接算法最近鄰：以最小距離度量簇間距離1234最近鄰聚類:MINNestedClustersDendrogram12345612345最近鄰聚類:MINNestedClustersDendrMIN的優(yōu)點OriginalPointsTwoClusters

能夠處理非橢圓形簇集MIN的優(yōu)點OriginalPointsTwoClustMIN的局限OriginalPointsTwoClusters

對噪聲和離群點敏感MIN的局限OriginalPointsTwoClust最遠鄰聚類與全連接算法最遠鄰：以最大距離度量簇間距離。（合并最大距離最小的兩個簇）全連接：當(dāng)最近簇間最大距離大于某個閾值時聚類便終止。12345最遠鄰聚類與全連接算法最遠鄰：以最大距離度量簇間距離。（合并最遠鄰聚類:MAXNestedClustersDendrogram12345612534最遠鄰聚類:MAXNestedClustersDendrMAX的優(yōu)點OriginalPointsTwoClusters

對噪聲和離群點不太敏感MAX的優(yōu)點OriginalPointsTwoClustMAX的局限OriginalPointsTwoClusters可能分裂大的簇偏好球形簇MAX的局限OriginalPointsTwoClust均值距離或平均距離聚類兩個簇間所有點對距離的平均值12345均值距離或平均距離聚類兩個簇間所有點對距離的平均值12345均值距離聚類NestedClustersDendrogram12345612534均值距離聚類NestedClustersDendrogra均值距離聚類是對最小和最大距離的一種折中優(yōu)點對噪聲和離群點不敏感不足偏好球形簇均值距離聚類是對最小和最大距離的一種折中層次聚類比較GroupAverageMINMAX123456125341234561253412345612345層次聚類比較GroupAverageMINMAX12345層次聚類的困難合并或分裂點的選擇非常關(guān)鍵一旦選定，下一步的處理將針對新的簇進行，已做過的處理不能撤銷，簇間也不能交換對象。若一步選擇沒做好，就可能導(dǎo)致低質(zhì)量的結(jié)果。合并與分裂的計算量較大改進：與其他聚類技術(shù)集成，多階段聚類層次聚類的困難合并或分裂點的選擇非常關(guān)鍵CURE(ClusteringUsingREpresentatives)CURE:byGuha,Rastogi&Shim,1998利用固定數(shù)目的具有代表性的點來代表一個簇，從而衡量兩個簇集之間的距離，合并有最近代表對的兩個簇集。CURE(ClusteringUsingREpreseCure:算法抽取隨機樣本s.將樣本分割成一組劃分對每個劃分局部的聚類刪除孤立點通過隨機抽樣如果一個簇增長的太慢，刪除它.對局部的簇集聚類用相應(yīng)的簇標(biāo)簽來標(biāo)記數(shù)據(jù)Cure:算法抽取隨機樣本s.數(shù)據(jù)劃分和聚類s=50p=2s/p=25xxxyyyyxyxs/pq=5數(shù)據(jù)劃分和聚類s=50xxxyyyyxyxs/pq=Cure:收縮代表點按照某個收縮因子向簇中心收縮代表點.代表點決定了簇集的形狀xyxyCure:收縮代表點按照某個收縮因子向簇中心收縮代表點.CURE不能處理不同密度的簇OriginalPointsCURECURE不能處理不同密度的簇OriginalPointsCHAMELEON基于圖的CHAMELEON:采用動態(tài)模型的算法，byG.Karypis,E.H.HanandV.Kumar’99通過動態(tài)模型衡量相似性如果兩個簇集的互聯(lián)性和相似度與簇內(nèi)部對象間的互聯(lián)性和相似度高度相關(guān)，則合并這兩個簇。算法分作兩步1.通過一個圖劃分算法將數(shù)據(jù)對象聚類成大量相對較小的子聚類2.然后用一個凝聚的層次凝聚算法通過反復(fù)地合并子類來找到真正的結(jié)果簇CHAMELEON基于圖的CHAMELEON:采用動態(tài)模型的CHAMELEON算法的大致框架構(gòu)造稀疏圖劃分圖合并劃分最終的簇集DataSetCHAMELEON算法的大致框架構(gòu)造稀疏圖劃分圖合并劃分最終ExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CURE(10clusters)ExperimentalResults:CURE(10ExperimentalResults:CURE(15clusters)ExperimentalResults:CURE(15ExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CURE(9clusters)ExperimentalResults:CURE(9ExperimentalResults:CURE(15clusters)ExperimentalResults:CURE(15小結(jié)層次聚類凝聚的和分裂的簇間距離：最小、最大、均值、中心點最近鄰與單連接最遠鄰與全連接CURE，CHAMELEON小結(jié)層次聚類4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法基于密度的方法4.2聚類分析什么是聚類分析?基于密度的簇集方法主要特征:發(fā)現(xiàn)任意形狀的簇集處理噪聲單次掃描需要密度參數(shù)作為中止條件若干相關(guān)研究:DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)基于密度的簇集方法主要特征:基于密度的聚集：背景知識兩個參數(shù):Eps:鄰域半徑MinPts:對象領(lǐng)域中至少包含的最小對象數(shù)目NEps(p): {q屬于D|dist(p,q)<=Eps}直接可達:在下面條件滿足情況下，我們稱點p侍從對象q

關(guān)于.Eps,MinPts

直接可達的 1)p

屬于NEps(q)2)核心對象條件:

|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm基于密度的聚集：背景知識兩個參數(shù):pqMinPts=5基于密度的聚集：背景知識(II)密度可達:當(dāng)存在一個對象鏈p1,…,pn,p1=q,pn=p

，其中pi+1

是pi直接密度可達的情況下，點p從點q關(guān)于Eps,MinPts密度相關(guān)點p

和點q

是關(guān)于.Eps,MinPts對象相關(guān)的，當(dāng)存在一個點o，使得p

和q

都是從o

關(guān)于.Eps和MinPts密度可達的.pqp1pqo基于密度的聚集：背景知識(II)密度可達:pqp1pqoDBSCAN:基于高密度連接區(qū)域的密度聚類方法基于密度的簇集:簇被定義為密度相連點的最大集合可以在帶有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。CoreBorderOutlierEps=1cmMinPts=5DBSCAN:基于高密度連接區(qū)域的密度聚類方法基于密度的簇DBSCAN:算法隨機的選擇點p尋找所有從點p

關(guān)于EpsandMinPts.密度可達的點如果p

是核心點,那么一個簇集已經(jīng)生成了如果p只是邊緣點,從點p

沒有哪一個點是密度可達的，DBSCAN訪問數(shù)據(jù)庫中下一個點.重復(fù)上述過程知道中止條件滿足DBSCAN:算法隨機的選擇點pDBSCAN:Core,Border,andNoisePointsDBSCAN:Core,Border,andNoisDBSCAN:SensitivetoParametersDBSCAN:SensitivetoParameterDBSCAN:Core,BorderandNoisePointsOriginalPointsPointtypes:core,borderandnoiseEps=10,MinPts=4DBSCAN:Core,BorderandNoiseWhenDBSCANWorksWellOriginalPointsClustersResistanttoNoiseCanhandleclustersofdifferentshapesandsizesWhenDBSCANWorksWellOriginalWhenDBSCANDoesNOTWorkWellOriginalPoints(MinPts=4,Eps=9.75).

(MinPts=4,Eps=9.92)VaryingdensitiesHigh-dimensionaldataWhenDBSCANDoesNOTWorkWell4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法基于密度的方法孤立點（離群點）分析4.2聚類分析什么是聚類分析?什么是孤立點?什么是孤立點?與數(shù)據(jù)的其他部分不同或不一致例如:Sports:MichaelJordon,WayneGretzky,...問題找到前n個孤立點應(yīng)用:監(jiān)測信用卡詐騙監(jiān)測電話詐騙分析收入極高和極低的消費者的行為醫(yī)療分析什么是孤立點?什么是孤立點?基于統(tǒng)計的孤立點查詢對給定的數(shù)據(jù)集合假設(shè)了一個分布或概率模型進行不一致性檢驗，根據(jù)數(shù)據(jù)集參數(shù)分布參數(shù)預(yù)期的孤立點數(shù)目缺點針對單個屬性很多情況下數(shù)據(jù)分布是未知的?；诮y(tǒng)計的孤立點查詢對給定的數(shù)據(jù)集合假設(shè)了一個分布或概率模基于距離的孤立點查詢?yōu)榱私鉀Q統(tǒng)計學(xué)方法的一些限制，引入了基于距離的孤立點概念我們需要在不知道數(shù)據(jù)分布的情況下處理多位數(shù)據(jù).基于距離的孤立點:如果數(shù)據(jù)集合T中至少有p部分對象與對象O的距離大于d，那么就稱O為一個帶參數(shù)p和d的基于距離的孤立點計語句你的孤立點算法基于索引的算法嵌套循環(huán)算法基于單元的算法基于距離的孤立點查詢?yōu)榱私鉀Q統(tǒng)計學(xué)方法的一些限制，引入了基于基于密度的方法:LOFForeachpoint,computethedensityofitslocalneighborhoodComputelocaloutlierfactor(LOF)ofasamplepastheaverageoftheratiosofthedensityofsamplepandthedensityofitsnearestneighborsOutliersarepointswithlargestLOFvaluep2p1基于密度的方法:LOFForeachpoint,co基于聚類的方法Basicidea:ClusterthedataintogroupsofdifferentdensityChoosepointsinsmallclusterascandidateoutliersComputethedistancebetweencandidatepointsandnon-candidateclusters.Ifcandidatepointsarefarfromallothernon-candidatepoints,theyareoutliers基于聚類的方法Basicidea:基于偏離的孤立點預(yù)測通過一組對象的主要特征來識別孤立點與給出描述偏離的對象就被認(rèn)為是孤立點序列異常技術(shù)模仿了人類從一系列的推測類似對象中識別異常對象的方式OLAP數(shù)據(jù)立方體技術(shù)利用在大規(guī)模多維數(shù)據(jù)中采用數(shù)據(jù)立方體來確定反常區(qū)域?；谄x的孤立點預(yù)測通過一組對象的主要特征來識別孤立點數(shù)據(jù)挖掘

DataMining閆雷鳴2022/12/9數(shù)據(jù)挖掘

DataMining閆雷鳴四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類2.聚類分析四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類4.1貝葉斯分類:為什么?可能性學(xué)習(xí)可能性預(yù)測4.1貝葉斯分類:為什么?貝葉斯定理給定訓(xùn)練數(shù)據(jù)

D,條件h的后驗概率MAP假設(shè)貝葉斯定理MAP極大后驗假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時可能性最大的假設(shè)h，h被稱為極大后驗假設(shè)（MAP）確定MAP的方法是用貝葉斯公式計算每個候選假設(shè)的后驗概率，計算式如下 最后一步，去掉了P(D)，因為它是不依賴于h的常量MAP極大后驗假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時可樸素貝葉斯分類樸素假定:屬性獨立P(x1,…,xk|C)=P(x1|C)·…·P(xk|C)假如i-th是分類屬性:

P(xi|C)類C中屬性i-th具有值xi假如i-th屬性連續(xù)的:

P(xi|C)通過高斯密度函數(shù)來估計兩種情況下計算容易樸素貝葉斯分類樸素假定:屬性獨立樸素貝葉斯分類(I)樸素假定:屬性類條件獨立:大大降低計算開銷,只計算類的分布.樸素貝葉斯分類(I)樸素假定:屬性類條件獨立:樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計算出概率（出去打網(wǎng)球）樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計算出概率（出去打網(wǎng)打網(wǎng)球?qū)嵗?估計P(xi|C)outlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(true|p)=3/9P(true|n)=3/5P(false|p)=6/9P(false|n)=2/5P(p)=9/14P(n)=5/14打網(wǎng)球?qū)嵗?估計P(xi|C)outlookP(sunn打網(wǎng)球?qū)嵗?分類XX=<rain,hot,high,false>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286樣本X通過類

n(don’tplay)來分類打網(wǎng)球?qū)嵗?分類X貝葉斯信念網(wǎng)絡(luò)(I)貝葉斯信念網(wǎng)絡(luò)允許在變量的子集間定義類條件獨立性提供一種因果關(guān)系的圖形學(xué)習(xí)貝葉斯信念網(wǎng)絡(luò)的幾種情況網(wǎng)絡(luò)結(jié)構(gòu)和變量均給出，容易給出網(wǎng)絡(luò)結(jié)構(gòu)和部分變量網(wǎng)絡(luò)結(jié)構(gòu)預(yù)先不知道貝葉斯信念網(wǎng)絡(luò)(I)貝葉斯信念網(wǎng)絡(luò)允許在變量的子集間定義類貝葉斯信念網(wǎng)絡(luò)(II)FamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.10.9貝葉斯信念網(wǎng)絡(luò)肺癌的條件概率表貝葉斯信念網(wǎng)絡(luò)(II)FamilyLungCancerPo國家政策（C）單位政策（U）身體狀況差（B）過勞死（D）工作壓力大（W）WBP(A)tttfftff0.3350.300.050.00UP(W)tf0.900.05CP(U)tf0.950.01P(C)0.50UP(B)tf0.300.01已知：一個事件e={單位政策U=true,and工作壓力大=true}，請近似計算出現(xiàn)過勞死的概率?！癗oonecanservetwomasters.Eitherhewillhatetheoneandlovetheother,orhewillbedevotedtotheoneanddespisetheother.YoucannotservebothGodandMoney.”

FromMatthew6:24NIV國家政策單位政策身體狀況過勞死工作壓力WBP(A)四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類2.聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法基于密度的方法孤立點分析四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類什么是聚類分析?聚類:數(shù)據(jù)對象的集合同一簇中的對象彼此相似與其他簇中的對象彼此相異Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以類聚人以群分什么是聚類分析?聚類:數(shù)據(jù)對象的集合Inter-cluste聚類分析將數(shù)據(jù)對象的集合分成由相似對象組成的多個類聚類分析中要劃分的類是未知的典型的應(yīng)用作為獨立的工具來獲得數(shù)據(jù)分布的情況也可以作為其他算法的預(yù)處理步驟

聚類分析同一數(shù)據(jù)的不同聚類結(jié)果Howmanyclusters?SixClusters

同一數(shù)據(jù)的不同聚類結(jié)果Howmanyclusters?SFourClusters

TwoClusters

FourClustersTwoClusters典型的聚類分析應(yīng)用模式識別數(shù)據(jù)分析圖象處理經(jīng)濟學(xué)（特別是在市場分析中）互聯(lián)網(wǎng)典型的聚類分析應(yīng)用對聚類算法的要求良好的聚類算法首先應(yīng)該保證簇內(nèi)對象的良好的相似性簇間對象的良好的相異性聚類算法的質(zhì)量取決于算法對相似性的判別標(biāo)準(zhǔn)以及算法的具體實現(xiàn)算法的質(zhì)量還取決于算法發(fā)現(xiàn)隱藏著的模式的能力對聚類算法的要求良好的聚類算法首先應(yīng)該保證數(shù)據(jù)挖掘?qū)垲惖牡湫鸵罂缮炜s性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀的聚類用于決定輸入?yún)?shù)的領(lǐng)域知識的最小化處理噪聲數(shù)據(jù)的能力對輸入記錄的順序不敏感高維性基于約束的聚類可解釋性和可用性數(shù)據(jù)挖掘?qū)垲惖牡湫鸵罂缮炜s性4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型4.2聚類分析什么是聚類分析?數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣(二模)相異度矩陣(單模)對象對的相異度數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣對象對的相異度聚類分析中的數(shù)據(jù)類型（1）區(qū)間標(biāo)度變量:重量、高度、經(jīng)緯度、氣溫二元變量:只有兩種狀態(tài)得病、未得??；0,1聚類分析中的數(shù)據(jù)類型（1）區(qū)間標(biāo)度變量:聚類分析中的數(shù)據(jù)類型（2）分類、序數(shù)型和比例標(biāo)度型變量:分類：紅、黃、藍、綠序數(shù)：講師、副教授、教授混合類型變量:聚類分析中的數(shù)據(jù)類型（2）分類、序數(shù)型和比例標(biāo)度型變量:如何計算對象間的相異度？兩個對象間的相異度是基于對象間距離來計算的常用的方法包括:明考斯基距離Minkowski:這里i=(xi1,xi2,…,xip)andj=(xj1,xj2,…,xjp)是兩個p維的數(shù)據(jù)對象如果q＝1，那么這個就是曼哈坦距離如何計算對象間的相異度？兩個對象間的相異度是基于對象間距離來SimilarityandDissimilarityBetweenObjects(Cont.)如果q＝2，那么就是歐幾里的距離:對于距離函數(shù)滿足如下要求d(i,j)

0d(i,i)

=0d(i,j)

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

d(i,k)

+d(k,j)加權(quán)也可以用于曼哈坦距離和明考斯基距離SimilarityandDissimilarityB4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類4.2聚類分析什么是聚類分析?主要的聚類方法劃分方法:構(gòu)建數(shù)據(jù)的若干個劃分層次方法:按某種標(biāo)準(zhǔn)將給定數(shù)據(jù)對象集合進行層次的分解基于密度的方法:基于連接和密度函數(shù)基于網(wǎng)格的方法:基于多層粒度結(jié)構(gòu)基于模型的方法:為每個簇假定一個模型，尋找數(shù)據(jù)對模型進行最佳擬和主要的聚類方法劃分方法:構(gòu)建數(shù)據(jù)的若干個劃分劃分聚類OriginalPointsAPartitionalClustering簇劃分聚類OriginalPointsAPartition層次聚類TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram層次聚類TraditionalHierarchicalC簇（Clusters）的類型

明顯分離的簇基于中心的簇基于鄰近的簇基于密度的簇概念簇簇（Clusters）的類型明顯分離的簇明顯分離的簇3well-separatedclusters明顯分離的簇3well-separatedcluster基于中心的簇Center-based

每個點到簇中心的距離，比到其他簇中心的距離更近4center-basedclusters基于中心的簇Center-based4center-bas基于鄰近的簇NearestneighborAclusterisasetofpointssuchthatapointinaclusteriscloser(ormoresimilar)tooneormoreotherpointsintheclusterthantoanypointnotinthecluster.8contiguousclusters基于鄰近的簇Nearestneighbor8contig基于密度的簇Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.6density-basedclusters基于密度的簇Density-based6density-b概念簇SharedPropertyorConceptualClustersFindsclustersthatsharesomecommonpropertyorrepresentaparticularconcept..2OverlappingCircles概念簇SharedPropertyorConceptu4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法4.2聚類分析什么是聚類分析?劃分方法:基本概念劃分方法:為包含n個數(shù)據(jù)對象的數(shù)據(jù)庫生成k個簇給定k值，采用一個劃分規(guī)則將對象組織成k個劃分全局優(yōu)化:盡可能枚舉所有劃分啟發(fā)式方法:k-均值和k-中心點算法k-均值

(MacQueen’67):每個簇以其對象平均值作為代表（簇中心，或質(zhì)心）k-中心點或

PAM(Kaufman&Rousseeuw’87):每個簇以其中的某一點代表劃分方法:基本概念劃分方法:為包含n個數(shù)據(jù)對象的數(shù)據(jù)庫生成K-均值方法給定k:1.任意選擇k個點作為初始的質(zhì)心2.repeat3.將每個點指派到最近（相似）的簇集4.重新計算每個簇的均值，即更新質(zhì)心5.until不再發(fā)生變化.K-均值方法給定k:K-均值方法例K-均值方法例最優(yōu)與次優(yōu)聚類結(jié)果Sub-optimalClusteringOptimalClusteringOriginalPoints最優(yōu)與次優(yōu)聚類結(jié)果Sub-optimalClusterin隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例1）隨機選擇初始質(zhì)心（例2）但是，隨機選擇的初始質(zhì)心，未必能得到最優(yōu)的結(jié)果隨機選擇初始質(zhì)心（例2）但是，隨機選擇的初始質(zhì)心，未必能得到隨機選擇初始質(zhì)心（例2）隨機選擇初始質(zhì)心（例2）k-均值的優(yōu)點簡單、有效可用于各種數(shù)據(jù)類型（但并非適合所有數(shù)據(jù)類型）k-均值的優(yōu)點簡單、有效k-均值的局限（缺點）不能處理：不同尺寸的簇不同密度的簇非球形的簇對含離群點的數(shù)據(jù)聚類時也有問題k-均值的局限（缺點）不能處理：不同尺寸的簇OriginalPointsK-means(3Clusters)不同尺寸的簇OriginalPointsK-means(不同密度的簇OriginalPointsK-means(3Clusters)不同密度的簇OriginalPointsK-means(非球形的簇OriginalPointsK-means(2Clusters)非球形的簇OriginalPointsK-means(2克服K-means的局限OriginalPoints K-meansClusters一種方法是使用更多的簇（較小的簇集）.發(fā)現(xiàn)簇集的子簇,但是需要將子簇合并.克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints 克服K-means的局限OriginalPoints K-meansClusters克服K-means的局限OriginalPoints K中心點方法在簇集中找到簇中最中心位置的點，也就是中心點PAM(圍繞中心點的劃分,1987)最初隨機選定k個中心點后，反復(fù)試圖尋找更好的中心點，分析所有可能的對象對。PAM

適合于小數(shù)據(jù)集，但是在大數(shù)據(jù)集上效果不佳CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):隨即抽樣K中心點方法在簇集中找到簇中最中心位置的點，也就是中心點對比k-中心與k-均值當(dāng)存在噪聲和離群點時，k-中心法更魯棒k-中心法的執(zhí)行代價高于k-均值法對比k-中心與k-均值當(dāng)存在噪聲和離群點時，k-中心法更魯棒小結(jié)與回顧聚類分析同一數(shù)據(jù)，不同聚類方法可導(dǎo)致不同結(jié)果距離的度量基于劃分的聚類k-均值法小結(jié)與回顧聚類分析K-均值方法給定k:1.任意選擇k個點作為初始的質(zhì)心2.repeat3.將每個點指派到最近（相似）的簇集4.重新計算每個簇的均值，即更新質(zhì)心5.until不再發(fā)生變化.K-均值方法給定k:K-均值方法例K-均值方法例k-均值的優(yōu)點簡單、有效可用于各種數(shù)據(jù)類型（但并非適合所有數(shù)據(jù)類型）k-均值的優(yōu)點簡單、有效k-均值的局限（缺點）不能處理：不同尺寸的簇不同密度的簇非球形的簇對含離群點的數(shù)據(jù)聚類時也有問題k-均值的局限（缺點）不能處理：4.2聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法4.2聚類分析什么是聚類分析?層次聚類HierarchicalClustering:NestedClustersDendrogram樹狀圖12345612345層次聚類HierarchicalClustering:Ne層次方法將嵌套定義的簇集組成一棵層次形式的樹按照分裂方式可分為：凝聚的把每個點都作為一個簇，開始聚類每一步合并兩個最近的簇，直到只剩下一個簇分裂的所有的點看做一個簇每一步，分裂一個簇，直到每個點都是一個簇層次方法將嵌套定義的簇集組成一棵層次形式的樹層次聚類方法利用相似度或距離矩陣作為聚類標(biāo)準(zhǔn).這種方法不需要提供k值，但是必須提供中止條件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚的(AGNES)分裂的(DIANA)層次聚類方法利用相似度或距離矩陣作為聚類標(biāo)準(zhǔn).這種方法不需AGNES(凝聚的層次聚類)KaufmannandRousseeuw(1990)將具有最少相異性的點合并將這些簇合并成越來越大的簇直到所有終結(jié)條件被滿足AGNES(凝聚的層次聚類)KaufmannandRoDIANA(分裂的層次聚類)KaufmannandRousseeuw(1990)與AGNES剛好相反直到每個對象自成一簇DIANA(分裂的層次聚類)KaufmannandRo基本層次凝聚聚類基本算法簡單直接：計算相似度矩陣（或鄰近矩陣）以每個點為一個簇Repeat

合并最近的兩個簇 更新相似度矩陣Until

僅剩下一個簇

關(guān)鍵操作:計算兩個簇間的相似度有多種方法度量距離或者相似度基本層次凝聚聚類基本算法簡單直接：簡單直接的凝聚聚類初始，每個點都為一個簇集，計算鄰近矩陣p1p3p5p4p2p1p2p3p4p5......ProximityMatrix簡單直接的凝聚聚類初始，每個點都為一個簇集，計算鄰近矩陣p中間過程經(jīng)若干次合并后C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中間過程經(jīng)若干次合并后C1C4C2C5C3C2C1C1C3C中間過程合并C2與C5，更新矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中間過程合并C2與C5，更新矩陣C1C4C2C5C3C2C合并后問題：“如何更新矩陣?”C1C4C2UC5C3???? ???C2UC5C1C1C3C4C2UC5C3C4ProximityMatrix合并后問題：“如何更新矩陣?”C1C4C2UC5C3如何度量簇間距離（相似性）

p1p3p5p4p2p1p2p3p4p5......Similarity?最小距離最大距離均值距離中心點間距離其他ProximityMatrix如何度量簇間距離（相似性）p1p3p5p4p2p1p2p3HowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他兩個極端折中HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點間距離其他HowtoDefineInter-ClusterSi最近鄰聚類與單連接算法最近鄰：以最小距離度量簇間距離單連接：最近的簇間距離超過某個閾值聚類就會終止12345最近鄰聚類與單連接算法最近鄰：以最小距離度量簇間距離1234最近鄰聚類:MINNestedClustersDendrogram12345612345最近鄰聚類:MINNestedClustersDendrMIN的優(yōu)點OriginalPointsTwoClusters

能夠處理非橢圓形簇集MIN的優(yōu)點OriginalPointsTwoClustMIN的局限OriginalPointsTwoClusters

對噪聲和離群點敏感MIN的局限OriginalPointsTwoClust最遠鄰聚類與全連接算法最遠鄰：以最大距離度量簇間距離。（合并最大距離最小的兩個簇）全連接：當(dāng)最近簇間最大距離大于某個閾值時聚類便終止。12345最遠鄰聚類與全連接算法最遠鄰：以最大距離度量簇間距離。（合并最遠鄰聚類:MAXNestedClustersDendrogram12345612534最遠鄰聚類:MAXNestedClustersDendrMAX的優(yōu)點OriginalPointsTwoClusters

對噪聲和離群點不太敏感MAX的優(yōu)點OriginalPointsTwoClustMAX的局限OriginalPointsTwoClusters可能分裂大的簇偏好球形簇MAX的局限OriginalPointsTwoClust均值距離或平均距離聚類兩個簇間所有點對距離的平均值12345均值距離或平均距離聚類兩個簇間所有點對距離的平均值12345均值距離聚類NestedClustersDendrogram12345612534均值距離聚類NestedClustersDendrogra均值距離聚類是對最小和最大距離的一種折中優(yōu)點對噪聲和離群點不敏感不足偏好球形簇均值距離聚類是對最小和最大距離的一種折中層次聚類比較GroupAverageMINMAX123456125341234561253412345612345層次聚類比較GroupAverageMINMAX12345層次聚類的困難合并或分裂點的選擇非常關(guān)鍵一旦選定，下一步的處理將針對新的簇進行，已做過的處理不能撤銷，簇間也不能交換對象。若一步選擇沒做好，就可能導(dǎo)致低質(zhì)量的結(jié)果。合并與分裂的計算量較大改進：與其他聚類技術(shù)集成，多階段聚類層次聚類的困難合并或分裂點的選擇非常關(guān)鍵CURE(ClusteringUsingREpresentatives)CURE:byGuha,Rastogi&Shim,1998利用固定數(shù)目的具有代表性的點來代表一個簇，從而衡量兩個簇集之間的距離，合并有最近代表對的兩個簇集。CURE(ClusteringUsingREpreseCure:算法抽取隨機樣本s.將樣本分割成一組劃分對每個劃分局部的聚類刪除孤立點通過隨機抽樣如果一個簇增長的太慢，刪除它.對局部的簇集聚類用相應(yīng)的簇標(biāo)簽來標(biāo)記數(shù)據(jù)Cure:算法抽取隨機樣本s.數(shù)據(jù)劃分和聚類s=50p=2s/p=25xxxyyyyxyxs/pq=5數(shù)據(jù)劃分和聚類s=50xxxyyyyxyxs/pq=Cure:收縮代表點按照某個收縮因子向簇中心收縮代表點.代表點決定了簇集的形狀xyxyCure:收縮代表點按照某個收縮因子向簇中心收縮代表點.CURE不能處理不同密度的簇OriginalPointsCURECURE不能處理不同密度的簇OriginalPointsCHAMELEON基于圖的CHAMELEON:采用動態(tài)模型的算法，byG.Karypis,E.H.HanandV.Kumar’99通過動態(tài)模型衡量相似性如果兩個簇集的互聯(lián)性和相似度與簇內(nèi)部對象間的互聯(lián)性和相似度高度相關(guān)，則合并這兩個簇。算法分作兩步1.通過一個圖劃分算法將數(shù)據(jù)對象聚類成大量相對較小的子聚類2.然后用一個凝聚的層次凝聚算法通過反復(fù)地合并子類來找到真正的結(jié)果簇CHAMELEON基于圖的CHAMELEON:采用動態(tài)模型的CHAMELEON算法的大致框架構(gòu)造稀疏圖劃分圖合并劃分最終的簇集DataSetCHAMELEON算法的大致框架構(gòu)造稀疏圖劃分圖合并劃分最終ExperimentalResults:CHAMELEONExperimentalResults:CHAMELEOExperimentalResults:CHAMELEONExpe