基于劃分的聚類算法聚類算法

ClusteringAnalysis

(聚類分析)數(shù)據(jù)挖掘技術(shù)講座之——提綱聚類概述基于劃分的聚類算法介紹基于層次的聚類算法基于密度的聚類算法基于原型的聚類算法聚類介紹聚類的定義聚類分析的應(yīng)用聚類分析原理介紹不同的聚類類型聚類算法性能評(píng)價(jià)什么是聚類

簡(jiǎn)單地描述，聚類(Clustering)是將數(shù)據(jù)集劃分為若干相似對(duì)象組成的多個(gè)組(group)或簇(cluster)的過(guò)程，使得同一組中對(duì)象間的相似度最大化，不同組中對(duì)象間的相似度最小化?；蛘哒f(shuō)一個(gè)簇(cluster)就是由彼此相似的一組對(duì)象所構(gòu)成的集合，不同簇中的對(duì)象通常不相似或相似度很低。類間相似度最小化(距離最大化)類內(nèi)相似度最大化(距離最小化)

一個(gè)具有清晰簇結(jié)構(gòu)的數(shù)據(jù)集提出一個(gè)算法來(lái)尋找該例中的簇結(jié)構(gòu)分類vs.聚類分類：有監(jiān)督的學(xué)習(xí)類別事先人工定義好，并且是學(xué)習(xí)算法的輸入一部分；聚類：無(wú)監(jiān)督的學(xué)習(xí)簇在沒(méi)有人工輸入的情況下從數(shù)據(jù)推理而得；很多因素會(huì)影響聚類的輸出結(jié)果：簇的個(gè)數(shù)、相似度計(jì)算方法、文檔的表示方式，等等聚類介紹文本聚類的定義聚類分析的應(yīng)用聚類分析原理的介紹不同的聚類類型聚類算法性能評(píng)價(jià)聚類分析正在蓬勃發(fā)展，廣泛應(yīng)用于一些探索性領(lǐng)域,如統(tǒng)計(jì)學(xué)與模式分析，金融分析，市場(chǎng)營(yíng)銷，決策支持，信息檢索，WEB挖掘，網(wǎng)絡(luò)安全，圖象處理，地質(zhì)勘探、城市規(guī)劃，土地使用、空間數(shù)據(jù)分析，生物學(xué)，天文學(xué)，心理學(xué)，考古學(xué)等。聚類分析無(wú)處不在誰(shuí)經(jīng)常光顧商店，誰(shuí)買什么東西，買多少？按購(gòu)物卡記錄的光臨次數(shù)、光臨時(shí)間、性別、年齡、職業(yè)、購(gòu)物種類、金額等變量分類這樣商店可以….識(shí)別顧客購(gòu)買模式（如喜歡一大早來(lái)買酸奶和鮮肉，習(xí)慣周末時(shí)一次性大采購(gòu)）刻畫不同的客戶群的特征（用變量來(lái)刻畫，就象刻畫貓和狗的特征一樣）為什么這樣分類？因?yàn)槊恳粋€(gè)類別里面的人消費(fèi)方式都不一樣，需要針對(duì)不同的人群，制定不同的關(guān)系管理方式，以提高客戶對(duì)公司商業(yè)活動(dòng)的相應(yīng)率。聚類分析無(wú)處不在挖掘有價(jià)值的客戶，并制定相應(yīng)的促銷策略：如，對(duì)經(jīng)常購(gòu)買酸奶的客戶對(duì)累計(jì)消費(fèi)達(dá)到12個(gè)月的老客戶針對(duì)潛在客戶派發(fā)廣告，比在大街上亂發(fā)傳單命中率更高，成本更低！聚類分析無(wú)處不在誰(shuí)是銀行信用卡的黃金客戶？利用儲(chǔ)蓄額、刷卡消費(fèi)金額、誠(chéng)信度等變量對(duì)客戶分類，找出“黃金客戶”！這樣銀行可以……制定更吸引的服務(wù)，留住客戶！比如：一定額度和期限的免息透支服務(wù)！貴賓打折卡！在他或她生日的時(shí)候送上一個(gè)小蛋糕！聚類的應(yīng)用領(lǐng)域經(jīng)濟(jì)領(lǐng)域：幫助市場(chǎng)分析人員從客戶數(shù)據(jù)庫(kù)中發(fā)現(xiàn)不同的客戶群，并且用購(gòu)買模式來(lái)刻畫不同的客戶群的特征。誰(shuí)喜歡打國(guó)際長(zhǎng)途，在什么時(shí)間，打到那里？對(duì)住宅區(qū)進(jìn)行聚類，確定自動(dòng)提款機(jī)ATM的安放位置股票市場(chǎng)板塊分析，找出最具活力的板塊龍頭股企業(yè)信用等級(jí)分類……萬(wàn)維網(wǎng)對(duì)WEB上的文檔進(jìn)行分類對(duì)WEB日志的數(shù)據(jù)進(jìn)行聚類，以發(fā)現(xiàn)相同的用戶訪問(wèn)模式數(shù)據(jù)挖掘領(lǐng)域作為其他數(shù)學(xué)算法的預(yù)處理步驟，獲得數(shù)據(jù)分布狀況，集中對(duì)特定的類做進(jìn)一步的研究萬(wàn)維望—搜索結(jié)果的聚類：更好地瀏覽萬(wàn)維望—全局瀏覽:Yahoo聚類介紹文本聚類的定義聚類分析的應(yīng)用聚類分析原理的介紹聚類方法的類型聚類算法性能評(píng)價(jià)聚類分析原理介紹聚類分析中“類”的特征：聚類所說(shuō)的類不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來(lái)劃分聚類的數(shù)目和結(jié)構(gòu)都沒(méi)有事先假定聚類方法的目的是尋找數(shù)據(jù)中：潛在的自然分組結(jié)構(gòu)感興趣的關(guān)系聚類分析原理介紹什么是自然分組結(jié)構(gòu)?我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ聚類分析原理介紹分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副聚類分析原理介紹分成四組符號(hào)相同的牌為一組AKQJ符號(hào)相同的的牌聚類分析原理介紹分成兩組顏色相同的牌為一組AKQJ顏色相同的配對(duì)聚類分析原理介紹這個(gè)例子告訴我們：聚類的結(jié)果不是唯一的類(簇)的概念可能是模糊的AKQJ大配對(duì)和小配對(duì)聚類介紹文本聚類的定義聚類分析的應(yīng)用聚類分析原理的介紹不同的聚類類型聚類算法性能評(píng)價(jià)不同的聚類類型層次的與劃分的一個(gè)聚類方法產(chǎn)生簇(cluster)的集合；

