bigdaa數(shù)據(jù)挖掘培訓(xùn)

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

DataMining閆雷鳴2023/1/17四、數(shù)據(jù)挖掘技術(shù)21.貝葉斯分類2.聚類分析4.1貝葉斯分類:為什么?可能性學(xué)習(xí)可能性預(yù)測(cè)貝葉斯定理給定訓(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)樗遣灰蕾囉趆的常量樸素貝葉斯分類樸素假定:屬性獨(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ì)算容易樸素貝葉斯分類(I)樸素假定:屬性類條件獨(dú)立:大大降低計(jì)算開銷,只計(jì)算類的分布.樸素貝葉斯分類(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ū)嵗?分類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)絡(luò)(I)貝葉斯信念念網(wǎng)絡(luò)允許許在變量的的子集間定定義類條件件獨(dú)立性提供一種因因果關(guān)系的的圖形學(xué)習(xí)貝葉斯斯信念網(wǎng)絡(luò)絡(luò)的幾種情情況網(wǎng)絡(luò)結(jié)構(gòu)和和變量均給給出，容易易給出網(wǎng)絡(luò)結(jié)結(jié)構(gòu)和部分分變量網(wǎng)絡(luò)結(jié)構(gòu)預(yù)預(yù)先不知道道貝葉斯信念念網(wǎng)絡(luò)(II)FamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.10.9貝葉斯信念念網(wǎng)絡(luò)肺癌的條件件概率表國(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è)個(gè)事件e={單位政策U=true,and工作壓力大大=true}，請(qǐng)近似計(jì)算出出現(xiàn)過(guò)勞死死的概率。?！癗oonecanservetwomasters.Eitherhewillhatetheoneandlovetheother,orhewillbedevotedtotheoneanddespisetheother.YoucannotservebothGodandMoney.””FromMatthew6:24NIV四、數(shù)據(jù)挖挖掘技術(shù)21.貝葉斯分類類2.聚類分析什么是聚類類分析?聚類分析中中的數(shù)據(jù)類類型主要的聚類類方法分類類劃分方法層次方法基于密度的的方法孤立點(diǎn)分析析什么是聚類類分析?聚類:數(shù)據(jù)對(duì)象的的集合同一簇中的的對(duì)象彼此此相似與其他簇中中的對(duì)象彼彼此相異Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized物以類聚人以群分聚類分析將數(shù)據(jù)對(duì)象象的集合分分成由相似似對(duì)象組成成的多個(gè)類類聚類分析中中要?jiǎng)澐值牡念愂俏粗牡湫偷膽?yīng)用用作為獨(dú)立的工具具來(lái)獲得數(shù)據(jù)據(jù)分布的情情況也可以作為為其他算法法的預(yù)處理步驟驟同一數(shù)據(jù)的的不同聚類類結(jié)果Howmanyclusters?SixClusters

FourClusters

TwoClusters

