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

第3章聚類分析

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

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

市場分析

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

(1)‖xi–xj

‖=0，當且僅當xi=xj

(2)非負性：‖xi–xj

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

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

‖xi–xk

‖≤‖xi–xj

‖+‖xj

–xk

‖

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

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

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

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

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

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

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

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

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

對每個對象，求離其最近的簇中心點，并將其分配到該中心點代表的簇隨機選取非中心點Orandom

計算用Orandom

代替Oj

形成新集合的總代價S

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

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

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

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

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

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

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

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

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

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

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

，μk

，σk

。下面是M步驟：

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

，μk

，σk

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

，μk

，σk

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

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

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

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

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

其中，N為子簇中點的數(shù)目；為N個點的線性和，即，反映簇的質(zhì)心位置；SS是N個點的平方和，即，SS反映簇的大?。鄢潭龋６ɡ?.1（CF可加性定理）假設(shè)有兩個不交的簇的聚類特征分別為和

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

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

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

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

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

其中，EC(Ci,Cj)是把由Ci和Cj組成的簇分裂為Ci和Cj的邊割集；EC(Ci)是將Ci對應(yīng)的子圖劃分為大致相等的兩部分需截斷的邊割集（最小截斷等分線上的邊）。簇Ci和Cj之間的相對接近度RC(Ci,Cj)定義為：

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

RI(Ci,Cj)

RC(Ci,Cj)

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

Nε(p)={qD|dist

(p,q)≤ε}

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

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

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

{pD|

i:pCi

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

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