不同類型的聚類之間產(chǎn)生簇的集合是嵌套的，還是非嵌套的；或者，是層次的還是劃分的；劃分的聚類方法，將數(shù)據(jù)對(duì)象劃分到非重疊的子集(簇)中，使得每個(gè)對(duì)象屬于唯一的一個(gè)子集；層次的聚類方法，產(chǎn)生一個(gè)嵌套的簇的集合，它們可組織為一棵層次樹(shù)；劃分聚類原始點(diǎn)一個(gè)劃分聚類層次聚類傳統(tǒng)的層次聚類非傳統(tǒng)的層次聚類非傳統(tǒng)的樹(shù)圖傳統(tǒng)的樹(shù)圖互斥vs非互斥在非互斥的聚類中，一個(gè)點(diǎn)可能屬于多個(gè)不同的簇。

互斥的聚類中，每個(gè)對(duì)象都指派到單個(gè)簇?？梢员硎径鄠€(gè)類別或者邊界點(diǎn)模糊vs非模糊在模糊的聚類中，每個(gè)對(duì)象點(diǎn)以0和1之間的隸屬權(quán)重屬于每個(gè)簇，即簇視為模糊集約束條件：權(quán)重值和必須為1實(shí)際中，通過(guò)將對(duì)象指派到具有最高隸屬權(quán)值或概率的簇，將模糊或概率聚類轉(zhuǎn)換成互斥聚類。不同的聚類類型部分的vs完全的完全聚類將每個(gè)對(duì)象指派到一個(gè)簇部分聚類，數(shù)據(jù)集中某些對(duì)象可能不屬于明確定義的組，數(shù)據(jù)集中一些對(duì)象可能代表噪聲、離群點(diǎn)或“不感興趣的背景”。因此，只需要聚類部分?jǐn)?shù)據(jù)不同的聚類類型聚類介紹文本聚類的定義聚類分析的應(yīng)用聚類分析原理的介紹聚類方法的類型聚類算法性能評(píng)價(jià)怎樣判斷聚類結(jié)果的好壞?內(nèi)部準(zhǔn)則(internalcriterion)將簇內(nèi)高相似度(簇內(nèi)文檔相似)及簇間低相似度(不同簇之間的文檔不相似)的目標(biāo)進(jìn)行形式化后得到的一個(gè)函數(shù)。

內(nèi)部準(zhǔn)則往往不能評(píng)價(jià)聚類在應(yīng)用中的實(shí)際效用外部準(zhǔn)則(internalcriterion)按照用戶定義的分類結(jié)果來(lái)評(píng)價(jià)，即對(duì)一個(gè)分好類的數(shù)據(jù)集進(jìn)行聚類，將聚類結(jié)果和事先的類別情況進(jìn)行比照，得到最后的評(píng)價(jià)結(jié)果純度、歸一劃互信息NMI(NormalizedMutualInformation)、蘭德指數(shù)(RandIndex)以及F值。外部準(zhǔn)則:純度?={ω1,ω2,...,ωK}是簇的集合C={c1,c2,...,cJ}是類別的集合對(duì)每個(gè)簇

ωk:找到一個(gè)類別cj

，該類別包含ωk中的元素最多，為nkj

個(gè)，也就是說(shuō)ωk的元素最多分布在cj中將所有

nkj

求和，然后除以所有的文檔數(shù)目純度計(jì)算的例子為計(jì)算純度

maxj|ω1∩cj

|=5(classx,cluster1);maxj|ω2∩cj|=4(classo,cluster2);maxj|ω3∩cj|=3(class?,cluster3)