典型的聚類類分析應(yīng)用用模式識(shí)別數(shù)據(jù)分析圖象處理經(jīng)濟(jì)學(xué)（特特別是在市市場(chǎng)分析中中）互聯(lián)網(wǎng)對(duì)聚類算法法的要求良好的聚類類算法首先先應(yīng)該保證證簇內(nèi)對(duì)象的的良好的相相似性簇間對(duì)象的的良好的相相異性聚類算法的的質(zhì)量取決決于算法對(duì)對(duì)相似性的的判別標(biāo)準(zhǔn)準(zhǔn)以及算法法的具體實(shí)實(shí)現(xiàn)算法的質(zhì)量量還取決于于算法發(fā)現(xiàn)現(xiàn)隱藏著的的模式的能能力數(shù)據(jù)挖掘?qū)?duì)聚類的典典型要求可伸縮性處理不同類類型屬性的的能力發(fā)現(xiàn)任意形形狀的聚類類用于決定輸輸入?yún)?shù)的的領(lǐng)域知識(shí)識(shí)的最小化化處理噪聲數(shù)數(shù)據(jù)的能力力對(duì)輸入記錄錄的順序不不敏感高維性基于約束的的聚類可解釋性和和可用性4.2聚類分析什么是聚類類分析?聚類分析中中的數(shù)據(jù)類類型數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣(二模)相異度矩陣陣(單模)對(duì)象對(duì)的相相異度聚類分析中中的數(shù)據(jù)類類型（1）區(qū)間標(biāo)度變變量:重量、高度度、經(jīng)緯度度、氣溫二元變量:只有兩種狀狀態(tài)得病、未得得??；0,1聚類分析中中的數(shù)據(jù)類類型（2）分類、序數(shù)數(shù)型和比例例標(biāo)度型變變量:分類：紅、、黃、藍(lán)、、綠序數(shù)：講師師、副教授授、教授混合類型變變量:如何計(jì)算對(duì)對(duì)象間的相相異度？?jī)蓚€(gè)對(duì)象間間的相異度度是基于對(duì)對(duì)象間距離離來(lái)計(jì)算的的常用的方法法包括:明考斯基距距離Minkowski:這里i=(xi1,xi2,…,xip)andj=(xj1,xj2,…,xjp)是兩個(gè)p維的數(shù)據(jù)對(duì)對(duì)象如果q＝1，那么這個(gè)個(gè)就是曼哈哈坦距離SimilarityandDissimilarityBetweenObjects(Cont.)如果果q＝2，那那么么就就是是歐歐幾幾里里的的距距離離:對(duì)于于距距離離函函數(shù)數(shù)滿滿足足如如下下要要求求d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)加權(quán)權(quán)也也可可以以用用于于曼曼哈哈坦坦距距離離和和明明考考斯斯基基距距離離4.2聚類類分分析析什么么是是聚聚類類分分析析?聚類類分分析析中中的的數(shù)數(shù)據(jù)據(jù)類類型型主要要的的聚聚類類方方法法分分類類主要要的的聚聚類類方方法法劃分分方方法法:構(gòu)建建數(shù)數(shù)據(jù)據(jù)的的若若干干個(gè)個(gè)劃劃分分層次次方方法法:按某某種種標(biāo)標(biāo)準(zhǔn)準(zhǔn)將將給給定定數(shù)數(shù)據(jù)據(jù)對(duì)對(duì)象象集集合合進(jìn)進(jìn)行行層層次次的的分分解解基于于密密度度的的方方法法:基于于連連接接和和密密度度函函數(shù)數(shù)基于于網(wǎng)網(wǎng)格格的的方方法法:基于于多多層層粒粒度度結(jié)結(jié)構(gòu)構(gòu)基于于模模型型的的方方法法:為每每個(gè)個(gè)簇簇假假定定一一個(gè)個(gè)模模型型，，尋尋找找數(shù)數(shù)據(jù)據(jù)對(duì)對(duì)模模型型進(jìn)進(jìn)行行最最佳佳擬擬和和劃分分聚聚類類OriginalPointsAPartitionalClustering簇層次次聚聚類類TraditionalHierarchicalClusteringNon-traditionalHierarchicalClusteringNon-traditionalDendrogramTraditionalDendrogram簇（（Clusters）的的類類型型明顯顯分分離離的的簇簇基于于中中心心的的簇簇基于于鄰鄰近近的的簇簇基于于密密度度的的簇簇概念念簇簇明顯顯分分離離的的簇簇3well-separatedclusters基于于中中心心的的簇簇Center-based每個(gè)個(gè)點(diǎn)點(diǎn)到到簇簇中中心心的的距距離離，，比比到到其其他他簇簇中中心心的的距距離離更更近近4center-basedclusters基于于鄰鄰近近的的簇簇NearestneighborAclusterisasetofpointssuchthatapointinaclusteriscloser(ormoresimilar)tooneormoreotherpointsintheclusterthantoanypointnotinthecluster.8contiguousclusters基于于密密度度的的簇簇Density-basedAclusterisadenseregionofpoints,whichisseparatedbylow-densityregions,fromotherregionsofhighdensity.Usedwhentheclustersareirregularorintertwined,andwhennoiseandoutliersarepresent.6density-basedclusters概念念簇簇SharedPropertyorConceptualClustersFindsclustersthatsharesomecommonpropertyorrepresentaparticularconcept..2OverlappingCircles4.2聚類類分分析析什么么是是聚聚類類分分析析?聚類類分分析析中中的的數(shù)數(shù)據(jù)據(jù)類類型型主要要的的聚聚類類方方法法分分類類劃分分方方法法劃分分方方法法:基本本概概念念劃分分方方法法:為包包含含n個(gè)數(shù)數(shù)據(jù)據(jù)對(duì)對(duì)象象的的數(shù)數(shù)據(jù)據(jù)庫(kù)庫(kù)生生成成k個(gè)簇簇給定定k值，，采采用用一一個(gè)個(gè)劃劃分分規(guī)規(guī)則則將將對(duì)對(duì)象象組組織織成成k個(gè)劃劃分分全局局優(yōu)優(yōu)化化:盡可可能能枚枚舉舉所所有有劃劃分分啟發(fā)發(fā)式式方方法法:k-均值值和k-中心心點(diǎn)點(diǎn)算法法k-均值值(MacQueen’67):每個(gè)個(gè)簇簇以以其其對(duì)對(duì)象象平平均均值值作作為為代代表表（（簇簇中中心心，，或或質(zhì)質(zhì)心心））k-中心心點(diǎn)點(diǎn)或或PAM(Kaufman&Rousseeuw’87):每個(gè)個(gè)簇簇以以其其中中的的某某一一點(diǎn)點(diǎn)代代表表K-均值值方方法法給定定k:1.任意意選選擇擇k個(gè)點(diǎn)點(diǎn)作作為為初初始始的的質(zhì)質(zhì)心心2.repeat3.將每每個(gè)個(gè)點(diǎn)點(diǎn)指指派派到到最最近近（（相相似似））的的簇簇集集4.重新新計(jì)計(jì)算算每每個(gè)個(gè)簇簇的的均均值值，，即即更更新新質(zhì)質(zhì)心心5.until不再再發(fā)發(fā)生生變變化化.K-均值值方方法法例最優(yōu)優(yōu)與與次次優(yōu)優(yōu)聚聚類類結(jié)結(jié)果果Sub-optimalClusteringOptimalClusteringOriginalPoints隨機(jī)機(jī)選選擇擇初初始始質(zhì)質(zhì)心心（（例例1）隨機(jī)機(jī)選選擇擇初初始始質(zhì)質(zhì)心心（（例例1）隨機(jī)機(jī)選選擇擇初初始始質(zhì)質(zhì)心心（（例例2）但是是，，隨隨機(jī)機(jī)選選擇擇的的初初始始質(zhì)質(zhì)心心，，未未必必能能得得到到最最優(yōu)優(yōu)的的結(jié)結(jié)果果隨機(jī)機(jī)選選擇擇初初始始質(zhì)質(zhì)心心（（例例2）k-均值值的的優(yōu)優(yōu)點(diǎn)點(diǎn)簡(jiǎn)單單、、有有效效可用用于于各各種種數(shù)數(shù)據(jù)據(jù)類類型型（但但并并非非適適合合所所有有數(shù)數(shù)據(jù)據(jù)類類型型））k-均值值的的局局限限（（缺缺點(diǎn)點(diǎn)））不能能處處理理：：不同同尺尺寸寸的的簇簇不同同密密度度的的簇簇非球球形形的的簇簇對(duì)含含離離群群點(diǎn)點(diǎn)的的數(shù)數(shù)據(jù)據(jù)聚聚類類時(shí)時(shí)也也有有問(wèn)問(wèn)題題不同同尺尺寸寸的的簇簇OriginalPointsK-means(3Clusters)不同密度的簇簇OriginalPointsK-means(3Clusters)非球形的簇OriginalPointsK-means(2Clusters)克服K-means的局限OriginalPointsK-meansClusters一種方法是使使用更多的簇簇（較小的簇簇集）.發(fā)現(xiàn)簇集的子子簇,但是需要將子子簇合并.克服K-means的局限OriginalPointsK-meansClusters克服K-means的局限OriginalPointsK-meansClustersK中心點(diǎn)方法在簇集中找到到簇中最中心心位置的點(diǎn)，，也就是中心心點(diǎn)PAM(圍繞中心點(diǎn)的的劃分,1987)最初隨機(jī)選定定k個(gè)中心點(diǎn)后，，反復(fù)試圖尋尋找更好的中中心點(diǎn)，分析析所有可能的的對(duì)象對(duì)。PAM適合于小數(shù)據(jù)據(jù)集，但是在在大數(shù)據(jù)集上上效果不佳CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):隨即抽樣對(duì)比k-中心與k-均值當(dāng)存在噪聲和和離群點(diǎn)時(shí)，，k-中心法更魯棒棒k-中心法的執(zhí)行行代價(jià)高于k-均值法小結(jié)與回顧聚類分析同一數(shù)據(jù)，不不同聚類方法法可導(dǎo)致不同同結(jié)果距離的度量基于劃分的聚聚類k-均值法K-均值方法給定k:1.任意選擇k個(gè)點(diǎn)作為初始始的質(zhì)心2.repeat3.將每個(gè)點(diǎn)指派派到最近（相相似）的簇集集4.重新計(jì)算每個(gè)個(gè)簇的均值，，即更新質(zhì)心心5.until不再發(fā)生變化化.K-均值方法例k-均值的優(yōu)點(diǎn)簡(jiǎn)單、有效可用于各種數(shù)數(shù)據(jù)類型（但并非適合合所有數(shù)據(jù)類類型）k-均值的局限（（缺點(diǎn)）不能處理：不同尺寸的簇簇不同密度的簇簇非球形的簇對(duì)含離群點(diǎn)的的數(shù)據(jù)聚類時(shí)時(shí)也有問(wèn)題4.2聚類分析什么是聚類分分析?聚類分析中的的數(shù)據(jù)類型主要的聚類方方法分類劃分方法層次方法層次聚類HierarchicalClustering:NestedClustersDendrogram樹狀圖12345612345層次方法將嵌套定義的的簇集組成一一棵層次形式式的樹按照分裂方式式可分為：凝聚的把每個(gè)點(diǎn)都作作為一個(gè)簇，，開始聚類每一步合并兩兩個(gè)最近的簇簇，直到只剩剩下一個(gè)簇分裂的所有的點(diǎn)看做做一個(gè)簇每一步，分裂裂一個(gè)簇，直直到每個(gè)點(diǎn)點(diǎn)都是一個(gè)簇簇層次聚類方法法利用相似度或或距離矩陣作作為聚類標(biāo)準(zhǔn)準(zhǔn).這種方法不需需要提供k值，但是必須須提供中止條條件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚的(AGNES)分裂的(DIANA)AGNES(凝聚的層次聚聚類)KaufmannandRousseeuw(1990)將具有最少相相異性的點(diǎn)合合并將這些簇合并并成越來(lái)越大大的簇直到所有終結(jié)結(jié)條件被滿足足DIANA(分裂的層次聚聚類)KaufmannandRousseeuw(1990)與AGNES剛好相反直到每個(gè)對(duì)象象自成一簇基本層次凝聚聚聚類基本算法簡(jiǎn)單單直接：計(jì)算相似度矩矩陣（或鄰近近矩陣）以每個(gè)點(diǎn)為一一個(gè)簇Repeat合并最近的兩兩個(gè)簇更新相似度矩矩陣Until僅剩下一個(gè)簇簇關(guān)鍵操作:計(jì)算兩個(gè)簇間間的相似度有多種方法度度量距離或者者相似度簡(jiǎn)單直接的凝凝聚聚類初始，每個(gè)點(diǎn)點(diǎn)都為一個(gè)簇簇集，計(jì)算鄰鄰近矩陣p1p3p5p4p2p1p2p3p4p5......ProximityMatrix中間過(guò)程經(jīng)若干次合并并后C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中間過(guò)程合并C2與C5，更新矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix合并后問(wèn)題：“如如何更新矩陣陣?”C1C4C2UC5C3???????C2UC5C1C1C3C4C2UC5C3C4ProximityMatrix如何度量簇間間距離（相似似性）p1p3p5p4p2p1p2p3p4p5......Similarity?最小距離最大距離均值距離中心點(diǎn)間距離離其他ProximityMatrixHowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點(diǎn)間距離離其他HowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點(diǎn)間距離離其他HowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點(diǎn)間距離離其他兩個(gè)極端折中HowtoDefineInter-ClusterSimilarityp1p3p5p4p2p1p2p3p4p5......ProximityMatrix最小距離最大距離均值距離中心點(diǎn)間距離離其他最近鄰聚類與與單連接算法法最近鄰：以最最小距離度量量簇間距離單連接：最近近的簇間距離離超過(guò)某個(gè)閾閾值聚類就會(huì)會(huì)終止12345最近鄰聚類:MINNestedClustersDendrogram12345612345MIN的優(yōu)點(diǎn)OriginalPointsTwoClusters能夠處理非橢橢圓形簇集MIN的局限OriginalPointsTwoClusters對(duì)噪聲和離群群點(diǎn)敏感最遠(yuǎn)鄰聚類與與全連接算法法最遠(yuǎn)鄰：以最最大距離度量量簇間距離。。（合并最大大距離最小的的兩個(gè)簇）全連接：當(dāng)最最近簇間最大大距離大于某某個(gè)閾值時(shí)聚聚類便終止。。12345最遠(yuǎn)鄰聚類:MAXNestedClustersDendrogram12345612534MAX的優(yōu)點(diǎn)OriginalPointsTwoClusters對(duì)噪聲和離群群點(diǎn)不太敏感感MAX的局限OriginalPointsTwoClusters可能分裂大的的簇偏好球形簇均值距離或平平均距離聚類類兩個(gè)簇間所有有點(diǎn)對(duì)距離的的平均值12345均值距離聚類類NestedClustersDendrogram12345612534均值距離聚類類是對(duì)最小和最最大距離的一一種折中優(yōu)點(diǎn)對(duì)噪聲和離群群點(diǎn)不敏感不足偏好球形簇層次聚類比較較GroupAverageMINMAX123456125341234561253412345612345層次聚類的困困難合并或分裂點(diǎn)點(diǎn)的選擇非常常關(guān)鍵一旦選定，下下一步的處理理將針對(duì)新的的簇進(jìn)行，已已做過(guò)的處理理不能撤銷，，簇間也不能能交換對(duì)象。。若一步選擇沒(méi)沒(méi)做好，就可可能導(dǎo)致低質(zhì)質(zhì)量的結(jié)果。。合并與分裂的的計(jì)算量較大大改進(jìn)：與其他他聚類技術(shù)集集成，多階段段聚類CURE(ClusteringUsingREpresentatives)CURE:byGuha,Rastogi&Shim,1998利用固定數(shù)目目的具有代表表性的點(diǎn)來(lái)代代表一個(gè)簇，，從而衡量?jī)蓛蓚€(gè)簇集之間間的距離，合合并有最近代代表對(duì)的兩個(gè)個(gè)簇集。Cure:算法抽取隨機(jī)樣本本s.將樣本分割成成一組劃分對(duì)每個(gè)劃分局局部的聚類刪除孤立點(diǎn)通過(guò)隨機(jī)抽樣樣如果一個(gè)簇增增長(zhǎng)的太慢，，刪除它.對(duì)局部的簇集集聚類用相應(yīng)的簇標(biāo)標(biāo)簽來(lái)標(biāo)記數(shù)數(shù)據(jù)數(shù)據(jù)劃分和聚聚類s=50p=2s/p=25xxxyyyyxyxs/pq=5Cure:收縮代表點(diǎn)按照某個(gè)收縮縮因子向簇中心收收縮代表點(diǎn).代表點(diǎn)決定了了簇集的形狀狀xyxyCURE不能處理不同同密度的簇OriginalPointsCURECHAMELEON基于圖的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ù)數(shù)據(jù)對(duì)象聚類類成大量相對(duì)對(duì)較小的子聚聚類2.然后用一個(gè)凝凝聚的層次凝凝聚算法通過(guò)過(guò)反復(fù)地合并并子類來(lái)找到到真正的結(jié)果果簇CHAMELEON算法的大致框框架構(gòu)造稀疏圖劃分圖合并劃分最終的簇集DataSetExperimentalResults:CHAMELEONExperimentalResults:CHAMELEONExperimentalResults:CURE(10clusters)ExperimentalResults:CURE(15clusters)ExperimentalResults:CHAMELEONExperimentalResults:CURE(9clusters)ExperimentalResults:CURE(15clusters)小結(jié)層次聚類凝聚的和分裂裂的簇間距離：最最小、最大、、均值、中心心點(diǎn)最近鄰與單連連接最遠(yuǎn)鄰與全連連接CURE，CHAMELEON4.2聚類分析什么是聚類分分析?聚類分析中的的數(shù)據(jù)類型主要的聚類方方法分類劃分方法層次方法基于密度的方方法基于密度的簇簇集方法主要特征:發(fā)現(xiàn)任意形狀狀的簇集處理噪聲單次掃描需要密度參數(shù)數(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)|>=MinPtspqMinPts=5Eps=1cm基于密度的聚聚集：背景知知識(shí)(II)密度可達(dá):當(dāng)存在一個(gè)對(duì)對(duì)象鏈p1,…,pn,p1=q,pn=p，其中pi+1是pi直接密度可達(dá)達(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è)個(gè)點(diǎn)o，使得p和q都是從o關(guān)于.Eps和MinPts密度可達(dá)的.pqp1pqoDBSCAN:基于高密度連連接區(qū)域的密密度聚類方法法基于密度的簇簇集:簇被定義為密密度相連點(diǎn)的的最大集合可以在帶有噪噪聲的空間數(shù)數(shù)據(jù)庫(kù)中發(fā)現(xiàn)現(xiàn)任意形狀的的聚類。CoreBorderOutlierEps=1cmMinPts=5DBSCAN:算法隨機(jī)的選擇點(diǎn)點(diǎn)p尋找所有從點(diǎn)點(diǎn)p關(guān)于EpsandMinPts.密度可達(dá)的點(diǎn)點(diǎn)如果p是核心點(diǎn),那么一個(gè)簇集集已經(jīng)生成了了如果p只是邊緣點(diǎn),從點(diǎn)p沒(méi)有哪一個(gè)點(diǎn)點(diǎn)是密度可達(dá)達(dá)的，DBSCAN訪問(wèn)數(shù)據(jù)庫(kù)中中下一個(gè)點(diǎn).重復(fù)上述過(guò)程程知道中止條條件滿足DBSCAN:Core,Border,andNoisePointsDBSCAN:SensitivetoParametersDBSCAN:Core,BorderandNoisePointsOriginalPointsPointtypes:core,borderandnoiseEps=10,MinPts=4WhenDBSCANWorksWellOriginalPointsClustersResistanttoNoiseCanhandleclustersofdifferentshapesandsizesWhenDBSCANDoesNOTWorkWellOriginalPoints(MinPts=4,Eps=9.75).(MinPts=4,Eps=9.92)VaryingdensitiesHigh-dimensionaldata4.2聚類分析什么是聚類