0%

K均值算法 K-mean Algorithm

K均值算法(K-mean Algorithm)應該可以說是最簡單的無監督學習算法了,
因為很直觀的關係,所以這篇應該蠻短的。

讓我們開始吧!

物以類聚

想像一下,如果「物以類聚」這件事情為真的話,
那麼一筆一筆的資料是不是也有這樣的特性呢?

$X_{0} \approx X_{1}$

兩筆資料由於特徵相近,所以映射在高維空間中的距離接近。
所以說,這些散布在空間中的點,
如果這堆點,每個都有所屬的類別的話。

很顯然的,那就存在一個類別的中心,
而這個類別的中心,我們常稱作「聚類中心」。

$\mu = \text{聚類中心}$

越靠近這個聚類中心,代表它越屬於這個類別。

K個類別

由於類別不只一個,
老實說,如果類別沒有兩個以上,那也不用去分了。
我們假定存在 $K$ 個類別的話,就有 $K$ 個聚類中心:

$\mu_{0}, \mu_{1}, … , \mu_{K}$

我們可以進一步去定義,
這些每個聚類都是集合,可以用來塞資料點:

$S_{j} = \{ … \}$

如此一來,聚類中心就有定義了:

$\mu_{j} = \frac{1}{|S_{j}|}\sum\limits_{x_{i} \in S_{j}} x_{i}$

聚類中心是「屬於聚類集合的點取平均」而來。

演算法

接下來,是演算法的實際做法:

  • 隨機初始化聚類中心
  • 計算資料點較接近哪個聚類中心
  • 把接近聚類中心的資料點塞進聚類集合
  • 計算新的聚類中心,代替掉舊的
  • 重複 2 ~ 5 步驟,直到不再更新為止

公式的定義:

$S_{j} = \{ x_{i} : \mid x_{i} - \mu_{j}\mid ^{2} \leq \mid x_{i} - \mu_{p}\mid ^{2} \forall p, 1 < p < K \}$

具體的作法就是迭代上式。至於這條公式的解釋:

第 j 個聚類集合,如果符合:
「第 i 筆資料與第 j 個聚類中心的距離」小於等於「第 i 筆資料與第 p 個聚類中心的距離」的話,
那麼第 i 筆資料就屬於第 j 個聚類集合(對於所有的 p 都要嘗試,至於 p 的範圍是 1 ~ K)

這是白話文翻譯。不過為了裝得很厲害的樣子,還是寫符號吧..XD
換言之,這筆資料是不是屬於這個聚類,就要嘗試看看他跟這個聚類中心的距離是不是小於等於其他聚類中心,
如果是則將它擺到這個聚類集合中;反之,則忽略這筆,繼續看下一筆資料。

值得一提的是,通常情況下一筆資料只會被分配到一個聚類集合。
依照這個定義的話,如果 $\mid x_{i} - \mu_{p}\mid ^{2} = |x_{i} - \mu_{q}\mid ^{2}$ 也就是距離一樣的話,
那麼資料點 $x_{i}$ 就會被分配到最後一個算的聚類中心。

形式化

  • $\mu_{j} = random$
  • $S_{j} = \{ x_{i} : \mid x_{i} - \mu_{j}\mid ^{2} \leq \mid x_{i} - \mu_{p}\mid ^{2} \forall p, 1 < p < K \}$
  • $\mu_{j} = \frac{1}{|S_{j}|}\sum\limits_{x_{i} \in S_{j}} x_{i}$
  • $\text{Repeat 2~3}$

以上,就是所有的內容了。來看演示吧!

演示