圖聚類演算法

① 聚類演算法--DBSCAN

       DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有雜訊的基於密度的聚類方法)是一種很典型的密度聚類演算法，和K-Means，BIRCH這些一般只適用於凸樣本集的聚類相比，DBSCAN既可以適用於凸樣本集，也可以適用於非凸樣本集。 基於密度的帶有雜訊的空間聚類，可用於異常值監測，通俗來說就是基於密度的聚類演算法 ！

        聚類就是對大量未知標注的數據集，按數據的內在相似性將數據集劃分為多個類別，使類別內的數據相似度較大而類別間的數據相似度較小。聚類演算法是無監督的演算法。

DBSCAN演算法的目的： 是基於密度尋找被低密度區域分離的高密度樣本分為三類： 

稠密區域內部的點（核心點）： 在半徑Eps內含有超過MinPts數目的點 

稠密區域邊緣上的點（邊緣點）： 在半徑Eps內點的數量小於MinPts（即不是核心點），但是其鄰域內至少包含一個核心點 

稀疏區域中的點（雜訊或者背景點）： 任何不是核心點或者邊界點的點

特點 ： 發現任意形狀的簇、對雜訊數據不敏感、一次掃描、需要密度參數作為停止條件，計算量大和復雜度高 。

    DBSCAN是一種基於密度的聚類演算法，這類密度聚類演算法一般假定類別可以通過樣本分布的緊密程度決定。同一類別的樣本，他們之間的緊密相連的，也就是說，在該類別任意樣本周圍不遠處一定有同類別的樣本存在。

    通過將緊密相連的樣本劃為一類，這樣就得到了一個聚類類別。通過將所有各組緊密相連的樣本劃為各個不同的類別，則我們就得到了最終的所有聚類類別結果。

    前面我們定性描述了密度聚類的基本思想，在這里我們就看看DBSCAN是如何描述密度聚類的。DBSCAN是基於一組鄰域來描述樣本集的緊密程度的，參數(ϵϵ, MinPts)用來描述鄰域的樣本分布緊密程度。其中，ϵϵ描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為ϵϵ的鄰域中樣本個數的閾值。

    假設我們的樣本集是D=(x1,x2,...,xm)(x1,x2,...,xm)，則DBSCAN具體的密度描述定義如下：

        1） ϵϵ-鄰域：對於xj∈Dxj∈D，其ϵϵ-鄰域包含樣本集D中與xjxj的距離不大於ϵϵ的子樣本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 這個子樣本集的個數記為|Nϵ(xj)||Nϵ(xj)|

        2）核心對象：對於任一樣本xj∈Dxj∈D，如果其ϵϵ-鄰域對應的Nϵ(xj)Nϵ(xj)至少包含MinPts個樣本，即如果|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts，則xjxj是核心對象。

        3）密度直達：如果xixi位於xjxj的ϵϵ-鄰域中，且xjxj是核心對象，則稱xixi由xjxj密度直達。注意反之不一定成立，即此時不能說xjxj由xixi密度直達, 除非且xixi也是核心對象。

        4）密度可達：對於xixi和xjxj,如果存在樣本樣本序列p1,p2,...,pTp1,p2,...,pT,滿p1=xi,pT=xjp1=xi,pT=xj, 且pt+1pt+1由ptpt密度直達，則稱xjxj由xixi密度可達。也就是說，密度可達滿足傳遞性。此時序列中的傳遞樣本p1,p2,...,pT−1p1,p2,...,pT−1均為核心對象，因為只有核心對象才能使其他樣本密度直達。注意密度可達也不滿足對稱性，這個可以由密度直達的不對稱性得出。

       5）密度相連：對於xixi和xjxj,如果存在核心對象樣本xkxk，使xixi和xjxj均由xkxk密度可達，則稱xixi和xjxj密度相連。注意密度相連關系是滿足對稱性的。

