大數(shù)據(jù)挖掘?qū)д撆c案例課件-第7章 聚類分析概念與方法

第1章緒論第2章數(shù)據(jù)分析與可視化技術(shù)第3章認(rèn)識數(shù)據(jù)第4章數(shù)據(jù)預(yù)處理第5章分類概念與方法第6章關(guān)聯(lián)分析概念與方法第7章聚類分析概念與方法第8章大數(shù)據(jù)挖掘關(guān)鍵技術(shù)第9章案例分析第7章聚類分析概念與方法大數(shù)據(jù)挖掘?qū)д撆c案例學(xué)習(xí)目標(biāo)/Target掌握基本k均值算法，了解k均值算法優(yōu)缺點和常見改進算法，熟悉算法在數(shù)據(jù)集上的代碼實現(xiàn)。掌握凝聚層次聚類,

熟悉簇間鄰近度度量，了解算法的代碼實現(xiàn)。掌握聚類分析的定義，熟悉主要的聚類分析方法分類，熟悉聚類分析的主要步驟。學(xué)習(xí)目標(biāo)/Target熟悉EM算法的兩個步驟，了解模糊聚類、最大似然模型和高斯混合模型。熟悉常見聚類評估指標(biāo)的定義和計算。

熟悉DBSCAN算法，熟悉密度聚類相關(guān)概念，了解DBSCAN的代碼實現(xiàn)。引言/Introduction“方以類聚，物以群分”

《周易·系辭傳》“物以類聚，人以群分”

《戰(zhàn)國策·齊策三》聚類分析（clusteranalysis）是為了發(fā)現(xiàn)有意義或者有用的群組或者簇（cluster）。同一個簇中的對象之間有很大的相似性，而不同簇間的對象之間有很大的相異性。相似性的度量可以根據(jù)對象的屬性值來計算，而距離是經(jīng)常使用的度量方式。聚類分析已被應(yīng)用于數(shù)據(jù)挖掘、機器學(xué)習(xí)、模式識別、計算機視覺、生物信息學(xué)等許多領(lǐng)域。目錄/Contents010203基本概念k均值聚類凝聚層次聚類040506DBSCAN聚類期望最大化算法聚類評估基本概念7.17.1.1什么是聚類分析聚類分析（clustering）是給定一個數(shù)據(jù)集，將數(shù)據(jù)點分成若干個簇（cluster）的過程。簇是一組數(shù)據(jù)對象的集合，在組內(nèi)的數(shù)據(jù)對象盡可能相似（或相關(guān)），而組間的數(shù)據(jù)對象盡可能不同（或無關(guān)）。聚類分析7.1.1什么是聚類分析聚類分析根據(jù)數(shù)據(jù)的特征，選擇適當(dāng)?shù)年P(guān)于數(shù)據(jù)對象之間鄰近性（相似性或相異性）的度量（相似度或相異度），進而將數(shù)據(jù)對象分成若干個簇。通常使用數(shù)據(jù)點之間的距離作為它們之間的相異度。兩個對象越相似，它們之間的相異度值越小，相似度值越大。簇內(nèi)對象間的相似性越大，簇間對象的相異性越大，聚類的結(jié)果就越好。聚類分析7.1.1什么是聚類分析聚類分析通常被認(rèn)為是無監(jiān)督學(xué)習(xí)（unsupervisedlearning）中最重要的任務(wù)，用于標(biāo)簽（label,也叫標(biāo)號）未知的情況。與用于分類中的每個數(shù)據(jù)點有類標(biāo)號不同，聚類分析一般對生成的每個組指定一個組編號（或名稱），組中的對象便與該編號對應(yīng)起來。比如，聚類將數(shù)據(jù)集按相似性分成3個組，組編號可以是“第1組”“第2組”“第3組”，也可以是“簇1”“簇2”“簇3”或“C1”“C2”“C3”等。這樣的組編號沒有明確的實際意義，因此它們并不能描述每個組具體是什么樣的組。無監(jiān)督學(xué)習(xí)7.1.1什么是聚類分析數(shù)據(jù)記號

。7.1.1什么是聚類分析聚類的形式化描述

