聚類算法總結

1      什麼是聚類算法？

聚類算法就是根據特定的規則，将資料進行分類。分類的輸入項是資料的特征，輸出項是分類标簽，它是無監督的。

常見的聚類規則包括：1）基于原型的，例如有通過質心或中心點聚類，常見的算法KMeans；2）基于圖的，也就是通過節點和邊的概念，形成連通分支的分類，常見的算法是凝聚層次聚類，最小生成樹聚類；3）基于密度的，根據資料密度的大小進行聚類，常見的算法是DBSCAN，SNN密度聚類；4）基于統計的聚類，資料一般符合一種或幾種機率分布，根據機率分布情況進行聚類。

2      常見的幾類聚類算法

這裡介紹KMeans、凝聚層次聚類和DBSCAN三種聚類方法。

2.1     KMeans聚類

KMeans聚類就是通過找出距離質心最近的點的分為一類的方法，達到SSE（誤差平方和）最小的目标。

2.1.1     基本概念

K類：參數，聚類前設定的聚類形成的簇的個數；

質心：每個簇的聚集中心，一般L2距離為均值；餘弦相似度為均值；L1距離為中位數。

距離：待聚類點到質心的距離，一般低維空間用L2距離，文檔用餘弦相似度。

SSE：KMeans聚類的目标函數，簇中各點到質心的距離平方和為簇内SSE，總SSE為K個簇内SSE之和。

2.1.2     KMeans聚類流程

Step1：确定要聚成的簇的個數n_clusters = k，選擇k個初始質心；

Repeat：

Step2：根據質心，将每個資料點選擇最近的質心聚為一個簇；

Step3：根據新簇，更新質心。

Until：質心不變動，或資料點所在簇不再更新；或者重複次數達到設定的上限。

2.1.3     KMeans聚類參數

KMeans聚類有兩個初始參數：k 和初始質心；

k值：

k值設定可能出現的問題：由于事先不清楚資料的分布情況導緻k值設定與資料實際的簇與設定不符；

解決方法：事前：1）通過可視化散點圖觀察，但是更多時候多元不好觀察；2）通過多個k值得疊代，計算SSE或silhouette_score的趨勢分布，找出拐點對應的k值；事後：3）嘗試對SSE較大的簇進行分裂，或對質心距離很近的簇進行合并，計算SSE的增加量，改變簇的數量。

另外，可以采用二分K均值方法，逐漸疊代。

初始質心：

初始質心預設采用随機選擇的方法，但是由于質心的選擇，如果初始質心在兩個簇中間或在一個比較密的簇内，可能會出現，本來是兩個簇的聚成一個簇或者本來該聚成一個簇的變成兩個簇，使結果不能達到預期。

解決方法：1）一般解決方法，就是對初始質心多次嘗試；2）還可以通過先計算全體資料均值，作為第一個質心，後一個質心取離前一個質心距離最遠的點的方法，取出所有質心，但這種方法可能将離群點選為質心。

2.1.4     複雜度

KMeans聚類的空間複雜度為O（ (m+k)n），其中m為點的個數，n為屬性的個數，k為分類個數，代表要存儲的質心數量；

時間複雜度為O（m*n*k*I），其中I為疊代次數。

2.1.5     算法優缺點

優點：簡單、便于了解，易于實作，空間複雜度和時間複雜度不高；

缺點：參數選取（k值和初始質心選取問題）；KMeans算法的本質是将按照距離将距離某個質心最近的點聚為一簇，它的計算中預設每個簇是以質心為中心的球形結構，對于不規則形狀的簇、基于密度的簇等劃分困難；3）KMeans聚類為完全聚類，目标函數為SSE，離群點對結果影響較大，可以先做離群點删除，再聚類。

2.2     凝聚層次聚類

凝聚層次聚類是一種基于圖的聚類。它先是将每個點作為一個簇，通過鄰近度矩陣，将距離最近的簇聚為一個新簇，然後更新鄰近度矩陣。

2.2.1     基本概念

鄰近度矩陣：任一簇到其他簇的距離形成的矩陣；

單鍊：用兩個簇的最小距離代表兩個簇的鄰近度；可以看成兩個簇結點的邊長的最小值。

