什麼是 k-means 分群法？

如前所述，許多分群演算法都無法擴充至資料集 這些應用領域中通常有數百萬個範例。例如： 主動或多元化階層分群演算法檢視所有的組合 且包含複雜的 \(O(n^2 log(n))\) 和 \(O(n^2)\)

本課程著重在 k-means 分，原因是規模達 \(O(nk)\)、 \(k\) 是使用者選擇的叢集數量演算法會將指向的 \(k\) 以盡可能減少分群的方式， 叢集的群集中心（見圖 1）。

因此，k-means 會將資料視為 並嘗試找出與這些目標相對應的叢集 發行。但實際資料包含離群值和密度為基礎的叢集 而且可能不符合基礎 k-means 的假設

k-means 分群演算法

演算法的步驟如下：

1. 請提供 \(k\)的初始猜測值，稍後可以修改。為此 例如，我們選擇 \(k = 3\)

2. 隨機選擇 \(k\) 群集。

   

   圖 1：初始化時的 k-means。

3. 將每個點指派給最接近的中心群， \(k\) 即可取得初始叢集。

   

   圖 2：初始叢集。

4. 為每個集群計算一個新質心， 叢集中的所有資料點圖 4 中的箭頭顯示 群集中心的位置。

   

   圖 3：重新計算群集中心。

5. 將每個點重新指派給最接近的新質心。

   

   圖 4：重新指派後的叢集。

6. 重複執行步驟 4 和 5，重新計算群集中心和叢集成員，直到 也不會變更叢集如果是大型資料集 根據其他條件在融合前停止演算法

由於群集位置一開始是隨機選擇，因此 k-means 可以 會在連續執行時傳回明顯不同的結果。為瞭解決這個問題 請多次執行 k-means 分次，以選出品質最佳的結果 指標。(本課程稍後會說明品質指標)。你需要 這個進階版本的 k-means 提供了更好的初始群集中心位置。

雖然 好奇心的 k-means 是特別的 expectation-maximization 演算法來達成。詳情請見 UPenn 針對這個主題的演講筆記。