機器學習筆記031 | 無監督學習演算法——K均值（K-means）

1 無監督演算法要做什麼

在監督學習中，我們是先對數據給定了標籤，然後進行學習。

和這個不同的是，無監督學習（Unsupervised Learning）是沒有給定標籤的。

我們希望通過某些聚類演算法（Clustering Algorithm），自動就從這些數據中找到一些結構。

例如通過對市場的分割，方便精準地進行營銷：

例如對人群進行社交關係分類，自動推薦可能認識的人：

2 K均值（K-means）演算法

2.1 演算法的直觀印象

K均值（K-means）演算法是現在廣泛使用的聚類方法。

例如我們有這樣的數據：

演算法將執行如下步驟，最終收斂到局部最優解：

一、設置聚類中心

二、對附近的數據進行染色歸類

三、移動聚類中心到對應類別數據的均值所在位置

四、重複第二、三步，直到聚類中心不再移動

大概的過程如下圖所示：

2.2 演算法的具體執行

假如對於訓練樣本集 { x(1), x(2), x(3), … ,x(m) } ，我們有 K 個聚類。

我們將每個聚類中心標記為：μ1, μ2, μ3, …,μK 。

對於每一個數據點 x(i) ，其和所有聚類中心 μk 的距離記為：

我們需要找到使得這個距離最小的聚類 k ，然後使用 c(i) = k 進行標記。

例如我們總共有5個聚類中心，點 x(10) 距離每個聚類中心的距離為：

|| x(10) - μ1 || = 21

|| x(10) - μ2 || = 16

|| x(10) - μ3 || = 11

|| x(10) - μ4 || = 6

|| x(10) - μ5 || = 1

那麼就有 c(10) = 5 。

以上就是 2.1 中第二步所執行的過程。

接下來就是對同類數據，求得其均值，並以此作為新的聚類中心，也就是第三步。

例如，除了 c(10) = 5 之外，我們還得到 c(1) = 5 ， c(5) = 5 ， c(6) = 5 ，那麼就有：

2.3 演算法的優化目標

我們之前學習線性回歸、邏輯回歸的時候，都有一個優化目標，就是其代價函數。

對於K均值（K-means）演算法，同樣也有這樣的優化目標：那就是使得各個數據點距離聚類中心的距離總和最小，也就是下圖中所有紅線和藍線加起來的總長度最小。

K均值（K-means）演算法的代價函數是：

我們的優化目標就是 min J( c(1) , … , c(m) , μ1 , … , μK) 。

2.4 隨機初始化

對於這樣的訓練數據：

我們是希望把它們分成三類的：

但有時候，因為初始化的選擇，我們得到的不是全局最優解，而是局部最優解。得到的結果可能是這樣的：

也可能是這樣的：

這樣的分類結果，都不是我們所期望的。

面對這樣的問題，我們應該怎麼辦呢？

多次進行隨機初始化，以及運行 k-means 演算法，最終選擇代價函數最小的一個結果。

這個次數，可以在 50 到 1000 次左右。

隨著運行次數的增加，經常都能找到較好的局部最優解。

當然如果聚類中心數量 K 很大的話，得到的結果可能不會好太多。

2.5 聚類中心數量 K 的選擇

首先我們可以知道的是， K 應該小於訓練樣本數量 m，如果聚類中心的數量比訓練樣本數量還要大，那麼還分類個啥。

那這個數量應該如何選擇呢？

K 的大小，常常是模凌兩可的，例如下面這個圖：

我們既可以認為 K = 4 ：

也可以認為 K = 2 ：

有一個方法叫做肘部法則（Elbow Method），可以給我們提供一個參考。

例如下圖，隨著聚類中心個數 K 的增加，其代價函數計算的結果會下降：

我們說圖中這個位置（之後的下降都不太明顯），就是應該設置的聚類中心個數 K 。

但是有時候，我們繪出的圖形是這樣的：

這樣的情況，我們就找不到比較明顯的肘部。

所以說，肘部法則值得嘗試，但是對其結果不要抱有太大的期待。

對於聚類中心個數 K 的選擇，更多是人工進行的。

這主要看我們運行K均值（K-means）演算法來達到什麼目的。

例如一個 T-shirt 的銷售商，有客戶的一些身高和體重數據：

它可以將這些數據劃分為三組，對應著衣服的大小為 S、M、L：

也可以將這些數據劃分為五組，對應著衣服的大小為 XS、S、M、L、XL：

T-shirt 型號種類應該如何劃分，其實可以從銷售的角度考慮。

例如怎麼樣才能怎樣才能讓顧客購買的最多。

文章提前發布在公眾號：止一之路

推薦閱讀：