資源描述：
《聚類層次聚類 Hierarchical Clustering .doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、聚類(2)——層次聚類HierarchicalClustering分類：MachineLearning2012-06-2311:095708人閱讀評論(9)收藏舉報算法2010聚類系列：·聚類(序)----監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)··聚類(1)----混合高斯模型GaussianMixtureModel·聚類(2)----層次聚類HierarchicalClustering·聚類(3)----譜聚類SpectralClustering--------------------------------?不管是GMM，還是k-mea
2、ns，都面臨一個問題，就是k的個數(shù)如何選?。勘热缭赽ag-of-words模型中，用k-means訓(xùn)練碼書，那么應(yīng)該選取多少個碼字呢？為了不在這個參數(shù)的選取上花費太多時間，可以考慮層次聚類。假設(shè)有N個待聚類的樣本，對于層次聚類來說，基本步驟就是：????1、（初始化）把每個樣本歸為一類，計算每兩個類之間的距離，也就是樣本與樣本之間的相似度；????2、尋找各個類之間最近的兩個類，把他們歸為一類（這樣類的總數(shù)就少了一個）；????3、重新計算新生成的這個類與各個舊類之間的相似度；????4、重復(fù)2和3直到所有樣本點都歸為一類
3、，結(jié)束。?整個聚類過程其實是建立了一棵樹，在建立的過程中，可以通過在第二步上設(shè)置一個閾值，當最近的兩個類的距離大于這個閾值，則認為迭代可以終止。另外關(guān)鍵的一步就是第三步，如何判斷兩個類之間的相似度有不少種方法。這里介紹一下三種：????SingleLinkage：又叫做nearest-neighbor，就是取兩個類中距離最近的兩個樣本的距離作為這兩個集合的距離，也就是說，最近兩個樣本之間的距離越小，這兩個類之間的相似度就越大。容易造成一種叫做Chaining的效果，兩個cluster明明從“大局”上離得比較遠，但是由于其中
4、個別的點距離比較近就被合并了，并且這樣合并之后Chaining效應(yīng)會進一步擴大，最后會得到比較松散的cluster。????CompleteLinkage：這個則完全是SingleLinkage的反面極端，取兩個集合中距離最遠的兩個點的距離作為兩個集合的距離。其效果也是剛好相反的，限制非常大，兩個cluster即使已經(jīng)很接近了，但是只要有不配合的點存在，就頑固到底，老死不相合并，也是不太好的辦法。這兩種相似度的定義方法的共同問題就是指考慮了某個有特點的數(shù)據(jù)，而沒有考慮類內(nèi)數(shù)據(jù)的整體特點。????Average-linkag
5、e：這種方法就是把兩個集合中的點兩兩的距離全部放在一起求一個平均值，相對也能得到合適一點的結(jié)果。????average-linkage的一個變種就是取兩兩距離的中值，與取均值相比更加能夠解除個別偏離樣本對結(jié)果的干擾。這種聚類的方法叫做agglomerativehierarchicalclustering（自下而上，@2013.11.20之前把它寫成自頂而下了，我又誤人子弟了。感謝4樓的網(wǎng)友指正）的，描述起來比較簡單，但是計算復(fù)雜度比較高，為了尋找距離最近/遠和均值，都需要對所有的距離計算個遍，需要用到雙重循環(huán)。另外從算法中
6、可以看出，每次迭代都只能合并兩個子類，這是非常慢的。盡管這么算起來時間復(fù)雜度比較高，但還是有不少地方用到了這種聚類方法，在《數(shù)學(xué)之美》一書的第14章介紹新聞分類的時候，就用到了自頂向下的聚類方法。??????是這樣的，谷歌02年推出了新聞自動分類的服務(wù)，它完全由計算機整理收集各個網(wǎng)站的新聞內(nèi)容，并自動進行分類。新聞的分類中提取的特征是主要是詞頻因為對不同主題的新聞來說，各種詞出現(xiàn)的頻率是不一樣的，比如科技報道類的新聞很可能出現(xiàn)的詞就是安卓、平板、雙核之類的，而軍事類的新聞則更可能出現(xiàn)釣魚島、航母、殲15、殲20這類詞匯。一
7、般對每篇文章提取TF-IDF(詞頻-逆文本頻率值)特征，組成一個高維的特征向量（每一維表示一個詞出現(xiàn)的TF-IDF值），然后采用監(jiān)督學(xué)習(xí)或者非監(jiān)督學(xué)習(xí)的方法對新聞進行分類。在已知一些新聞類別的特征的情況下，采用監(jiān)督學(xué)習(xí)的方法是很OK的。但是在未知的情況下，就采用這種agglomerativehierarchicalclustering進行自動分類。?這種分類方法的動機很有意思。1998年雅讓斯基是某個國際會議的程序委員會主席，需要把提交上來的幾百篇論文發(fā)給各個專家去評審是否錄用。雖然論文的作者自己給定了論文的方向，但方向還
8、是太廣，沒有什么指導(dǎo)意義。雅讓斯基就想到了這個將論文自動分類的方法，由他的學(xué)生費羅里安很快實現(xiàn)了。???????另外有一種聚類方法叫做divisivehierarchicalclustering（自頂而下），過程恰好是相反的，一開始把所有的樣本都歸為一類，然后逐步將他們劃分為更小的單元，直到最后每個樣本
