聚類(2)——層次聚類 Hierarchical Clustering

聚類系列：

• 聚類(序)----監督學習與無監督學習      

• • 聚類(1)----混合高斯模型 Gaussian Mixture Model       

• 聚類(2)----層次聚類 Hierarchical Clustering       

• 聚類(2*)----k-means如何訓練很大的碼書      

• 聚類(3)----譜聚類 Spectral Clustering      

--------------------------------

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

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

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

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

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

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

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

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

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

       Average-linkage：這種方法就是把兩個集合中的點兩兩的距離全部放在一起求一個平均值，相對也能得到合适一點的結果。

       average-linkage的一個變種就是取兩兩距離的中值，與取均值相比更加能夠解除個别偏離樣本對結果的幹擾。

這種聚類的方法叫做agglomerative hierarchical clustering（自下而上，@2013.11.20 之前把它寫成自頂而下了，我又誤人子弟了。感謝4樓的網友指正）的，描述起來比較簡單，但是計算複雜度比較高，為了尋找距離最近/遠和均值，都需要對所有的距離計算個遍，需要用到雙重循環。另外從算法中可以看出，每次疊代都隻能合并兩個子類，這是非常慢的。盡管這麼算起來時間複雜度比較高，但還是有不少地方用到了這種聚類方法，在《數學之美》一書的第14章介紹新聞分類的時候，就用到了自頂向下的聚類方法。

       是這樣的，谷歌02年推出了新聞自動分類的服務，它完全由計算機整理收集各個網站的新聞内容，并自動進行分類。新聞的分類中提取的特征是主要是詞頻因為對不同主題的新聞來說，各種詞出現的頻率是不一樣的， 比如科技報道類的新聞很可能出現的詞就是安卓、平闆、雙核之類的，而軍事類的新聞則更可能出現釣魚島、航母、殲15、殲20這類詞彙。一般對每篇文章提取TF-IDF(詞頻-逆文本頻率值)特征，組成一個高維的特征向量（每一維表示一個詞出現的TF-IDF值），然後采用監督學習或者非監督學習的方法對新聞進行分類。在已知一些新聞類别的特征的情況下，采用監督學習的方法是很OK的。但是在未知的情況下，就采用這種agglomerative hierarchical clustering進行自動分類。 這種分類方法的動機很有意思。1998年雅讓斯基是某個國際會議的程式委員會主席，需要把送出上來的幾百篇論文發給各個專家去評審是否錄用。雖然論文的作者自己給定了論文的方向，但方向還是太廣，沒有什麼指導意義。雅讓斯基就想到了這個将論文自動分類的方法，由他的學生費羅裡安很快實作了。

        另外有一種聚類方法叫做divisive hierarchical clustering（自頂而下），過程恰好是相反的，一開始把所有的樣本都歸為一類，然後逐漸将他們劃分為更小的單元，直到最後每個樣本都成為一類。在這個疊代的過程中通過對劃分過程中定義一個松散度，當松散度最小的那個類的結果都小于一個門檻值，則認為劃分可以終止。這種方法用的不普遍，原文也沒有做更多介紹。

        由于這種層次結構，普通的k-means也被稱為一種flat clustering。

[email protected] 

        層次聚類如何使用呢，借助matlab就可以實作了，十分簡單。首先需要構造距離矩陣Y。這是一個對稱矩陣，且對角線元素為0（自己與自己的距離為0）。假設所有樣本儲存為X，則通過：

[plain]  view plain  copy  print ?

1. Y=pdist(X);  
2. Y=squareform(Y);  

      就能夠得到距離矩陣。注意pdist可以選擇距離度量的方法，例如歐式距離，内積或者餘弦夾角。在很多時候這個參數十分重要。

      然後通過Z=linkage(Y)就能産生層次聚類的樹結構了。

[plain]  view plain  copy  print ?

1. Z=linkage(Y)；  

      Z的結果描述起來需要借助實際的例子，大家可以通過matlab help檢視，并結合實際結果領悟一下。這棵樹可以通過以下指令可視化：

[plain]  view plain  copy  print ?

1. dendrogram(Z)   

      這樣就完成了一次層次聚類了（雖然我們什麼都沒有做

）

---------------------------

jiang1st2010

原文位址：http://blog.csdn.net/jiang1st2010/article/details/7685809