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

ClusteringAnalysis

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

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

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

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

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

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

ωk:找到一個類別cj

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

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

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

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

時，過程結(jié)束。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p1p3p5p4p2p1p2p3p4p5......相似度MINMAX組平均GroupAverage質(zhì)心距離DistanceBetweenCentroids目標(biāo)函數(shù)驅(qū)動方法Ward’sMethodusessquarederror鄰近度矩陣簇相似度:MIN或者單鏈(SingleLink)最小距離法(singlelinkagemethod)Min定義簇的鄰近度為不同簇的兩個最近的點(diǎn)之間的鄰近度，或者使用圖的術(shù)語，不同的結(jié)點(diǎn)子集中兩個結(jié)點(diǎn)之間的最短邊。簇相似度:MIN或者單鏈(SingleLink)示例2，有6個二維點(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個二維點(diǎn)的樣本數(shù)據(jù)。點(diǎn)x和y坐標(biāo)，以及點(diǎn)之間的歐幾里得距離如下表所示。樹圖嵌套的簇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定義簇的鄰近度為不同簇中兩個最遠(yuǎn)的點(diǎn)之間的鄰近度，或者使用圖的術(shù)語，不同的結(jié)點(diǎn)子集中兩個結(jié)點(diǎn)之間的最長邊?；氐絼偛诺睦幼畲缶嚯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嵌套的簇樹圖簇相似度:組平均組平均距離法(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嵌套的簇樹圖層次聚類：時間和空間復(fù)雜度空間復(fù)雜度：O(N2)N是點(diǎn)的數(shù)量使用了鄰近度矩陣大多數(shù)情況下時間復(fù)雜度：O(N3)由N步構(gòu)成，在每一步，大小為N2的鄰近度矩陣需要更新和搜索對于某些方法，復(fù)雜度可以減少到O(N2log(N))層次聚類:問題和局限性一旦決定合并兩個簇，就不能撤銷缺乏全局目標(biāo)函數(shù)凝聚層次聚類技術(shù)使用各種標(biāo)準(zhǔn)，在每一步局部地確定哪些簇應(yīng)當(dāng)合并，這種方法產(chǎn)生的聚類算法避開了解決困難的組合優(yōu)化問題這種方法沒有很難選擇初始點(diǎn)的問題不同的方案存在一個或多個下列問題:對噪音和離群點(diǎn)敏感處理不同大小和凸?fàn)钚螤顣r存在困難會分裂大型簇——基于密度的聚類算法聚類算法(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ù)庫中發(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))。給定一個對象集合D，對象之間的距離函數(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一個點(diǎn)是核心點(diǎn)，如果該點(diǎn)的給定鄰域內(nèi)的點(diǎn)的個數(shù)超過指定數(shù)量(MinPts)的點(diǎn)這些點(diǎn)在簇內(nèi)部，點(diǎn)的鄰域由距離函數(shù)和用戶指定的距離參數(shù)Eps決定。一個邊界點(diǎn)不是核心點(diǎn)，但它落在某個核心點(diǎn)的鄰域內(nèi)。邊界點(diǎn)可能落在多個核心點(diǎn)的鄰域內(nèi)。一個噪音點(diǎn)既不是核心點(diǎn)也不是邊界點(diǎn)DBSCAN:核心、邊界和噪音點(diǎn)直接密度可達(dá)：如果p在q的Eps鄰域內(nèi)，而q是一個核心對象，則稱對象p從對象q出發(fā)時是直接密度可達(dá)的(directlydensity-reachableDBSCAN－基于中心的密度方法MinPts=5Eps=1cmpq密度可達(dá)：如果存在一個對象鏈，對于,是從關(guān)于Eps和MinPts直接密度可達(dá)的，則對象p是從對象q關(guān)于Eps和MinPts密度可達(dá)的(density-reachable)。p1pq密度相連：如果存在對象O∈D，使對象p和q都是從O關(guān)于Eps和MinPts密度可達(dá)的，那么對象p到q是關(guān)于Eps和MinPts密度相連的(density-connected)。DBSCAN－基于中心的密度方法pqoDBSCAN算法示例如圖，Eps用一個相應(yīng)的半徑表示，設(shè)MinPts=3。圖4.7“直接密度可達(dá)”和“密度可達(dá)”概念示意描述解答：根據(jù)以上概念知道：由于有標(biāo)記的各點(diǎn)-M、P、O和R的Eps近鄰均包含3個以上的點(diǎn)，因此它們都是核對象；M-是從P“直接密度可達(dá)”；而Q則是從-M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無法“密度可達(dá)”(非對稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。密度可達(dá)是直接密度可達(dá)的傳遞閉包，這種關(guān)系式非對稱的。只有核心對象之間相互密度可達(dá)。密度相連性是一個對稱關(guān)系基于密度的蔟是基于密度可達(dá)性的最大的密度相連對象的集合不包含在任何蔟中的對象被認(rèn)為是噪聲。DBSCAN－基于中心的密度方法DBSCAN通過檢查數(shù)據(jù)集中每點(diǎn)的Eps鄰域來搜索簇。如果點(diǎn)p的Eps鄰域包含的點(diǎn)多于MinPts個，則創(chuàng)建一個以p為核心對象的簇；然后DBSCAN迭代地聚集從這些核心對象直接密度可達(dá)的對象，這個過程可能涉及一些密度可達(dá)簇的合并；當(dāng)沒有新的點(diǎn)添加到任何簇時，該過程結(jié)束。DBSCAN－基于中心的密度方法算法具體描述(1)首先將數(shù)據(jù)集D中的所有對象標(biāo)記為未處理狀態(tài)(2)for數(shù)據(jù)集D中每個對象pdo(3)ifp已經(jīng)歸入某個簇或標(biāo)記為噪聲then(4)continue;(5)else(6)檢查對象p的Eps鄰域；(7)if包含的對象數(shù)小于MinPtsthen(8)標(biāo)記對象p為邊界點(diǎn)或噪聲點(diǎn)；(9)else(10)標(biāo)記對象p為核心點(diǎn)，并建立新簇C；(11)for中所有尚未被處理的對象qdo(12)檢查其Eps鄰域，若包含至少M(fèi)inPts個對象，則將中未歸入任何一個簇的對象加入C；(13)endfor(14)endif(15)endif(16)endforDBSCAN算法示例對于表所示二維平面上的數(shù)據(jù)集，取Eps=3，MinPts=3來演示DBSCAN算法的聚類過程(使用Mahattan距離公式)。表聚類過程示例數(shù)據(jù)集3P1P2P3P4P5P6P7P8P9P10P11P12P1312245667913532143879951212123解答：(1)隨機(jī)選擇一個點(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ò)展，每個點(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沒有落在任何核心點(diǎn)的鄰域內(nèi)，為噪聲點(diǎn)。最終識別出三個簇，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)均被識別成噪聲點(diǎn)。DBSCAN算法的優(yōu)點(diǎn)：可以識別具有任意形狀和不同大小的蔟，自動確定蔟的數(shù)目，分離簇和環(huán)境噪聲，一次掃描數(shù)據(jù)即可完成聚類。DBSCAN算法示例DBSCAN適用的情形原始點(diǎn)簇抗噪能夠處理不同形狀和大小的簇DBSCAN:確定EPS和MinPts同一個簇中的點(diǎn)到它們的k個最近鄰的距離大致相當(dāng)噪音點(diǎn)到它們的k個最近鄰距離則比較遠(yuǎn)對于某個k，計(jì)算所有點(diǎn)的k距離(點(diǎn)到它的k個最近鄰的距離)，并增序排列，然后繪制排序后的值，則會看到k-距離的急劇變化，對應(yīng)于合適的Eps值。選取該距離為Eps參數(shù)，取k值為MinPts參數(shù)，則k-距離小于Eps的點(diǎn)將被標(biāo)記為核心點(diǎn)，而其他點(diǎn)將被標(biāo)記為噪聲或邊界點(diǎn)。——基于原型的聚類算法聚類算法(ClusteringAlgorithm)基于原型的聚類基于原型的聚類：簇是對象的集合，一個簇中的任何對象離該簇的原型比其他簇的原型更近k-means，使用簇中對象的質(zhì)心作為簇的原型擴(kuò)展基于原型的聚類允許對象屬于多個簇，即對象以某個權(quán)值屬于每一個簇模糊聚類用統(tǒng)計(jì)分布對簇進(jìn)行建模，即對象通過一個隨機(jī)過程，由一個被若干統(tǒng)計(jì)參數(shù)(如均值和方差)刻畫的統(tǒng)計(jì)分布產(chǎn)生EM聚類模糊聚類如果數(shù)據(jù)對象分布在明顯分離的組中，則把對象明確分類成不相交的簇是一種理想的方法；在大部分情況下，數(shù)據(jù)集中的對象不能劃分明顯分離的簇，指派一個對象到一個特定的簇具有一定的任意性。

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

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

賦值2repeat3

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

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

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