機(jī)器學(xué)習(xí)原理、算法與應(yīng)用

第八章：聚類算法目錄8.1聚類算法概述8.2基于劃分的聚類算法8.3基于模型的聚類算法8.4基于密度的聚類算法8.5基于層次的聚類算法8.6基于圖的聚類算法8.7編程框架8.8實(shí)例分析機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法2本章的重點(diǎn)、難點(diǎn)和需要掌握的內(nèi)容掌握聚類算法的原理。掌握常見的聚類算法，如K-Means算法。了解基于劃分、基于模型、基于密度、基于層次和基于圖的聚類算法。掌握聚類算法的性能評(píng)價(jià)方法。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法3目錄8.1聚類算法概述8.1.1聚類算法分類8.1.2聚類的性能評(píng)價(jià)機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法4聚類算法概述聚類算法是一種無監(jiān)督學(xué)習(xí)算法，即進(jìn)行聚類的樣本不帶有類標(biāo)簽。聚類算法以樣本中數(shù)據(jù)的相似度或距離為依據(jù)，直接從數(shù)據(jù)的內(nèi)在性質(zhì)中學(xué)習(xí)最優(yōu)劃分結(jié)果，確定離散標(biāo)簽類型，把樣本劃分成若干簇，使得同一類的數(shù)據(jù)盡可能在同一簇，不同類的數(shù)據(jù)盡可能分離。通過聚類得到的類或簇，類內(nèi)的樣本具有相近的性質(zhì)，特征差異小，不同類之間的樣本特征差異較大。聚類算法在模式識(shí)別、異常數(shù)據(jù)識(shí)別等領(lǐng)域有著廣泛的應(yīng)用。圖8-1子圖a)顯示了一組隨機(jī)生成的數(shù)據(jù)，使用聚類算法就可以將其根據(jù)分布情況分成四類。子圖b)展示了分類后的效果，不同類的數(shù)據(jù)用不同的顏色標(biāo)示。這里使用的是經(jīng)典的K-Means算法，其思想是距離相近的數(shù)據(jù)點(diǎn)被劃分到一類（參考代碼K-Means.ipynb）。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法5a)隨機(jī)生成的散點(diǎn)數(shù)據(jù)b)分類結(jié)果圖8-1聚類算法分類示意圖聚類算法分類機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法66模型名稱聚類類別參數(shù)使用場(chǎng)景K-Means劃分聚類簇的個(gè)數(shù)簇的數(shù)量較小，通用,均勻的簇大小,平面幾何Gaussianmixtures模型聚類參數(shù)較多大型數(shù)據(jù)集，異常值去除，數(shù)據(jù)簡(jiǎn)化Mean-shift密度聚類帶寬簇的數(shù)量較多，不均勻的簇大小，非平面幾何DBSCAN密度聚類近鄰大小非平面幾何，不均勻的簇大小Birch層次聚類分支因子,閾值,可選全局簇簇的數(shù)量較少，通用,均勻的簇大小,平面幾何Wardhierarchicalclustering層次聚類簇的個(gè)數(shù)或距離閾值簇的數(shù)量較多，可能連接限制Agglomerativeclustering層次聚類簇的個(gè)數(shù)，鏈接類型，距離簇的數(shù)量較多，可能連接限制，非歐氏距離Affinitypropagation圖聚類樣本數(shù)量和阻尼簇的數(shù)量較多，不均勻的簇大小，非平面幾何Spectralclustering圖聚類簇的個(gè)數(shù)簇的數(shù)量較少，均勻的簇大小，非平面幾何）表8-1不同聚類的參數(shù)及使用場(chǎng)景聚類的性能評(píng)價(jià)聚類算法的評(píng)估通常基于相似性度量或距離度量，用于衡量聚類結(jié)果中的對(duì)象之間的相似性或距離。常見的評(píng)估指標(biāo)包括：內(nèi)部指標(biāo)：用于評(píng)估聚類結(jié)果的內(nèi)部一致性和緊密性。例如，簇內(nèi)的平均距離應(yīng)該小，而簇間的距離應(yīng)該大。常見的內(nèi)部評(píng)估指標(biāo)包括輪廓系數(shù)（silhouettecoefficient）、Davies-Bouldin指數(shù)等。外部指標(biāo)：用于與已知標(biāo)簽或真實(shí)類別進(jìn)行比較，評(píng)估聚類結(jié)果的準(zhǔn)確性。但請(qǐng)注意，這些標(biāo)簽并沒有用于聚類過程本身，而僅用于評(píng)估目的。常見的外部評(píng)估指標(biāo)包括蘭德指數(shù)（RandIndex）、互信息（MutualInformation）等。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法7聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法8聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法9聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法10聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法11聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法12聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法13聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法14聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法15聚類的性能評(píng)價(jià)

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法16目錄8.2基于劃分的聚類算法8.2.1K-Means算法8.2.2MiniBatchKMeans算法8.2.3K-Means++算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法17基于劃分的聚類算法定義基于劃分的聚類將數(shù)據(jù)集劃分為互不重疊的簇，通過迭代地優(yōu)化簇內(nèi)的樣本相似性來劃分?jǐn)?shù)據(jù)集?；趧澐值木垲愂蔷垲惙治鲋凶畛Ｓ?、最普遍的方法，簡(jiǎn)單易于使用，在實(shí)際中廣泛運(yùn)用。常見的基于劃分的聚類算法包括K-Means、K-medoids和二分K-Means等。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法18K-Means算法K-Means算法是一種常用的基于距離的聚類算法，它通過將數(shù)據(jù)點(diǎn)劃分為K個(gè)簇來實(shí)現(xiàn)聚類。該算法的核心思想是將數(shù)據(jù)點(diǎn)分配到距離最近的簇中，同時(shí)調(diào)整簇的中心以最小化簇內(nèi)的均方差。在K-Means算法中，距離被用作相似性的度量指標(biāo)，常用的距離計(jì)算方法包括歐式距離、曼哈頓距離和余弦相似度等。選擇適當(dāng)?shù)木嚯x計(jì)算方法應(yīng)考慮數(shù)據(jù)的特征和問題的要求。K-Means算法對(duì)初始簇中心的選擇敏感，并且可能收斂到局部最優(yōu)解。為了克服這些問題，可以采用多次隨機(jī)初始化和迭代運(yùn)行算法，并選擇最優(yōu)的聚類結(jié)果。此外，K-Means算法對(duì)異常值和噪聲敏感，因此在使用前需要進(jìn)行數(shù)據(jù)預(yù)處理和異常值處理。原理從樣本數(shù)據(jù)中隨機(jī)選取K個(gè)質(zhì)心作為初始的聚類中心。計(jì)算每個(gè)樣本點(diǎn)到所有質(zhì)心的距離，樣本離哪個(gè)近就將該樣本分配到哪個(gè)質(zhì)心，得到K個(gè)簇，對(duì)于每個(gè)簇，計(jì)算所有被分到該簇的樣本點(diǎn)的平均距離作為新的質(zhì)心，重復(fù)上述過程直到收斂，即所有簇不再發(fā)生變化。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法19K-Means算法根據(jù)具體示例理解K-Means算法求解過程，如圖8-2將A、B、C、D、E五個(gè)點(diǎn)分為兩類：

