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ù)測(cè)4.1貝葉斯分類:為什么?貝葉斯定理給定訓(xùn)練數(shù)據(jù)

D,條件h的后驗(yàn)概率MAP假設(shè)貝葉斯定理MAP極大后驗(yàn)假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時(shí)可能性最大的假設(shè)h，h被稱為極大后驗(yàn)假設(shè)（MAP）確定MAP的方法是用貝葉斯公式計(jì)算每個(gè)候選假設(shè)的后驗(yàn)概率，計(jì)算式如下 最后一步，去掉了P(D)，因?yàn)樗遣灰蕾囉趆的常量MAP極大后驗(yàn)假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時(shí)可樸素貝葉斯分類樸素假定:屬性獨(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)通過(guò)高斯密度函數(shù)來(lái)估計(jì)兩種情況下計(jì)算容易樸素貝葉斯分類樸素假定:屬性獨(dú)立樸素貝葉斯分類(I)樸素假定:屬性類條件獨(dú)立:大大降低計(jì)算開銷,只計(jì)算類的分布.樸素貝葉斯分類(I)樸素假定:屬性類條件獨(dú)立:樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計(jì)算出概率（出去打網(wǎng)球）樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計(jì)算出概率（出去打網(wǎng)打網(wǎng)球?qū)嵗?估計(jì)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ū)嵗?估計(jì)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通過(guò)類

n(don’tplay)來(lái)分類打網(wǎng)球?qū)嵗?分類X貝葉斯信念網(wǎng)絡(luò)(I)貝葉斯信念網(wǎng)絡(luò)允許在變量的子集間定義類條件獨(dú)立性提供一種因果關(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國(guó)家政策（C）單位政策（U）身體狀況差（B）過(guò)勞死（D）工作壓力大（W）WBP(A)tttfftff0.3350.300.050.00UP(W)tf0.900.05CP(U)tf0.950.01P(C)0.50UP(B)tf0.300.01已知：一個(gè)事件e={單位政策U=true,and工作壓力大=true}，請(qǐng)近似計(jì)算出現(xiàn)過(guò)勞死的概率?！癗oonecanservetwomasters.Eitherhewillhatetheoneandlovetheother,orhewillbedevotedtotheoneanddespisetheother.YoucannotservebothGodandMoney.”

FromMatthew6:24NIV國(guó)家政策單位政策身體狀況過(guò)勞死工作壓力WBP(A)四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類2.聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法基于密度的方法孤立點(diǎn)分析四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類什么是聚類分析?聚類:數(shù)據(jù)對(duì)象的集合同一簇中的對(duì)象彼此相似與其他簇中的對(duì)象彼此相異Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以類聚人以群分什么是聚類分析?聚類:數(shù)據(jù)對(duì)象的集合Inter-cluste聚類分析將數(shù)據(jù)對(duì)象的集合分成由相似對(duì)象組成的多個(gè)類聚類分析中要?jiǎng)澐值念愂俏粗牡湫偷膽?yīng)用作為獨(dú)立的工具來(lái)獲得數(shù)據(jù)分布的情況也可以作為其他算法的預(yù)處理步驟

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

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

TwoClusters

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

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

每個(gè)點(diǎn)到簇中心的距離，比到其他簇中心的距離更近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個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)生成k個(gè)簇給定k值，采用一個(gè)劃分規(guī)則將對(duì)象組織成k個(gè)劃分全局優(yōu)化:盡可能枚舉所有劃分啟發(fā)式方法:k-均值和k-中心點(diǎn)算法k-均值

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

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

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

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

僅剩下一個(gè)簇

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

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

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

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

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點(diǎn)間距離其他兩個(gè)極端折中HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

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

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

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

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

關(guān)于.Eps,MinPts

直接可達(dá)的 1)p

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

|NEps(q)|>=MinPts

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

，其中pi+1

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

和點(diǎn)q

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

和q

都是從o

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

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

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

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

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

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

D,條件h的后驗(yàn)概率MAP假設(shè)貝葉斯定理MAP極大后驗(yàn)假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時(shí)可能性最大的假設(shè)h，h被稱為極大后驗(yàn)假設(shè)（MAP）確定MAP的方法是用貝葉斯公式計(jì)算每個(gè)候選假設(shè)的后驗(yàn)概率，計(jì)算式如下 最后一步，去掉了P(D)，因?yàn)樗遣灰蕾囉趆的常量MAP極大后驗(yàn)假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時(shí)可樸素貝葉斯分類樸素假定:屬性獨(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)通過(guò)高斯密度函數(shù)來(lái)估計(jì)兩種情況下計(jì)算容易樸素貝葉斯分類樸素假定:屬性獨(dú)立樸素貝葉斯分類(I)樸素假定:屬性類條件獨(dú)立:大大降低計(jì)算開銷,只計(jì)算類的分布.樸素貝葉斯分類(I)樸素假定:屬性類條件獨(dú)立:樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計(jì)算出概率（出去打網(wǎng)球）樸素貝葉斯分類(II)給定訓(xùn)練集,我們能計(jì)算出概率（出去打網(wǎng)打網(wǎng)球?qū)嵗?估計(jì)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ū)嵗?估計(jì)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通過(guò)類

n(don’tplay)來(lái)分類打網(wǎng)球?qū)嵗?分類X貝葉斯信念網(wǎng)絡(luò)(I)貝葉斯信念網(wǎng)絡(luò)允許在變量的子集間定義類條件獨(dú)立性提供一種因果關(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國(guó)家政策（C）單位政策（U）身體狀況差（B）過(guò)勞死（D）工作壓力大（W）WBP(A)tttfftff0.3350.300.050.00UP(W)tf0.900.05CP(U)tf0.950.01P(C)0.50UP(B)tf0.300.01已知：一個(gè)事件e={單位政策U=true,and工作壓力大=true}，請(qǐng)近似計(jì)算出現(xiàn)過(guò)勞死的概率?！癗oonecanservetwomasters.Eitherhewillhatetheoneandlovetheother,orhewillbedevotedtotheoneanddespisetheother.YoucannotservebothGodandMoney.”

FromMatthew6:24NIV國(guó)家政策單位政策身體狀況過(guò)勞死工作壓力WBP(A)四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類2.聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要的聚類方法分類劃分方法層次方法基于密度的方法孤立點(diǎn)分析四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類什么是聚類分析?聚類:數(shù)據(jù)對(duì)象的集合同一簇中的對(duì)象彼此相似與其他簇中的對(duì)象彼此相異Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以類聚人以群分什么是聚類分析?聚類:數(shù)據(jù)對(duì)象的集合Inter-cluste聚類分析將數(shù)據(jù)對(duì)象的集合分成由相似對(duì)象組成的多個(gè)類聚類分析中要?jiǎng)澐值念愂俏粗牡湫偷膽?yīng)用作為獨(dú)立的工具來(lái)獲得數(shù)據(jù)分布的情況也可以作為其他算法的預(yù)處理步驟

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

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

TwoClusters

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

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

每個(gè)點(diǎn)到簇中心的距離，比到其他簇中心的距離更近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個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)生成k個(gè)簇給定k值，采用一個(gè)劃分規(guī)則將對(duì)象組織成k個(gè)劃分全局優(yōu)化:盡可能枚舉所有劃分啟發(fā)式方法:k-均值和k-中心點(diǎn)算法k-均值

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

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

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

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

僅剩下一個(gè)簇

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

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

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

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

p1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點(diǎn)間距離其他兩個(gè)極端折中HowtoDefineInter-ClusterSiHowtoDefineInter-ClusterSimilarity

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

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

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

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