從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點都是核心對象，因為其ϵϵ-鄰域至少有5個樣本。黑色的樣本是非核心對象。所有核心對象密度直達的樣本在以紅色核心對象為中心的超球體內，如果不在超球體內，則不能密度直達。圖中用綠色箭頭連起來的核心對象組成了密度可達的樣本序列。在這些密度可達的樣本序列的ϵϵ-鄰域內所有的樣本相互都是密度相連的。

    DBSCAN的聚類定義很簡單： 由密度可達關系導出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇 。

    這個DBSCAN的簇裡面可以有一個或者多個核心對象。如果只有一個核心對象，則簇裡面其他的非核心對象樣本都在這個核心對象的ϵϵ-鄰域里；如果有多個核心對象，則簇里的任意一個核心對象的ϵϵ-鄰域中一定有一個其他的核心對象，否則這個核心對象無法密度可達。這些核心對象的ϵϵ-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。

       那麼怎麼才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。基本上這就是DBSCAN演算法的主要內容了，但是我們還有三個問題沒有考慮。

    1）一些異常樣本點或者說少量游離於簇外的樣本點，這些點不在任何一個核心對象的周圍，在DBSCAN中，我們一般將這些樣本點標記為噪音點。

    2）距離的度量問題，即如何計算某樣本和核心對象樣本的距離。在DBSCAN中，一般採用最近鄰思想，採用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類演算法的最近鄰思想完全相同。對應少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，比如樣本量較大，則一般採用KD樹或者球樹來快速的搜索最近鄰。

    3）某些樣本可能到兩個核心對象的距離都小於ϵϵ，但是這兩個核心對象由於不是密度直達，又不屬於同一個聚類簇，那麼如何界定這個樣本的類別呢？一般來說，此時DBSCAN採用先來後到，先進行聚類的類別簇會標記這個樣本為它的類別。也就是說DBSCAN的演算法不是完全穩定的演算法。

DBSCAN通過檢查數據集中的每個對象的ε-鄰域來尋找聚類，如果一個點p的ε-鄰域包含對於m個對象，則創建一個p作為核心對象的新簇。然後，DBSCAN反復地定址這些核心對象直接密度可達的對象，這個過程可能涉及密度可達簇的合並。當沒有新的點可以被添加到任何簇時，該過程結束。演算法中的ε和m是根據先驗只是來給出的。

DBSCAN聚類演算法原理的基本要點：

    1.DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反應了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里得距離來進行度量。

    2.DBSCAN演算法需要用戶輸入2個參數： 一個參數是半徑(Eps)，表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量(MinPts)。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點 。

    3.DBSCAN聚類聚類使用到一個 k-距離 的概念，k-距離是指：給定數據集P={p(i); i=0,1,……n},對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中 所有點之間的距離 ， 距離按照從小到大的順序排序 ，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}， 則d(k)就被稱為k-距離 。也就是說， k-距離是點p(i)到所有點(除了p(i)點)之間距離第K近的距離 。對待聚類集合中 每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)} 。

    4.根據經驗計算半徑Eps：根據得到的所有點的 k-距離集合E ，對集合E進行 升序排序 後得到k-距離集合 E' ，需要擬合一條排序後的E'集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察， 將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值 。

    5.根據經驗計算最少點的數量MinPts： 確定MinPts的大小，實際上也是確定k-距離中k的值 ，DBSCAN演算法中取k=4，則MinPts=4。

    6.另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變。Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為離群點，MinPts過小，會導致發現大量的核心點。

我們需要知道的是，DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。

對於演算法的實現，我們概要地描述一下實現的過程：

    1.解析樣本數據文件。

    2.計算每個點與其他所有點之間的歐幾里得距離。

    3.計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。

    4.將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢

    5.根據散點圖確定半徑Eps的值

    6.根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與核心點距離小於半徑Eps的點映射。

    7.根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，並得到離群點。

    8.將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。

    9.選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其離群點，使用散點圖對比聚類效果。

    和傳統的K-Means演算法相比，DBSCAN最大的不同就是不需要輸入類別數K，當然它最大的優勢是可以發現任意形狀的聚類簇，而不是像K-Means，一般僅僅使用於凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH演算法類似。

    那麼我們什麼時候需要用DBSCAN來聚類呢？一般來說，如果數據集是稠密的，並且數據集不是凸的，那麼用DBSCAN會比K-Means聚類效果好很多。 如果數據集不是稠密的，則不推薦用DBSCAN來聚類 。

    優點：

        1）可以對任意形狀的稠密數據集進行聚類，相對的，K-Means之類的聚類演算法一般只適用於凸數據集。不用指明類別的數量，能靈活找到並分離各種形狀和大小的類。能很好地處理雜訊和離群點。

        2）可以在聚類的同時發現異常點，對數據集中的異常點不敏感。

        3）聚類結果沒有偏倚，相對的，K-Means之類的聚類演算法初始值對聚類結果有很大影響。

    缺點：

         1）在不同密度的類方面有一定難度。如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合( HDBSCAN適合密度不均勻問題 )。

        2）如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰近時建立的KD樹或者球樹進行規模限制來改進。當數據量增大時，要求較大的內存支持I/O消耗也很大；演算法聚類效果依賴與距離公式選取，實際應用中常用歐式距離，對於高維數據，存在「維數災難」。

        3）調參相對於傳統的K-Means之類的聚類演算法稍復雜，主要需要對距離閾值ϵϵ，鄰域樣本數閾值MinPts聯合調參，不同的參數組合對最後的聚類效果有較大影響。

        4）對於從兩類均可達的邊界點，由於各個點是被隨機訪問的，因此DBSCAN不能保證每次都返回相同的聚類。

    DBSCAN類的重要參數分為兩類，一類是DBSCAN演算法本身的參數，一類是最近鄰度量的參數，下面我們對這些參數做一個總結。

    1） eps： DBSCAN演算法參數，即我們的ϵ-鄰域的距離閾值，和樣本距離超過ϵ的樣本點不在ϵ-鄰域內。 默認值是0.5 ，一般需要通過在多組值裡面選擇一個合適的閾值。eps過大，則更多的點會落在核心對象的ϵ-鄰域，此時我們的類別數可能會減少，本來不應該是一類的樣本也會被劃分為一類。反之則類別數可能會增大，本來是一類的樣本卻被劃分開。

   2） min_samples： DBSCAN演算法參數，即樣本點要成為核心對象所需要的ϵ-鄰域的樣本數閾值。默認值是5。一般需要通過在多組值裡面選擇一個合適的閾值。通常和eps一起調參。在eps一定的情況下，min_samples過大，則核心對象會過少，此時簇內部分本來是一類的樣本可能會被標為噪音點，類別數也會變多。反之min_samples過小的話，則會產生大量的核心對象，可能會導致類別數過少。

    3） metric： 最近鄰距離度量參數。可以使用的距離度量比較多，一般來說DBSCAN使用默認的歐式距離(即p=2的閔可夫斯基距離)就可以滿足我們的需求。可以使用的距離量度參數有：歐式距離、曼哈頓距離、切比雪夫距離、閔可夫斯基距離、帶權重閔可夫斯基距離、標准化歐式距離、馬氏距離。