。7.1.2聚類分析方法可伸縮性處理不同數(shù)據(jù)類型發(fā)現(xiàn)任意形狀的簇對輸入?yún)?shù)的領(lǐng)域知識的要求處理噪聲數(shù)據(jù)處理新增數(shù)據(jù)和對輸入數(shù)據(jù)順序不敏感處理高維數(shù)據(jù)滿足約束可解釋性和可用性1.對聚類分析的基本要求7.1.2聚類分析方法劃分方法（PartitioningMethods）層次方法（HierarchicalMethods）基于密度的方法（Density-basedmethods）基于網(wǎng)格的方法（Grid-basedmethods）基于模型的方法（Model-basedmethods）2.主要的聚類方法7.1.2聚類分析方法特征選擇：選擇任務(wù)的相關(guān)特征，包含最小的冗余信息；相似度度量：確定合適的度量方法，以描述兩個特征向量（數(shù)據(jù)點）之間的相似度，例如距離；效果評估準(zhǔn)則：通過損失函數(shù)或者其他規(guī)則制定；聚類算法：采用特定的聚類算法，執(zhí)行聚類；結(jié)果評估：驗證聚類；結(jié)果解釋：解釋聚類的結(jié)果。3.聚類分析的主要步驟k均值聚類7.2基于劃分的聚類算法通常需要選擇代表每個簇的原型點（prototypepoints），因此它們也被稱為基于原型的聚類算法（prototype-basedclustering）。7.2k均值聚類7.2.1基本k均值算法k均值聚類是在實際應(yīng)用中最簡單、有效和流行的一種劃分聚類算法?；緆均值算法需要把整個數(shù)據(jù)集劃分成k個簇，每個簇都有一個點作為原型或者質(zhì)心（centroids），作為這個簇的代表?；静襟E：用戶指定表示簇數(shù)目的參數(shù)k的取值，并選擇k個數(shù)據(jù)點作為初始質(zhì)心。指派每個點到最近的質(zhì)心，分配到同一質(zhì)心的點形成一個簇。根據(jù)同一個簇中的數(shù)據(jù)點，計算平均值來更新每個簇的質(zhì)心。重復(fù)分配和更新步驟，直到簇或質(zhì)心不發(fā)生變化。k均值（k-Means）聚類7.2.1基本k均值算法算法7.1k均值聚類算法輸入：數(shù)據(jù)集X，簇數(shù)k輸出：k個簇的集合過程：1：從X中任意選取k個數(shù)據(jù)點作為初始質(zhì)心2：repeat3：

通過將每個點指派給離它最近的質(zhì)心，得到k簇；4：

基于均值重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化7.2.1基本k均值算法圖7.1k均值聚類算法的圖形演示7.2.1基本k均值算法鄰近度（proximity）是聚類分析中的重要概念，直接影響聚類結(jié)果，它的選擇是聚類的根本問題。常用的鄰近度度量有閔可夫斯基距離、馬氏距離、相關(guān)系數(shù)和余弦相似度等。通常，歐氏空間的點用歐氏距離（L2）或曼哈頓距離（L1），文檔數(shù)據(jù)用余弦相似度或Jaccard系數(shù)等。鄰近度矩陣是包含數(shù)據(jù)集X鄰近度的成對指標(biāo)的矩陣。常用的鄰近度矩陣有距離矩陣（D）和相似度矩陣（S）。

幾個關(guān)鍵問題1.指派點到最近的質(zhì)心7.2.1基本k均值算法幾個關(guān)鍵問題1.指派點到最近的質(zhì)心

7.2.1基本k均值算法目標(biāo)函數(shù)用來表示聚類的目標(biāo)，依賴于點之間或點到簇質(zhì)心的鄰近度。歐氏空間中的數(shù)據(jù)使用誤差平方和（SSE，SumofSquaredErrors）或殘差平方和（RSS，ResidualSumofSquares）作為度量聚類質(zhì)量的目標(biāo)函數(shù)。SSE也稱為散度（scatter）。也就是計算每個數(shù)據(jù)點的誤差，即每個數(shù)據(jù)點到它所在簇的質(zhì)心的歐氏距離，然后計算誤差平方和。誤差平方和越小，簇中的點距離簇的原型（質(zhì)心）越近，簇中的點越緊密地（分散度越低地）圍繞在質(zhì)心周圍，簇中點的相似度也越高。

幾個關(guān)鍵問題2.質(zhì)心和目標(biāo)函數(shù)7.2.1基本k均值算法幾個關(guān)鍵問題2.質(zhì)心和目標(biāo)函數(shù)

其中，

代表Cj中數(shù)據(jù)點的個數(shù)。