從圖8-2中可以看到，A，B，C，D，E是五個(gè)在圖中的點(diǎn)。而灰色的點(diǎn)是中心點(diǎn)，也就是用來找點(diǎn)群的點(diǎn)。因?yàn)橐獙?shù)據(jù)分為2類，所以有兩個(gè)中心點(diǎn)。聚類過程如下：隨機(jī)在圖中取K（這里K=2）個(gè)聚類中心點(diǎn)。針對(duì)數(shù)據(jù)集中每個(gè)樣本計(jì)算它到個(gè)聚類中心的距離，并將其分到距離最小的聚類中心所對(duì)應(yīng)的類中。假如點(diǎn)離中心點(diǎn)最近，那么將被分到點(diǎn)群。（圖中可以看到A，B屬于上面的中心點(diǎn)，C，D，E屬于下面中部的中心點(diǎn)）重新計(jì)算每個(gè)類的聚類中心，（見圖中的第三步）重復(fù)第2、3步，直到聚類中心點(diǎn)不再移動(dòng)（可以看到圖中的第四步上面的種子點(diǎn)聚合了A，B，C，下面的種子點(diǎn)聚合了D，E）。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法20圖8-2K-Means算法步驟示意圖K-Means算法如圖8-3為使用K-Means算法將圖中點(diǎn)分為四類的效果，每一簇用不同顏色區(qū)分,并標(biāo)注出了每一類的聚類中心點(diǎn)。K-Means算法并不保證結(jié)果是全局最優(yōu)的，并且在聚類之前需要指定聚類的個(gè)數(shù)，也就是簇的數(shù)量。該算法不會(huì)從數(shù)據(jù)中找出最優(yōu)的簇?cái)?shù)。如果選擇的簇的數(shù)量不恰當(dāng)，K-Means算法盡管也會(huì)執(zhí)行，但結(jié)果會(huì)不盡人意。圖8-4顯示了在四類數(shù)據(jù)上強(qiáng)行分為7類時(shí)的效果，可以看到并沒有很好地區(qū)分開不同類別。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法21圖8-3K-Means算法分類效果

圖8-4K-Means算法簇?cái)?shù)不匹配時(shí)的分類效果K-Means算法缺點(diǎn)K-Means算法是解決聚類問題的一種經(jīng)典算法，算法簡(jiǎn)單、快速，當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí),它的效果較好，主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)。但K-Means算法只有在簇的平均值被定義的情況下才能使用，且對(duì)有些分類屬性的數(shù)據(jù)不適合，且K-Means要求用戶必須事先給出要生成的簇的數(shù)目，很多情況下K值的估計(jì)是非常困難的。K-Means算法對(duì)初始選取的質(zhì)心點(diǎn)較為敏感，不同的隨機(jī)種子點(diǎn)得到的聚類結(jié)果完全不同，對(duì)結(jié)果影響很大，不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。K-Means采用迭代方法進(jìn)行求解，可能只能得到局部的最優(yōu)解，而無法得到全局的最優(yōu)解。K-Means本質(zhì)上是一種基于歐式距離度量的數(shù)據(jù)劃分方法，由于均值和方差大的維度會(huì)對(duì)數(shù)據(jù)的聚類結(jié)果產(chǎn)生決定性影響，所以在聚類前對(duì)每一個(gè)維度的特征進(jìn)行歸一化和單位統(tǒng)一至關(guān)重要，同時(shí)異常值會(huì)對(duì)均值計(jì)算產(chǎn)生較大影響而導(dǎo)致中心偏移，因此對(duì)于“噪聲”和孤立點(diǎn)數(shù)據(jù)最好能提前過濾。該算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分，當(dāng)簇是密集的、球狀或團(tuán)狀且簇與簇之間區(qū)別明顯時(shí)，聚類效果會(huì)較好。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法22K-Means算法解決策略針對(duì)K-Means算法的缺點(diǎn)，有以下幾種解決策略：1、數(shù)據(jù)預(yù)處理（去除異常點(diǎn)）K-Means的本質(zhì)是基于歐式距離的數(shù)據(jù)劃分算法，均值和方差大的維度將對(duì)數(shù)據(jù)的聚類產(chǎn)生決定性影響。所以未做歸一化處理和統(tǒng)一單位的數(shù)據(jù)是無法直接參與運(yùn)算和比較的。常見的數(shù)據(jù)預(yù)處理方式有：數(shù)據(jù)歸一化，數(shù)據(jù)標(biāo)準(zhǔn)化。此外，離群點(diǎn)或者噪聲數(shù)據(jù)會(huì)對(duì)均值產(chǎn)生較大的影響，導(dǎo)致中心偏移，因此我們還需要對(duì)數(shù)據(jù)進(jìn)行異常點(diǎn)檢測(cè)。2、合理選擇K值K值的變化對(duì)聚類結(jié)果影響較大，這也是K-Means最大的缺點(diǎn)，常見的選取K值的方法有：手肘法、Gapstatistic方法等。3、采用核函數(shù)當(dāng)數(shù)據(jù)不是線性可分的時(shí)候，可以采用核函數(shù)來改進(jìn)K-Means算法。核函數(shù)將數(shù)據(jù)映射到高維特征空間，使得在原始特征空間中線性不可分的數(shù)據(jù)在高維特征空間中變得線性可分，從而提高聚類的效果。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法23MiniBatchKMeans算法K-Means算法缺陷每次迭代需遍歷全部數(shù)據(jù)，數(shù)據(jù)量過大時(shí)因計(jì)算復(fù)雜、迭代次數(shù)多導(dǎo)致收斂慢；對(duì)初始簇中心敏感，隨機(jī)初始化可能使簇中心集中于同一簇，難以收斂到全局最優(yōu)。對(duì)于K-Means算法的效率問題，可以從樣本數(shù)量太大和迭代次數(shù)過多兩個(gè)方面進(jìn)行優(yōu)化。MiniBatchKMeans是K-Means算法的一個(gè)變種，主要解決K-Means算法樣本數(shù)量過多的問題，通過優(yōu)化樣本數(shù)量對(duì)K-Means進(jìn)行優(yōu)化，它使用小批量(mini-batches)減少計(jì)算時(shí)間，每個(gè)批次仍然嘗試優(yōu)化相同的目標(biāo)函數(shù)。小批量是輸入數(shù)據(jù)的子集，在每次訓(xùn)練迭代中隨機(jī)抽樣。這些小批量大大減少了收斂到局部解所需的計(jì)算量。與其他降低K-Means收斂時(shí)間的算法不同，小批量K-Means產(chǎn)生的結(jié)果通常只比標(biāo)準(zhǔn)算法略差。MiniBatchKMeans算法在兩個(gè)步驟之間進(jìn)行迭代。在第一步，從數(shù)據(jù)集中隨機(jī)抽取部分?jǐn)?shù)據(jù)，形成一個(gè)小批量。然后將它們分配到最近的質(zhì)心。在第二步，質(zhì)心被更新。與K-Means不同,該變種算法是基于每個(gè)樣本。對(duì)于小批量中的每個(gè)樣本，通過取樣本的平均值和分配給該質(zhì)心的所有先前樣本來更新分配的質(zhì)心，這具有隨時(shí)間降低質(zhì)心的變化率的效果。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法24MiniBatchKMeans算法算法偽代碼如下：MiniBatchKMeans收斂速度比K-Means快，但是結(jié)果的質(zhì)量會(huì)降低。MiniBatchKMeans優(yōu)化方法是通過減少計(jì)算樣本量來達(dá)到縮短迭代時(shí)長(zhǎng)，另一種方法是降低收斂需要的迭代次數(shù)，從而達(dá)到快速收斂的目的。收斂的速度除了取決于每次迭代的變化率之外，另一個(gè)重要指標(biāo)就是迭代起始的位置，如果初始狀態(tài)離最終的收斂狀態(tài)越近，那么收斂需要的迭代次數(shù)就越少。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法25

