0。引入

聚類(clustering)是無監督學習(unsuperviserd learning)中研究和應用最多的一類學習演算法,目的是將樣本劃分成若干個“簇”(cluster),每個“簇”之間儘量相異,每個簇之內的樣本儘量相似。

聚類有啥用呢?

可以作為一個單獨的過程,用於尋找

資料內的分佈規律

;也可以作為

分類

等學習任務的

前驅過程

,用於確定分類的標籤;還可以用來進行

異常檢測

基於不同的相似性假設,可以有多種不同的聚類演算法,例如原型聚類、密度聚類、層次聚類、分佈。

機器學習第8篇——K-Means(聚類演算法)

原型聚類——K-Means,原型指的是中心(質心)

原型聚類

,此類演算法假設聚類結構能夠透過一組原型刻畫,K-Means中的原型是指每個“簇”的質心,這個原型可以使得“簇”內的平方誤差的加和達到最小,公式如下:

機器學習第8篇——K-Means(聚類演算法)

K-Means 劃分後的平方誤差

機器學習第8篇——K-Means(聚類演算法)

層次聚類——SLINK,基於連通性來區分“簇”,連通性指的是距離遠近(間接啟發了密度聚類)

層次聚類,

此類算分試圖在不同層次對資料集進行劃分,從而形成樹形的聚類結構。資料集的劃分可採用“自底向上”的聚合策略,也可採用“自頂向下”的拆分策略。樹形結構如下:

機器學習第8篇——K-Means(聚類演算法)

層次聚類——樹形結構,按途中虛線的簇距離分割,可以得到7個聚類簇

這個簇距離是怎麼計算的呢?我們待續!

機器學習第8篇——K-Means(聚類演算法)

密度聚類——DBSCAN,密度指的是鄰域(指定大小的圓形區域)

密度聚類

,密度聚類也稱作“基於密度的聚類”,此類演算法假設聚類結構能夠透過樣本分佈的緊密程度確定。密度指的是“鄰域”,即如下圖所示:

機器學習第8篇——K-Means(聚類演算法)

鄰域和密度可達

虛線指的是鄰域的範圍,初始物件/點透過鄰域可以觸達到鄰域範圍的其它點,這個過程叫做密度可達,即透過密度可達篩聚類出各個分佈緊密程度的簇。

說了這麼多,其實本文只打算詳細介紹一種聚類演算法——K-Means,原型的聚類中最常見的一種演算法,有機會再詳細介紹其他演算法。

1。K-Means原理

如前文所述,K-Means假設聚類結構能夠透過一組原型(點)刻畫,K-Means中的原型是指每個“簇”的質心,這個原型可以使得“簇”內的平方誤差的加和達到最小,公式如下:

機器學習第8篇——K-Means(聚類演算法)

誤差公式(‖加下標表示求向量範數)

K-Means演算法的目標是最小化聚類後“簇”內的平方誤差和,因為E值越小,“簇”內的樣本相似性越高。但是這個最小化過程是NP難問題,沒有有效的演算法,只能遍歷所有可能的組合(“簇”),當樣本量較大時就是非常浪費資源甚至無解的。所以考慮使用貪心演算法,即透過迭代最佳化來求近似解。

演算法大致如下:

輸入:樣本集

過程:

第一步隨機選擇K個點作為初始原型;

第二步計算剩餘的點到K個點的距離,並將點劃入距離最近的原型所在的“簇”內;

第三步計算每個“簇”點的均值,並將每個“簇”的均值更新為新的原型;

第四步,重複前面3步,直到每個“簇”點的均值不再變化;

第五步,輸出每個“簇”的中心。

為避免執行時間過長,通常會設定一個最大的迭代輪次或者設定最小調整幅度閥值。

2。K-Means超引數選擇

2。1手肘法

核心思想:隨著聚類數k的增大,樣本劃分會更加精細,每個簇的聚合程度會逐漸提高,那麼誤差平方和SSE自然會逐漸變小。並且,當k小於真實聚類數時,由於k的增大會大幅增加每個簇的聚合程度,故SSE的下降幅度會很大,而當k到達真實聚類數時,再增加k所得到的聚合程度回報會迅速變小,所以SSE的下降幅度會驟減,然後隨著k值的繼續增大而趨於平緩,也就是說SSE和k的關係圖是一個手肘的形狀,而這個肘部對應的k值就是資料的真實聚類數。當然,這也是該方法被稱為手肘法的原因。

2。2 輪廓係數

簇內不相似度:每個樣本到質心(原型、中心)的平均距離

簇間不相似度:每個樣本到 其它某簇所有樣本的均值的距離稱為該樣本和該“簇”的不相似度bij,該樣本的“簇”間不相似度bi = min{bi1,bi2……}。

根據樣本i的簇內不相似度a i 和簇間不相似度b i ,定義樣本i的輪廓係數

3。K-Means 演算法變體

k-means不能解決非凸(non-convex)資料,所以有了kernel k-means

k-means對初始值的設定很敏感,所以有了k-means++、intelligent%20k-means、genetic%20k-means;

k-means對噪聲和離群值非常敏感,所以有了k-medoids和k-medians;

k-means只用於numerical型別資料,不適用於categorical型別資料,所以k-modes;

以上均轉載自——參考資料第1條《用於資料探勘的聚類演算法有哪些,各有何優勢?》

以上為K-Means的基礎理論,與君共勉。

參考資料:

用於資料探勘的聚類演算法有哪些,各有何優勢?

《機器學習》。周志華 第九章

維基百科——聚類分析

機器學習中的聚類

K-means聚類最優k值的選取

kmeans最優k值的確定方法-手肘法和輪廓係數法