什麼是 k-means 分群法？

如先前所述，許多分群演算法無法擴展至機器學習中使用的資料集，因為這些資料集通常包含數百萬個範例。舉例來說，聚合或分割式階層式聚類演算法會查看所有組點，分別具有 $O(n^2 log(n))$ 和 $O(n^2)$的複雜度。

本課程著重於 k 均值，因為它會以 $O(nk)$的比例進行縮放，其中 $k$是使用者選擇的叢集數量。這個演算法會將點分組成$k$ 叢集，方法是盡可能縮短各個點與其叢集的圓心之間的距離 (請見圖 1)。

因此，k-means 會有效地將資料視為由多個大致圓形分布的資料組成，並嘗試找出與這些分布相對應的叢集。但現實世界資料含有異常值和以密度為基礎的叢集，可能不符合 k 均值的假設。

k-means 分群演算法

演算法會按照以下步驟運作：

1. 提供 $k$的初步預估值，之後可再進行修改。在本例中，我們選擇 $k = 3$。

2. 隨機選擇 $k$ 重心。

   

   圖 1：初始化時的 k 均值。

3. 將每個點指派至最近的群集中心，取得 $k$ 初始叢集。

   

   圖 2：初始叢集。

4. 針對每個叢集，計算叢集中所有點的平均位置，以便計算新的重心。圖 4 中的箭頭顯示了 centroid 位置的變化。

   

   圖 3：重新計算的中心點。

5. 將每個點重新指派至最近的新群集中心。

   

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

6. 重複執行步驟 4 和 5，重新計算質心和叢集成員資格，直到點集不再變更叢集為止。如果是大型資料集，您可以根據其他條件，在收斂前停止演算法。

由於中心位置一開始是隨機選擇，k 均值在連續執行時可能會傳回截然不同的結果。如要解決這個問題，請多次執行 k 均值，然後選擇品質指標最佳的結果。(我們會在本課程稍後介紹品質指標)。您需要使用進階版的 k 均值，才能選擇更理想的初始中位點位置。

雖然您不必深入瞭解數學，但如果您好奇，k 均值是期望最大化演算法的特殊情況。請參閱賓州大學的相關講義筆記。