這章節(jié)主要介紹機器學習傳統(tǒng)算法的非監(jiān)督學習的部分。是否有監(jiān)督（supervised）衙伶，就看輸入數據是否有標簽（label）祈坠。輸入數據有標簽，則為有監(jiān)督學習矢劲，沒標簽則為無監(jiān)督學習赦拘。

1. ?K-means

K-Means算法主要解決的問題如下圖所示。我們可以看到芬沉，在圖的左邊有一些點躺同，我們用肉眼可以看出來有四個點群，但是我們怎么通過計算機程序找出這幾個點群來呢丸逸？于是就出現(xiàn)了我們的K-Means算法蹋艺。

1.1 算法

然后，K-Means的算法如下：

1. 隨機在圖中取K（這里K=2）個種子點椭员。

2. 然后對圖中的所有點求到這K個種子點的距離车海，假如點Pi離種子點Si最近，那么Pi屬于Si點群隘击。（上圖中侍芝，我們可以看到A，B屬于上面的種子點埋同，C州叠，D，E屬于下面中部的種子點）

3. 接下來凶赁，我們要移動種子點到屬于他的“點群”的中心逆甜。（見圖上的第三步）

4. 然后重復第2）和第3）步，直到致板，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了A，B素征，C御毅，下面的種子點聚合了D，E）今豆。

1.2 求點群中心的算法

一般來說柔袁，求點群中心點的算法你可以很簡的使用各個點的X/Y坐標的平均值晚凿。不過，我這里想告訴大家另三個求中心點的的公式：

1.3 K-means的改進

K-Means主要有兩個最重大的缺陷——都和初始值有關：

(1) K是事先給定的瘦馍，這個K值的選定是非常難以估計的歼秽。很多時候，事先并不知道給定的數據集應該分成多少個類別才最合適情组。（ISODATA算法通過類的自動合并和分裂燥筷，得到較為合理的類型數目K）。

(2) K-Means算法需要用初始隨機種子點來搞院崇，這個隨機種子點太重要肆氓，不同的隨機種子點會有得到完全不同的結果。（K-Means++算法可以用來解決這個問題底瓣，其可以有效地選擇初始點）谢揪。

我在這里重點說一下K-Means++算法步驟：

先從我們的數據庫隨機挑個隨機點當“種子點”。

對于每個點捐凭，我們都計算其和最近的一個“種子點”的距離D(x)并保存在一個數組里拨扶，然后把這些距離加起來得到Sum(D(x))。

然后茁肠，再取一個隨機值患民，用權重的方式來取計算下一個“種子點”。這個算法的實現(xiàn)是垦梆，先取一個能落在Sum(D(x))中的隨機值Random匹颤，然后用Random?-=?D(x)仅孩，直到其<=0，此時的點就是下一個“種子點”印蓖。

重復第（2）和第（3）步直到所有的K個種子點都被選出來辽慕。

進行K-Means算法。

2. ?高斯混合模型(Gaussian mixture model)

GMM和k-means其實是十分相似的赦肃，區(qū)別僅僅在于對GMM來說鼻百，我們引入了概率。說到這里摆尝，我想先補充一點東西。統(tǒng)計學習的模型有兩種因悲，一種是概率模型堕汞，一種是非概率模型。所謂概率模型晃琳，就是指我們要學習的模型的形式是P(Y|X)讯检，這樣在分類的過程中，我們通過未知數據X可以獲得Y取值的一個概率分布卫旱，也就是訓練后模型得到的輸出不是一個具體的值人灼，而是一系列值的概率（對應于分類問題來說，就是對應于各個不同的類的概率）顾翼，然后我們可以選取概率最大的那個類作為判決對象（算軟分類soft assignment）投放。而非概率模型，就是指我們學習的模型是一個決策函數Y=f(X)适贸，輸入數據X是多少就可以投影得到唯一的一個Y灸芳，就是判決結果（算硬分類hard assignment）。