純度為(1/17)×(5+4+3)≈0.71.外部準(zhǔn)則－F值將每個(gè)聚類結(jié)果看作是查詢的結(jié)果。這樣對(duì)于最終的某個(gè)聚類類別r和原來(lái)預(yù)定類別i。n(i,r)是聚類r中包含類別i中的文檔個(gè)數(shù)，ni是預(yù)定義類別的個(gè)數(shù)，nr是聚類形成的類別r中的文檔個(gè)數(shù)。外部準(zhǔn)則－F值將每個(gè)聚類結(jié)果看作是查詢的結(jié)果。這樣對(duì)于最終的某個(gè)聚類類別r和原來(lái)預(yù)定類別r。最終聚類結(jié)果的評(píng)價(jià)函數(shù)為：這里n是所有測(cè)試文檔的個(gè)數(shù)。值得指出的是，通過(guò)以上這兩種方法獲得的聚類評(píng)價(jià)只是對(duì)數(shù)據(jù)集作一次劃分的評(píng)價(jià)。為了客觀評(píng)價(jià)聚類算法的性能.有必要進(jìn)行多次聚類獲得其評(píng)價(jià)結(jié)果，并用其均值仿卻來(lái)評(píng)價(jià)算法?！趧澐值木垲愃惴ň垲愃惴?ClusteringAlgorithm)劃分方法對(duì)包含n個(gè)文檔的文本集合，劃分將生成k個(gè)分組，k<=n，每一個(gè)分組代表一個(gè)聚類典型的劃分方法（Partitioningmethods）:k-平均方法(k-meansMethods)k-中心點(diǎn)方法(K-medoidsMethods)

k均值用質(zhì)心定義，其中質(zhì)心是一組點(diǎn)的均值；k中心點(diǎn)使用中心點(diǎn)來(lái)定義，其中中心點(diǎn)是一組點(diǎn)中最有代表性的點(diǎn)；基本k-Means算法step1.任意選擇k個(gè)對(duì)象作為初始質(zhì)心，k是用戶指定的參數(shù)，即所期望的簇的個(gè)數(shù)；step2.repeat

將每個(gè)點(diǎn)(文檔)指派到最近的質(zhì)心，形成k個(gè)簇；重新計(jì)算每個(gè)簇的質(zhì)心until質(zhì)心不再發(fā)生變化,即沒(méi)有對(duì)象進(jìn)行被重新分配

時(shí)，過(guò)程結(jié)束。

質(zhì)心：基本k-Means算法－指派最近質(zhì)心為了將點(diǎn)指派到最近的質(zhì)心，需要鄰近性度量來(lái)量化數(shù)據(jù)的“最近”概念歐式空間中的點(diǎn)使用歐幾里得距離、曼哈頓距離文檔用余弦相似性，Jarccard系數(shù)歐氏距離：

曼哈頓距離：加權(quán)的歐幾里得距離：對(duì)每個(gè)變量根據(jù)其重要性賦予一個(gè)權(quán)重：基本k-Means算法－質(zhì)心和目標(biāo)函數(shù)歐幾里得空間中的數(shù)據(jù)：鄰近性度量為歐幾里得距離，使用誤差平方和(SumoftheSquaredError,SSE)作為度量聚類質(zhì)量的目標(biāo)函數(shù)。選擇誤差平方和最小的說(shuō)明：dist是歐幾里得空間中兩個(gè)對(duì)象之間的標(biāo)準(zhǔn)歐幾里得

距離。ci是簇Ci的質(zhì)心。計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的誤差，該

誤差為它到最近質(zhì)心的歐幾里得距離。文檔數(shù)據(jù)：鄰近性度量為余弦相似度，目標(biāo)是最大化簇中文檔與簇的質(zhì)心的相似性，該度量稱作簇的凝聚度(cohesion)。基本k-Means算法示例1：坐標(biāo)表示5個(gè)點(diǎn)｛X1,X2,X3,X4,X5｝作為一個(gè)聚類分析的二維樣本：X1＝(0,2),X2＝(0,0),X3＝(1.5,0)，X4＝(5,0)，X5＝(5,2)。

假設(shè)要求的簇的數(shù)量k=2。思路：

由樣本的隨機(jī)分布形成兩個(gè)簇：C1={X1,X2,X4}和C2＝{X3,X5}這兩個(gè)簇的質(zhì)心M1和M2是：

M1＝{(0+0+5)/3,(2+0+0)/3}＝{1.66,0.66｝；M2＝{(1.5+5)/2，(0+2)/2}={3.25,1.00}；基本k-Means算法示例樣本初始隨機(jī)分布之后，誤差是：

E12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+[(5-1.66)2+(0-0.66)2]=19.36；E22=8.12；誤差平方和是：E2＝E12+E22＝19.36+8.12＝27.48基本k-Means算法示例

按與質(zhì)心（M1或M2）間距離關(guān)系，選擇最小距離分配所有樣本，簇內(nèi)樣本的重新分布如下：d(M1,X1)=(1.662+1.342)1/2=2.14d(M2,X1)=3.40==>X1∈C1；d(M1,X2)=1.79和d(M2,X2)=3.40==>X2∈C1d(M1,X3)=0.83和d(M2,X3)=2.01==>X3∈C1d(M1,X4)=3.41和d(M2,X4)=2.01==>X4∈C2d(M1,X5)=3.60和d(M2,X5)=2.01==>X5∈C2

新簇C1＝{X1,X2,X3}和C2＝{X4,X5}基本k-Means算法示例計(jì)算新的質(zhì)心：M1＝｛0.5，0.67｝；M2＝｛5.0，1.0｝。相應(yīng)的方差及總體平方誤差分別是：E12＝4.17；E22＝2.00；E＝6.17；可以看出第一次迭代后，總體誤差顯著減小(從值27.48到6.17)。在這個(gè)簡(jiǎn)單的例子中，第一次迭代同時(shí)也是最后一次迭代，因?yàn)槿绻^續(xù)分析新中心和樣本間的距離樣本將會(huì)全部分給同樣的簇，不將重新分配，算法停止?；緆-Means算法示例k-Means特點(diǎn)該算法試圖找出使誤差平方和最小的k個(gè)劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)分明顯時(shí)，它的效果較好。算法復(fù)雜度O(I*K*m*n)，其中I是迭代次數(shù),m是點(diǎn)數(shù)，n是屬性數(shù)。因此其可擴(kuò)展性較好，對(duì)大數(shù)據(jù)集處理有較高的效率。算法并不能保證達(dá)到全局最小值，特別是文檔集包含很多離群點(diǎn)時(shí)，這個(gè)問(wèn)題尤其明顯。這些離群點(diǎn)遠(yuǎn)離其他文檔，因此不適合歸入任何一個(gè)簇。如果離群點(diǎn)被選為初始種子，那么在后續(xù)迭代中不會(huì)有任何其他的向量被分配到該簇中。因此，常以局部最優(yōu)結(jié)束缺點(diǎn)：要求用戶必須事先給出要生成的簇的數(shù)目，聚類結(jié)果依賴于初始種子的選??；不適合發(fā)現(xiàn)非凸面狀的簇。不適合大小差別較大的簇；對(duì)于噪聲和孤立點(diǎn)是敏感的，因?yàn)樯倭康脑擃悢?shù)據(jù)能對(duì)平均值產(chǎn)生較大的影響。二分k-means算法－對(duì)初始化質(zhì)心問(wèn)題不太敏感二分K-means算法是基本k-means算法的直接擴(kuò)充，基于如下想法：為了得到k個(gè)簇，將所有點(diǎn)的集合分裂成兩個(gè)簇，從中選擇一個(gè)繼續(xù)分裂，如此重復(fù)直到產(chǎn)生k個(gè)簇。算法詳細(xì)描述如下：初始化簇表，使之包含由所有的點(diǎn)組成的簇。Repeat