K-Means++算法介紹K-Means++算法是在K-Means算法基礎(chǔ)上，針對(duì)迭代次數(shù)，優(yōu)化選擇初始質(zhì)心的方法原理在初始化簇中心時(shí)，從樣本點(diǎn)中逐個(gè)選取簇中心，且離其他簇中心越遠(yuǎn)的樣本越有可能被選為下個(gè)簇中心。算法步驟從數(shù)據(jù)即數(shù)據(jù)集中隨機(jī)（均勻分布）選取一個(gè)樣本點(diǎn)作為第一個(gè)初始聚類中心，計(jì)算每個(gè)樣本與當(dāng)前已有聚類中心之間的最短距離；計(jì)算每個(gè)樣本點(diǎn)被選為下個(gè)聚類中心的概率，選擇最大概率值所對(duì)應(yīng)的樣本點(diǎn)作為下一個(gè)簇中心，重復(fù)上步驟，直到選出最終的聚類中心。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法26K-Means++算法K-Means++算法選取k個(gè)初始聚類中心的偽代碼如下：K-Means++算法初始化的簇中心彼此相距都十分的遠(yuǎn)，從而不可能再發(fā)生初始簇中心在同一個(gè)簇中的情況。當(dāng)然K-Means++本身也具有隨機(jī)性，并不一定每一次隨機(jī)得到的起始點(diǎn)都能有很好的效果，但是通過此策略，可以保證即使出現(xiàn)最壞的情況也不會(huì)太壞。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法27輪盤法：通過隨機(jī)方式選擇簇心，其核心邏輯是離已有簇心越遠(yuǎn)的點(diǎn)被選中概率越大。具體過程為：先計(jì)算所有點(diǎn)到簇心的距離總和，乘以0到1之間的隨機(jī)數(shù)得到縮小后的距離和，再用該值依次減去各點(diǎn)到簇心的距離，由于距離和經(jīng)隨機(jī)縮放且最大距離分布不固定，最終實(shí)現(xiàn)遠(yuǎn)簇心點(diǎn)更易被選中的效果。

