基于距離的聚類算法K-means的設(shè)計(jì)實(shí)現(xiàn)

K-means 算法是典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，兩個(gè)對(duì)象的距離越近，其相似度就越大。而簇是由距離靠近的對(duì)象組成的，因此算法目的是得到緊湊并且獨(dú)立的簇。

假設(shè)要將對(duì)象分成 k 個(gè)簇，算法過程如下：

(1) 隨機(jī)選取任意 k 個(gè)對(duì)象作為初始聚類的中心（質(zhì)心，Centroid），初始代表每一個(gè)簇；

(2) 對(duì)數(shù)據(jù)集中剩余的每個(gè)對(duì)象根據(jù)它們與各個(gè)簇中心的距離將每個(gè)對(duì)象重新賦給最近的簇；

(3) 重新計(jì)算已經(jīng)得到的各個(gè)簇的質(zhì)心；

(4) 迭代步驟(2)-(3)直至新的質(zhì)心與原來的質(zhì)心相等或小于設(shè)定的閾值，算法結(jié)束。

注意！

(1) 在 K-means 算法 k 值通常取決于人的主觀經(jīng)驗(yàn)；

(2) 距離公式常用歐氏距離和余弦相似度公式，前者是根據(jù)位置坐標(biāo)直接計(jì)算的，主要體現(xiàn)個(gè)體數(shù)值特征的差異，而后者更多體現(xiàn)了方向上的差異而不是位置上的，cosθ越接近 1 個(gè)體越相似，可以修正不同度量標(biāo)準(zhǔn)不統(tǒng)一的問題；

(3) K-means 算法獲得的是局部最優(yōu)解，在算法中，初始聚類中心常常是隨機(jī)選擇的，一旦初始值選擇的不好，可能無法得到有效的聚類結(jié)果。

對(duì)于一堆數(shù)據(jù)，K 值（簇?cái)?shù)）的最優(yōu)解如何確定呢？常見的有“肘”方法

（Elbow method）和輪廓系數(shù)法（Silhouette Coeffient）：

① “肘”方法：核心指標(biāo)是 SSE（sum of the squared errors，誤差平方和），即所有樣本的聚類誤差（累計(jì)每個(gè)簇中樣本到質(zhì)心距離的平方和），隨著 K 的增大每個(gè)簇聚合度會(huì)增強(qiáng)，SSE 下降幅度會(huì)增大，隨著 K 值繼續(xù)增大 SSE 的下降幅度會(huì)減少并趨于平緩，SSE 和 K 值的關(guān)系圖會(huì)呈現(xiàn)成一個(gè)手肘的形狀，此肘部對(duì)應(yīng)的 K 值就是最佳的聚類數(shù)。

② 輪廓系數(shù)法：結(jié)合聚類的凝聚度（Cohesion）和分離度（Separation）來考慮，凝聚度為樣本與同簇其他樣本的平均距離，分離度為樣本與最近簇中所有樣本的平均距離，該值處于-1~1 之間，值越大表示聚類效果越好。

以 iris 數(shù)據(jù)為例：

代碼實(shí)現(xiàn)

由圖看出拐點(diǎn)在 K=2 處，K=3 次之，iris 實(shí)際數(shù)據(jù)分成了三類。