原文：http://blog.csdn.net/abcjennifer/article/details/7914952
本欄目（Machine learning）包括單參數(shù)的線性回歸、多參數(shù)的線性回歸、Octave Tutorial、Logistic Regression、Regularization、神經(jīng)網(wǎng)絡、機器學習系統(tǒng)設計、SVM（Support Vector Machines 支持向量機）、聚類、降維、異常檢測、大規(guī)模機器學習等章節(jié)。內(nèi)容大多來自Standford公開課machine learning中Andrew老師的講解和其他書籍的借鑒。（https://class.coursera.org/ml/class/index）
第九講. 聚類——Clustering
===============================
（一）、什么是無監(jiān)督學習？
（二）、KMeans聚類算法
（三）、Cluster問題的(distortion)cost function
（四）、如何選擇初始化時的類中心
（五）、聚類個數(shù)的選擇
=====================================
（一）、什么是無監(jiān)督學習
之前的幾章我們只涉及到有監(jiān)督學習，本章中，我們通過討論另一種Machine learning方式：無監(jiān)督學習。首先呢，我們來看一下有監(jiān)督學習與無監(jiān)督學習的區(qū)別。
給定一組數(shù)據(jù)(input，target)為Z=(X，Y)。
有監(jiān)督學習：最常見的是regression?&?classification。
regression：Y是實數(shù)vector。回歸問題，就是擬合(X，Y)的一條曲線，使得下式cost function L最小。
classification：Y是一個finite number，可以看做類標號。分類問題需要首先給定有l(wèi)abel的數(shù)據(jù)訓練分類器，故屬于有監(jiān)督學習過程。分類問題中，cost function L(X,Y)是X屬于類Y的概率的負對數(shù)。
，其中fi(X)=P(Y=i | X);
無監(jiān)督學習：無監(jiān)督學習的目的是學習一個function f，使它可以描述給定數(shù)據(jù)的位置分布P(Z)。 包括兩種：density estimation?&?clustering.
density estimation就是密度估計，估計該數(shù)據(jù)在任意位置的分布密度
clustering就是聚類，將Z聚集幾類（如K-Means），或者給出一個樣本屬于每一類的概率。由于不需要事先根據(jù)訓練數(shù)據(jù)去train聚類器，故屬于無監(jiān)督學習。
PCA和很多deep learning算法都屬于無監(jiān)督學習。
好了，大家理解了吧，unsupervised learning也就是不帶類標號的機器學習。
練習：
=====================================
（二）、K-Means聚類算法
KMeans是聚類算法的一種，先來直觀的看一下該算法是怎樣聚類的。給定一組數(shù)據(jù)如下圖所示，K-Means算法的聚類流程如圖：
圖中顯示了Kmeans聚類過程，給定一組輸入數(shù)據(jù){x(1),x(2),...,x(n)}和預分類數(shù)k，算法如下：
首先隨機指定k個類的中心U1~Uk，然后迭代地更新該centroid。
其中，C(i)表示第i個數(shù)據(jù)離那個類中心最近，也就是將其判定為屬于那個類，然后將這k各類的中心分別更新為所有屬于這個類的數(shù)據(jù)的平均值。
=====================================
（三）、Cluster問題的(distortion)cost function
在supervised learning中我們曾講過cost function，類似的，在K-means算法中同樣有cost function，我們有時稱其為distortion cost function.
如下圖所示，J(C,U)就是我們要minimize的function.
即最小化所有數(shù)據(jù)與其聚類中心的歐氏距離和。
再看上一節(jié)中我們講過的KMeans算法流程，第一步為固定類中心U，優(yōu)化C的過程：
第二步為優(yōu)化U的過程：
這樣進行迭代，就可以完成cost function J的優(yōu)化。
練習：
這里大家注意，回歸問題中有可能因為學習率設置過大產(chǎn)生隨著迭代次數(shù)增加，cost function反倒增大的情況。但聚類是不會產(chǎn)生這樣的問題的，因為每一次聚類都保證了使J下降，且無學習率做參數(shù)。
=====================================
（四）、如何選擇初始化時的類中心
在上面的kmeans算法中，我們提到可以用randomly的方法選擇類中心，然而有時效果并不是非常好，如下圖所示：
fig.1. original data
對于上圖的這樣一組數(shù)據(jù)，如果我們幸運地初始化類中心如圖2，
fig.2. lucky initialization
fig.3. unfortunate initialization
但如果將數(shù)據(jù)初始化中心選擇如圖3中的兩種情況，就悲劇了！最后的聚類結果cost function也會比較大。針對這個問題，我們提出的solution是，進行不同initialization（50~1000次），每一種initialization的情況分別進行聚類，最后選取cost function J(C,U)最小的作為聚類結果。
=====================================
（五）、聚類個數(shù)的選擇
How to choose the number of clusters? 這應該是聚類問題中一個頭疼的part，比如KMeans算法中K的選擇。本節(jié)就來解決這個問題。
最著名的一個方法就是elbow-method，做圖k-J(cost function)如下：
若做出的圖如上面左圖所示，那么我們就找圖中的elbow位置作為k的選定值，如果像右圖所示并無明顯的elbow點呢，大概就是下圖所示的數(shù)據(jù)分布：
這種情況下需要我們根據(jù)自己的需求來進行聚類，比如Tshirt的size，可以聚成{L,M,S}三類，也可以分為{XL，L，M，S，XS}5類。需要大家具體情況具體分析了~
練習：
==============================================
小結
本章講述了Machine learning中的又一大分支——無監(jiān)督學習，其實大家對無監(jiān)督學習中的clustering問題應該很熟悉了，本章中講到了幾個significant points就是elbow 方法應對聚類個數(shù)的選擇和聚類中心初始化方法，值得大家投入以后的應用。