7.2.1基本k均值算法幾個關(guān)鍵問題2.質(zhì)心和目標(biāo)函數(shù)（7.6）7.2.1基本k均值算法幾個關(guān)鍵問題3.選擇初始質(zhì)心當(dāng)隨機選取初始質(zhì)心時，不同的質(zhì)心初始化往往會產(chǎn)生不同的聚類結(jié)果，即不同的簇劃分、質(zhì)心和總SSE。(a)

最優(yōu)聚類

(b)

次優(yōu)聚類圖7.2最優(yōu)和非最優(yōu)的簇7.2.1基本k均值算法幾個關(guān)鍵問題3.選擇初始質(zhì)心選擇合適的初始質(zhì)心是k均值聚類的關(guān)鍵步驟。常見方法是隨機選取初始質(zhì)心，但是簇的質(zhì)量往往很差。可以重復(fù)運行幾次k均值聚類算法，每次隨機取一組不同的初始質(zhì)心，最后選取SSE最小的運行結(jié)果。7.2.1基本k均值算法幾個關(guān)鍵問題4.時間和空間復(fù)雜度因為只需要存儲數(shù)據(jù)點和質(zhì)心，k均值的空間復(fù)雜度為O((n+k)d)，其中n是數(shù)據(jù)點數(shù)，d是屬性數(shù)（維數(shù)）。k均值的時間復(fù)雜度為O(tkdn)，其中t是迭代次數(shù)。t通常很小，目標(biāo)函數(shù)往往經(jīng)過幾次迭代就可以快速收斂。因此，只要k<<n，k均值的計算時間就與n線性相關(guān)，并且簡單有效。

7.2.2基本k均值的附加問題處理空簇離群點使用后處理降低SSE增量更新質(zhì)心7.2.3k均值的優(yōu)點和缺點優(yōu)點：解決聚類問題的經(jīng)典和流行算法，簡單快速；處理大數(shù)據(jù)集時相對可伸縮并且高效；當(dāng)結(jié)果簇密集時，效果較好；適用于球形簇；二分k均值等改進算法運行良好，受初始化問題的影響較小。7.2.3k均值的優(yōu)點和缺點缺點：僅限于具有質(zhì)心概念的數(shù)據(jù)；不能應(yīng)用于所有的數(shù)據(jù)類型；必須提前指定超參數(shù)：簇數(shù)k；初始化敏感，不同初始值可能導(dǎo)致不同結(jié)果；容易陷入局部最優(yōu)；難以處理具有不同大小、不同密度或非球形簇（非凸形狀）；對于“噪聲”和孤立點數(shù)據(jù)敏感。7.2.4k均值的改進算法k中心點（k-medoids）k中位數(shù)（k-medians）k眾數(shù)（k-mode）k原型（k-prototype）二分k均值（Bisectingk-means）k均值++（k-means++）模糊k均值（FuzzyK-Means，F(xiàn)KM）核k均值（kernelk-means）7.2.5Iris數(shù)據(jù)集上的k均值聚類

