????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ī)處理分類問(wèn)題時(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)記(或者說(shuō)標(biāo)記是未知的)。所以我們需要對(duì)無(wú)標(biāo)記的訓(xùn)練樣本進(jìn)行學(xué)習(xí),來(lái)揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律。我們把這種學(xué)習(xí)稱為無(wú)監(jiān)督學(xué)習(xí)(Unsupervised Learning)。所以,無(wú)監(jiān)督學(xué)習(xí)的訓(xùn)練樣本如下形式,它僅包含特征量。
圖9-1形象的表示了監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)的區(qū)別。圖(1)表示給帶標(biāo)記的樣本進(jìn)行分類,分界線兩邊為不同的類(一類為圈,另一類為叉);圖(2)是基于變量x1和x2對(duì)無(wú)標(biāo)記的樣本(表面上看起來(lái)都是圈)進(jìn)行聚類(Clustering)。
圖9-1 一個(gè)監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)的區(qū)別實(shí)例
無(wú)監(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í)與無(wú)監(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è)廣泛使用的用于簇劃分的算法。下面說(shuō)明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均值算法的演示
通過(guò)上述描述,下面我們形式化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è)簇中心沒(méi)有分配到一個(gè)樣本,我們既可以重新初始化這個(gè)簇中心,也可以直接將其去除。
經(jīng)過(guò)若干次迭代后,該算法將會(huì)收斂,也就是繼續(xù)迭代不會(huì)再影響簇的情況。
在某些應(yīng)用中,樣本可能比較連續(xù),看起來(lái)沒(méi)有明顯的簇劃分,但是我們還是可以用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)是通過(guò)改變
在移動(dòng)簇中心步驟中,我們的目標(biāo)通過(guò)改變
注意,在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的取值通常是主觀的,不明確的。也就是沒(méi)有一種方式確保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)所示。
但是,通常這條曲線是漸變的,沒(méi)有很顯然的"肘部"。如圖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 )來(lái)確定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的兩種不同情況
-
機(jī)器學(xué)習(xí)算法
+關(guān)注
關(guān)注
2文章
47瀏覽量
6441 -
無(wú)監(jiān)督學(xué)習(xí)
+關(guān)注
關(guān)注
1文章
16瀏覽量
2749
原文標(biāo)題:Stanford機(jī)器學(xué)習(xí)筆記-9. 聚類(Clustering)
文章出處:【微信號(hào):AI_shequ,微信公眾號(hào):人工智能愛好者社區(qū)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論