還有一些其他不是實數的距離度量，一般在DBSCAN演算法用不上，這里也就不列了。

    4）algorithm：最近鄰搜索演算法參數，演算法一共有三種，第一種是蠻力實現，第二種是KD樹實現，第三種是球樹實現。這三種方法與K近鄰法(KNN)原理中演算法一致。對於這個參數，一共有4種可選輸入，"brute"對應第一種蠻力實現,"kd_tree"對應於第二種KD樹實現，"ball_tree"對應於第三種的球樹實現，"auto"則會在上面三種演算法中做權衡，選擇一個擬合最好的最優演算法。 需要注意的是，如果輸入樣本特徵是稀疏的時候，無論我們選擇哪種演算法，最後sklearn都會去用蠻力實現"brute" 。個人的經驗，一般情況使用默認的"auto"就夠了。如果數據量很大或者特徵也很多，用「auto」建樹時間可能會很長，效率不高，建議選擇KD樹實現「kd_tree」,此時如果發現"kd_tree"速度比較慢或者已經知道樣本分布不是很均勻時，可以嘗試用"ball_tree"。

    5） leaf_size ：最近鄰搜索演算法參數，為使用KD樹或者球樹時，停止建子樹的葉子節點數量的閾值。這個值越小，則生成的KD樹或者球樹就越大，層數越深，建樹時間越長，反之，則生成的KD樹或者球樹會小，層數較淺，建樹時間較短。默認是30，因為這個值一般隻影響演算法是運行速度和使用內存大小，因此一般情況下可以不管它。

    6） p ：最近鄰距離度量參數。只有用於閔可夫斯基距離和帶權重閔客服斯基距離中p值的選擇，p=1為曼哈頓距離，p=2為歐式距離。如果使用默認的歐式距離不需要管這個參數。

以上就是DBSCAN類的主要參數介紹，其實需要調參的就是兩個參數eps和min_samples，這兩個值的組合對最終的聚類效果有很大的影響。

② 數據挖掘干貨總結（四）--聚類演算法

本文共計2680字，預計閱讀時長七分鍾

聚類演算法

 

一 、 本質

將數據劃分到不同的類里，使相似的數據在同一類里，不相似的數據在不同類里

 

二 、 分類演算法用來解決什麼問題

文本聚類、圖像聚類和商品聚類，便於發現規律，以解決數據稀疏問題

三 、 聚類演算法基礎知識

1. 層次聚類 vs 非層次聚類

– 不同類之間有無包含關系

2. 硬聚類 vs 軟聚類

– 硬聚類：每個對象只屬於一個類

– 軟聚類：每個對象以某個概率屬於每個類

3. 用向量表示對象

– 每個對象用一個向量表示，可以視為高維空間的一個點

– 所有對象形成數據空間（矩陣）

– 相似度計算：Cosine、點積、質心距離

4. 用矩陣列出對象之間的距離、相似度

5. 用字典保存上述矩陣（節省空間）

    D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}