基于模型的聚類算法定義基于模型的聚類假設(shè)數(shù)據(jù)集是由一系列的概率分布所決定的，它給每一個(gè)聚簇預(yù)先假定一個(gè)模型，之后在數(shù)據(jù)集中尋找能夠很好滿足這個(gè)模型的簇。模型可以是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)，它由一系列的概率分布決定。常見的模型聚類算法Fish提出的COBWEB、Gennarim提出的CLASSI、Cheeseman和Stutz提出的AutoClass，其中，高斯分布混合模型應(yīng)用最為廣泛。高斯混合模型（GaussianMixedModel，GMM）是通過數(shù)據(jù)點(diǎn)學(xué)習(xí)出一些概率密度函數(shù)，同K-Means將每個(gè)數(shù)據(jù)點(diǎn)劃分到其中某個(gè)聚類簇不同，GMM是給出這些數(shù)據(jù)點(diǎn)被劃分到每個(gè)聚類簇的概率。K-Means無法將兩個(gè)均值相同（聚類中心點(diǎn)相同）的類進(jìn)行聚類，而高斯混合模型可以解決此問題。GMM通過選擇成分最大化后驗(yàn)概率來完成聚類，各數(shù)據(jù)點(diǎn)的后驗(yàn)概率表示屬于各類的可能性，GMM不是判定樣本點(diǎn)完全屬于某個(gè)類，所以稱為軟聚類。GMM在各類尺寸不同、聚類間有相關(guān)關(guān)系的時(shí)候可能比K-Means聚類更合適。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法28基于模型的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法29基于模型的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法30基于模型的聚類算法聚類步驟1)設(shè)置k的個(gè)數(shù)，即初始化高斯混合模型的成分個(gè)數(shù)。（隨機(jī)初始化每個(gè)簇的高斯分布參數(shù)（均值和方差）。也可觀察數(shù)據(jù)給出一個(gè)相對(duì)精確的均值和方差）2)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)屬于每個(gè)高斯模型的概率，即計(jì)算后驗(yàn)概率。（點(diǎn)越靠近高斯分布的中心，則概率越大，即屬于該簇可能性更高）3)計(jì)算參數(shù)使得數(shù)據(jù)點(diǎn)的概率最大化，使用數(shù)據(jù)點(diǎn)概率的加權(quán)來計(jì)算這些新的參數(shù)，權(quán)重就是數(shù)據(jù)點(diǎn)屬于該簇的概率。4)重復(fù)迭代2和3直到收斂。高斯分布模型的本質(zhì)并不是聚類，而是得到一個(gè)能夠生成當(dāng)前樣本形式的分布，GMM使用均值和標(biāo)準(zhǔn)差，簇可以呈現(xiàn)出橢圓形，優(yōu)于K-Means的圓形，GMM是使用概率，故一個(gè)數(shù)據(jù)點(diǎn)可以屬于多個(gè)簇。但GMM容易收斂到局部最優(yōu)解。對(duì)于K-Means，通常是重復(fù)多次然后取最好的結(jié)果，但GMM每次迭代的計(jì)算量比K-Means要大很多，一般是先用K-Means（重復(fù)并取最優(yōu)值），然后將聚類中心點(diǎn)作為GMM的初始值進(jìn)行訓(xùn)練。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法31基于密度的聚類算法定義基于密度的聚類算法假設(shè)聚類結(jié)構(gòu)可以通過樣本分布的緊密程度確定。算法通常從樣本密度的角度來考慮樣本之間的可連接性，并基于可連接樣本不斷擴(kuò)展聚類簇以獲得最終的聚類結(jié)果。所以算法的主要目標(biāo)是尋找被低密度區(qū)域分離的高密度區(qū)域。與基于距離的聚類算法不同的是，基于距離的聚類算法的聚類結(jié)果是球狀的簇，而基于密度的聚類算法可以發(fā)現(xiàn)任意形狀的聚類，這對(duì)于帶有噪音點(diǎn)的數(shù)據(jù)起著重要的作用。典型的基于密度的聚類算法包括DBSCAN，OPTICS，MeanShift等，本節(jié)以DBSCAN為例介紹基于密度的聚類。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法32基于密度的聚類算法DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)是一種基于密度的聚類算法，所謂密度，即樣本的緊密程度對(duì)應(yīng)其類別，屬于同一個(gè)簇的樣本是緊密相連的。聚類的時(shí)候不需要預(yù)先指定簇的個(gè)數(shù)。最終的簇的個(gè)數(shù)不定?；诰嚯x的算法的聚類結(jié)果是球狀的簇，當(dāng)數(shù)據(jù)集中的聚類結(jié)果是非球狀結(jié)構(gòu)時(shí)，基于距離的聚類算法的聚類效果并不好。與基于距離的聚類算法不同的是，基于密度的聚類算法可以發(fā)現(xiàn)任意形狀的聚類。在基于密度的聚類算法中，通過在數(shù)據(jù)集中尋找被低密度區(qū)域分離的高密度區(qū)域，將分離出的高密度區(qū)域作為一個(gè)獨(dú)立的類別。傳統(tǒng)的密度定義中，需要事先給定半徑，數(shù)據(jù)集中點(diǎn)的密度，要通過落入以點(diǎn)為中心以為半徑的圓內(nèi)點(diǎn)的計(jì)數(shù)（包括點(diǎn)本身）來估計(jì)。很顯然，密度是依賴于半徑的。如圖8-5所示，點(diǎn)a在半徑為r時(shí)的密度。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法33圖8-5點(diǎn)a在半徑為r時(shí)的密度基于密度的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法34基于密度的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法35圖8-6核心點(diǎn)、邊界點(diǎn)、噪聲點(diǎn)示意圖噪聲點(diǎn)是不會(huì)被聚類納入的點(diǎn)，邊界點(diǎn)與核心點(diǎn)組成聚類的“簇”?；诿芏鹊木垲愃惴ㄔ卩徲蚝蚆inPts的基礎(chǔ)上，通過以下三個(gè)概念來描述樣本的緊密相連。1、密度直達(dá)如圖8-7,樣本X在核心樣本Y的鄰域內(nèi)，則稱Y到X是密度直達(dá)的，這個(gè)關(guān)系是單向的，反向不一定成立。2、密度可達(dá)如圖8-8核心樣本Y到核心樣本P3是密度直達(dá)的，核心樣本P3到核心樣本P2是密度直達(dá)的，核心樣本P2到樣本X是密度直達(dá)的，像這種通過P3和P2的中轉(zhuǎn)，在樣本Y到樣本X建立的關(guān)系叫做密度可達(dá)。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法36圖8-7密度直達(dá)圖8-8密度可達(dá)基于密度的聚類算法3、密度相連如圖8-9，核心樣本O到樣本Y是密度可達(dá)的，同時(shí)核心樣本O到樣本X是密度可達(dá)的，這樣的關(guān)系，我們可以說樣本X和樣本Y是密度相連的。對(duì)于一系列密度可達(dá)的點(diǎn)而言，其鄰域范圍內(nèi)的點(diǎn)都是密度相連的，核心點(diǎn)能夠連通（密度可達(dá)），它們構(gòu)成的以為半徑的圓形鄰域相互連接或重疊，這些連通的核心點(diǎn)及其所處的鄰域內(nèi)的全部點(diǎn)構(gòu)成一個(gè)簇。如圖8-10所示，紅色點(diǎn)為核心點(diǎn),綠色箭頭連接起來的則是密度可達(dá)的樣本集合，在這些樣本點(diǎn)的鄰域內(nèi)的點(diǎn)構(gòu)成了一個(gè)密度相連的樣本集合，這些樣本就屬于同一個(gè)簇。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法37圖8-9密度相連圖8-10簇的生成示意圖基于密度的聚類算法DBSCAN的聚類過程根據(jù)核心點(diǎn)來推導(dǎo)出最大密度相連的樣本集合，首先隨機(jī)尋找一個(gè)核心樣本點(diǎn)，按照MinPts和eps來推導(dǎo)其密度相連的點(diǎn)，賦予一個(gè)簇編號(hào)，然后再選擇一個(gè)沒有賦予類別的核心樣本點(diǎn)，開始推導(dǎo)其密度相連的樣本結(jié)合，一直迭代到所有的核心樣本點(diǎn)都有對(duì)應(yīng)的類別為止。算法過程1)將所有點(diǎn)標(biāo)記為核心點(diǎn)、邊界點(diǎn)或噪聲點(diǎn)；2)刪除所有噪聲點(diǎn)；3)為距離在eps之內(nèi)的所有核心點(diǎn)之間賦予一條邊；4)每組連通的核心點(diǎn)形成一個(gè)新簇；5）將每個(gè)邊界點(diǎn)指派到一個(gè)與之關(guān)聯(lián)的核心點(diǎn)的簇中；6）將結(jié)果輸出。從算法的流程中可以看出算法的兩個(gè)參數(shù)eps和min_samples區(qū)分了高密度區(qū)域和低密度區(qū)域。較高的min_samples或者較低的eps表示形成聚類需要較高的密度。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法38基于密度的聚類算法DBSCAN算法將聚類視為被低密度區(qū)域分隔的高密度區(qū)域。因此，DBSCAN發(fā)現(xiàn)的聚類可以是任何形狀的，而K-Means則假設(shè)所有的類都是凸形狀的。如圖8-11展示了在非凸數(shù)據(jù)集分別使用K-Means算法和DBSCAN算法分類的效果。DBSCAN算法基于密度定義，具有可以對(duì)抗噪聲，能處理任意形狀和大小的簇的優(yōu)點(diǎn)，但當(dāng)簇的密度變化太大時(shí)候，聚類得到的結(jié)果會(huì)不理想，且對(duì)于高維問題，密度定義較為麻煩。同時(shí)DBSCAN算法對(duì)輸入?yún)?shù)敏感．確定參數(shù)

