原文:http://blog.csdn.net/abcjennifer/article/details/7914952
本欄目(Machine learning)包括單參數(shù)的線(xiàn)性回歸、多參數(shù)的線(xiàn)性回歸空幻、Octave Tutorial烁峭、Logistic Regression、Regularization秕铛、神經(jīng)網(wǎng)絡(luò)约郁、機(jī)器學(xué)習(xí)系統(tǒng)設(shè)計(jì)、SVM(Support Vector Machines 支持向量機(jī))但两、聚類(lèi)鬓梅、降維、異常檢測(cè)谨湘、大規(guī)模機(jī)器學(xué)習(xí)等章節(jié)绽快。內(nèi)容大多來(lái)自Standford公開(kāi)課machine learning中Andrew老師的講解和其他書(shū)籍的借鑒。(https://class.coursera.org/ml/class/index)
第九講. 聚類(lèi)——Clustering
===============================
(一)紧阔、什么是無(wú)監(jiān)督學(xué)習(xí)坊罢?
(二)、KMeans聚類(lèi)算法
(三)擅耽、Cluster問(wèn)題的(distortion)cost function
(四)活孩、如何選擇初始化時(shí)的類(lèi)中心
(五)、聚類(lèi)個(gè)數(shù)的選擇
=====================================
(一)乖仇、什么是無(wú)監(jiān)督學(xué)習(xí)
之前的幾章我們只涉及到有監(jiān)督學(xué)習(xí)诱鞠,本章中挎挖,我們通過(guò)討論另一種Machine learning方式:無(wú)監(jiān)督學(xué)習(xí)。首先呢航夺,我們來(lái)看一下有監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)的區(qū)別蕉朵。
給定一組數(shù)據(jù)(input,target)為Z=(X阳掐,Y)始衅。
有監(jiān)督學(xué)習(xí):最常見(jiàn)的是regression?&?classification。
regression:Y是實(shí)數(shù)vector缭保⊙凑ⅲ回歸問(wèn)題,就是擬合(X艺骂,Y)的一條曲線(xiàn)诸老,使得下式cost function L最小。
classification:Y是一個(gè)finite number钳恕,可以看做類(lèi)標(biāo)號(hào)别伏。分類(lèi)問(wèn)題需要首先給定有l(wèi)abel的數(shù)據(jù)訓(xùn)練分類(lèi)器旋膳,故屬于有監(jiān)督學(xué)習(xí)過(guò)程诱担。分類(lèi)問(wèn)題中,cost function L(X,Y)是X屬于類(lèi)Y的概率的負(fù)對(duì)數(shù)舞虱。
睦番,其中fi(X)=P(Y=i | X);
無(wú)監(jiān)督學(xué)習(xí):無(wú)監(jiān)督學(xué)習(xí)的目的是學(xué)習(xí)一個(gè)function f类茂,使它可以描述給定數(shù)據(jù)的位置分布P(Z)。 包括兩種:density estimation?&?clustering.
density estimation就是密度估計(jì)托嚣,估計(jì)該數(shù)據(jù)在任意位置的分布密度
clustering就是聚類(lèi)巩检,將Z聚集幾類(lèi)(如K-Means),或者給出一個(gè)樣本屬于每一類(lèi)的概率示启。由于不需要事先根據(jù)訓(xùn)練數(shù)據(jù)去train聚類(lèi)器碴巾,故屬于無(wú)監(jiān)督學(xué)習(xí)。
PCA和很多deep learning算法都屬于無(wú)監(jiān)督學(xué)習(xí)丑搔。
好了厦瓢,大家理解了吧,unsupervised learning也就是不帶類(lèi)標(biāo)號(hào)的機(jī)器學(xué)習(xí)啤月。
練習(xí):
=====================================
(二)煮仇、K-Means聚類(lèi)算法
KMeans是聚類(lèi)算法的一種,先來(lái)直觀的看一下該算法是怎樣聚類(lèi)的谎仲。給定一組數(shù)據(jù)如下圖所示浙垫,K-Means算法的聚類(lèi)流程如圖:
圖中顯示了Kmeans聚類(lèi)過(guò)程,給定一組輸入數(shù)據(jù){x(1),x(2),...,x(n)}和預(yù)分類(lèi)數(shù)k,算法如下:
首先隨機(jī)指定k個(gè)類(lèi)的中心U1~Uk夹姥,然后迭代地更新該centroid杉武。
其中,C(i)表示第i個(gè)數(shù)據(jù)離那個(gè)類(lèi)中心最近辙售,也就是將其判定為屬于那個(gè)類(lèi)轻抱,然后將這k各類(lèi)的中心分別更新為所有屬于這個(gè)類(lèi)的數(shù)據(jù)的平均值。
=====================================
(三)旦部、Cluster問(wèn)題的(distortion)cost function
在supervised learning中我們?cè)v過(guò)cost function祈搜,類(lèi)似的,在K-means算法中同樣有cost function士八,我們有時(shí)稱(chēng)其為distortion cost function.
如下圖所示容燕,J(C,U)就是我們要minimize的function.
即最小化所有數(shù)據(jù)與其聚類(lèi)中心的歐氏距離和。
再看上一節(jié)中我們講過(guò)的KMeans算法流程婚度,第一步為固定類(lèi)中心U蘸秘,優(yōu)化C的過(guò)程:
第二步為優(yōu)化U的過(guò)程:
這樣進(jìn)行迭代,就可以完成cost function J的優(yōu)化蝗茁。
練習(xí):
這里大家注意醋虏,回歸問(wèn)題中有可能因?yàn)閷W(xué)習(xí)率設(shè)置過(guò)大產(chǎn)生隨著迭代次數(shù)增加,cost function反倒增大的情況评甜。但聚類(lèi)是不會(huì)產(chǎn)生這樣的問(wèn)題的,因?yàn)槊恳淮尉垲?lèi)都保證了使J下降仔涩,且無(wú)學(xué)習(xí)率做參數(shù)忍坷。
=====================================
(四)、如何選擇初始化時(shí)的類(lèi)中心
在上面的kmeans算法中熔脂,我們提到可以用randomly的方法選擇類(lèi)中心佩研,然而有時(shí)效果并不是非常好,如下圖所示:
fig.1. original data
對(duì)于上圖的這樣一組數(shù)據(jù)霞揉,如果我們幸運(yùn)地初始化類(lèi)中心如圖2旬薯,
fig.2. lucky initialization
fig.3. unfortunate initialization
但如果將數(shù)據(jù)初始化中心選擇如圖3中的兩種情況,就悲劇了适秩!最后的聚類(lèi)結(jié)果cost function也會(huì)比較大绊序。針對(duì)這個(gè)問(wèn)題,我們提出的solution是秽荞,進(jìn)行不同initialization(50~1000次)骤公,每一種initialization的情況分別進(jìn)行聚類(lèi),最后選取cost function J(C,U)最小的作為聚類(lèi)結(jié)果扬跋。
=====================================
(五)阶捆、聚類(lèi)個(gè)數(shù)的選擇
How to choose the number of clusters? 這應(yīng)該是聚類(lèi)問(wèn)題中一個(gè)頭疼的part,比如KMeans算法中K的選擇。本節(jié)就來(lái)解決這個(gè)問(wèn)題洒试。
最著名的一個(gè)方法就是elbow-method倍奢,做圖k-J(cost function)如下:
若做出的圖如上面左圖所示,那么我們就找圖中的elbow位置作為k的選定值垒棋,如果像右圖所示并無(wú)明顯的elbow點(diǎn)呢卒煞,大概就是下圖所示的數(shù)據(jù)分布:
這種情況下需要我們根據(jù)自己的需求來(lái)進(jìn)行聚類(lèi),比如Tshirt的size捕犬,可以聚成{L,M,S}三類(lèi)跷坝,也可以分為{XL,L碉碉,M柴钻,S,XS}5類(lèi)垢粮。需要大家具體情況具體分析了~
練習(xí):
==============================================
小結(jié)
本章講述了Machine learning中的又一大分支——無(wú)監(jiān)督學(xué)習(xí)贴届,其實(shí)大家對(duì)無(wú)監(jiān)督學(xué)習(xí)中的clustering問(wèn)題應(yīng)該很熟悉了,本章中講到了幾個(gè)significant points就是elbow 方法應(yīng)對(duì)聚類(lèi)個(gè)數(shù)的選擇和聚類(lèi)中心初始化方法蜡吧,值得大家投入以后的應(yīng)用毫蚓。