6. 評價方法

– 內部評價法（Internal Evalution）：

• 沒有外部標准，非監督式

• 同類是否相似，跨類是否相異

DB值越小聚類效果越好，反之，越不好

– 外部評價法（External Evalution）：

• 准確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)

• 精度（Precision）: C11 / (C11 + C21 )

• 召回（Recall）: C11 / (C11 + C12 )

• F值（F-measure）：

β表示對精度P的重視程度，越大越重視，默認設置為1，即變成了F值，F較高時則能說明聚類效果較好。

四 、 有哪些聚類演算法

主要分為 層次化聚類演算法 ， 劃分式聚類演算法 ， 基於密度的聚類演算法 ， 基於網格的聚類演算法 ， 基於模型的聚類演算法等 。

4.1 層次化聚類演算法

又稱樹聚類演算法，透過一種層次架構方式，反復將數據進行分裂或聚合。典型的有BIRCH演算法，CURE演算法，CHAMELEON演算法，Sequence data rough clustering演算法,Between groups average演算法,Furthest neighbor演算法,Neares neighbor演算法等。

凝聚型層次聚類 ：

先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。

演算法流程：

1. 將每個對象看作一類，計算兩兩之間的最小距離；

2. 將距離最小的兩個類合並成一個新類；

3. 重新計算新類與所有類之間的距離；

4. 重復2、3，直到所有類最後合並成一類。

特點：

1. 演算法簡單

2. 層次用於概念聚類（生成概念、文檔層次樹）

3. 聚類對象的兩種表示法都適用

4. 處理大小不同的簇

5. 簇選取步驟在樹狀圖生成之後

4.2 劃分式聚類演算法

預先指定聚類數目或聚類中心，反復迭代逐步降低目標函數誤差值直至收斂，得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

經典K-means：

演算法流程：

1. 隨機地選擇k個對象，每個對象初始地代表了一個簇的中心；

2. 對剩餘的每個對象，根據其與各簇中心的距離，將它賦給最近的簇；

3. 重新計算每個簇的平均值，更新為新的簇中心；

4. 不斷重復2、3，直到准則函數收斂。

特點：

1.K的選擇

2.中心點的選擇

– 隨機

– 多輪隨機：選擇最小的WCSS

3.優點

– 演算法簡單、有效

– 時間復雜度：O(nkt)

4.缺點

– 不適於處理球面數據

– 密度、大小不同的聚類，受K的限制，難於發現自然的聚類

4.3 基於模型的聚類演算法

為每簇假定了一個模型，尋找數據對給定模型的最佳擬合，同一」類「的數據屬於同一種概率分布，即假設數據是根據潛在的概率分布生成的。主要有基於統計學模型的方法和基於神經網路模型的方法，尤其以基於概率模型的方法居多。一個基於模型的演算法可能通過構建反應數據點空間分布的密度函數來定位聚類。基於模型的聚類試圖優化給定的數據和某些數據模型之間的適應性。

SOM 神經網路演算法 ：

該演算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。

SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特徵。

演算法流程：

1. 網路初始化，對輸出層每個節點權重賦初值；

2. 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；

3. 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；

4. 提供新樣本、進行訓練；

5. 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。

4.4 基於密度聚類演算法

只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類，擅於解決不規則形狀的聚類問題，廣泛應用於空間信息處理,SGC,GCHL，DBSCAN演算法、OPTICS演算法、DENCLUE演算法。

DBSCAN：

對於集中區域效果較好，為了發現任意形狀的簇，這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域；一種基於高密度連通區域的基於密度的聚類方法，該演算法將具有足夠高密度的區域劃分為簇，並在具有雜訊的空間數據中發現任意形狀的簇。

4.5 基於網格的聚類演算法

    基於網格的方法把對象空間量化為有限數目的單元，形成一個網格結構。所有的聚類操作都在這個網格結構（即量化空間）上進行。這種方法的主要優點是它的處理 速度很快，其處理速度獨立於數據對象的數目，只與量化空間中每一維的單元數目有關。但這種演算法效率的提高是以聚類結果的精確性為代價的。經常與基於密度的演算法結合使用。代表演算法有STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法等。 

③ 建議收藏！10 種 python 聚類演算法完整操作示例

聚類或聚類分析是無監督學習問題。它通常被用作數據分析技術，用於發現數據中的有趣模式，例如基於其行為的客戶群。有許多聚類演算法可供選擇，對於所有情況，沒有單一的最佳聚類演算法。相反，最好探索一系列聚類演算法以及每種演算法的不同配置。在本教程中，你將發現如何在 python 中安裝和使用頂級聚類演算法。完成本教程後，你將知道：