、MinPts困難，若參數(shù)選取不當(dāng)，將造成聚類質(zhì)量下降。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法39圖8-11DBSCAN分類算法示意圖基于層次的聚類算法定義基于層次的聚類算法(Hierarchicalclustering)試圖在不同層次上對(duì)數(shù)據(jù)集進(jìn)行劃分，從而形成樹狀的聚類結(jié)構(gòu)。這種類別的算法通過不斷的合并或者分割內(nèi)置聚類來構(gòu)建最終聚類。聚類的層次可以被表示成樹（或者樹形圖）。樹根是擁有所有樣本的唯一聚類，葉子是僅有一個(gè)樣本的聚類。常用的算法有AgglomerativeClustering，Birch等。分類層次聚類可以分為兩大類，自頂向下的分裂聚類和自頂而上的合并聚類。分裂聚類是將所有的對(duì)象看成一個(gè)聚類，然后將其不斷分解直至滿足終止條件。后者與前者相反，它先將每個(gè)對(duì)象各自作為一個(gè)原子聚類，然后對(duì)這些原子聚類逐層進(jìn)行聚類，直至滿足終止條件。層次聚類算法使用數(shù)據(jù)的聯(lián)結(jié)規(guī)則，對(duì)數(shù)據(jù)集合進(jìn)行層次的聚類。AgglomerativeClustering算法是自底向上方法，Brich是自頂向下方法。本節(jié)以Birch聚類算法為例，詳細(xì)講解基于層次的聚類。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法40基于層次的聚類算法Birch算法Birch算法全稱為利用層次方法的平衡迭代規(guī)約和聚類(BalancedIterativeReducingandClusteringUsingHierarchie)。BIRCH算法利用了一個(gè)樹結(jié)構(gòu)來幫助快速聚類，這個(gè)樹結(jié)構(gòu)類似于平衡樹，一般將它稱之為聚類特征樹(ClusteringFeatureTree，簡(jiǎn)稱CFTree)。這顆樹的每一個(gè)節(jié)點(diǎn)是由若干個(gè)聚類特征(ClusteringFeature，簡(jiǎn)稱CF)組成。CFTree結(jié)構(gòu)如圖8-12所示。CF定義在聚類特征樹中，一個(gè)聚類特征CF是這樣定義的：每一個(gè)CF是一個(gè)三元組，可以用（N，LS，SS）表示。其中N代表了這個(gè)CF中擁有的樣本點(diǎn)的數(shù)量，LS代表了這個(gè)CF中擁有的樣本點(diǎn)各特征維度的和向量，SS代表了這個(gè)CF中擁有的樣本點(diǎn)各特征維度的平方和。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法41圖8-12CFTree結(jié)構(gòu)圖基于層次的聚類算法CFTree的三個(gè)參數(shù)B：每個(gè)內(nèi)部節(jié)點(diǎn)的最大CF數(shù)。L：每個(gè)葉子節(jié)點(diǎn)的最大CF數(shù)。T：葉節(jié)點(diǎn)每個(gè)CF的最大樣本半徑閾值。Brich算法的主要內(nèi)容是生成特征聚類樹，方法是逐漸將元素放在樹中合適的位置，根據(jù)閾值T和分支因子（B、L）值確定位置，在某些時(shí)候需要新增節(jié)點(diǎn)。算法流程一個(gè)新的樣本作為一個(gè)CF-Node被插入到CF-Tree的根節(jié)點(diǎn)。然后將其合并到根節(jié)點(diǎn)的子簇中去，使得合并后子簇?fù)碛凶钚〉陌霃剑哟氐倪x取受閾值和分支因子的約束。如果子簇也擁有孩子節(jié)點(diǎn)，則重復(fù)執(zhí)行這個(gè)步驟直到到達(dá)葉子結(jié)點(diǎn)。在葉子結(jié)點(diǎn)中找到最近的子簇以后，遞歸的更新這個(gè)子簇及其父簇的屬性。如果合并了新樣本和最近的子簇獲得的子簇半徑大于閾值的平方(squareofthethreshold)，并且子簇的數(shù)量大于分支因子，則將為這個(gè)樣本分配一個(gè)臨時(shí)空間。最遠(yuǎn)的兩個(gè)子簇被選取，剩下的子簇按照之間的距離分為兩組作為被選取的兩個(gè)子簇的孩子節(jié)點(diǎn)。如果拆分的節(jié)點(diǎn)有一個(gè)父級(jí)子簇(parentsubcluster)，并且有足夠容納一個(gè)新的子簇的空間，那么父簇拆分成兩個(gè)。如果沒有空間容納一個(gè)新的簇，那么這個(gè)節(jié)點(diǎn)將被再次拆分，依次向上檢查父節(jié)點(diǎn)是否需要分裂，如果需要,則按葉子節(jié)點(diǎn)方式相同分裂。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法42基于層次的聚類算法CFTree生成過程詳解：首先對(duì)CFTree的參數(shù)值進(jìn)行定義，開始時(shí)，CFTree是空的，沒有任何樣本，從訓(xùn)練集讀入第一個(gè)樣本點(diǎn)，將它放入一個(gè)新的CF三元組A，這個(gè)三元組的N=1，將這個(gè)新的CF放入根節(jié)點(diǎn)，此時(shí)的CFTree如圖8-14。繼續(xù)讀入第二個(gè)樣本點(diǎn)，第二個(gè)樣本點(diǎn)和第一個(gè)樣本點(diǎn)A，在半徑為T的超球體范圍內(nèi)，也就是說，他們屬于一個(gè)CF，將第二個(gè)點(diǎn)也加入A,此時(shí)需要更新A的三元組的值。此時(shí)A的三元組中N=2。此時(shí)的CFTree如圖8-15。此時(shí)讀入第三個(gè)節(jié)點(diǎn)，結(jié)果發(fā)現(xiàn)第三個(gè)節(jié)點(diǎn)不能融入剛才前面的節(jié)點(diǎn)形成的超球體內(nèi)，也就是說，需要一個(gè)新的CF三元組B，來容納這個(gè)新的值。此時(shí)根節(jié)點(diǎn)有兩個(gè)CF三元組A和B，此時(shí)的CFTree如圖8-16。第四個(gè)樣本點(diǎn)和B在半徑小于T的超球體，更新后的CFTree如圖8-17。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法43圖8-14新CF三元組A圖8-15插入第二個(gè)樣本點(diǎn)圖8-16新CF組B圖8-17插入第四個(gè)樣本點(diǎn)基于層次的聚類算法假設(shè)現(xiàn)有的CFTree如下圖8-18，葉子節(jié)點(diǎn)LN1有三個(gè)CF，LN2和LN3各有兩個(gè)CF。葉子節(jié)點(diǎn)的最大CF數(shù)L=3。此時(shí)讀入新的樣本點(diǎn)，發(fā)現(xiàn)其離LN1節(jié)點(diǎn)最近，因此開始判斷它是否在sc1,sc2,sc3這3個(gè)CF對(duì)應(yīng)的超球體之內(nèi)，但是很不幸，它不在，因此它需要建立一個(gè)新的CF，即sc8來容納它。但是設(shè)定L=3，即LN1的CF個(gè)數(shù)已經(jīng)達(dá)到最大值，不能再創(chuàng)建新的CF，此時(shí)需要將LN1葉子節(jié)點(diǎn)一分為二。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法44圖8-18現(xiàn)有CFTree結(jié)構(gòu)基于層次的聚類算法從LN1里所有CF元組中，找到兩個(gè)最遠(yuǎn)的CF做這兩個(gè)新葉子節(jié)點(diǎn)的種子CF，將LN1節(jié)點(diǎn)里所有CFsc1,sc2,sc3，以及新樣本點(diǎn)的新元組sc8劃分到兩個(gè)新的葉子節(jié)點(diǎn)上。將LN1節(jié)點(diǎn)劃分后的CFTree如下圖8-19。如果內(nèi)部節(jié)點(diǎn)的最大CF數(shù)B=3，則此時(shí)葉子節(jié)點(diǎn)一分為二會(huì)導(dǎo)致根節(jié)點(diǎn)的最大CF數(shù)超了，也就是說，根節(jié)點(diǎn)現(xiàn)在也要分裂，分裂的方法和葉子節(jié)點(diǎn)分裂一樣，分裂后的CFTree如下圖8-20。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法45圖8-19LN1節(jié)點(diǎn)劃分后CFTree結(jié)構(gòu)圖8-20根節(jié)點(diǎn)分裂后CFTree結(jié)構(gòu)基于層次的聚類算法BIRCH算法不用輸入類別數(shù)K值，這點(diǎn)和K-Means，MiniBatchK-Means不同。如果不輸入K值，則最后的CF元組的組數(shù)即為最終的K，否則會(huì)按照輸入的K值對(duì)CF元組按距離大小進(jìn)行合并。一般來說，BIRCH算法適用于樣本量較大的情況，這點(diǎn)和MiniBatchK-Means類似，但是BIRCH適用于類別數(shù)比較大的情況，而MiniBatchK-Means一般用于類別數(shù)適中或者較少的時(shí)候。BIRCH除了聚類還可以額外做一些異常點(diǎn)檢測(cè)和數(shù)據(jù)初步按類別規(guī)約的預(yù)處理。但是如果數(shù)據(jù)特征的維度非常大，比如大于20，則BIRCH不太適合，此時(shí)MiniBatchK-Means的表現(xiàn)較好。對(duì)于調(diào)參，BIRCH比K-Means，MiniBatchK-Means復(fù)雜，因?yàn)樗枰獙?duì)CFTree的幾個(gè)關(guān)鍵的參數(shù)進(jìn)行調(diào)參，這幾個(gè)參數(shù)對(duì)CFTree的最終形式影響很大。BIRCH算法節(jié)約內(nèi)存，所有樣本都在磁盤上，CFTree僅僅存了CF節(jié)點(diǎn)和對(duì)應(yīng)的指針。聚類速度快，只需要一遍掃描訓(xùn)練集就可以建立CFTree，CFTree的增刪改都很快?？梢宰R(shí)別噪音點(diǎn)，還可以對(duì)數(shù)據(jù)集進(jìn)行初步分類的預(yù)處理。由于CFTree對(duì)每個(gè)節(jié)點(diǎn)的CF個(gè)數(shù)有限制，BIRCH算法導(dǎo)致聚類的結(jié)果可能和真實(shí)的類別分布不同。BIRCH算法對(duì)高維特征的數(shù)據(jù)聚類效果不好，如果數(shù)據(jù)集的分布簇不是非凸的，則BIRCH算法聚類效果不佳。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法46基于圖的聚類算法定義基于圖的聚類算法是一種基于圖論的算法，這里的圖不是指圖片，而是指由頂點(diǎn)和邊構(gòu)成的圖，算法通過對(duì)頂點(diǎn)的不斷劃分完成聚類。譜聚類（Spectralclustering）和AP聚類（AffinityPropagation）是常見的基于圖的兩種聚類算法。本節(jié)以AP聚類為例介紹基于圖的聚類算法。AP聚類定義AP聚類又稱為近鄰傳播算法或者親和力傳播算法，該算法無需事先定義類數(shù)，而是在迭代過程中不斷搜索合適的聚類中心，自動(dòng)從數(shù)據(jù)點(diǎn)間識(shí)別類中心的位置及個(gè)數(shù)，使所有的數(shù)據(jù)點(diǎn)到最近的類代表點(diǎn)的相似度之和最大。算法開始時(shí)把所有的數(shù)據(jù)點(diǎn)均視作類中心，通過數(shù)據(jù)點(diǎn)間的“信息傳遞”來實(shí)現(xiàn)聚類過程。與傳統(tǒng)的K-均值算法對(duì)初始類中心選擇的敏感性相比，AP算法是一種確定性的聚類算法，多次獨(dú)立運(yùn)行的聚類結(jié)果都十分穩(wěn)定。AP算法是在數(shù)據(jù)點(diǎn)的相似度矩陣上進(jìn)行聚類的，聚類的目標(biāo)是使數(shù)據(jù)點(diǎn)與其類代表點(diǎn)之間的距離達(dá)到最小化。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法47基于圖的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法48基于圖的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法49基于圖的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法50圖8-21鄰接矩陣表示基于圖的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法51圖8-22吸引度傳遞基于圖的聚類算法

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法52圖8-23歸屬度傳遞53機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法基于圖的聚類算法