回到GMM拜姿，學習的過程就是訓練出幾個概率分布烙样，所謂混合高斯模型就是指對樣本的概率密度分布進行估計，而估計的模型是幾個高斯模型加權之和（具體是幾個要在模型訓練前建立好）蕊肥。每個高斯模型就代表了一個類（一個Cluster）谒获。對樣本中的數據分別在幾個高斯模型上投影，就會分別得到在各個類上的概率壁却。然后我們可以選取概率最大的類所為判決結果批狱。

得到概率有什么好處呢？我們知道人很聰明展东，就是在于我們會用各種不同的模型對觀察到的事物和現(xiàn)象做判決和分析精耐。當你在路上發(fā)現(xiàn)一條狗的時候，你可能光看外形好像鄰居家的狗琅锻，又更像一點點女朋友家的狗卦停，你很難判斷向胡，所以從外形上看，用軟分類的方法惊完，是女朋友家的狗概率51%僵芹，是鄰居家的狗的概率是49%，屬于一個易混淆的區(qū)域內小槐，這時你可以再用其它辦法進行區(qū)分到底是誰家的狗拇派。而如果是硬分類的話，你所判斷的就是女朋友家的狗凿跳，沒有“多像”這個概念件豌，所以不方便多模型的融合。

(1) 高斯混合模型

從中心極限定理的角度上看控嗜，把混合模型假設為高斯的是比較合理的茧彤，當然也可以根據實際數據定義成任何分布的Mixture Model,不過定義為高斯的在計算上有一些方便之處，另外疆栏，理論上可以通過增加Model的個數曾掂，用GMM近似任何概率分布。

混合高斯模型的定義為：

在做參數估計的時候壁顶，常采用的方法是最大似然珠洗。最大似然法就是使樣本點在估計的概率密度函數上的概率值最大。由于概率值一般都很小若专，N很大的時候這個連乘的結果非常小许蓖，容易造成浮點數下溢。所以我們通常取log调衰，將目標改寫成：

一般用來做參數估計的時候蛔糯，我們都是通過對待求變量進行求導來求極值，在上式中窖式，log函數中又有求和蚁飒，你想用求導的方法算的話方程組將會非常復雜，所以我們不好考慮用該方法求解（沒有閉合解）萝喘』绰撸可以采用的求解方法是EM算法——將求解分為兩步：

第一步是假設我們知道各個高斯模型的參數（可以初始化一個，或者基于上一步迭代結果）阁簸，去估計每個高斯模型的權值爬早；

第二步是基于估計的權值，回過頭再去確定高斯模型的參數启妹。重復這兩個步驟筛严，直到波動很小，近似達到極值（注意這里是個極值不是最值饶米，EM算法會陷入局部最優(yōu)）桨啃。

具體表達如下：

3. 層次聚類(Hierarchical Clustering)

不管是GMM车胡，還是k-means，都面臨一個問題照瘾，就是k的個數如何選刃偌？比如在bag-of-words模型中析命，用k-means訓練碼書主卫，那么應該選取多少個碼字呢？為了不在這個參數的選取上花費太多時間鹃愤，可以考慮層次聚類簇搅。

3.1 層次聚類算法

假設有N個待聚類的樣本，對于層次聚類來說软吐，基本步驟就是：

1瘩将、（初始化）把每個樣本歸為一類，計算每兩個類之間的距離关噪，也就是樣本與樣本之間的相似度；

2乌妙、尋找各個類之間最近的兩個類使兔，把他們歸為一類（這樣類的總數就少了一個）；

3藤韵、重新計算新生成的這個類與各個舊類之間的相似度虐沥；

4、重復2和3直到所有樣本點都歸為一類泽艘，結束欲险。

整個聚類過程其實是建立了一棵樹，在建立的過程中匹涮，可以通過在第二步上設置一個閾值天试，當最近的兩個類的距離大于這個閾值，則認為迭代可以終止然低。另外關鍵的一步就是第三步喜每，如何判斷兩個類之間的相似度有不少種方法。