sepallength(cm)sepalwidth(cm)petallength(cm)petalwidth(cm)target05.13.51.40.20.014.93.01.40.20.024.73.21.30.20.034.63.11.50.20.045.03.61.40.20.0圖7.4鳶尾花的三個亞屬表7.1Iris數(shù)據(jù)集（節(jié)選）代碼7.1利用sklearn庫對Iris數(shù)據(jù)進行k均值聚類fromsklearnimportdatasetsfromsklearn.clusterimportKMeansimportnumpyasnpimportpandasaspdimportmatplotlib.pyplotaspltimportseabornassnsdefdisplay_iris():iris=datasets.load_iris()print(iris)data_frame=pd.DataFrame(data=np.c_[iris['data'],iris['target']],columns=iris['feature_names']+['target'])pd.set_option('display.width',1000)#調(diào)整顯示寬度，以便整行顯示pd.set_option('display.max_columns',None)#顯示所有列pd.set_option('display.max_rows',None)#顯示所有行print(data_frame)sns.pairplot(data_frame,hue="target",markers=["o","s","v"])plt.show()7.2.5Iris數(shù)據(jù)集上的k均值聚類代碼7.1利用sklearn庫對Iris數(shù)據(jù)進行k均值聚類defk_means():iris=datasets.load_iris()#加載Iris數(shù)據(jù)集model=KMeans(n_clusters=3)#分3類model.fit(iris.data)#訓(xùn)練predict=model.predict(iris.data)#預(yù)測print(predict)data=pd.DataFrame(data=np.c_[iris['data'],predict],columns=iris['feature_names']+['predict'])sns.pairplot(data,hue="predict",markers=["o","s","D"],palette="colorblind")plt.show()if__name__=='__main__’:display_iris()k_means()7.2.5Iris數(shù)據(jù)集上的k均值聚類7.2.5Iris數(shù)據(jù)集上的k均值聚類圖7.5Iris數(shù)據(jù)集的k均值聚類的配對圖7.2.5Iris數(shù)據(jù)集上的k均值聚類圖7.6在Iris數(shù)據(jù)集上k均值聚類的迭代優(yōu)化過程凝聚層次聚類7.3層次聚類（HierarchicalClustering）也是出現(xiàn)較早又非常流行的方法，它假設(shè)數(shù)據(jù)對象之間存在層次結(jié)構(gòu)關(guān)系，將數(shù)據(jù)聚到層次化的簇中。有兩種基本的層次聚類方法：凝聚的層次聚類和分裂的層次聚類。凝聚的：從單個點作為個體簇開始，自底向上，每一步合并兩個最接近的簇。分裂的：從包含所有點的簇開始，自頂向下，每一步分裂一個簇，直到僅剩下單點簇。本節(jié)介紹最常見的凝聚的層次聚類。7.3凝聚層次聚類(a)樹狀圖 (b)嵌套簇圖圖7.76個數(shù)據(jù)點層次聚類的樹狀圖和嵌套簇圖7.3凝聚層次聚類7.3.1簇間鄰近度度量單鏈接：也叫最小距離。將兩個簇中任意兩點之間距離的最小值定義為兩個簇的簇間距離。

全鏈接：也叫最大距離。與單鏈接相反，將兩個簇中任意兩點之間距離的最大值定義為兩個簇的簇間距離。

7.3.1簇間鄰近度度量平均鏈接：也叫平均距離。將兩個不同簇中所有點對之間距離的平均值定義為兩個簇的簇間距離。質(zhì)心：將兩個簇的質(zhì)心間的距離定義為兩個簇間的鄰近度?；谠偷挠^點，用質(zhì)心代表簇，所以兩個簇的鄰近度定義為這兩個簇的質(zhì)心之間的鄰近度

7.3.1簇間鄰近度度量Ward：簇用質(zhì)心代表，使用合并兩個簇導(dǎo)致的SSE增量來定義簇間的鄰近性。像k均值一樣，Ward方法也試圖最小化SSE。設(shè)簇Ci和Cj合并后的簇為Ck，其對應(yīng)的SSE分別為SSEi、SSEj和SSEk

7.3.1簇間鄰近度度量(a)

單鏈(b)全鏈(c)

平均鏈(d)質(zhì)心距離圖7.8簇間的相似性度量7.3.2基本凝聚層次聚類算法算法7.5AGNES算法(1)輸入：數(shù)據(jù)集X＝{x1,x2,...,xn}，簇數(shù)k，簇距離度量函數(shù)d輸出：簇劃分:C={C1,C2,...,Ck}過程：1:forj=1,2,...,ndo2:Cj={xj}3:endfor4:fori=1,2,...,ndo5:forj=1,2,...,ndo6:M(i,j)=d(Ci,Cj)7:M(j,i)=M(i,j)8:endfor9:endfor7.3.2基本凝聚層次聚類算法算法7.5AGNES算法(1)輸入：數(shù)據(jù)集X＝{x1,x2,...,xn}，簇數(shù)k，簇距離度量函數(shù)d輸出：簇劃分:C={C1,C2,...,Ck}過程：1:forj=1,2,...,ndo2:Cj={xj}3:endfor4:fori=1,2,...,ndo5:forj=1,2,...,ndo6:M(i,j)=d(Ci,Cj)7:M(j,i)=M(i,j)8:endfor9:endfor7.3.3凝聚層次聚類實例

x1x2x3x4x5x10.000.502.243.353.00x20.500.002.503.613.04x32.242.500.001.121.41x43.353.611.120.001.50x53.003.041.411.500.00數(shù)據(jù)圖7.9包含5個點的2維數(shù)據(jù)集圖7.10初始的相異度矩陣7.3.3凝聚層次聚類實例1.單鏈接第1輪迭代合并最近的兩個簇（點），得到新簇

