????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

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

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

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

圖9-1 一個(gè)監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)的區(qū)別實(shí)例

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

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

圖9-2 一些聚類的應(yīng)用

9.2 K-means algorithm

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

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

隨機(jī)初始化K個(gè)樣本(點(diǎn))，稱之為簇中心(cluster centroids)；

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

移動(dòng)簇中心：對(duì)于每一個(gè)簇，計(jì)算屬于該簇的所有樣本的平均值，移動(dòng)簇中心到平均值處；

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

圖9-3演示了以特征量個(gè)數(shù)和簇?cái)?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

}

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

第二個(gè)循環(huán)對(duì)應(yīng)移動(dòng)簇中心的步驟，即移動(dòng)簇中心到該簇的平均值處。更數(shù)學(xué)的方式表示如下：

其中

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

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

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

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

9.3 Optimization objective

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

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

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

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

在簇分配步驟中，我們的目標(biāo)是通過改變

在移動(dòng)簇中心步驟中，我們的目標(biāo)通過改變

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

9.4 Random Initialization

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

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

隨機(jī)選擇K個(gè)訓(xùn)練樣本；

令K個(gè)簇中心

K均值算法可能陷入局部最優(yōu)。為了減少這種情況的發(fā)生，我們可以基于隨機(jī)初始化，多次運(yùn)行K均值算法。所以，算法變成如下形式(以運(yùn)行100次為例：效率與準(zhǔn)確性的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的某個(gè)取值一定優(yōu)于其他取值。但是，有一些方法可供參考。

The elbow method: 畫出代價(jià)J關(guān)于簇?cái)?shù)K的函數(shù)圖，J值應(yīng)該隨著K的增加而減小，然后趨于平緩，選擇當(dāng)J開始趨于平衡時(shí)的K的取值。如圖9-5的(1)所示。

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

圖9-5 代價(jià)J關(guān)于簇?cái)?shù)K的曲線圖

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

一些其他的方法參見wikipedia。

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

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