無監督核心聚類演算法

引言

開始講解演算法之前，我們先來看一個例子：假設有n種中藥混在一起，我們想把這堆藥材放在m個葯匣中，且m

現在，我們可以開始討論演算法了。

第一種 K-means

現在，我們暫時不去考慮原始數據的形式，假設我們已經講其映射到了一個歐式空間上了，為了方便，我們用二維空間來展示，如下圖所示：

圖1 散點圖

單純用肉眼看，我們的大腦很快就能判斷出，這些散點大致屬於三個集群，其中兩個很緊湊，一個很鬆散。我們的目的就是區分這些散點從屬於哪個集群，同樣為了方便，我們把三個集群圖上不同的顏色，如下圖所示：

圖2 被標註顏色的散點圖

人的大腦可以掃一眼就分辨出的集群，計算機卻不會這麼輕易做到，它無法僅通過形狀就「大致看出來」，這就需要用到我們馬上要講的演算法K-means了。K-means基於一個假設：對於每一個集群（cluster），我們都可以選出一個中心點（center），使得該cluster中的所有點到該cluster中心點的距離小於到其他cluster中心點的距離。當然，實際情況可能無法總是滿足這個假設，但這是我們能達到的最好結果，而那些誤差通常是固有存在的或者問題本身的不可分性造成的。所以，我們暫且認為這個假設是合理的。

在此基礎上，我們來推導K-means的目標函數：假設有N個點，要分為K個cluster，K-means要做的就是最小化：

其中，rnk在數據點n被歸類到clusterk時為1，否則為0。直接尋找rnk和μk來最小化J並不容易，不過我們可以採用迭代的辦法，先固定μk，選擇最優的rnk。可以看出，只要將數據點歸類到離他最近的那個中心就能保證J最小。下一步則固定rnk，再求最優的μk。將J對uk求導並令導數等於0，很容易得到J最小的時候μk應該滿足：

也就是uk的值應該是cluster k中所有數據點的平均值。由於每一次迭代都是為了取到更小的J，所有J會不斷減小直到不變。這個迭代方法保證可k-means最終會達到一個極小值。

此處要做個說明，K-means不能保證總是能收斂到全局最優解，這與初值的選擇有很大關係。因此在實際操作中，我們通常會多次選擇初值跑K-means，並取其中最好的一次結果。K-means結束的判斷依據可以是迭代到了最大次數，或者是J的減小已經小於我們設定的閾值。

總結一下，在眾多聚類方法中，K-means屬於最簡單的一類。其大致思想就是把數據分為多個堆，每個堆就是一類。每個堆都有一個聚類中心（學習的結果就是獲得這k個聚類中心），這個中心就是這個類中所有數據的均值，而這個堆中所有的點到該類的聚類中心都小於到其他類的聚類中心（分類的過程就是將未知數據對這k個聚類中心進行比較的過程，離誰近就是誰）。其實K-means算的上最直觀、最方便理解的一種聚類方式了，原則就是把最像的數據分在一起，而「像」這個定義由我們來完成（類比把藥材按照什麼特徵裝入葯匣）。

下面，我們來介紹另外一種比較流行的聚類演算法——高斯混合模型GMM（Gaussian Mixture Model）。GMM和K-means很相似，區別僅在於GMM中，我們採用的是概率模型P(Y|X)，也就是我們通過未知數據X可以獲得Y取值的一個概率分布，我們訓練後模型得到的輸出不是一個具體的值，而是一系列值的概率。然後我們可以選取概率最大的那個類作為判決對象，屬於軟分類soft assignment（對比與非概率模型Y=f(X)的硬分類hard assignment）。

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

圖3 兩個高斯分布

得到概率有什麼好處呢？拿下圖中的兩個高斯分布來說，(2.5,0) 屬於其重合區域，它由兩個分布產生的概率相等，你沒辦法說它屬於那一邊。這時，你只能猜測，選擇2好像更好一點，於是你得出(2.5,0)屬於左邊的概率是51%，屬於右邊的概率是49%。然後，在用其他辦法分別到底屬於哪一邊。可以想像，如果採用硬分類，分類的相似度結果要麼0要麼1，沒有「多像」這個概念，所以，不方便多模型融合（繼續判斷）。

混合高斯模型的定義為：

其中K為模型的個數，πk為第k個高斯的權重，p(x|k)則為第k個高斯的概率密度函數，其均值為μk，方差為σk。我們對此概率密度的估計就是要求πk、μk和σk各個變數。求解得到的最終求和式的各項結果就分別代表樣本x屬於各個類的概率。

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

也就是最大化log - likelihood function，完整形式則為：

一般用來做參數估計的時候，我們都是通過對待求變數進行求導來求極值，在上式中，log函數中又有求和，若用求導的方法算，方程組將會非常複雜，所以我們不直接求導，而是採用EM（Expection Maximization）演算法。這與K-means的迭代法相似，都是初始化各個高斯模型的參數，然後用迭代的方式，直至波動很小，近似達到極值。

總結一下，用GMM的優點是投影后樣本點不是得到一個確定的分類標記，而是得到每個類的概率，這是一個重要信息。GMM每一步迭代的計算量比較大，大於k-means。GMM的求解辦法基於EM演算法，因此有可能陷入局部極值，這與初始值的選取十分相關。

不管是K-means，還是GMM，都面臨一個問題，那就是k取幾比較合適。比如在bag-of-words模型中，用k-means訓練碼書，那麼應該選取多少個碼字呢？為了不在這個參數的選取上花費太多時間，可以考慮層次聚類。

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

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

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

3. 重新計算新生成的這個類與各箇舊類之間的相似度；

4. 重複2和3直到所有樣本點都歸為一類，結束。

整個聚類過程其實是建立了一棵樹，在建立的過程中，可以通過在第二步上設置一個閾值，當最近的兩個類的距離大於這個閾值，則認為迭代可以終止。另外關鍵的一步就是第三步，如何判斷兩個類之間的相似度有很多種方法。這裡介紹一下三種：

· Single Linkage：又叫做nearest-neighbor ，就是取兩個類中距離最近的兩個樣本的距離作為這兩個集合的距離，也就是說，最近兩個樣本之間的距離越小，這兩個類之間的相似度就越大。容易造成一種叫做Chaining 的效果，兩個cluster 明明從「大局」上離得比較遠，但是由於其中個別的點距離比較近就被合併了，並且這樣合併之後Chaining 效應會進一步擴大，最後會得到比較鬆散的cluster 。

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

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

以上這幾種聚類的方法叫做agglomerative hierarchical clustering（自下而上），描述起來比較簡單，但是計算複雜度比較高，為了尋找距離最近/遠和均值，都需要對所有的距離計算個遍，需要用到雙重循環。另外從演算法中可以看出，每次迭代都只能合併兩個子類，非常慢。

另外有一種聚類方法叫做divisive hierarchical clustering（自上而下），過程恰好是相反的，一開始把所有的樣本都歸為一類，然後逐步將他們劃分為更小的單元，直到最後每個樣本都成為一類。在這個迭代的過程中通過對劃分過程中定義一個鬆散度，當鬆散度最小的那個類的結果都小於一個閾值，則認為劃分可以終止。