{x1,x2}。

{x1,x2}{x3}{x4}{x5}{x1,x2}0.002.243.353.00{x3}2.240.001.121.41{x4}3.351.120.001.50{x5}3.001.411.500.007.3.3凝聚層次聚類實例1.單鏈接第2輪迭代距離最近的兩個簇是{x3}和{x4}。合并{x3}和{x4}，得到新簇{x3,x4}

{x1,x2}{x3,x4}{x5}{x1,x2}0.002.243.00{x3,x4}2.240.001.41{x5}3.001.410.007.3.3凝聚層次聚類實例1.單鏈接第3輪迭代合并距離最小的兩個簇{x3,x4}和x5

{x1,x2}{x3,x4，x5}{x1,x2}0.002.24{x3,x4，x5}2.240.007.3.3凝聚層次聚類實例1.單鏈接第4輪迭代所有點都被合并成1個簇。7.3.3凝聚層次聚類實例1.單鏈接圖7.14單鏈接層次凝聚聚類的樹狀圖圖7.15單鏈接層次凝聚聚類的嵌套簇圖7.3.4時間和空間復(fù)雜度設(shè)n是數(shù)據(jù)點的數(shù)目，假定鄰近度矩陣對稱，需要存儲n2/2個鄰近度，保存簇的空間正比于簇數(shù)n-1，因此層次聚類算法總的空間復(fù)雜度為O(n2)。需要O(n2)時間計算鄰近度矩陣，一般需要n次迭代，時間復(fù)雜度為O(n3)。通過一些優(yōu)化措施，層次聚類算法的時間復(fù)雜度可以降到O(n2logn)。

7.3.5層次聚類的優(yōu)點和主要問題凝聚層次聚類沒有直接的全局優(yōu)化目標(biāo)函數(shù)，算法在每一步局部地確定應(yīng)當(dāng)合并或分裂哪些簇，這避開了難解的組合優(yōu)化問題。算法沒有選擇初始點的困難。在許多情況下，較高的時間復(fù)雜度O(n2logn)和空間復(fù)雜度O(n2)阻礙了算法的應(yīng)用。處理合并的兩個簇的大小差別有兩種方法：加權(quán)方法和非加權(quán)方法。若平等對待大小不同的簇，就對不同簇的點賦不同的權(quán)值；不考慮簇的大小，就對不同簇的點賦相同的權(quán)值。一旦合并了兩個簇，就不能撤銷，這阻礙了局部最優(yōu)變成全局最優(yōu)。算法能夠產(chǎn)生較高質(zhì)量的聚類。對于噪聲、高維數(shù)據(jù)（如文檔數(shù)據(jù)）是敏感的。

7.3.6凝聚層次聚類的python實現(xiàn)圖7.21凝聚聚類合并數(shù)據(jù)點的迭代過程7.3.6凝聚層次聚類的python實現(xiàn)圖7.22凝聚聚類嵌套簇圖7.3.6凝聚層次聚類的python實現(xiàn)7.234種不同鏈接的層次聚類樹狀圖和散點圖DBSCAN聚類7.4密度聚類亦稱“基于密度的聚類”（density-basedclustering）。密度聚類尋找被低密度區(qū)域分離的高密度區(qū)域。這種聚類算法假設(shè)能通過樣本分布的緊密程度確定簇的結(jié)構(gòu)，從樣本密度的角度來考察樣本之間的可連接性，并基于可連接樣本不斷擴展簇以獲得最終結(jié)果。密度聚類7.4DBSCAN聚類7.4.1DBSCAN算法的有關(guān)概念ε鄰域（?-neighborhood）：點p的密度可以用點p的鄰近點數(shù)量來度量。點p的ε鄰域是以點p為中心、以參數(shù)鄰域半徑ε為半徑的空間。鄰域密度可以用鄰域內(nèi)的點數(shù)來度量。使用參數(shù)鄰域密度閾值MinPts指定稠密區(qū)域的密度閾值。核心點（corepoint）：如果點p的ε鄰域至少包含MinPts個點，那么點p是核心點。核心點是稠密區(qū)域的核心。找出核心點就找到了稠密區(qū)域。稠密區(qū)域可以作為簇。給定點集D，便可以識別關(guān)于參數(shù)ε和MinPts的所有核心點，聚類任務(wù)就歸結(jié)為使用核心點和它們的鄰域形成稠密區(qū)域（簇）了。直接密度可達(dá)（directlydensity-reachable）：如果點p在核心點q的ε鄰域內(nèi)，則稱點p是從核心點q(關(guān)于ε和MinPts)直接密度可達(dá)的。顯然，點p是從點q直接密度可達(dá)的，當(dāng)且僅當(dāng)q是核心點，并且p在q的ε鄰域中。使用直接密度可達(dá)關(guān)系，核心點可以把它的鄰域中的所有點都“帶入”一個稠密區(qū)域。7.4.1DBSCAN算法的有關(guān)概念