54機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法基于圖的聚類算法

目錄55機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法8.7編程框架8.7.1KMeans類8.7.2高斯混合聚類8.7.3DBSCAN類8.7.4Birch類8.7.5AP類8.7.6sklearn中的函數(shù)8.7.7性能評(píng)價(jià)指標(biāo)56機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法編程框架在機(jī)器學(xué)習(xí)庫sklearn中，模塊sklearn.cluster實(shí)現(xiàn)了十個(gè)聚類相關(guān)的機(jī)器學(xué)習(xí)算法。每個(gè)聚類算法(clusteringalgorithm)都提供了面向?qū)ο蠛兔嫦蜻^程兩種方式:一個(gè)是類（面向?qū)ο螅?它實(shí)現(xiàn)了fit方法來學(xué)習(xí)訓(xùn)練數(shù)據(jù)的簇，另一個(gè)為函數(shù)（面向過程），當(dāng)給定訓(xùn)練數(shù)據(jù)時(shí)，返回與不同簇對(duì)應(yīng)的整數(shù)標(biāo)簽數(shù)組。對(duì)于類來說，訓(xùn)練數(shù)據(jù)上的標(biāo)簽可以在labels_屬性中找到。如表8-2所示，sklearn.cluster模塊中包含以下聚類算法類：類名聚類算法cluster.AffinityPropagation(*[,damping,...])AffinityPropagation（AP）聚類cluster.AgglomerativeClustering([...])AgglomerativeClustering聚類cluster.Birch(*[,threshold,...])Birch聚類cluster.DBSCAN([eps,min_samples,metric,...])DBSCAN聚類cluster.FeatureAgglomeration([n_clusters,...])FeatureAgglomeration聚類cluster.KMeans([n_clusters,init,n_init,...])Kmeans聚類cluster.MiniBatchKMeans([n_clusters,init,...])MiniBatchKMeans聚類cluster.MeanShift(*[,bandwidth,seeds,...])MeanShift聚類cluster.OPTICS(*[,min_samples,max_eps,...])OPTICS聚類cluster.SpectralClustering([n_clusters,...])譜聚類（Spectralclustering）cluster.SpectralBiclustering([n_clusters,...])光譜雙聚類(SpectralBiclustering)cluster.SpectralCoclustering([n_clusters,...])光譜聯(lián)合聚類(SpectralCo-Clustering)表8-2sklearn.cluster模塊中的聚類算法類57機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法KMeans類sklearn.cluster中的KMeans類實(shí)現(xiàn)了K-Means算法。K-Means聚類需要提前確定聚類簇個(gè)數(shù)，k值的變化對(duì)結(jié)果影響較大。對(duì)應(yīng)的參數(shù)為：1)n_clusters:即k值，聚類后希望得到的聚類簇個(gè)數(shù)。默認(rèn)為8個(gè)聚類簇2）max_iter：最大迭代次數(shù)，指定最大的迭代次數(shù)讓算法及時(shí)退出循環(huán)，防止數(shù)據(jù)集難以收斂陷入死循環(huán)。在使用時(shí)可以省略該參數(shù)。3）n_init：用不同的初始化質(zhì)心運(yùn)行算法的次數(shù)。由于K-Means是結(jié)果受初始值影響的局部最優(yōu)的迭代算法，因此需要多次運(yùn)行選擇一個(gè)較好的聚類效果，默認(rèn)值為10。4）init：初始值選擇的方式，有完全隨機(jī)選擇'random',優(yōu)化過的'K-Means++'或者自己指定初始化的k個(gè)質(zhì)心三種方式。一般建議使用默認(rèn)的'K-Means++'。5）algorithm：所使用的K-Means算法，有“auto”,“full”or“elkan”三種選擇。"full"為傳統(tǒng)的K-Means算法，“elkan”為elkanK-Means算法。目前為止默認(rèn)的"auto"選擇的是“elkan”。K-Means類中包含方法如下：class