聚類分析，即聚類，是一項無監督的機器學習任務。它包括自動發現數據中的自然分組。與監督學習（類似預測建模）不同，聚類演算法只解釋輸入數據，並在特徵空間中找到自然組或群集。

群集通常是特徵空間中的密度區域，其中來自域的示例（觀測或數據行）比其他群集更接近群集。群集可以具有作為樣本或點特徵空間的中心(質心)，並且可以具有邊界或范圍。

聚類可以作為數據分析活動提供幫助，以便了解更多關於問題域的信息，即所謂的模式發現或知識發現。例如：

聚類還可用作特徵工程的類型，其中現有的和新的示例可被映射並標記為屬於數據中所標識的群集之一。雖然確實存在許多特定於群集的定量措施，但是對所識別的群集的評估是主觀的，並且可能需要領域專家。通常，聚類演算法在人工合成數據集上與預先定義的群集進行學術比較，預計演算法會發現這些群集。

有許多類型的聚類演算法。許多演算法在特徵空間中的示例之間使用相似度或距離度量，以發現密集的觀測區域。因此，在使用聚類演算法之前，擴展數據通常是良好的實踐。

一些聚類演算法要求您指定或猜測數據中要發現的群集的數量，而另一些演算法要求指定觀測之間的最小距離，其中示例可以被視為「關閉」或「連接」。因此，聚類分析是一個迭代過程，在該過程中，對所識別的群集的主觀評估被反饋回演算法配置的改變中，直到達到期望的或適當的結果。scikit-learn 庫提供了一套不同的聚類演算法供選擇。下面列出了10種比較流行的演算法：

每個演算法都提供了一種不同的方法來應對數據中發現自然組的挑戰。沒有最好的聚類演算法，也沒有簡單的方法來找到最好的演算法為您的數據沒有使用控制實驗。在本教程中，我們將回顧如何使用來自 scikit-learn 庫的這10個流行的聚類演算法中的每一個。這些示例將為您復制粘貼示例並在自己的數據上測試方法提供基礎。我們不會深入研究演算法如何工作的理論，也不會直接比較它們。讓我們深入研究一下。

在本節中，我們將回顧如何在 scikit-learn 中使用10個流行的聚類演算法。這包括一個擬合模型的例子和可視化結果的例子。這些示例用於將粘貼復制到您自己的項目中，並將方法應用於您自己的數據。

1.庫安裝

首先，讓我們安裝庫。不要跳過此步驟，因為你需要確保安裝了最新版本。你可以使用 pip Python 安裝程序安裝 scikit-learn 存儲庫，如下所示：

接下來，讓我們確認已經安裝了庫，並且您正在使用一個現代版本。運行以下腳本以輸出庫版本號。

運行該示例時，您應該看到以下版本號或更高版本。

2.聚類數據集

我們將使用 make _ classification ()函數創建一個測試二分類數據集。數據集將有1000個示例，每個類有兩個輸入要素和一個群集。這些群集在兩個維度上是可見的，因此我們可以用散點圖繪制數據，並通過指定的群集對圖中的點進行顏色繪制。這將有助於了解，至少在測試問題上，群集的識別能力如何。該測試問題中的群集基於多變數高斯，並非所有聚類演算法都能有效地識別這些類型的群集。因此，本教程中的結果不應用作比較一般方法的基礎。下面列出了創建和匯總合成聚類數據集的示例。

運行該示例將創建合成的聚類數據集，然後創建輸入數據的散點圖，其中點由類標簽（理想化的群集）著色。我們可以清楚地看到兩個不同的數據組在兩個維度，並希望一個自動的聚類演算法可以檢測這些分組。

已知聚類著色點的合成聚類數據集的散點圖接下來，我們可以開始查看應用於此數據集的聚類演算法的示例。我已經做了一些最小的嘗試來調整每個方法到數據集。3.親和力傳播親和力傳播包括找到一組最能概括數據的範例。

它是通過 AffinityPropagation 類實現的，要調整的主要配置是將「 阻尼 」設置為0.5到1，甚至可能是「首選項」。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，我無法取得良好的結果。

數據集的散點圖，具有使用親和力傳播識別的聚類

4.聚合聚類

聚合聚類涉及合並示例，直到達到所需的群集數量為止。它是層次聚類方法的更廣泛類的一部分，通過 AgglomerationClustering 類實現的，主要配置是「 n _ clusters 」集，這是對數據中的群集數量的估計，例如2。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，可以找到一個合理的分組。

使用聚集聚類識別出具有聚類的數據集的散點圖

5.BIRCHBIRCH

聚類（ BIRCH 是平衡迭代減少的縮寫，聚類使用層次結構)包括構造一個樹狀結構，從中提取聚類質心。