從簇表中選取一個(gè)簇。{對(duì)選定的簇進(jìn)行多次二分“試驗(yàn)”}Fori=1to試驗(yàn)次數(shù)do

使用基本k-means，二分選定的簇Endfor從二分試驗(yàn)中選擇具有最小總誤差平方和SSE的兩個(gè)簇。將這兩個(gè)簇添加到簇表中Until簇表中包含k個(gè)簇K-Mediods(K-中心點(diǎn))算法k均值算法對(duì)離群點(diǎn)是敏感的，平方誤差函數(shù)也會(huì)扭曲數(shù)據(jù)的分布。修改k均值算法降低敏感性：

不采用簇中對(duì)象的均值作為參照點(diǎn)，而是在每個(gè)簇中選出一個(gè)實(shí)際的對(duì)象來(lái)代表該簇。

使用絕對(duì)誤差標(biāo)準(zhǔn)

k中心點(diǎn)算法之一--PAM算法：k中心點(diǎn)。PAM，一種基于中心點(diǎn)或中心對(duì)象進(jìn)行劃分的k中心點(diǎn)算法。輸入：

k：結(jié)果簇的數(shù)目

D：包含n個(gè)對(duì)象的數(shù)據(jù)集輸出：k個(gè)簇的集合。方法：(1)從D中任意選擇k個(gè)對(duì)象作為初始的代表對(duì)象或種子；(2)repeat(3)將每個(gè)剩余對(duì)象指派到最近的代表對(duì)象所代表的簇；(4)隨機(jī)選擇一個(gè)非代表對(duì)象orandom；(5)計(jì)算用orandom交換代表對(duì)象oj的總代價(jià)S(所有非代表對(duì)象所產(chǎn)生的代價(jià)之和，代價(jià)就是絕對(duì)誤差值的差)；(6)

ifS<0(說(shuō)明實(shí)際的絕對(duì)誤差E將會(huì)減小),then用orandom替換oj，形成新的k個(gè)代表對(duì)象的集合；(5)until不發(fā)生變化k中心點(diǎn)算法分析

當(dāng)存在噪聲和離群點(diǎn)時(shí)，k-中心點(diǎn)方法比k-均值更魯棒，因?yàn)橹行狞c(diǎn)不像均值那樣容易受離群點(diǎn)或其他極端值影響；k-中心點(diǎn)算法的每次迭代的復(fù)雜度時(shí)O(k(n-k)2)。當(dāng)n和k的值較大時(shí)，這種計(jì)算開(kāi)銷變得很大，遠(yuǎn)高于k-均值方法；

兩種方法都需要用戶指定簇?cái)?shù)k?！趯哟蔚木垲愃惴ň垲愃惴?ClusteringAlgorithm)層次聚類概述層次聚類的目標(biāo)是生成目錄的一個(gè)層次結(jié)構(gòu)：這個(gè)層次結(jié)構(gòu)是自動(dòng)創(chuàng)建的，可以通過(guò)自頂向下或自底向上的方法來(lái)實(shí)現(xiàn)。層次聚類概述主要有兩種類型凝聚式:一開(kāi)始將每個(gè)對(duì)象作為單獨(dú)的一個(gè)簇在每一步，將最相近的簇合并，直到所有的組合并成一

個(gè)，或達(dá)到一個(gè)終止條件為止分裂式:一開(kāi)始將所有的對(duì)象置于一類在迭代的每一步中，一個(gè)類不斷地分為更小的類，直到每