sklearn.cluster.KMeans(n_clusters=8,

*,

init='K-Means++',

n_init=10,

max_iter=300,

tol=0.0001,

verbose=0,

random_state=None,

copy_x=True,

algorithm='auto')KMeans類K-Means類中包含方法如下：機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法58方法名含義fit(X[,y,sample_weight])根據(jù)輸入X進(jìn)行K-Means聚類fit_predict(X[,y,sample_weight])計(jì)算聚類中心并返回每個(gè)樣本所屬聚類標(biāo)簽fit_transform(X[,y,sample_weight])計(jì)算聚類中心并將X轉(zhuǎn)換到聚類距離空間get_feature_names_out([input_features])獲取轉(zhuǎn)換的輸出特性名稱get_params([deep])獲取此估計(jì)量的參數(shù)predict(X[,sample_weight])預(yù)測(cè)X中每個(gè)樣本所屬的最近簇score(X[,y,sample_weight])與k均值目標(biāo)中的X值相反set_output(*[,transform])設(shè)置輸出容器KMeans類fix：計(jì)算k均值聚類1）X：聚類訓(xùn)練數(shù)據(jù)集2）y：該參數(shù)未使用，在此處顯示以保持API一致性。3）sample_weight：X中每個(gè)觀測(cè)值的權(quán)重。如果沒有，所有觀測(cè)值將都被賦予相同的權(quán)重。fit_predict:計(jì)算聚類中心并計(jì)算每個(gè)樣本的聚類標(biāo)簽1）X：進(jìn)行轉(zhuǎn)換的數(shù)據(jù)2）y：該參數(shù)未使用，在此處顯示以保持API一致性。3）X中每個(gè)觀測(cè)值的權(quán)重。如果沒有，所有觀測(cè)值將都被賦予相同的權(quán)重。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法59fit(X,

y=None,

sample_weight=None)fit_predict(X,y=None,sample_weight=None)60機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法KMeans類應(yīng)用舉例（完整實(shí)例請(qǐng)參考Kmeans.ipynb）：得到結(jié)果如圖8-24所示：#設(shè)定訓(xùn)練的簇中心數(shù)量為4，初始化KMeans對(duì)象并完成訓(xùn)練，用labels_4centers存儲(chǔ)樣本標(biāo)簽kmeans_4centers=KMeans(n_clusters=4).fit(X)print("\n簇?cái)?shù)量","4",",訓(xùn)練完成")print("簇中心\n",kmeans_4centers.cluster_centers_)labels_4centers=kmeans_4centers.labels_#設(shè)定為4個(gè)簇時(shí)，輸出聚類效果plt.scatter(X[:,0],X[:,1],c=labels_4centers,marker='+')圖8-24使用K-Means算法聚類結(jié)果61機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法高斯聚類高斯混合聚類模型并不在sklearn.cluster中定義，而是在sklearn.mixture中單獨(dú)定義。高斯混合聚類中的主要參數(shù)有：1)n_components：int,default=1，混合成分?jǐn)?shù)，即聚類簇的數(shù)目2)max_iter：要執(zhí)行的EM迭代次數(shù)，即規(guī)定的迭代次數(shù)，此參數(shù)可以選填。3)covariance_type：描述要使用的協(xié)方差參數(shù)類型的字符串，有{‘full’,‘tied’,‘diag’,‘spherical’}可供選擇,default=’full’。4)‘full’：每個(gè)分量都有自己的通用協(xié)方差矩陣。5)‘tied’：所有分量共享相同的通用協(xié)方差矩陣。6)‘diag’：每個(gè)分量都有自己的對(duì)角協(xié)方差矩陣。7)‘spherical’：每個(gè)組件都有自己的單一方差。classsklearn.mixture.GaussianMixture(n_components=1,*,covariance_type='full',tol=0.001,reg_covar=1e-06,max_iter=100,n_init=1,init_params='kmeans',weights_init=None,means_init=None,precisions_init=None,random_state=None,warm_start=False,verbose=0,verbose_interval=10)62機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法高斯聚類高斯模型聚類所包含的方法如表8-4所示：該類同樣具有該類同樣擁有fit和fit_pridect函數(shù)，使用方法同KMeans相同方法名含義aic(X)計(jì)算當(dāng)前模型在輸入X上的ACI(Akaikeinformationcriterion，一種衡量統(tǒng)計(jì)模型質(zhì)量的方法)bic(X)計(jì)算當(dāng)前模型在輸入X上的BIC(Bayesianinformationcriterion，一種用于評(píng)估統(tǒng)計(jì)模型質(zhì)量的常用指標(biāo))fit(X[,y])使用EM（期望最大化）算法估計(jì)模型參數(shù)fit_predict(X[,y])使用輸入X來估計(jì)模型參數(shù)并預(yù)測(cè)X的標(biāo)簽predict(X)使用訓(xùn)練好的模型預(yù)測(cè)X中的數(shù)據(jù)樣本的標(biāo)簽score(X[,y])計(jì)算給定數(shù)據(jù)X的每個(gè)樣本平均對(duì)數(shù)似然score_samples(X)計(jì)算每個(gè)樣本的對(duì)數(shù)似然表8-4高斯模型聚類方法63機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法高斯聚類以下對(duì)高斯混合模型聚類使用方法進(jìn)行舉例說明：該實(shí)例對(duì)隨機(jī)生成的橢圓形數(shù)據(jù)使用高斯混合聚類，完整實(shí)例請(qǐng)參考GMM.ipynb。聚類結(jié)果如右圖8-25所示：圖8-25