它是通過 Birch 類實現的，主要配置是「 threshold 」和「 n _ clusters 」超參數，後者提供了群集數量的估計。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，可以找到一個很好的分組。

使用BIRCH聚類確定具有聚類的數據集的散點圖

6.DBSCANDBSCAN

聚類（其中 DBSCAN 是基於密度的空間聚類的雜訊應用程序）涉及在域中尋找高密度區域，並將其周圍的特徵空間區域擴展為群集。

它是通過 DBSCAN 類實現的，主要配置是「 eps 」和「 min _ samples 」超參數。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，盡管需要更多的調整，但是找到了合理的分組。

使用DBSCAN集群識別出具有集群的數據集的散點圖

7.K均值

K-均值聚類可以是最常見的聚類演算法，並涉及向群集分配示例，以盡量減少每個群集內的方差。

它是通過 K-均值類實現的，要優化的主要配置是「 n _ clusters 」超參數設置為數據中估計的群集數量。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，可以找到一個合理的分組，盡管每個維度中的不等等方差使得該方法不太適合該數據集。

使用K均值聚類識別出具有聚類的數據集的散點圖

8.Mini-Batch

K-均值Mini-Batch K-均值是 K-均值的修改版本，它使用小批量的樣本而不是整個數據集對群集質心進行更新，這可以使大數據集的更新速度更快，並且可能對統計雜訊更健壯。

它是通過 MiniBatchKMeans 類實現的，要優化的主配置是「 n _ clusters 」超參數，設置為數據中估計的群集數量。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，會找到與標准 K-均值演算法相當的結果。

帶有最小批次K均值聚類的聚類數據集的散點圖

9.均值漂移聚類

均值漂移聚類涉及到根據特徵空間中的實例密度來尋找和調整質心。

它是通過 MeanShift 類實現的，主要配置是「帶寬」超參數。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，可以在數據中找到一組合理的群集。

具有均值漂移聚類的聚類數據集散點圖

10.OPTICSOPTICS

聚類（ OPTICS 短於訂購點數以標識聚類結構）是上述 DBSCAN 的修改版本。

它是通過 OPTICS 類實現的，主要配置是「 eps 」和「 min _ samples 」超參數。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，我無法在此數據集上獲得合理的結果。

使用OPTICS聚類確定具有聚類的數據集的散點圖

11.光譜聚類

光譜聚類是一類通用的聚類方法，取自線性線性代數。

它是通過 Spectral 聚類類實現的，而主要的 Spectral 聚類是一個由聚類方法組成的通用類，取自線性線性代數。要優化的是「 n _ clusters 」超參數，用於指定數據中的估計群集數量。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，找到了合理的集群。

使用光譜聚類聚類識別出具有聚類的數據集的散點圖

12.高斯混合模型

高斯混合模型總結了一個多變數概率密度函數，顧名思義就是混合了高斯概率分布。它是通過 Gaussian Mixture 類實現的，要優化的主要配置是「 n _ clusters 」超參數，用於指定數據中估計的群集數量。下面列出了完整的示例。

運行該示例符合訓練數據集上的模型，並預測數據集中每個示例的群集。然後創建一個散點圖，並由其指定的群集著色。在這種情況下，我們可以看到群集被完美地識別。這並不奇怪，因為數據集是作為 Gaussian 的混合生成的。

使用高斯混合聚類識別出具有聚類的數據集的散點圖

在本文中，你發現了如何在 python 中安裝和使用頂級聚類演算法。具體來說，你學到了：

④ 聚類演算法數據分析

提到聚類演算法，K-Means算是略懂數據分析的人都知道的一種。但K-Means也有其局限性，基本只能處理數值型聚類。而且按距離進行聚類而非密度，無法處理環形圖樣。實際在使用聚類演算法時，還有很多技巧性問題。

聚類演算法需要各變數間相關性較低，可以採用DataFrame的corr()函數進行相關性計算。另外，聚類的變數要區分離散值和非離散值。對於非離散變數，需要進行標准化或歸一化；對於離散變數，可以轉換為虛擬變數，並採用{0, 1}編碼。建議採用min-max標准化，這樣和虛擬變數保持相同的相同范圍。

對於包含非離散變數和虛擬變數的數據集（通常情況），建議採用K-Prototype而非K-Means演算法進行聚類。在使用時可以標記相關虛擬變數，確保區別處理（實際虛擬變數採用K-Modes，非離散變數採用K-Means，再基於權重a進行結果合並）。

KPrototypes(n_clusters=np).fit(df.values, categorical=[1, 2])