3.2 相似度計算

1. SingleLinkage：又叫做 nearest-neighbor 雳攘，就是取兩個類中距離最近的兩個樣本的距離作為這兩個集合的距離带兜，也就是說，最近兩個樣本之間的距離越小吨灭，這兩個類之間的相似度就越大刚照。容易造成一種叫做 Chaining 的效果，兩個 cluster 明明從“大局”上離得比較遠喧兄，但是由于其中個別的點距離比較近就被合并了无畔，并且這樣合并之后 Chaining 效應會進一步擴大啊楚，最后會得到比較松散的 cluster 。

2. CompleteLinkage：這個則完全是 Single Linkage 的反面極端檩互，取兩個集合中距離最遠的兩個點的距離作為兩個集合的距離特幔。其效果也是剛好相反的，限制非常大闸昨，兩個 cluster 即使已經很接近了蚯斯，但是只要有不配合的點存在，就頑固到底饵较，老死不相合并拍嵌，也是不太好的辦法。這兩種相似度的定義方法的共同問題就是指考慮了某個有特點的數據循诉，而沒有考慮類內數據的整體特點横辆。

3. Average-linkage：這種方法就是把兩個集合中的點兩兩的距離全部放在一起求一個平均值，相對也能得到合適一點的結果茄猫。average-linkage的一個變種就是取兩兩距離的中值狈蚤，與取均值相比更加能夠解除個別偏離樣本對結果的干擾。

4. Centroid linkage： 定義類間距離為類間質心的距離划纽，質心為類中所有成員? ? ? 的原始數據的均值脆侮。

3.3 自頂而下／自下而上

上面介紹的這種聚類的方法叫做agglomerative hierarchical clustering（自下而上）的，描述起來比較簡單勇劣，但是計算復雜度比較高靖避，為了尋找距離最近/遠和均值，都需要對所有的距離計算個遍比默，需要用到雙重循環(huán)幻捏。另外從算法中可以看出，每次迭代都只能合并兩個子類命咐，這是非常慢的篡九。

另外有一種聚類方法叫做divisivehierarchical clustering（自頂而下），過程恰好是相反的醋奠，一開始把所有的樣本都歸為一類瓮下，然后逐步將他們劃分為更小的單元，直到最后每個樣本都成為一類钝域。在這個迭代的過程中通過對劃分過程中定義一個松散度讽坏，當松散度最小的那個類的結果都小于一個閾值，則認為劃分可以終止例证。這種方法用的不普遍路呜。

4. 三種方法對比

(1) K-means

優(yōu)點：簡單、時間復雜度、空間復雜度低

缺點：隨機初始化的中心點對結果影響很大胀葱；hold不住族之間的size或密度差別較大的情況漠秋，因為K-means的目標函數是距離和，導致最后必然出來一種很社會主義的結果抵屿。

(2) 層次聚類

優(yōu)點：可解釋性好（如當需要創(chuàng)建一種分類法時）庆锦；還有些研究表明這些算法能產生高質量的聚類，也會應用在上面說的先取K比較大的K-means后的合并階段轧葛；還有對于K-means不能解決的非球形族就可以解決了搂抒。

缺點：時間復雜度高啊，o(m^3)尿扯，改進后的算法也有o(m^2lgm)求晶，m為點的個數；貪心算法的缺點衷笋，一步錯步步錯芳杏；同K-means，difficulty handling different sized clusters and convex shapes辟宗。

(3) 高斯混合模型

優(yōu)點：投影后樣本點不是得到一個確定的分類標記爵赵，而是得到每個類的概率，這是一個重要信息泊脐。

缺點：GMM每一步迭代的計算量比較大空幻，大于k-means。GMM的求解辦法基于EM算法晨抡，因此有可能陷入局部極值氛悬，這和初始值的選取十分相關了则剃。