高斯混合聚類效果#用橢圓形來擬合數(shù)據(jù)rng=np.random.RandomState(13)X_stretched=np.dot(X,rng.randn(2,2))#設(shè)定訓(xùn)練的簇中心數(shù)量為4gmm=GMM(n_components=4,covariance_type='full',random_state=42)plot_gmm(gmm,X_stretched)DBSCAN類sklearn.cluster中的DBSCAN類實(shí)現(xiàn)了DBSCAN算法。DBSCAN重要的參數(shù)包括DBSCAN算法本身的參數(shù)和定義距離的參數(shù)。min_samples：樣本點(diǎn)要成為核心點(diǎn)需要有多少樣本與之距離小于eps。默認(rèn)值是5。通常和eps一起調(diào)參。在eps一定的情況下，min_samples過大，則核心對(duì)象會(huì)過少，此時(shí)簇內(nèi)部分本來是一類的樣本可能會(huì)被標(biāo)為噪音點(diǎn)，類別數(shù)也會(huì)變多。metric：最近鄰距離度量參數(shù)，默認(rèn)為歐式距離，一般來說使用歐式距離即可滿足要求?？梢允褂玫木嚯x度量方式及參數(shù)包括:機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法64class

sklearn.cluster.DBSCAN(eps=0.5,

*,

min_samples=5,

metric='euclidean',

metric_params=None,

algorithm='auto',

leaf_size=30,

p=None,

n_jobs=None)DBSCAN類

機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法6566機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法DBSCAN類DBSCAN類中包含方法如表8-5所示：該類同樣擁有fit和fit_pridect函數(shù)，使用方法同KMeans相同。方法名含義fit(X[,y,sample_weight])根據(jù)特征或距離矩陣執(zhí)行DBSCAN聚類fit_predict(X[,y,sample_weight])根據(jù)數(shù)據(jù)或距離矩陣計(jì)算聚類并預(yù)測(cè)標(biāo)簽get_params([deep])獲取參數(shù)set_params(**params)設(shè)置參數(shù)表8-5DBSCAN類中包含的方法DBSCAN類應(yīng)用舉例：以下代碼對(duì)隨機(jī)生成的月牙形數(shù)據(jù)使用DBSCAN算法進(jìn)行聚類，完整實(shí)例請(qǐng)參考DBSCAN.ipynb。聚類結(jié)果如圖8-26所示。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法67圖8-26DBSCAN聚類結(jié)果#設(shè)定鄰域半徑和鄰域樣本數(shù)量閾值，初始化DBSCAN對(duì)象并完成訓(xùn)練，用labels_dbscan存儲(chǔ)樣本標(biāo)簽dbscan_ncenters=DBSCAN(eps=0.1,min_samples=10).fit(X)print("\nDBSCAN訓(xùn)練完成\n")labels_dbscan=dbscan_ncenters.labels_#輸出聚類效果plt.scatter(X[:,0],X[:,1],c=labels_dbscan,marker='+',label='DBSCANeps=0.1,min_samples=10')plt.xlabel('x')plt.ylabel('y')plt.legend(loc=0)plt.show()Birch類1)

threshold:葉節(jié)點(diǎn)每個(gè)CF的最大樣本半徑閾值T，決定了每個(gè)CF里所有樣本形成的超球體的半徑閾值。threshold越小，則CFTree的建立階段的規(guī)模會(huì)越大，即BIRCH算法第一階段所花的時(shí)間和內(nèi)存會(huì)越多。默認(rèn)值為0.5.，如果樣本的方差較大，則一般需要增大這個(gè)默認(rèn)值。2)

branching_factor：CFTree內(nèi)部節(jié)點(diǎn)的最大CF數(shù)B，以及葉子節(jié)點(diǎn)的最大CF數(shù)L。branching_factor決定了CFTree里所有節(jié)點(diǎn)的最大CF數(shù)。默認(rèn)為50。3）n_clusters：K值，即聚類后得到的聚類簇個(gè)數(shù)，在BIRCH算法中為可選參數(shù)，如果類別數(shù)非常多，則一般輸入None。默認(rèn)值為3。4）compute_labels：布爾值，表示是否標(biāo)示類別輸出，默認(rèn)值為True。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法68class

sklearn.cluster.Birch(*,

threshold=0.5,

branching_factor=50,

n_clusters=3,

compute_labels=True,

copy=True)69機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法Birch類Brich類中包含方法如表8-6所示：該類同樣擁有fit和fit_pridect函數(shù)，使用方法同KMeans相同。方法名含義fit(X[,y])為輸入數(shù)據(jù)構(gòu)建CF樹fit_predict(X[,y])對(duì)X進(jìn)行聚類并返回簇標(biāo)簽fit_transform(X[,y])擬合數(shù)據(jù)，然后對(duì)其進(jìn)行轉(zhuǎn)換get_feature_names_out([input_features])獲取轉(zhuǎn)換的輸出特性名稱get_params([deep])獲取參數(shù)。partial_fit([X,y])在線學(xué)習(xí)predict(X)使用亞簇的質(zhì)心來預(yù)測(cè)數(shù)據(jù)transform(X)將X轉(zhuǎn)換為子簇的質(zhì)心維度表8-6Brich類中包含的方法70機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法Birch類以下實(shí)例使用sklearn中的Brich類對(duì)隨機(jī)生成的數(shù)據(jù)進(jìn)行聚類，完整實(shí)例請(qǐng)參考Brich.ipynb。聚類結(jié)果展示如圖8-27所示：圖8-27Brich算法聚類結(jié)果#設(shè)定訓(xùn)練的簇中心數(shù)量為4，初始化Birch對(duì)象并完成訓(xùn)練，用y_pred存儲(chǔ)樣本標(biāo)簽model=Birch(n_clusters=4)y_pred=model.fit_predict(X)plt.scatter(X[:,0],X[:,1],c=y_pred)plt.show()AP類1）damping：阻尼系數(shù)(0.5到1之間)，默認(rèn)值為0.5，用于避免數(shù)值振蕩。2）max_iter：最大迭代次數(shù)，默認(rèn)值為200。3）copy：是否保存一個(gè)輸入數(shù)據(jù)的副本，默認(rèn)值為True。4）preference：參考度，每個(gè)點(diǎn)的參考度越大就越有可能被選擇作為樣本。樣本數(shù)和聚類的數(shù)目受輸入?yún)⒖级戎档挠绊?。如果參考度不是作為參?shù)傳遞，則將其值設(shè)置為輸入相似性的中位數(shù)。5）affinity：用于計(jì)算數(shù)據(jù)點(diǎn)之間親和度的度量方式。目前支持precomputed和euclidean兩種，默認(rèn)選擇為euclidean。表示使用點(diǎn)之間的負(fù)平方歐幾里德距離。機(jī)器學(xué)習(xí)原理、算法與應(yīng)用-聚類算法71方法名含義fit(X[,y])根據(jù)特征或關(guān)聯(lián)矩陣擬合聚類fit_predict(X[,y])基于特征/相似度矩陣的聚類；返回簇標(biāo)簽get_params([deep])獲取參數(shù)predict(X)預(yù)測(cè)X中每個(gè)樣本所屬的