全連：用兩個簇的最大距離代表兩個簇的鄰近度；可以看成兩個簇結點的邊長的最大值。

組平均：用分别在兩個簇中點的全部點距離的平均值代表兩個簇的鄰近度。可以看成兩個簇結點的邊長的均值。

Ward：兩個簇合并導緻的平方誤差的增量代表兩個簇的鄰近度。

2.2.2     聚類流程

Repeat：

Step1：計算鄰近度矩陣；

Step2：将鄰近度矩陣中最近的點合并為一個新簇；

Until：

隻剩下一個簇。（這個有問題吧，隻剩一個簇還聚類幹嘛？）

2.2.3     複雜度

空間複雜度：由于要存儲鄰近度矩陣，是以空間複雜度為O（m2）；

時間複雜度：需要m-1次疊代，每一步聚一個簇，第i步需要做O（（m-i+1）2），是以時間複雜度為O（m3）。

2.2.4     算法優缺點

優點：1）不用事先設定聚類數量，根據結果就可以自動地形成合适的簇；2）不受初始質心影響，而且會将最近的點聚為一簇。

缺點：1）由于每次更新鄰近度矩陣會覆寫原來的鄰近度矩陣，是以聚類結果很可能是次最優的；2）複雜度比較高，開銷大。3）對噪聲可能不夠敏感，高維計算時也可能出現問題。可以先使用其他技術進行局部聚類，再進行層次聚類。

2.3     DBSCAN（density based spatial cluster of application with noise）

将某一鄰域内密度大于給定值的資料聚為一簇。這一聚類屬于不完全聚類，噪聲點将不會屬于任何一個簇。

2.3.1     基本概念

核心點：在給定點的r鄰域内，包含資料中點的個數大于等于min_pts個；

邊界點：在某個核心點的鄰域内，但是它的r鄰域内點的個數小于min_pts個；

噪聲點：非核心點和邊界點。

2.3.2     聚類流程

Step1：将所有點标記為核心點、邊界點和噪聲點；

Step2：删除噪聲點；

Step3：為距離小于eps的所有核心點建構一條邊；

Step4：每組連通的核心點形成一個簇；

Step5：将邊界點指派到與之相關聯的核心點。

2.3.3     參數

DBSCAN的初始參數有兩個，Eps和min_pts，即核心點鄰域的半徑和鄰域中最小點的個數。

Eps：鄰域的半徑大小。

鄰域設定可能會出現的問題：設定值過大，可能會将該分離的簇聚到一起；鄰域設定過小，每個點都可能成為一個鄰域。

方法：可以先計算任何點的距離，然後用線性圖展現，找出距離的拐點，作為半徑大小。

Min_pts：鄰域中最小點的個數。

點的個數的設定與鄰域的大小相關，設定過大，可能無法形成核心鄰域，設定過小，可能将噪聲作為核心點。

優化方法：？？？

2.3.4     複雜度

空間複雜度：要存儲點m，空間複雜度為O（m）；

時間複雜度：m*找出eps内的點需要的時間，複雜度最大O（m2），最小為O（mlogm）。

2.3.5     算法優缺點

優點：1）可以區分不規則形狀的簇；2）簡單、空間複雜度低；3）抗噪聲；

缺點：1）初始參數eps和min_pts不好确定；2）高維空間不适用；3）對于不同區域密度不同的資料不能形成好的聚類效果；4）不是完全聚類，噪聲會被删除。

3      聚類算法評估

1）    凝聚度SSE

2）    分離度：,c為全部點的均值；為簇的均值。

TSS=SSE+SSB。

3）    凝聚度和分裂度的融合，輪廓系數（silhouette_score），某個點i的輪廓系數

為一個資料點到其他簇所有點的距離；為一個資料點到簇内點的距離。

的值在[-1, 1]間，越大聚類效果越好。值為-1時，=0，沒有形成聚類；值為1時，，達到了最好的聚類效果。

    鄰近度矩陣矩陣：理想的相似度矩陣和現實的相似度矩陣的相關度。理想的相似度矩陣是塊對角陣，每個資料點一行一列，兩個點相似度矩陣值的坐标為：在同一簇中為1，不在同一簇中中值為0。

轉載于:https://www.cnblogs.com/bigdatadnsc/p/10708333.html