,

ε鄰域（?-neighborhood）：如果存在點o，使點p和點q都是關(guān)于ε和MinPts密度可達(dá)的，則稱點p和點q是關(guān)于ε和MinPts密度相連的。7.4.1DBSCAN算法的有關(guān)概念圖7.24密度可達(dá)和密度相連7.4.2DBSCAN算法及實現(xiàn)最初標(biāo)記數(shù)據(jù)集D中的所有點為“unvisited”。隨機選擇一個未訪問點p并標(biāo)記為“visited”。檢查p的ε鄰域是否至少包含MinPts個點。如果不是就標(biāo)記p為噪聲點。否則為p創(chuàng)建新簇C,并且把p的ε鄰域中所有點都放到候選集合N中。迭代地把N中不屬于其他簇的點添加到C中。在此過程中，對于N中標(biāo)記為“unvisited”的點q，標(biāo)記為“visited”，并且檢查它的ε鄰域。如果q的ε鄰域至少有MinPts個點，則q的ε鄰域中的所有點都被添加到N中。繼續(xù)添加點到C，直到C不能再擴展，即直到N為空。這時，簇C完全生成。為了找下一個簇，從剩下的點中隨機地選擇一個未訪問點。繼續(xù)直到訪問了所有點。DBSCAN算法7.4.2DBSCAN算法及實現(xiàn)算法7.6DBSCAN算法輸入：D：n個點的數(shù)據(jù)集,ε：半徑，MinPts：鄰域密度閾值輸出：基于密度的簇的集合方法：1:標(biāo)記所有點為unvisited2：do3：

隨機選擇一個unvisited點p4：

標(biāo)記p即為visited5：ifp的ε鄰域至少有MinPts個點6：

創(chuàng)建一個新簇C，并把p添加到C7：

設(shè)N為p的ε鄰域中的點集8：forN中每個點q

9：ifq是unvisited10：

標(biāo)記q為visited11：ifq的ε鄰域至少有MinPts個點12：

把這些點添加到N13：ifq還不是任何簇的成員，14：

把q添加到C

15：endfor16：

輸出C17：else18：

標(biāo)記p為噪聲19：until沒有標(biāo)記為unvisited的點7.4.2DBSCAN算法及實現(xiàn)代碼7.6在“雙月”數(shù)據(jù)集上DBSCAN算法fromsklearn.datasetsimportmake_moons

fromsklearn.clusterimportDBSCAN

importmatplotlib.pyplotasplt

fromsklearn.preprocessingimportStandardScaler

defdbscan_moons():

X,y=make_moons(n_samples=200,noise=0.05,random_state=0)

scaler=StandardScaler()

scaler.fit(X)

X_scaled=scaler.transform(X)

markers={0:"o",1:"^"}colors=['#FF9C34','#4E9A06']labels=dbscan.fit_predict(X_scaled)foriinrange(2):plt.scatter(X_scaled[labels==i,0],X_scaled[labels==i,1],c=colors[i],s=40,marker=markers[i])plt.show()

if__name__=='__main__':

dbscan_moons()7.4.2DBSCAN算法及實現(xiàn)圖7.25在“雙月”數(shù)據(jù)集上DBSCAN的聚類結(jié)果期望最大化算法7.5給定數(shù)據(jù)集X={x1,x2,?,xn}，模糊集S是X的一個子集，它允許X中的每個對象都具有一個0到1之間屬于S的隸屬度。形式地，模糊集S可以用函數(shù)把模糊集概念用在聚類分析上產(chǎn)生了模糊聚類。給定數(shù)據(jù)集X，一個簇C就是一個模糊集S。這種簇稱為模糊簇。一個聚類包含多個模糊簇。一個對象對于所有模糊簇的隸屬度之和為1。傳統(tǒng)的聚類（又稱硬聚類）強制要求每個對象互斥地僅屬于一個簇。而前邊介紹過的模糊C均值（FCM）屬于模糊聚類（又稱軟聚類），允許一個對象屬于多個簇。7.5.1模糊簇從統(tǒng)計學(xué)講，可以假定隱藏的類別是數(shù)據(jù)空間上的一個分布，可以使用概率密度函數(shù)（或分布函數(shù)）精確地表示，這種隱藏的類別被稱為概率簇（probabilisticcluster）。對于一個概率簇C，它的密度函數(shù)f和數(shù)據(jù)空間的點x，f(x)是C的一個實例在x上出現(xiàn)的相對似然。7.5.2基于概率模型的聚類