其中的1, 2代表df數據集中的第1, 2列（從0計數）。評估聚類演算法可以基於輪廓系數，對比不同的K值，在業務允許范圍內得到最佳K值。建議的輪廓系數函數是silhouette_score，其最大值為1，越接近1越好，可以在不同演算法情況下進行相對比較。

除輪廓系數外，還可以降維繪制散點圖（通過TSNE降維），按聚類演算法分類對散點進行著色，進而直觀的進行聚類演算法分類結果的判斷。

TSNE(n_components=2)

總結來說，整個聚類演算法數據分析的操作步驟如下：

1. 構建低相關性變數數據集（通過給高相關性變數設置固定值）；

2. 對非離散變數進行min-max歸一化操作；

3. 對包含虛擬變數的數據集採用K-Prototype聚類演算法，對只包含非離散變數的數據集採用K-Means演算法；

4. 通過輪廓系數silhouette_score對K值進行循環測試，得到最佳K值；

5. 通過TSNE將數據集降維為兩維顯著特徵值，並通過散點圖，配合聚類演算法分類結果配色對聚類演算法分類結果進行合理判斷；

6. 對聚類演算法分類結果，結合業務邏輯進行解釋，確保分類結果支撐業務分析。

⑤ 多視圖譜聚類演算法介紹

假設給出了具有多個視圖的數據 。

視圖v的相似度矩陣：

視圖v的拉普拉斯矩陣：

單視圖聚類演算法解決了歸一化圖拉普拉斯運算元 如下的優化問題：

其中的tr代表求矩陣的跡。

矩陣 的行是數據點的嵌入，就是說一行對應一個數據，一共有n行，然後用k均值演算法進行聚類。

作者的多視圖譜聚類框架建立在標准譜聚類基礎上，增加了半監督學習中的共正則化框架增加單一視圖。

半監督學習中的共正則化基本上是通過使不同數據視圖中的學習的假設在未標記數據上一致。

框架成功採用了兩個主要假設：(a)每個視圖中的真實目標函數應該就未標記數據的標簽(兼容性)達成一致;(b)視圖在類標簽(條件獨立性)下是獨立的。

兼容性假設允許我們通過進搜索通過僅搜索兼容的函數來縮小可能的目標假設的空間。

作者提出了兩種基於共正則化的方法，使得不同視圖的聚類假設彼此一致。同時作者構建包含所有數據視圖的拉普拉斯運算元，同時在拉普拉斯運算元的基礎上進行了規范化，使得每個拉普拉斯運算元得到的聚類結構在每個視圖中一致。

第一個共正則化強制一個視圖對 的特徵向量應該具有高度的成對相似性(使用成對的正則化標准)。第二個共正則化方案是通過將他們規范化為共同的共識(基於中心的共正則化)來強制使視圖特定的特徵向量看起來相似。

在多視圖的情況下，我們希望每個視圖的特徵向量矩陣是相似的。相當於在強制使所有視圖中的譜聚類假設相同。

先討論雙視圖情況。

提出以下損失函數作為兩個視圖之間聚類結果是否一致性的度量。

其中的 是 的相似矩陣。

進行除法的意義在於進行歸一化使得兩個視圖具有可比較性。

然後作者選擇了線性核作為相似性的度量方式。

從而得出：

選擇線性核的原因：

因為 對上面的代價函數進行化簡最終的到

然後我們在其中增加各個視圖之間的譜聚類目標函數，得到以下的最大化問題：

然後我們可以通過不斷的進行迭代去最大化上面的式子。

例如當給定 時，上式的優化目標就變成了：

這時候就化簡成了普通的單視圖的優化目標函數的形式。它的拉普拉斯矩陣為 。

上面的拉普拉斯矩陣是一種自適應(隨著每次迭代，拉普拉斯運算元會改變)的，結合內核和拉普拉斯運算元的方法。

然後我們可以交替最大化使得演算法得到最大值。但是同時要注意選擇合適的初始化值從而避免陷入局部最大值。迭代開始時，可以選擇最具有信息性的視圖開始進行迭代。

對固定的 和 ，可以保證演算法收斂。實踐中通過觀察連續迭代之間的目標值的差值來監視是否收斂，當低於某一閾值時，停止迭代。

我們擴展上一節中提出的共正則化譜聚類。對於m個視圖，我們有：

在這里，對所有的共正則化部分使用了共同的 進行平衡。然後優化方法和雙視圖情況類似。

給定一個視圖的 ，優化目標如下所示：

然後我們可以通過迭代對它進行不斷優化。

這里提出的正則化方案是對上面的正則化方案的一種替代。將所有視圖的特徵向量 朝向共同的中心 (類似一組共同的特徵向量)。這樣可以減少正則化項的對數(m對)。

目標函數可以寫為：

