k means algorithm

k 均值演算法

這是 k-means 演算法的 Python 實現，包括肘部方法和輪廓方法，用於選擇最佳 K

K-means 是一種流行的聚類演算法，用於將資料劃分為 K 個簇。它的工作原理是迭代地將每個資料點分配給最近的聚類質心，然後根據分配給它的資料點重新計算每個聚類的質心。重複該過程直到收斂。

演算法

• 從資料點中隨機選擇 K 個初始簇質心。
• 將每個數據點分配給最近的聚類質心。
• 根據分配給每個簇的資料點重新計算其質心。
• 重複步驟 2-3 直到收斂（即當簇分配不再改變時）。

目標函數

k 均值的目標是最小化每個資料點與其指定的簇質心之間的距離平方和。目標函數可以寫為： $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$在哪裡 $x_i^j$是簇j內的i-th資料點， μj是簇j的質心， N是資料點的總數。

彎頭法

Elbow 方法是一種啟發式方法，用於確定 K 均值聚類中的最佳聚類數。此方法將每個觀測值與其指定質心之間的平方距離總和繪製為聚類數量的函數。圖上的「彎頭」點表示增加額外簇不會導致平方距離總和顯著減少的簇數。

Elbow 方法可以歸納為以下步驟：

• 對一系列 k 值執行 K 均值聚類
• 計算每個 k 值的距離平方和
• 繪製距離平方和作為 k 的函數
• 識別繪圖上的“肘部”點

剪影法

Silhouette 方法是另一種啟發式方法，用於確定 K 均值聚類中的最佳聚類數。此方法透過計算其輪廓係數來衡量每個觀測的聚類分配的品質。 Silhouette 係數的範圍從 -1 到 1，其中值 1 表示觀測值聚類良好，值 -1 表示觀測值分類錯誤。數據點i的輪廓係數計算公式為： $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$其中a(i)是i與其聚類中所有其他資料點之間的平均距離， b(i)是i與所有其他聚類（即具有下一個最近質心的聚類）之間的最小平均距離。整個聚類的輪廓係數是所有資料點的輪廓係數的平均值。

Silhouette方法可以概括為以下步驟：

• 對一系列 k 值執行 K 均值聚類
• 對於每個觀測值，計算輪廓係數
• 計算每個k值的平均輪廓係數
• 將平均輪廓係數繪製為 k 的函數
• 辨識平均輪廓係數最高的k值