個(gè)對(duì)象在單獨(dú)的一個(gè)類中，或達(dá)到一個(gè)終止條件傳統(tǒng)的層次聚類算法需要用到一個(gè)相似性或者距離矩陣層次聚類概述層次聚類的優(yōu)點(diǎn)：不必事先假定特定數(shù)目的簇，在樹(shù)圖中合適的層次上做切面，就可以得到任意理想數(shù)量的簇；可能對(duì)應(yīng)于有意義的分類層次，如在生物學(xué)中(e.g.,動(dòng)物王國(guó),生物種系,…)凝聚式聚類更普遍的一種聚類方法基本算法很直觀關(guān)鍵操作是計(jì)算兩個(gè)簇之間的鄰近度使用不同的鄰近度方法，產(chǎn)生不同的聚類算法初始情形每個(gè)點(diǎn)構(gòu)成一個(gè)簇，并給出它們的鄰近度矩陣p1p3p5p4p2p1p2p3p4p5......鄰近度矩陣聚類過(guò)程中的情形經(jīng)過(guò)一些合并后，得到了一些簇C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5鄰近度矩陣聚類過(guò)程中的情形假設(shè)需要合并兩個(gè)最近的簇(C2和C5)，并需要更新鄰近度矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5鄰近度矩陣合并后問(wèn)題是“如何更新鄰近度矩陣?”C1C4C2UC5C3???? ???C2UC5C1C1C3C4C2UC5C3C4鄰近度矩陣如何定義簇間的相似度

