本文意圖

結合目標函數，了解 k-means步驟和每一步的目的

如何避免陷入局部最優

如何使聚類出的簇更加平衡

---

目錄

本文意圖

第一部分? K-Means步驟

1.1 什么是聚類？

1.2 K-Means詳細步驟

1.2.1 目標函數

1.2.2 隨機初始化簇心

1.2.3 數據點分簇

1.2.4 重新計算簇心

1.2.5 迭代過程

第二部分 避免局部最優

2.1 隨機初始化會導致什么問題？

2.2 用實驗說明

2.3 如何解決隨機結果不好的問題？

2.4 實驗中的一些其他細節

2.4.1 “距離”度量方式

2.4.2 簇心數量K的選取

第三部分 平衡聚類

3.1?-balance聚類

3.2 平衡聚類應用場景

3.3?-balance方法一——在K-Means上改進

3.3.1 方法說明

3.3.2 例子

3.4 -balance方法二——陰陽K-Means加速重新分簇

3.4.1 陰陽K-Means

3.4.2?對于方法一的改進

---

第一部分? K-Means步驟

1.1 什么是聚類？

給定一組未加標簽的數據集，希望通過算法自動將數據分成有緊密關聯的子集或是簇。

假設我們采集到了一些牡丹花數據，但我們并不知道這些牡丹花具體是哪個品種的。植物學家想要按照特征的相似性，先大致對牡丹花進行粗分類，再對每個類別做具體細致的研究。此時，我們首先想到的就是無監督學習聚類算法。

?

1.2 K-Means詳細步驟

1.2.1 目標函數

下面用一個簡單的例子，對K-Means的步驟做說明。假設我們有一些二維樣本點，最終聚類的結果如下圖所示。K-Means算法是怎樣將這些點聚成兩個簇的呢？

1.2.2 隨機初始化簇心

所有樣本點一開始是沒有被聚類的。將K取為2，即我們希望最終聚成2個簇。完成初始化簇心之后，我們隨機選中了兩個樣本作為簇心。

1.2.3 數據點分簇

第一次分簇之后，我們將得到下圖所示的2個簇

1.2.4 重新計算簇心

由于簇心是到簇內所有點距離相等的位置，因此在第一次分簇結束之后，簇心的位置會相應的發生改變。我們重新計算簇心位置，如下圖所示：

1.2.5 迭代過程

重復1.2.3和1.2.4兩個步驟，直到在重新計算簇心時，所有簇的簇心都不再變化為止。下面給出例子的后續操作，直到聚類完成。

?

---

第二部分 避免局部最優

2.1 隨機初始化會導致什么問題？

• 理想情況下，k-means算法會收斂到一個全局最優解上。下圖就是一個我們希望看到的聚類結果。

• 但如果隨機初始化的結果不好，k-means算法最終可能會收斂到局部最優解上。下圖就是當初始化結果不好時，算法最終迭代出的結果，這顯然不是我們希望看到的。

2.2 用實驗說明

• 具體參數：

樣本數：350

特征維度：4

簇數量：3

距離度量：歐式距離

• 我們希望看到，當K-Means迭代收斂時，應該為全局最優。其效果應該如下圖所示。

• 但在實驗中，第一次測試的結果就收斂到了一個效果不怎么好的局部最優，如下圖所示。

2.3 如何解決隨機結果不好的問題？

多隨機幾次，取最好的結果！

• 多次隨機初始化

?

2.4 實驗中的一些其他細節

2.4.1 “距離”度量方式

距離實際上反映了不同樣本之間的相似度。

滿足非負性、對稱性、同一性、三角不等式性的度量，如歐氏距離、曼哈頓距離、切比雪夫距離等，都可以作為距離度量。

2.4.2 簇心數量K的選取

• 肘部原則

嘗試不同的k值，繪制均方誤差曲線圖，找到圖像的肘部為宜

?

---

第三部分 平衡聚類

3.1?-balance聚類

下圖中一共有12個樣本點。我們希望將它們分成3個簇，并且保證分成的簇相對平衡。在這個例子中，這是一個絕對平衡的分簇，即每個簇內含有的樣本點完全相同。

3.2 平衡聚類應用場景

• 數據預處理

①??圖像分類領域，使用詞袋模型對圖像進行分割，分割后需要使用K-Means對分割除的特征聚類。更平衡的聚類會得到更準確的圖像分類結果。

②??當未標記的樣本直覺上服從均勻分布時，平衡聚類可以更好的反應實際樣本類別。

?

3.3?-balance方法一——在K-Means上改進

3.3.1 方法說明

• 設定2個規則：

規定簇數量K(同K-Means)

規定簇最多包含多少個點

• 對K-Means改進：

設定2個規則

在最終收斂前，每個簇心維持1個邊界值，該邊界值為簇心到簇中每個點距離的最大值

當一個簇已滿，又有1個新樣本想加入，進行一個判斷。若簇心到該樣本距離小于邊界值，則踢出已在簇中的最遠樣本，接納該樣本

每次接納新樣本，都更新簇心位置

3.3.2 例子

下圖為使用K-Means聚類過程中的中間狀態。假設在樣本點重新分簇的過程中，紅色星星代表的樣本需要被重新分配到綠色簇中，如下圖所示：

假設我們允許每個簇最大包含5個樣本。此時，綠色簇已經包含了5個樣本，達到了上限。我們計算綠色簇心到紅色星星的距離，拿去和綠色簇的邊界值比較。在這個例子當中，綠色簇心到紅色星星的距離，小于綠色簇的邊界值。因此，我們將綠色簇中距離簇心最遠的樣本踢出簇，并將紅色星星樣本包含進來，如下圖所示：

?

3.4 -balance方法二——陰陽K-Means加速重新分簇

3.4.1 陰陽K-Means

• 全局過濾

對于每個樣本點，維持上下兩個邊界。上邊界大于等于樣本到最優簇簇心的距離，下邊界小于等于樣本到次優簇簇心的距離

利用這兩個邊界，可以使樣本在重新分配簇的步驟中，不需要和每個簇心計算距離

• 組過濾/局部過濾

將K個簇按照簇心之間的距離遠近分組

對于每個樣本點，先判斷屬于哪個分組，再在這個組內計算上下兩個邊界

3.4.2?對于方法一的改進

在方法一中，-balance平衡聚類會在重新分簇步驟時，將樣本點踢出簇，因此會比普通的K-Means有更多的重新分簇步驟。因此，在方法二中，平衡聚類的步驟思路和方法一相同，但使用陰陽K-Means的思想，加速了重新分簇的步驟，使得算法整體的效率提高。

陰陽K-Means具體使用方法，如下圖所示：

?

?

總結

以上是生活随笔為你收集整理的【零基础系列】K-Means聚类算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。