《數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)》第3章聚類分析

第3章聚類分析

《數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)》(第2版)數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-2)聚類分析

聚類是對(duì)物理的或抽象的對(duì)象集合分組的過(guò)程。本章主要介紹如下幾個(gè)方面的內(nèi)容：聚類算法的特點(diǎn)聚類分析中的數(shù)據(jù)類型基于劃分的方法基于層次的方法基于密度的方法基于網(wǎng)格的方法基于模型的方法孤立點(diǎn)分析數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-3)引言聚類(Clustering)是對(duì)物理的或抽象的對(duì)象集合分組的過(guò)程聚類生成的組稱為簇(Cluster)，簇是數(shù)據(jù)對(duì)象的集合。簇內(nèi)部的任意兩個(gè)對(duì)象之間具有較高的相似度屬于不同簇的兩個(gè)對(duì)象間具有較高的相異度相異度可以根據(jù)描述對(duì)象的屬性值計(jì)算，最常用的度量指標(biāo)是距離。聚類最初來(lái)自數(shù)學(xué)、統(tǒng)計(jì)學(xué)和數(shù)值分析；機(jī)器學(xué)習(xí)領(lǐng)域把聚類描述成隱含模式，發(fā)現(xiàn)簇的過(guò)程是無(wú)監(jiān)督學(xué)習(xí)；聚類是模式識(shí)別的重要手段。聚類的特點(diǎn)用少量的簇描述大量數(shù)據(jù)的特征數(shù)據(jù)簡(jiǎn)潔丟失精細(xì)部分聚類在數(shù)據(jù)挖掘?qū)嵺`中的應(yīng)用數(shù)據(jù)預(yù)處理科學(xué)數(shù)據(jù)探索信息獲取與文本挖掘空間數(shù)據(jù)庫(kù)應(yīng)用CRM

市場(chǎng)分析

Web分析醫(yī)學(xué)診斷計(jì)算生物學(xué)數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-4)引言統(tǒng)計(jì)學(xué)：聚類分析是通過(guò)數(shù)據(jù)建模簡(jiǎn)化數(shù)據(jù)的一種方法。包括系統(tǒng)聚類法、分解法、加入法、動(dòng)態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。機(jī)器學(xué)習(xí)：簇相當(dāng)于隱藏模式。聚類是搜索簇的無(wú)監(jiān)督學(xué)習(xí)過(guò)程。與分類不同，無(wú)監(jiān)督學(xué)習(xí)不依賴預(yù)先定義的類或帶類標(biāo)記的訓(xùn)練實(shí)例，需要由聚類學(xué)習(xí)算法自動(dòng)確定標(biāo)記，而分類學(xué)習(xí)的實(shí)例或數(shù)據(jù)對(duì)象有類別標(biāo)記。聚類是觀察式學(xué)習(xí)，而不是示例式的學(xué)習(xí)。實(shí)際應(yīng)用：聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一。作為一個(gè)獨(dú)立的工具獲得數(shù)據(jù)的分布狀況，觀察每一簇?cái)?shù)據(jù)的特征，集中對(duì)特定的聚簇集合作進(jìn)一步地分析。作為其他數(shù)據(jù)挖掘任務(wù)（如分類、關(guān)聯(lián)規(guī)則）的預(yù)處理步驟。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-5)引言聚類算法的特征處理不同類型屬性的能力對(duì)大型數(shù)據(jù)集的可擴(kuò)展性處理高維數(shù)據(jù)的能力發(fā)現(xiàn)任意形狀簇的能力處理孤立點(diǎn)或“噪聲”數(shù)據(jù)的能力對(duì)“噪聲”數(shù)據(jù)具有較低的敏感性合理地發(fā)現(xiàn)孤立點(diǎn)對(duì)數(shù)據(jù)順序的不敏感性對(duì)先驗(yàn)知識(shí)和用戶自定義參數(shù)的依賴性聚類結(jié)果的可解釋性和實(shí)用性基于約束的聚類數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-6)引言聚類算法分類基于劃分的方法k-means算法基于密度的算法基于層次的方法匯聚算法分裂算法基于網(wǎng)格的方法非數(shù)據(jù)與數(shù)值屬性同時(shí)出現(xiàn)的方法基于約束的方法運(yùn)用機(jī)器學(xué)習(xí)技術(shù)的方法。梯度下降法人工神經(jīng)網(wǎng)絡(luò)法進(jìn)化模型有擴(kuò)展性的算法面向高維數(shù)據(jù)集的算法數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-7)數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型區(qū)間標(biāo)度型：用線性標(biāo)度描述的連續(xù)度量。（如，重量、高度、經(jīng)緯度坐標(biāo)、溫度等）布爾型：若兩個(gè)狀態(tài)同等重要，稱為對(duì)稱的，否則是不對(duì)稱的。標(biāo)稱型：有若干個(gè)離散的取值。序數(shù)型：取離散的序數(shù)值，序列排序是有意義的。比例標(biāo)度型：在非線性標(biāo)度上取正的度量值。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣相異度矩陣數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-8)計(jì)算對(duì)象之間的距離距離函數(shù)距離函數(shù)‖‖應(yīng)滿足的條件是：

(1)‖xi–xj

‖=0，當(dāng)且僅當(dāng)xi=xj

(2)非負(fù)性：‖xi–xj

‖≥0(3)對(duì)稱性：‖xi–xj

‖=‖xj–xi‖(4)三角不等式：

‖xi–xk

‖≤‖xi–xj

‖+‖xj

–xk

‖

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-9)計(jì)算對(duì)象之間的距離設(shè)兩個(gè)對(duì)象的p維向量分別表示為

xi=(xi1,xi2,…,xip)T

和xj=(xj1,xj2,…,xjp)T

，有多種形式的距離度量可以采用。如，閔可夫斯基（Minkowski）距離曼哈坦（Manhattan）距離歐幾里得（Euclidean）距離切比雪夫（Chebyshev）距離馬哈拉諾比斯（Mahalanobis）距離數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-10)計(jì)算對(duì)象之間的距離閔可夫斯基(Minkowski)距離：其中q[1,]。曼哈坦(Manhattan)距離：歐幾里德(Euclidean)距離：切比雪夫(Chebyshev)距離：馬哈拉諾比斯(Mahalanobis)距離：其中A為正定矩陣。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-11)計(jì)算對(duì)象之間的距離令對(duì)象的維數(shù)p=2，在二維空間中考察到原點(diǎn)距離為常數(shù)的所有點(diǎn)形成的形狀。即，考察集合{x|||x||=c}的形狀。

菱形：曼哈坦距離；圓形：歐幾里德距離；方形：切比雪夫距離。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-12)基于劃分的聚類方法已知由n個(gè)對(duì)象(或元組)構(gòu)成的數(shù)據(jù)庫(kù)，對(duì)其采用目標(biāo)函數(shù)最小化的策略，通過(guò)迭代把數(shù)據(jù)分成k個(gè)劃分塊，每個(gè)劃分塊為一個(gè)簇(cluster)，這就是劃分方法。劃分方法滿足兩個(gè)條件：每個(gè)簇至少包含一個(gè)對(duì)象；每個(gè)對(duì)象必需屬于且僅屬于某一個(gè)簇。常見(jiàn)的劃分方法：k-means(k-均值)方法k-medoids(k-中心點(diǎn))方法數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-13)k-means聚類算法k-均值(K-means)聚類算法的核心思想是通過(guò)迭代把數(shù)據(jù)對(duì)象劃分到不同的簇中，以求目標(biāo)函數(shù)最小化，從而使生成的簇盡可能地緊湊和獨(dú)立。設(shè)p表示數(shù)據(jù)對(duì)象，ci表示簇Ci的均值，通常目標(biāo)函數(shù)采用平方誤差準(zhǔn)則函數(shù)：

這個(gè)目標(biāo)函數(shù)采用歐幾里得距離度量。如果采用Mahalanobis距離可以對(duì)橢圓形的簇進(jìn)行分析。k-means算法步驟如下：首先，隨機(jī)選取k個(gè)對(duì)象作為初始的k個(gè)簇的質(zhì)心；然后，將其余對(duì)象根據(jù)其與各個(gè)簇質(zhì)心的距離分配到最近的簇；再求新形成的簇的質(zhì)心。這個(gè)迭代重定位過(guò)程不斷重復(fù)，直到目標(biāo)函數(shù)最小化為止。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-14)k-means聚類算法k-means算法輸入：期望得到的簇的數(shù)目k，n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：使得平方誤差準(zhǔn)則函數(shù)最小化的k個(gè)簇。方法：選擇k個(gè)對(duì)象作為初始的簇的質(zhì)心；repeat

計(jì)算對(duì)象與各個(gè)簇的質(zhì)心的距離，將對(duì)象劃分到距離其最近的簇；重新計(jì)算每個(gè)新簇的均值；Until簇的質(zhì)心不再變化。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-15)k-means聚類算法k-means算法特點(diǎn)(1)算法的計(jì)算復(fù)雜度為O(nkt),其中，n為數(shù)據(jù)集中對(duì)象的數(shù)目，k為期望得到的簇的數(shù)目，t為迭代的次數(shù)。在處理大數(shù)據(jù)庫(kù)時(shí)也是相對(duì)有效的(可擴(kuò)展性)。(2)應(yīng)用局限性：用戶必須事先指定聚類簇的個(gè)數(shù)常常終止于局部最優(yōu)只適用于數(shù)值屬性聚類(計(jì)算均值有意義)對(duì)噪聲和異常數(shù)據(jù)也很敏感不適合用于發(fā)現(xiàn)非凸形狀的聚類簇?cái)?shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-16)k-means算法改進(jìn)工作算法改進(jìn)工作主要集中在如下幾個(gè)方面：參數(shù)k的選擇差異程度計(jì)算聚類均值的計(jì)算方法等例如：先應(yīng)用自下而上層次算法來(lái)獲得聚類數(shù)目，并發(fā)現(xiàn)初始分類,然后再應(yīng)用循環(huán)再定位(k-mean)來(lái)幫助改進(jìn)分類結(jié)果。k-modes：用新的相異性度量方法處理對(duì)象，用基于頻率的方法修改簇的modes。k-prototype:將k-means擴(kuò)展到處理符號(hào)屬性。EM(期望最大化)概率權(quán)值,聚類邊界不嚴(yán)格可擴(kuò)展性,識(shí)別數(shù)據(jù)中存在的三種類型區(qū)域數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-17)k-medoids算法k-means利用簇內(nèi)點(diǎn)的均值或加權(quán)平均值ci（質(zhì)心）作為簇Ci的代表點(diǎn)。對(duì)數(shù)值屬性數(shù)據(jù)有較好的幾何和統(tǒng)計(jì)意義。對(duì)孤立點(diǎn)是敏感的，如果具有極大值，就可能大幅度地扭曲數(shù)據(jù)的分布。k-中心點(diǎn)(k-medoids)算法是為消除這種敏感性提出的，它選擇簇中位置最接近簇中心的對(duì)象(稱為中心點(diǎn))作為簇的代表點(diǎn)，目標(biāo)函數(shù)仍然可以采用平方誤差準(zhǔn)則。

k-medoids算法處理過(guò)程首先，隨機(jī)選擇k個(gè)對(duì)象作為初始的k個(gè)簇的代表點(diǎn)，將其余對(duì)象按與代表點(diǎn)對(duì)象的距離分配到最近的簇；然后，反復(fù)用非代表點(diǎn)來(lái)代替代表點(diǎn)，以改進(jìn)聚類質(zhì)量。(用一個(gè)代價(jià)函數(shù)來(lái)估計(jì)聚類質(zhì)量，該函數(shù)度量對(duì)象與代表點(diǎn)對(duì)象之間的平均相異度。)

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-18)k-medoids算法k-medoids算法輸入：n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，期望得到的k個(gè)聚類簇輸出：k個(gè)簇，使所有對(duì)象與其所屬簇中心點(diǎn)的偏差總和最小化方法：選擇k個(gè)對(duì)象作為初始的簇中心repeat

對(duì)每個(gè)對(duì)象，求離其最近的簇中心點(diǎn)，并將其分配到該中心點(diǎn)代表的簇隨機(jī)選取非中心點(diǎn)Orandom

計(jì)算用Orandom

代替Oj

形成新集合的總代價(jià)S

ifS<0then用Orandom代替Oj，形成新的k個(gè)中心點(diǎn)的集合until不再發(fā)生變化數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-19)k-medoids算法K-medoids算法特點(diǎn)(1)優(yōu)點(diǎn)：對(duì)屬性類型沒(méi)有局限性；魯棒性強(qiáng)：通過(guò)簇內(nèi)主要點(diǎn)的位置來(lái)確定選擇中心點(diǎn)，對(duì)孤立點(diǎn)和噪聲數(shù)據(jù)的敏感性小。(2)不足：處理時(shí)間要比k-mean更長(zhǎng)用戶事先指定所需聚類簇個(gè)數(shù)k。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-20)與k-medoids相關(guān)的算法PAM(PartitioningAroundMedoid)是最早提出的k-中心點(diǎn)算法之一；總在中心點(diǎn)周圍試圖尋找更好的中心點(diǎn)；針對(duì)各種組合計(jì)算代價(jià)；不足在于n和k較大時(shí)，時(shí)間代價(jià)太大。CLARA(Clustering

LARgeApplication)是面向大型數(shù)據(jù)庫(kù)的劃分方法；是基于抽樣的方法；先從數(shù)據(jù)集中抽取若干樣本，在每份樣本上使用PAM算法，求得抽樣數(shù)據(jù)的中心點(diǎn)。有效性取決于抽樣的合理性。如果樣本偏斜，產(chǎn)生的聚類結(jié)果也不會(huì)很好。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-21)EM算法期望最大化(ExpectationMaximization，EM)算法不將對(duì)象明確地分到某個(gè)簇，而是根據(jù)表示隸屬可能性的權(quán)來(lái)分配對(duì)象。在實(shí)際應(yīng)用中，相當(dāng)多的問(wèn)題屬于數(shù)據(jù)殘缺問(wèn)題。不能直接觀察到的變量(屬性)稱為隱含變量，任何含有隱含變量的模型都可以歸為數(shù)據(jù)殘缺問(wèn)題。EM算法是解決數(shù)據(jù)殘缺問(wèn)題的有效的算法。EM聚類：假定存在一個(gè)離散值的隱含變量C，其取值為{c1,c2,…,ck

}。對(duì)于所有n個(gè)對(duì)象，隱含變量值是未知的。聚類的目的是估計(jì)出每一個(gè)觀察值x(i)（1≤i≤n）對(duì)應(yīng)的C的取值。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-22)EM算法D={x(1),x(2),…,

x(n)}為n個(gè)觀察到的數(shù)據(jù)向量組成的集合。H={z(1),z(2),…,z(n)}表示隱含變量Z的n個(gè)值。分別與觀察到的數(shù)據(jù)點(diǎn)一一對(duì)應(yīng)，即z(i)與數(shù)據(jù)點(diǎn)x(i)相聯(lián)系，z(i)表示數(shù)據(jù)x(i)的不可見(jiàn)聚類標(biāo)簽?？梢园延^察到的數(shù)據(jù)的對(duì)數(shù)似然寫(xiě)為：（3.10）

其中右側(cè)的求和項(xiàng)表明，觀察到的似然可以表示為觀察到的數(shù)據(jù)和隱藏?cái)?shù)據(jù)的似然對(duì)隱藏值的求和。（3.10）式中假定了一個(gè)以未知參數(shù)θ為參量的概率模型p(D,H|θ)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-23)EM算法

設(shè)Q(H)為殘缺數(shù)據(jù)H的任意概率分布?？梢杂靡韵路绞奖硎舅迫唬汉瘮?shù)F(Q,θ)是要最大化的似然函數(shù)l(θ)的下限。

Jensen不等式數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-24)EM算法

EM算法重復(fù)以下兩個(gè)步驟直至收斂：(1)E步驟：固定參數(shù)θ，使F相對(duì)于分布Q最大化：

(2)M步驟：固定分布Q(H)，使F相對(duì)于參數(shù)θ最大化：

在E步驟中，以參數(shù)向量θk的特定設(shè)置為條件，估計(jì)隱藏變量的分布;在M步驟中，保持Q不變，選取新的參數(shù)θk＋1，使觀察到的數(shù)據(jù)的期望對(duì)數(shù)似然最大化。通過(guò)E步驟和M步驟的迭代，求出收斂的參數(shù)解。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-25)EM算法例3.1EM算法應(yīng)用于估計(jì)正態(tài)混合模型的參數(shù)。設(shè)測(cè)量數(shù)據(jù)x是一維的，假定數(shù)據(jù)來(lái)自于K個(gè)潛在的正態(tài)分布。沒(méi)有觀察到分量的標(biāo)簽，因此不知道每個(gè)數(shù)據(jù)來(lái)自哪一個(gè)分量分布。希望擬和的正態(tài)混合模型為：其中，μk和σk分別為第k個(gè)分量的均值和標(biāo)準(zhǔn)差，πk

是數(shù)據(jù)點(diǎn)屬于第k個(gè)分量的先驗(yàn)概率。解：參數(shù)向量為θ={π1,…,πk,μ1,…,μk,σ1,…,σk}，假定此時(shí)知道θ的值，則對(duì)象x來(lái)自第k個(gè)分量的概率為：上式是E步驟，可以利用以下各式估計(jì)πk

，μk

，σk

。下面是M步驟：

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-26)EM算法E步驟和M步驟形成迭代關(guān)系，先取πk

，μk

，σk

的初始值，估計(jì)P(k|x)，然后更新πk

，μk

，σk

，再用新的參數(shù)進(jìn)行下一次迭代，直到收斂判斷成立（如似然的收斂或模型參數(shù)達(dá)到某個(gè)穩(wěn)定點(diǎn)）。解畢。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-27)層次聚類層次聚類按數(shù)據(jù)分層建立簇，形成一棵以簇為節(jié)點(diǎn)的樹(shù)，稱為聚類圖。自底向上層次聚合，稱為凝聚的層次聚類。自頂向下層次分解，稱為分裂的層次聚類。凝聚的層次聚類：開(kāi)始時(shí)把每個(gè)對(duì)象作為一個(gè)單獨(dú)的簇，然后逐次對(duì)各個(gè)簇進(jìn)行適當(dāng)合并，直到滿足某個(gè)終止條件。分裂的層次聚類：開(kāi)始時(shí)將所有對(duì)象置于同一個(gè)簇中，然后逐次將簇分裂為更小的簇，直到滿足某個(gè)終止條件。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-28)層次聚類

簇的凝聚或分裂要遵循一定的距離(或相似度)準(zhǔn)則。常見(jiàn)的簇間距離度量方法如下：1.最小距離(單鏈接方法)：2.最大距離(完全鏈接方法)：3.平均距離(平均鏈接方法)：4.均值的距離(質(zhì)心方法)：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-29)層次聚類例3.2

圖3.3給出了凝聚的層次聚類方法AGNES、分裂的層次聚類方法DIANA的處理過(guò)程。

其中，對(duì)象間距離函數(shù)采用歐氏距離，簇間距離采用最小距離。在AGNES中，選擇簇間距離最小的兩個(gè)簇進(jìn)行合并。而在DIANA中，按最大歐氏距離進(jìn)行簇分裂。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-30)層次聚類層次聚類方法的優(yōu)點(diǎn)：可以在不同粒度水平上對(duì)數(shù)據(jù)進(jìn)行探測(cè)，容易實(shí)現(xiàn)相似度量或距離度量。層次聚類方法的缺點(diǎn)：?jiǎn)渭兊膶哟尉垲愃惴ńK止條件含糊（需人為設(shè)定），執(zhí)行合并或分裂簇的操作后不可修正，可能導(dǎo)致聚類結(jié)果質(zhì)量很低。可擴(kuò)展性較差，需要檢查和估算大量的對(duì)象或簇才能決定簇的合并或分裂。通常考慮把層次聚類方法與其他方法（如迭代重定位方法）相結(jié)合來(lái)解決實(shí)際聚類問(wèn)題。層次聚類和其他聚類方法的有效集成可以形成多階段聚類，能夠改善聚類質(zhì)量。這類方法包括BIRCH、CURE、ROCK、Chameleon等。

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-31)BIRCH算法BIRCH算法(BalancedIterativeReducingandClusteringusingHierachies)利用層次方法進(jìn)行平衡迭代歸約和聚類。首先將對(duì)象劃分成樹(shù)形結(jié)構(gòu)，然后采用其他聚類算法對(duì)聚類結(jié)果求精。BIRCH的核心概念是聚類特征和聚類特征樹(shù)（CF樹(shù)），并用于概括聚類描述。某子簇中含有N個(gè)d維數(shù)據(jù)點(diǎn){Xi}(i=1,2,…,N)，該子簇的聚類特征定義為一個(gè)三元組

其中，N為子簇中點(diǎn)的數(shù)目；為N個(gè)點(diǎn)的線性和，即，反映簇的質(zhì)心位置；SS是N個(gè)點(diǎn)的平方和，即，SS反映簇的大小（凝聚程度）。定理3.1（CF可加性定理）假設(shè)有兩個(gè)不交的簇的聚類特征分別為和

，由這兩個(gè)合并形成的新簇的聚類特征CF為：

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-32)BIRCH算法CF樹(shù)存儲(chǔ)了層次聚類的聚類特征。它是一棵帶有兩個(gè)參數(shù)的高度平衡的樹(shù)，這兩個(gè)參數(shù)為分支因子B和閾值T。非葉子節(jié)點(diǎn)至多有B個(gè)形如[CFi,childi

]的項(xiàng)(i=1,2,…,B)?！癱hildi”是指向第i個(gè)孩子節(jié)點(diǎn)的指針，CFi是該孩子節(jié)點(diǎn)表示的子簇的聚類特征。非葉子節(jié)點(diǎn)表示由所有孩子節(jié)點(diǎn)表示的子簇組合形成的簇。葉子節(jié)點(diǎn)至多包含L個(gè)項(xiàng)，形如[CFi](i=1,2,…,L)。有兩個(gè)指針“prev”和“next”，用于把所有葉子連成鏈。葉子節(jié)點(diǎn)表示由相應(yīng)項(xiàng)描述的子簇形成的簇。葉子節(jié)點(diǎn)的項(xiàng)滿足閾值T，T表示葉子節(jié)點(diǎn)中子聚類的最大直徑（或半徑）。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-33)BIRCH算法BIRCH算法：采用多階段聚類技術(shù)，對(duì)數(shù)據(jù)集合進(jìn)行單遍掃描后生成初步簇，再經(jīng)過(guò)一遍或多遍掃描改進(jìn)聚類質(zhì)量，CF樹(shù)的重建類似于B＋樹(shù)構(gòu)建中的節(jié)點(diǎn)插入和節(jié)點(diǎn)分裂。算法優(yōu)點(diǎn)：對(duì)大型數(shù)據(jù)庫(kù)的高效性和可擴(kuò)展性支持增量聚類復(fù)雜度為O(n)算法缺點(diǎn)：CF樹(shù)對(duì)節(jié)點(diǎn)中包含項(xiàng)的數(shù)目有限制，這可能導(dǎo)致節(jié)點(diǎn)并未對(duì)應(yīng)實(shí)際數(shù)據(jù)集的一個(gè)自然簇。不適合發(fā)現(xiàn)非球形的簇。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-34)CURE算法CURE（利用代表點(diǎn)聚類,ClusteringUsingRepresentatives）算法是介于基于質(zhì)心方法和基于代表對(duì)象點(diǎn)方法之間的策略。CURE算法不是利用質(zhì)心或單個(gè)代表對(duì)象點(diǎn)來(lái)代表一個(gè)簇，而是首先在簇中選取固定數(shù)目的、離散分布的點(diǎn)，用這些點(diǎn)反映簇的形狀和范圍。然后把離散的點(diǎn)按收縮因子

向簇的質(zhì)心收縮。收縮后的離散點(diǎn)作為簇的代表點(diǎn)。兩個(gè)簇的距離定義為代表點(diǎn)對(duì)（分別來(lái)自兩個(gè)簇）距離的最小值，在CURE算法的每一步合并距離最近的兩個(gè)簇。調(diào)節(jié)收縮因子α，α[0,1]，可以讓CURE發(fā)現(xiàn)不同形式的簇。當(dāng)α=1時(shí)，CURE還原為基于質(zhì)心的方法。當(dāng)α=0時(shí)，CURE還原為MST（最小生成樹(shù)）方法。CURE算法特點(diǎn)：可以發(fā)現(xiàn)非球形及大小差異較大的簇。對(duì)噪聲不敏感。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-35)Chameleon算法Chameleon算法是一種采用動(dòng)態(tài)建模技術(shù)的層次聚類算法。Chameleon算法分兩個(gè)步驟：第一步利用圖劃分算法將數(shù)據(jù)對(duì)象聚類為若干相對(duì)較小的子聚類；另一步是采用凝聚的層次聚類算法合并子簇，從而發(fā)現(xiàn)真實(shí)的簇。Chameleon中數(shù)據(jù)項(xiàng)的稀疏圖表示采用k-最近鄰圖方法。k-最近鄰圖中每個(gè)頂點(diǎn)表示一個(gè)數(shù)據(jù)對(duì)象。如果對(duì)象u是對(duì)象ν的k-最近似點(diǎn)之一，或ν是u的k-最近似點(diǎn)之一，則在表示u和ν的頂點(diǎn)間存在一條邊。把對(duì)象所在區(qū)域的密度作為邊的權(quán)重，權(quán)重可以反映數(shù)據(jù)空間的總體密度分布，應(yīng)該對(duì)密集區(qū)域和稀疏區(qū)域的數(shù)據(jù)均勻建模。由于Chameleon算法建立在稀疏圖基礎(chǔ)之上，所以每一個(gè)簇是數(shù)據(jù)集原始稀疏圖的一個(gè)子圖。

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-36)Chameleon算法Chameleon考查兩個(gè)簇的相對(duì)互聯(lián)度RI和相對(duì)接近度RC，利用動(dòng)態(tài)建?？蚣軄?lái)決定簇間的相似度。簇Ci和Cj之間的相對(duì)互聯(lián)度RI(Ci,Cj)定義為：

其中，EC(Ci,Cj)是把由Ci和Cj組成的簇分裂為Ci和Cj的邊割集；EC(Ci)是將Ci對(duì)應(yīng)的子圖劃分為大致相等的兩部分需截?cái)嗟倪吀罴ㄗ钚〗財(cái)嗟确志€上的邊）。簇Ci和Cj之間的相對(duì)接近度RC(Ci,Cj)定義為：

其中，是連接Ci和Cj頂點(diǎn)的邊的平均權(quán)重；是Ci在EC(Ci)中的邊的平均權(quán)重；∣Ci∣表示Ci中數(shù)據(jù)點(diǎn)的個(gè)數(shù)。實(shí)際上，RC是相對(duì)于兩個(gè)簇內(nèi)部接近度對(duì)簇間絕對(duì)接近度的規(guī)范化。采用RC避免了將小而稀疏的簇合并到大而密集的簇。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-37)Chameleon算法Chameleon選擇RI和RC都高的簇進(jìn)行合并，實(shí)質(zhì)上是合并既有良好互聯(lián)性又相互接近的兩個(gè)簇。因此，可以定義一個(gè)由RI和RC組合而成的函數(shù)，選擇使該函數(shù)取最大值的一對(duì)簇進(jìn)行合并。例如，可以采用下述形式：

RI(Ci,Cj)

RC(Ci,Cj)

其中，α是用戶定義的參數(shù)。α>1時(shí)，側(cè)重于相對(duì)接近度；α<1時(shí)，側(cè)重于相對(duì)互聯(lián)度。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-38)基于密度的聚類方法大型空間數(shù)據(jù)庫(kù)中可能含有球形、線形、延展形等多種形狀的簇，要求聚類算法應(yīng)具有：發(fā)現(xiàn)任意形狀簇的能力。在大型數(shù)據(jù)庫(kù)上具有高效性?；诿芏鹊姆椒ㄖ饕袃深惢谶B通性的算法包括DBSCAN、GDBSCAN、OPTICS、DBCLASD等?；诿芏群瘮?shù)的算法如，DBNCLUE等算法。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-39)DBSCAN算法DBSCAN（DensityBasedSpatialClusteringofApplicationswithNoise）算法是一種基于密度的聚類算法，它將足夠高密度的區(qū)域劃分為簇，能夠在含有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇。點(diǎn)的鄰域的形狀取決于兩點(diǎn)間的距離函數(shù)dist(p,q)。例如，采用二維空間的曼哈坦距離時(shí)，鄰域的形狀為矩形。定義3.1點(diǎn)p的ε-鄰域記為Nε(p)，定義如下：

Nε(p)={qD|dist

(p,q)≤ε}

定義3.2如果p，q滿足下列條件：①pNε(q)，②∣Nε(q)∣≥MinPts，則稱點(diǎn)p是從點(diǎn)q關(guān)于ε和MinPts直接密度可達(dá)的。MinPts為數(shù)據(jù)點(diǎn)個(gè)數(shù)。直接密度可達(dá)關(guān)系在核心點(diǎn)對(duì)間是對(duì)稱的，在核心點(diǎn)和邊界點(diǎn)間直接密度可達(dá)關(guān)系不是對(duì)稱的。定義3.3如果存在一個(gè)點(diǎn)的序列p1,p2,…,pn，p1=q，pn=p，pi+1是從pi直接密度可達(dá)的，則稱點(diǎn)p是從點(diǎn)q關(guān)于ε和MinPts密度可達(dá)的。密度可達(dá)是直接密度可達(dá)的擴(kuò)展，密度可達(dá)關(guān)系滿足傳遞性，但不滿足對(duì)稱性。

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-40)DBSCAN算法數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-41)DBSCAN算法定義3.4如果存在一個(gè)點(diǎn)o，p和q都是從點(diǎn)o關(guān)于ε和MinPts密度可達(dá)的，則稱點(diǎn)p是從點(diǎn)q關(guān)于ε和MinPts密度相連的。密度相連是一個(gè)對(duì)稱關(guān)系。密度可達(dá)的點(diǎn)之間的密度相連關(guān)系還滿足自反性。定義3.5令D表示數(shù)據(jù)點(diǎn)的集合，若D的非空子集C滿足下列條件：(1)對(duì)任意p和q，若pC且q是從p關(guān)于ε和MinPts密度可達(dá)的，則有qC。（最大性）(2)p,qC

:p與q是關(guān)于ε和MinPts密度相連的。（連通性）則稱C是基于密度的簇。基于密度的簇是基于密度可達(dá)的最大的密度相連的點(diǎn)的集合。定義3.6令C1,C2,…,Ck是數(shù)據(jù)庫(kù)中分別關(guān)于參數(shù)εi和MinPtsi構(gòu)成的簇（i=1,2,…,k），則定義“噪聲”為數(shù)據(jù)庫(kù)D中不屬于任何簇的數(shù)據(jù)點(diǎn)的集合，即集合

{pD|

i:pCi

}數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-42)DBSCAN算法引理3.1令p為數(shù)據(jù)庫(kù)D中的一個(gè)點(diǎn)，∣Nε(p)∣≥MinPts，則集合

O={o|oD且o是從p關(guān)于ε和MinPts密度可達(dá)的}是一個(gè)關(guān)于ε和MinPts的簇。引理3.2令C為一個(gè)關(guān)于ε和MinPts的簇，p為C中某個(gè)滿足∣Nε(p)∣≥MinPts的點(diǎn)，則C等于集合O={o|oD且o是從p關(guān)于ε和MinPts密度可達(dá)的}。DBSCAN算法：輸入：給定參數(shù)ε和MinPts方法：(1)從數(shù)據(jù)庫(kù)中任意選取一個(gè)滿足核心點(diǎn)條件的點(diǎn)作為種子；(2)檢索從種子點(diǎn)密度可達(dá)的所有點(diǎn)，獲得包括種子點(diǎn)在內(nèi)的簇。討論：雖然DBSCAN算法可以對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類，但需要由用戶確定輸入?yún)?shù)ε和MinPts。在現(xiàn)實(shí)的高維數(shù)據(jù)集合中，很難準(zhǔn)確確定聚類參數(shù)。由于這類算法對(duì)參數(shù)值非常敏感，參數(shù)值的微小變化往往會(huì)導(dǎo)致差異很大的聚類結(jié)果?，F(xiàn)實(shí)的高維數(shù)據(jù)集往往不是均勻分布的，因此，全局密度參數(shù)不能很好地刻畫(huà)內(nèi)在的聚類結(jié)構(gòu)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-43)基于網(wǎng)格的聚類方法基于網(wǎng)格的方法首先將空間量化為有限數(shù)目的單元，然后在這個(gè)量化空間上進(jìn)行所有的聚類操作。這類方法的處理時(shí)間不受數(shù)據(jù)對(duì)象數(shù)目影響，僅依賴于量化空間中每一維上的單元數(shù)目，因此處理速度較快。STING（StatisticalInformationGrid-basedMethod，基于統(tǒng)計(jì)信息網(wǎng)格的方法）是針對(duì)空間數(shù)據(jù)挖掘的算法。它利用層次結(jié)構(gòu)將空間區(qū)域劃分為矩形單元，在每個(gè)單元中存儲(chǔ)對(duì)象的統(tǒng)計(jì)參數(shù)（如均值、方差、最小值、最大值、分布的類型等），用以描述有關(guān)數(shù)據(jù)特征。STING通過(guò)對(duì)數(shù)據(jù)集進(jìn)行一次掃描，計(jì)算單元中的統(tǒng)計(jì)參數(shù)。因此，若n表示對(duì)象的個(gè)數(shù)，則生成簇的時(shí)間復(fù)雜度為O(n)。在生成層次結(jié)構(gòu)后，一個(gè)查詢的響應(yīng)時(shí)間是O(k)。其中，k是最低分辨率下網(wǎng)絡(luò)單元的數(shù)目，通常k遠(yuǎn)小于n。STING采用多分辨率的方式進(jìn)行聚類，聚類質(zhì)量取決于網(wǎng)絡(luò)結(jié)構(gòu)中最底層的粒度。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(49-44)WaveCluster算法WaveCluster算法是基于網(wǎng)格的，也是基于密度的。主要思想：(1)量化特征空間，形成一