p1p3p5p4p2p1p2p3p4p5......相似度MINMAX組平均GroupAverage質(zhì)心距離DistanceBetweenCentroids目標(biāo)函數(shù)驅(qū)動(dòng)方法Ward’sMethodusessquarederror鄰近度矩陣簇相似度:MIN或者單鏈(SingleLink)最小距離法(singlelinkagemethod)Min定義簇的鄰近度為不同簇的兩個(gè)最近的點(diǎn)之間的鄰近度，或者使用圖的術(shù)語(yǔ)，不同的結(jié)點(diǎn)子集中兩個(gè)結(jié)點(diǎn)之間的最短邊。簇相似度:MIN或者單鏈(SingleLink)示例2，有6個(gè)二維點(diǎn)的樣本數(shù)據(jù)。點(diǎn)x和y坐標(biāo)，以及點(diǎn)之間的歐幾里得距離如下表所示。點(diǎn)X坐標(biāo)Y坐標(biāo)P10.40050.5306P20.21480.3854P30.35470.3156P40.26520.1875P50.07890.4139p60.45480.3022P1P2P3P4P5P6P100.23570.22180.36880.34210.2347P20.235700.14830.20420.13880.2540P30.22180.148300.15130.28430.1100P40.36880.20420.151300.29320.2216P50.34210.13880.28430.293200.3921p60.23470.25400.11000.22160.39210簇相似度:MIN或者單鏈(SingleLink)示例2，有6個(gè)二維點(diǎn)的樣本數(shù)據(jù)。點(diǎn)x和y坐標(biāo)，以及點(diǎn)之間的歐幾里得距離如下表所示。樹(shù)圖嵌套的簇12345612345dist({3,6},{2,5})=min(dist(3,2),dist(6,2),dist(3,5),dist(6,5))=min(0.15,0.25,0.28,0.39)=0.15簇相似度:MAX或全鏈(CompleteLinkage)最大距離法(completelinkagemethod)MAX定義簇的鄰近度為不同簇中兩個(gè)最遠(yuǎn)的點(diǎn)之間的鄰近度，或者使用圖的術(shù)語(yǔ)，不同的結(jié)點(diǎn)子集中兩個(gè)結(jié)點(diǎn)之間的最長(zhǎng)邊?；氐絼偛诺睦幼畲缶嚯x法(completelinkagemethod)dist({3,6},{4})=max(dist(3,4),dist(6,4))=max(0.15,0.22)=0.22dist({3,6},{2,5})=max(dist(3,2),dist(6,2),dist(3,5),dist(6,5))=max(0.15,0.25,0.28,0.39)=0.39dist({3,6},{1})=max(dist(3,1),dist(6,1))=max(0.22,0.23)=0.23回到剛才的例子最大距離法(completelinkagemethod)12345612534嵌套的簇樹(shù)圖簇相似度:組平均組平均距離法(averagelinkagemethod)類間所有樣本點(diǎn)的平均距離該法利用了所有樣本的信息，是單鏈和全鏈之間的折中，被認(rèn)為是較好的層次聚類法回到剛才的例子組平均距離法dist({3,6,4},{1})=(0.22+0.37+0.23)/(3*1)=0.28dist({2,5},{1})=(0.2357+0.342d1)/(2*1)=0.2889dist({3,6,4},{2,5})=(0.15+0.28+0.25+0.39+0.20+0.29)/(3*2)=0.26因?yàn)閐ist({3,6,4},{2,5})比dist({3,6,4},{1})和dist({2,5},{1})小，簇{3,6,4}和{2,5}在第4階段合并層次聚類:組平均51234561234嵌套的簇樹(shù)圖層次聚類：時(shí)間和空間復(fù)雜度空間復(fù)雜度：O(N2)N是點(diǎn)的數(shù)量使用了鄰近度矩陣大多數(shù)情況下時(shí)間復(fù)雜度：O(N3)由N步構(gòu)成，在每一步，大小為N2的鄰近度矩陣需要更新和搜索對(duì)于某些方法，復(fù)雜度可以減少到O(N2log(N))層次聚類:問(wèn)題和局限性一旦決定合并兩個(gè)簇，就不能撤銷缺乏全局目標(biāo)函數(shù)凝聚層次聚類技術(shù)使用各種標(biāo)準(zhǔn)，在每一步局部地確定哪些簇應(yīng)當(dāng)合并，這種方法產(chǎn)生的聚類算法避開(kāi)了解決困難的組合優(yōu)化問(wèn)題這種方法沒(méi)有很難選擇初始點(diǎn)的問(wèn)題不同的方案存在一個(gè)或多個(gè)下列問(wèn)題:對(duì)噪音和離群點(diǎn)敏感處理不同大小和凸?fàn)钚螤顣r(shí)存在困難會(huì)分裂大型簇——基于密度的聚類算法聚類算法(ClusteringAlgorithm)基于密度的聚類聚類標(biāo)準(zhǔn)基于密度，即尋找被低密度區(qū)域分離的高密度區(qū)域主要特征:能發(fā)現(xiàn)具有任意形狀的簇易于處理離群點(diǎn)需要用密度參數(shù)作為終止條件幾種方法:DBSCAN:Ester等(KDD’96)OPTICS:Ankerst等(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal等(SIGMOD’98)(基于神經(jīng)網(wǎng)絡(luò))72DBSCAN是一種基于高密度連通區(qū)域的聚類方法，該算法將具有足夠高密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的最大的集合。根據(jù)點(diǎn)的密度將點(diǎn)分為三類：稠密區(qū)域內(nèi)部的點(diǎn)(核心點(diǎn))，(2)稠密區(qū)域邊緣上的點(diǎn)(邊界點(diǎn))，(3)稀疏區(qū)域中的點(diǎn)(噪聲或背景點(diǎn))。給定一個(gè)對(duì)象集合D，對(duì)象之間的距離函數(shù)為distance(*，*)，鄰域半徑為Eps。DBSCAN－基于中心的密度方法DBSCAN－基于中心的密度方法點(diǎn)的密度：在點(diǎn)的給定半徑(Eps)之內(nèi)的點(diǎn)計(jì)數(shù)(包括點(diǎn)本身)

該點(diǎn)密度取決于指定的半徑，如果半徑足夠大，則所有點(diǎn)的密度都等于數(shù)據(jù)集中的點(diǎn)數(shù)，如果半徑太小，則所有點(diǎn)的密度都是1一個(gè)點(diǎn)是核心點(diǎn)，如果該點(diǎn)的給定鄰域內(nèi)的點(diǎn)的個(gè)數(shù)超過(guò)指定數(shù)量(MinPts)的點(diǎn)這些點(diǎn)在簇內(nèi)部，點(diǎn)的鄰域由距離函數(shù)和用戶指定的距離參數(shù)Eps決定。一個(gè)邊界點(diǎn)不是核心點(diǎn)，但它落在某個(gè)核心點(diǎn)的鄰域內(nèi)。邊界點(diǎn)可能落在多個(gè)核心點(diǎn)的鄰域內(nèi)。一個(gè)噪音點(diǎn)既不是核心點(diǎn)也不是邊界點(diǎn)DBSCAN:核心、邊界和噪音點(diǎn)直接密度可達(dá)：如果p在q的Eps鄰域內(nèi)，而q是一個(gè)核心對(duì)象，則稱對(duì)象p從對(duì)象q出發(fā)時(shí)是直接密度可達(dá)的(directlydensity-reachableDBSCAN－基于中心的密度方法MinPts=5Eps=1cmpq密度可達(dá)：如果存在一個(gè)對(duì)象鏈，對(duì)于,是從關(guān)于Eps和MinPts直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于Eps和MinPts密度可達(dá)的(density-reachable)。p1pq密度相連：如果存在對(duì)象O∈D，使對(duì)象p和q都是從O關(guān)于Eps和MinPts密度可達(dá)的，那么對(duì)象p到q是關(guān)于Eps和MinPts密度相連的(density-connected)。DBSCAN－基于中心的密度方法pqoDBSCAN算法示例如圖，Eps用一個(gè)相應(yīng)的半徑表示，設(shè)MinPts=3。圖4.7“直接密度可達(dá)”和“密度可達(dá)”概念示意描述解答：根據(jù)以上概念知道：由于有標(biāo)記的各點(diǎn)-M、P、O和R的Eps近鄰均包含3個(gè)以上的點(diǎn)，因此它們都是核對(duì)象；M-是從P“直接密度可達(dá)”；而Q則是從-M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無(wú)法“密度可達(dá)”(非對(duì)稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。密度可達(dá)是直接密度可達(dá)的傳遞閉包，這種關(guān)系式非對(duì)稱的。只有核心對(duì)象之間相互密度可達(dá)。密度相連性是一個(gè)對(duì)稱關(guān)系基于密度的蔟是基于密度可達(dá)性的最大的密度相連對(duì)象的集合不包含在任何蔟中的對(duì)象被認(rèn)為是噪聲。DBSCAN－基于中心的密度方法DBSCAN通過(guò)檢查數(shù)據(jù)集中每點(diǎn)的Eps鄰域來(lái)搜索簇。如果點(diǎn)p的Eps鄰域包含的點(diǎn)多于MinPts個(gè)，則創(chuàng)建一個(gè)以p為核心對(duì)象的簇；然后DBSCAN迭代地聚集從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過(guò)程可能涉及一些密度可達(dá)簇的合并；當(dāng)沒(méi)有新的點(diǎn)添加到任何簇時(shí)，該過(guò)程結(jié)束。DBSCAN－基于中心的密度方法算法具體描述(1)首先將數(shù)據(jù)集D中的所有對(duì)象標(biāo)記為未處理狀態(tài)(2)for數(shù)據(jù)集D中每個(gè)對(duì)象pdo(3)ifp已經(jīng)歸入某個(gè)簇或標(biāo)記為噪聲then(4)continue;(5)else(6)檢查對(duì)象p的Eps鄰域；(7)if包含的對(duì)象數(shù)小于MinPtsthen(8)標(biāo)記對(duì)象p為邊界點(diǎn)或噪聲點(diǎn)；(9)else(10)標(biāo)記對(duì)象p為核心點(diǎn)，并建立新簇C；(11)for中所有尚未被處理的對(duì)象qdo(12)檢查其Eps鄰域，若包含至少M(fèi)inPts個(gè)對(duì)象，則將中未歸入任何一個(gè)簇的對(duì)象加入C；(13)endfor(14)endif(15)endif(16)endforDBSCAN算法示例對(duì)于表所示二維平面上的數(shù)據(jù)集，取Eps=3，MinPts=3來(lái)演示DBSCAN算法的聚類過(guò)程(使用Mahattan距離公式)。表聚類過(guò)程示例數(shù)據(jù)集3P1P2P3P4P5P6P7P8P9P10P11P12P1312245667913532143879951212123解答：(1)隨機(jī)選擇一個(gè)點(diǎn)，如P1(1，2)，其Eps鄰域中包含{P1，P2，P3，P13}，P1是核心點(diǎn)，其鄰域中的點(diǎn)構(gòu)成簇1的一部分，依次檢查P2，P3，P13的Eps鄰域，進(jìn)行擴(kuò)展，將點(diǎn)P4并入，P4為邊界點(diǎn)；(2)檢查點(diǎn)P5，其Eps鄰域中包含{P5，P6，P7，P8}，P5是核心點(diǎn)，其鄰域中的點(diǎn)構(gòu)成簇2的一部分，依次檢查P6，P7，P8的Eps鄰域，進(jìn)行擴(kuò)展，每個(gè)點(diǎn)都是核心點(diǎn)，不能擴(kuò)展；(3)檢查點(diǎn)P9，其Eps鄰域中包含{P9}，P9為噪聲點(diǎn)或邊界點(diǎn)；(4)檢查點(diǎn)P10，其Eps鄰域中包含{P10，P11}，P10為噪聲點(diǎn)或邊界點(diǎn)；檢查P11，其Eps鄰域中包含{P10，P11，P12}，P11為核心點(diǎn)，其鄰域中的點(diǎn)構(gòu)成簇3的一部分；進(jìn)一步檢查，P10、P12為邊界點(diǎn)。DBSCAN算法示例所有點(diǎn)標(biāo)記完畢，P9沒(méi)有落在任何核心點(diǎn)的鄰域內(nèi)，為噪聲點(diǎn)。最終識(shí)別出三個(gè)簇，P9為噪聲點(diǎn)。簇1包含{P1，P2，P3，P4，P13}，P4為邊界點(diǎn)，其它點(diǎn)為核心點(diǎn)；簇2包含{P5，P6，P7，P8}，其全部點(diǎn)均為核心點(diǎn)；簇3包含{P10，P11，P12}，P10、P12為邊界點(diǎn)，P11為核心點(diǎn)；如果MinPts=4，則簇3中的點(diǎn)均被識(shí)別成噪聲點(diǎn)。DBSCAN算法的優(yōu)點(diǎn)：可以識(shí)別具有任意形狀和不同大小的蔟，自動(dòng)確定蔟的數(shù)目，分離簇和環(huán)境噪聲，一次掃描數(shù)據(jù)即可完成聚類。DBSCAN算法示例DBSCAN適用的情形原始點(diǎn)簇抗噪能夠處理不同形狀和大小的簇DBSCAN:確定EPS和MinPts同一個(gè)簇中的點(diǎn)到它們的k個(gè)最近鄰的距離大致相當(dāng)噪音點(diǎn)到它們的k個(gè)最近鄰距離則比較遠(yuǎn)對(duì)于某個(gè)k，計(jì)算所有點(diǎn)的k距離(點(diǎn)到它的k個(gè)最近鄰的距離)，并增序排列，然后繪制排序后的值，則會(huì)看到k-距離的急劇變化，對(duì)應(yīng)于合適的Eps值。選取該距離為Eps參數(shù)，取k值為MinPts參數(shù)，則k-距離小于Eps的點(diǎn)將被標(biāo)記為核心點(diǎn)，而其他點(diǎn)將被標(biāo)記為噪聲或邊界點(diǎn)?！谠偷木垲愃惴ň垲愃惴?ClusteringAlgorithm)基于原型的聚類基于原型的聚類：簇是對(duì)象的集合，一個(gè)簇中的任何對(duì)象離該簇的原型比其他簇的原型更近k-means，使用簇中對(duì)象的質(zhì)心作為簇的原型擴(kuò)展基于原型的聚類允許對(duì)象屬于多個(gè)簇，即對(duì)象以某個(gè)權(quán)值屬于每一個(gè)簇模糊聚類用統(tǒng)計(jì)分布對(duì)簇進(jìn)行建模，即對(duì)象通過(guò)一個(gè)隨機(jī)過(guò)程，由一個(gè)被若干統(tǒng)計(jì)參數(shù)(如均值和方差)刻畫的統(tǒng)計(jì)分布產(chǎn)生EM聚類模糊聚類如果數(shù)據(jù)對(duì)象分布在明顯分離的組中，則把對(duì)象明確分類成不相交的簇是一種理想的方法；在大部分情況下，數(shù)據(jù)集中的對(duì)象不能劃分明顯分離的簇，指派一個(gè)對(duì)象到一個(gè)特定的簇具有一定的任意性。

對(duì)每個(gè)對(duì)象和每個(gè)簇賦予一個(gè)權(quán)值，指明該對(duì)象屬于該簇的程度。模糊聚類理論基礎(chǔ):模糊集合論：對(duì)象以0和1之間的某個(gè)隸屬度屬于一個(gè)集合模糊邏輯：一個(gè)命題以0和1之間的確定度為真模糊簇：假定有一個(gè)數(shù)據(jù)點(diǎn)集合{x1,x2,…,xm}，模糊簇集c1,c2,…,ck(1)wij表示xi屬于cj的隸屬度,滿足

(2)每個(gè)簇Cj以非零權(quán)值至少包含一個(gè)點(diǎn)，但不以權(quán)值1包含所有的點(diǎn)模糊聚類算法-k均值的模糊版本基本的模糊c均值算法（FCM）1選擇一個(gè)初始模糊劃分，即對(duì)所有的wij

賦值2repeat3

使用模糊劃分，計(jì)算每個(gè)簇的質(zhì)心4

重新計(jì)算模糊劃分，即wij5until質(zhì)心不發(fā)生變化(替換的終止條件是“如果誤差的變化低于指定的閾值”或“如果所有wij的變化的絕對(duì)值都低于指定的閾值)與K均值一樣，F(xiàn)CM可以解釋為視圖最小化誤差的平方和(SSE)初始化：通常隨機(jī)選取，與k-means類似。對(duì)于權(quán)值，隨機(jī)地選取，同時(shí)限定與任何對(duì)象相關(guān)聯(lián)地權(quán)值之和必須等于1計(jì)算質(zhì)心：所有點(diǎn)都需要考慮，每個(gè)點(diǎn)對(duì)質(zhì)心的貢獻(xiàn)根據(jù)隸屬度加權(quán)p>1,p越大，劃分越來(lái)越模糊，p=1，則為傳統(tǒng)的K均值更新模糊劃分模糊聚類算法更新模糊劃分模糊聚類算法分析：權(quán)值wij指明點(diǎn)xi在簇Cj中的隸屬度。如果xi靠近質(zhì)心cj，則wij相對(duì)較高；而如果xi遠(yuǎn)離質(zhì)心cj，則wij相對(duì)較低。P=2P>2分析：該指數(shù)降低賦予離點(diǎn)最近的簇的權(quán)值。事實(shí)上，隨著p趨向無(wú)窮大，該指數(shù)趨向于0，而權(quán)值趨向于1/k；另一方面，隨著p趨向于1，該指數(shù)加大賦予離點(diǎn)最近的簇的權(quán)值。隨著p趨向于1，關(guān)于最近簇的隸屬度權(quán)值趨向于1，而關(guān)于其他簇的隸屬度權(quán)值趨向于0，這對(duì)應(yīng)于K均值。目標(biāo)函數(shù)-誤差的平方和模糊聚類算法三個(gè)圓形簇上的模糊c均值。對(duì)于100點(diǎn)的二維數(shù)據(jù)集，使用模糊c均值發(fā)現(xiàn)其三個(gè)簇的結(jié)果。每個(gè)點(diǎn)指派到它具有最大隸屬度權(quán)值的簇。屬于各個(gè)簇的點(diǎn)用不同的標(biāo)記顯示，而點(diǎn)在簇中的隸屬度用明暗程度表示。模糊聚類算法的優(yōu)點(diǎn)與局限性能指示任意點(diǎn)屬于任意簇的程度與k-means具有相同的優(yōu)缺點(diǎn)計(jì)算密集性更高使用混合模型的聚類基于統(tǒng)計(jì)模型的聚類假定數(shù)據(jù)由一個(gè)統(tǒng)計(jì)過(guò)程產(chǎn)生，通過(guò)找出最佳擬合數(shù)據(jù)的統(tǒng)計(jì)模型來(lái)描述數(shù)據(jù)，其中統(tǒng)計(jì)模型用分布和該分布的一組參數(shù)描述EM算法基于混合模型使用若干統(tǒng)計(jì)分布對(duì)數(shù)據(jù)建模，每個(gè)分布對(duì)應(yīng)于一個(gè)簇，每個(gè)分布的參數(shù)提供對(duì)應(yīng)簇的描述使用混合模型的聚類混合模型混合模型將數(shù)據(jù)看作從不同的概率分布得到的觀測(cè)值的集合，概率分布可以是任意分布，但通常是多元正態(tài)的混合模型對(duì)應(yīng)于如下數(shù)據(jù)產(chǎn)生過(guò)程，給定幾個(gè)分布(通常類型相同但參數(shù)不同)，隨機(jī)地選取一個(gè)分布并由它產(chǎn)生一個(gè)對(duì)象。重復(fù)該過(guò)程m次，其中m是對(duì)象的個(gè)數(shù)形式的，假定有k個(gè)分布和m個(gè)對(duì)象x1,…,xm，第j個(gè)分布的參數(shù)θj,Θ是所有參數(shù)的集合，即Θ={θ1,…,θk}，prob(xi|θj)是第i個(gè)對(duì)象來(lái)自第j個(gè)分布的概率，wj是對(duì)象x由第j個(gè)分布產(chǎn)生的概率，∑wj=1，對(duì)象x的概率

如果對(duì)象以獨(dú)立的方式產(chǎn)生，則整個(gè)對(duì)象集的概率是