無監督，分類

K-Means 演算法分為三個步驟：

  • 初始化 Initialization
  • 分配 Assignment
  • 更新 Update

分配和更新兩個步驟會不斷重複，直到收斂

相關概念

簇

K-Means 的目標就是將資料分為 K 個類別，也就是 K 個簇

質心

每個簇都有一個質心，表示該類別資料的平均水平
是和一般資料等長的向量，一般用簇中資料的均值表示

初始化

隨機初始化

指定 K 個簇，並把資料隨機分配給一個簇

如果最後有空的簇，則要從其他簇（至少要兩筆資料）中取一筆資料分給它

隨機初始化後要直接進行「更新」操作，來計算每個簇的質心

Forgy 初始化

先設置 K 個只含一筆資料的簇，然後執行「分配」操作

更具體一些，在創建好一個簇之後（結構體內容為空），隨機為該簇指定一筆未用過的資料，並令其為該簇的質心

分配

遍歷所有資料，根據資料與每個簇質心的距離，把每筆資料分到最接近的簇上。

一般採用歐氏距離

要記錄是否有資料從一個簇轉移到另一個簇上，作為演算法的終止條件

更新

緊跟在「分配」後面的操作，計算每個簇新的質心