????Content：

9.1 Supervised Learning and Unsupervised Learning

9.2 K-means algorithm

9.3 Optimization objective

9.4 Random Initialization

9.5 Choosing the Number of Clusters

9.1 Supervised Learning and Unsupervised Learning

我們已經學習了許多機器學習算法，包括線性回歸，Logistic回歸，神經網絡以及支持向量機。這些算法都有一個共同點，即給出的訓練樣本自身帶有標記。比如，使用線性回歸預測房價時，我們所使用的每一個訓練樣本是一個或多個變量(如面積，樓層等)以及自身帶有的標記即房價。而使用Logistic回歸，神經網絡和支持向量機處理分類問題時，也是利用訓練樣本自身帶有標記即種類，例如進行垃圾郵件分類時是利用已有的垃圾郵件(標記為1)和非垃圾郵件(標記為0)，進行數(shù)字識別時，變量是每個像素點的值，而標記是數(shù)字本身的值。我們把使用帶有標記的訓練樣本進行學習的算法稱為監(jiān)督學習(Supervised Learning)。監(jiān)督學習的訓練樣本可以統(tǒng)一成如下形式，其中x為變量，y為標記。

顯然，現(xiàn)實生活中不是所有數(shù)據(jù)都帶有標記(或者說標記是未知的)。所以我們需要對無標記的訓練樣本進行學習，來揭示數(shù)據(jù)的內在性質及規(guī)律。我們把這種學習稱為無監(jiān)督學習(Unsupervised Learning)。所以，無監(jiān)督學習的訓練樣本如下形式，它僅包含特征量。

圖9-1形象的表示了監(jiān)督學習與無監(jiān)督學習的區(qū)別。圖(1)表示給帶標記的樣本進行分類，分界線兩邊為不同的類(一類為圈，另一類為叉)；圖(2)是基于變量x1和x2對無標記的樣本(表面上看起來都是圈)進行聚類(Clustering)。

圖9-1 一個監(jiān)督學習與無監(jiān)督學習的區(qū)別實例

無監(jiān)督學習也有很多應用，一個聚類的例子是：對于收集到的論文，根據(jù)每個論文的特征量如詞頻，句子長，頁數(shù)等進行分組。聚類還有許多其它應用，如圖9-2所示。一個非聚類的例子是雞尾酒會算法，即從帶有噪音的數(shù)據(jù)中找到有效數(shù)據(jù)(信息)，例如在嘈雜的雞尾酒會你仍然可以注意到有人叫你。所以雞尾酒會算法可以用于語音識別(詳見wikipedia)。

quora上有更多關于監(jiān)督學習與無監(jiān)督學習之間的區(qū)別的討論。

圖9-2 一些聚類的應用

9.2 K-means algorithm

聚類的基本思想是將數(shù)據(jù)集中的樣本劃分為若干個通常是不相交的子集，每個子集稱為一個"簇"(cluster)。劃分后，每個簇可能有對應的概念(性質)，比如根據(jù)頁數(shù)，句長等特征量給論文做簇數(shù)為2的聚類，可能得到一個大部分是包含碩士畢業(yè)論文的簇，另一個大部分是包含學士畢業(yè)論文的簇。

K均值(K-means)算法是一個廣泛使用的用于簇劃分的算法。下面說明K均值算法的步驟：

隨機初始化K個樣本(點)，稱之為簇中心(cluster centroids)；

簇分配: 對于所有的樣本，將其分配給離它最近的簇中心；

移動簇中心：對于每一個簇，計算屬于該簇的所有樣本的平均值，移動簇中心到平均值處；

重復步驟2和3，直到找到我們想要的簇（即優(yōu)化目標，詳解下節(jié)9.3）

圖9-3演示了以特征量個數(shù)和簇數(shù)K均為2的情況。

圖9-3 K均值算法的演示

通過上述描述，下面我們形式化K均值算法。

輸入：

K (number of clusters)

Training set

算法:

Randomly initialize K cluster centroids

Repeat {

for i = 1 to m

for k = 1 to K

}

上述算法中，第一個循環(huán)對應了簇分配的步驟：我們構造向量c，使得c(i)的值等于x(i)所屬簇的索引，即離x(i)最近簇中心的索引。用數(shù)學的方式表示如下：

第二個循環(huán)對應移動簇中心的步驟，即移動簇中心到該簇的平均值處。更數(shù)學的方式表示如下：

其中

如果有一個簇中心沒有分配到一個樣本，我們既可以重新初始化這個簇中心，也可以直接將其去除。

經過若干次迭代后，該算法將會收斂，也就是繼續(xù)迭代不會再影響簇的情況。

在某些應用中，樣本可能比較連續(xù)，看起來沒有明顯的簇劃分，但是我們還是可以用K均值算法將樣本分為K個子集供參考。例如根據(jù)人的身高和體重劃分T恤的大小碼，如圖9-4所示。

圖9-4K-means for non-separated clusters

9.3 Optimization objective

重新描述在K均值算法中使用的變量：

使用這些變量，定義我們的cost function如下：

所以我們的優(yōu)化目標就是

結合9.2節(jié)所描述的算法，可以發(fā)現(xiàn)：

在簇分配步驟中，我們的目標是通過改變

在移動簇中心步驟中，我們的目標通過改變

注意，在K均值算法中，cost function不可能能增加，它應該總是下降的(區(qū)別于梯度下降法)。

9.4 Random Initialization

下面介紹一種值得推薦的初始化簇中心的方法。

確保K < m，也就是確保簇的數(shù)量應該小于樣本數(shù)；

隨機選擇K個訓練樣本；

令K個簇中心

K均值算法可能陷入局部最優(yōu)。為了減少這種情況的發(fā)生，我們可以基于隨機初始化，多次運行K均值算法。所以，算法變成如下形式(以運行100次為例：效率與準確性的tradeoff)

For i = 1 to 100 {

Randomly initialize K-means.

Run K-means. Get

Compute cost function (distortion)

}

Pick clustering that gave lowest cost

9.5 Choosing the Number of Clusters

選擇K的取值通常是主觀的，不明確的。也就是沒有一種方式確保K的某個取值一定優(yōu)于其他取值。但是，有一些方法可供參考。

The elbow method: 畫出代價J關于簇數(shù)K的函數(shù)圖，J值應該隨著K的增加而減小，然后趨于平緩，選擇當J開始趨于平衡時的K的取值。如圖9-5的(1)所示。

但是，通常這條曲線是漸變的，沒有很顯然的"肘部"。如圖9-5的(2)所示。

圖9-5 代價J關于簇數(shù)K的曲線圖

注意：隨著K的增加J應該總是減少的，否則，一種出錯情況可能是K均值陷入了一個糟糕的局部最優(yōu)。

一些其他的方法參見wikipedia。

當然，我們有時應該根據(jù)后續(xù)目的( later/downstream purpose )來確定K的取值。還是以根據(jù)人的身高和體重劃分T恤的大小碼為例，若我們想將T恤大小劃分為S/M/L這3種類型，那么K的取值應為3；若想要劃分為XS/S/M/L/XL這5種類型，那么K的取值應為5。如圖9-6所示。

圖9-6 劃分T恤size的兩種不同情況