這個目標函數平衡各個譜聚類目標與每個視圖特定特徵向量 和共有特徵向量 之間的折中。同時與第一種共正則化方法不同的是，我們可以對每一個正則化項設置一個參數來反映它的重要性。

這里的優化方法和上面的還是一樣的，通過固定其他特徵向量對單個特徵向量進行優化。不同的地方在於需要對 進行優化，我們可以固定其他變數，然後對他進行優化。

只有對 進行優化時，和第一種共正則化方法不同，需要優化以下式子：

然後由矩陣的跡的性質tr(AB)=tr(BA)和tr(mA+nB)=mtr(A)+ntr(B)可以得到：

然後就又將這個問題轉化成了單視圖譜聚類的目標函數形式。對應的拉普拉斯矩陣為：

使用第二種基於中心的共正則化和第一種共正則化的另一個差別在於這種方法可以直接得到最終的特徵向量集合 ，然後可以直接對他應用k均值等聚類演算法進行聚類。而第一種共正則化方法需要對得出的所有特徵向量集合進行拼接等處理步驟。

基於中心的共正則化方法一個缺點是容易受到有雜訊的視圖的影響，為了解決這個問題，需要仔細的選擇每個視圖對應的權重 。

參考論文：Co-regularized Spectral Clustering，Abhishek Kumar∗，Piyush Rai∗，Hal Daum ́e III.

⑥ 常用的聚類方法有哪幾種

聚類分析的演算法可以分為劃分法、層次法、基於密度的方法、基於網格的方法、基於模型的方法。

1、劃分法，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。

2、層次法，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。

3、基於密度的方法，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。

5、基於網格的方法，這種方法首先將數據空間劃分成為有限個單元的網格結構,所有的處理都是以單個的單元為對象的。

6、基於模型的方法，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。

(6)圖聚類演算法擴展閱讀：

在商業上，聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來，並且概括出每一類消費者的消費模式或者說習慣。

它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

⑦ 聚類演算法有哪些分類

聚類演算法的分類有：

1、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K小於N。而且這K個分組滿足下列條件：

（1） 每一個分組至少包含一個數據紀錄；

（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；

2、層次法

層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。

例如，在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。

3、密度演算法

基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類法

圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。

通常有兩種嘗試方向：統計的方案和神經網路的方案。

(7)圖聚類演算法擴展閱讀：

聚類演算法的要求：

1、可伸縮性

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

我們需要具有高度可伸縮性的聚類演算法。

2、不同屬性

許多演算法被設計用來聚類數值類型的數據。但是，應用可能要求聚類其他類型的數據，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。

3、任意形狀

許多聚類演算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的演算法趨向於發現具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發現任意形狀簇的演算法是很重要的。

4、領域最小化

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

5、處理「雜訊」

絕大多數現實中的資料庫都包含了孤立點，缺失，或者錯誤的數據。一些聚類演算法對於這樣的數據敏感，可能導致低質量的聚類結果。

6、記錄順序

一些聚類演算法對於輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序交給同一個演算法時，可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的演算法具有重要的意義。

⑧ 用於數據挖掘的聚類演算法有哪些，各有何優勢

聚類方法的分類，主要分為層次化聚類演算法，劃分式聚類演算法，基於密度的聚類演算法，基於網格的聚類演算法，基於模型的聚類演算法等。

而衡量聚類演算法優劣的標准主要是這幾個方面：處理大的數據集的能力；處理任意形狀，包括有間隙的嵌套的數據的能力；演算法處理的結果與數據輸入的順序是否相關，也就是說演算法是否獨立於數據輸入順序；處理數據雜訊的能力；是否需要預先知道聚類個數，是否需要用戶給出領域知識；演算法處理有很多屬性數據的能力，也就是對數據維數是否敏感。

.聚類演算法主要有兩種演算法，一種是自下而上法（bottom-up），一種是自上而下法（top-down）。這兩種路徑本質上各有優勢，主要看實際應用的時候要根據數據適用於哪一種，Hierarchical methods中比較新的演算法有BIRCH主要是在數據體量很大的時候使用；ROCK優勢在於異常數據抗干擾性強……

關於數據挖掘的相關學習，推薦CDA數據師的相關課程，課程以項目調動學員數據挖掘實用能力的場景式教學為主，在講師設計的業務場景下由講師不斷提出業務問題，再由學員循序漸進思考並操作解決問題的過程中，幫助學員掌握真正過硬的解決業務問題的數據挖掘能力。這種教學方式能夠引發學員的獨立思考及主觀能動性，學員掌握的技能知識可以快速轉化為自身能夠靈活應用的技能，在面對不同場景時能夠自由發揮。點擊預約免費試聽課。