（7.23）

（7.24）7.5.2基于概率模型的聚類

（7.25）

（7.26）使用參數(shù)概率分布模型，基于概率模型的聚類分析任務(wù)是推導(dǎo)出最大化式（7.26）的參數(shù)集7.5.3使用最大似然估計模型參數(shù)（7.32）（7.33）（7.34）（7.35）7.5.4期望最大化算法容易證明，k均值聚類是模糊聚類的一種特例。k均值算法迭代地執(zhí)行,直到不能再改進聚類。每次迭代包括兩個步驟：期望步（E步）：給定當(dāng)前的簇質(zhì)心，每個對象都被指派到簇質(zhì)心距離該對象最近的簇。這里，期望每個對象都屬于最近的簇。最大化步（M步）：給定簇指派，對于每個簇，算法調(diào)整其質(zhì)心，使得指派到該簇的對象到該新質(zhì)心的距離之和最小化。也就是將指派到一個簇的對象的相似度最大化。7.5.4期望最大化算法可以推廣這個兩步過程來處理模糊聚類和基于概率模型的聚類。通常，期望最大化（Expectation-Maximization,EM）算法是一種框架，它逼近統(tǒng)計模型參數(shù)的最大似然或最大后驗估計。在模糊聚類或基于概率模型聚類的情況下，EM算法從初始參數(shù)集出發(fā)，并且迭代直到不能改善聚類，即直到聚類收斂或改變充分?。ㄐ∮诮o定閾值）。每次迭代也由兩步組成：期望步。根據(jù)當(dāng)前的模糊聚類或概率簇的參數(shù)，把對象指派到簇中。最大化步。發(fā)現(xiàn)新的聚類或參數(shù)，最小化模糊聚類的SSE或基于概率模型的聚類的期望似然。聚類評估7.67.6.1概述用于評估簇的評估度量或指標(biāo)一般分成以下三類。?無監(jiān)督的。這類指標(biāo)是聚類結(jié)構(gòu)的優(yōu)良性度量，不考慮外部信息（例如SSE），可以分成兩類：簇的凝聚性（cohesion）度量確定簇中對象的密切相關(guān)程度，簇的分離性(separation)度量確定簇與簇之間的差異性程度。因為只使用數(shù)據(jù)集內(nèi)部的信息，無監(jiān)督度量通常稱為內(nèi)部指標(biāo)（internalindex)。?監(jiān)督的。這類指標(biāo)度量聚類算法發(fā)現(xiàn)的簇結(jié)構(gòu)與外部結(jié)構(gòu)的匹配程度，例如熵，可以用來度量簇的標(biāo)號與外部提供的類的標(biāo)簽的匹配程度。因為使用了不在數(shù)據(jù)集中出現(xiàn)的外部信息，監(jiān)督度量通常稱為外部指標(biāo)（externalindex)。?相對的。比較不同的聚類或簇。是用于比較的監(jiān)督或無監(jiān)督評估度量。實際上相對度量不是一種單獨的簇評估度量類型，而是度量的一種具體使用。例如，兩個k均值聚類可以使用SSE或熵進行比較。7.6.2無監(jiān)督簇評估：凝聚度和分離度基于原型的凝聚度和分離度基于圖的凝聚度和分離度凝聚度和分離度的總度量基于原型的凝聚度和基于圖的凝聚度之間的聯(lián)系兩種基于原型的分離性度量方法凝聚度和分離度之間的聯(lián)系評估個體簇和數(shù)據(jù)點輪廓系數(shù)7.6.3無監(jiān)督簇評估：鄰近度矩陣通過相關(guān)性度量簇的有效性通過可視化相似度矩陣評價聚類7.6.4層次聚類的無監(jiān)督評