第一種 K-means

現(xiàn)在，我們暫時(shí)不去考慮原始數(shù)據(jù)的形式，假設(shè)我們已經(jīng)講其映射到了一個(gè)歐式空間上了，為了方便，我們用二維空間來展示，如下圖所示：

圖1 散點(diǎn)圖

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

圖2 被標(biāo)注顏色的散點(diǎn)圖

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

在此基礎(chǔ)上，我們來推導(dǎo)K-means的目標(biāo)函數(shù)：假設(shè)有N個(gè)點(diǎn)，要分為K個(gè)cluster，K-means要做的就是最小化：

其中，rnk在數(shù)據(jù)點(diǎn)n被歸類到clusterk時(shí)為1，否則為0。直接尋找rnk和μk來最小化J并不容易，不過我們可以采用迭代的辦法，先固定μk，選擇最優(yōu)的rnk。可以看出，只要將數(shù)據(jù)點(diǎn)歸類到離他最近的那個(gè)中心就能保證J最小。下一步則固定rnk，再求最優(yōu)的μk。將J對uk求導(dǎo)并令導(dǎo)數(shù)等于0，很容易得到J最小的時(shí)候μk應(yīng)該滿足：

也就是uk的值應(yīng)該是cluster k中所有數(shù)據(jù)點(diǎn)的平均值。由于每一次迭代都是為了取到更小的J，所有J會(huì)不斷減小直到不變。這個(gè)迭代方法保證可k-means最終會(huì)達(dá)到一個(gè)極小值。

此處要做個(gè)說明，K-means不能保證總是能收斂到全局最優(yōu)解，這與初值的選擇有很大關(guān)系。因此在實(shí)際操作中，我們通常會(huì)多次選擇初值跑K-means，并取其中最好的一次結(jié)果。K-means結(jié)束的判斷依據(jù)可以是迭代到了最大次數(shù)，或者是J的減小已經(jīng)小于我們設(shè)定的閾值。

總結(jié)一下，在眾多聚類方法中，K-means屬于最簡單的一類。其大致思想就是把數(shù)據(jù)分為多個(gè)堆，每個(gè)堆就是一類。每個(gè)堆都有一個(gè)聚類中心（學(xué)習(xí)的結(jié)果就是獲得這k個(gè)聚類中心），這個(gè)中心就是這個(gè)類中所有數(shù)據(jù)的均值，而這個(gè)堆中所有的點(diǎn)到該類的聚類中心都小于到其他類的聚類中心（分類的過程就是將未知數(shù)據(jù)對這k個(gè)聚類中心進(jìn)行比較的過程，離誰近就是誰）。其實(shí)K-means算的上最直觀、最方便理解的一種聚類方式了，原則就是把最像的數(shù)據(jù)分在一起，而“像”這個(gè)定義由我們來完成（類比把藥材按照什么特征裝入藥匣） 。

第二種 高斯混合模型

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

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

圖3 兩個(gè)高斯分布

得到概率有什么好處呢？拿下圖中的兩個(gè)高斯分布來說，(2.5,0) 屬于其重合區(qū)域，它由兩個(gè)分布產(chǎn)生的概率相等，你沒辦法說它屬于那一邊。這時(shí)，你只能猜測，選擇2好像更好一點(diǎn)，于是你得出(2.5,0)屬于左邊的概率是51%，屬于右邊的概率是49%。然后，在用其他辦法分別到底屬于哪一邊。可以想象，如果采用硬分類，分類的相似度結(jié)果要么0要么1，沒有“多像”這個(gè)概念，所以，不方便多模型融合（繼續(xù)判斷）。

混合高斯模型的定義為：

其中K為模型的個(gè)數(shù)，πk為第k個(gè)高斯的權(quán)重，p(x|k)則為第k個(gè)高斯的概率密度函數(shù)，其均值為μk，方差為σk。我們對此概率密度的估計(jì)就是要求πk、μk和σk各個(gè)變量。求解得到的最終求和式的各項(xiàng)結(jié)果就分別代表樣本x屬于各個(gè)類的概率。

在做參數(shù)估計(jì)的時(shí)候，常采用的方法是最大似然。最大似然法就是使樣本點(diǎn)在估計(jì)的概率密度函數(shù)上的概率值最大。由于概率值一般都很小，N很大的時(shí)候這個(gè)連乘的結(jié)果非常小，容易造成浮點(diǎn)數(shù)下溢。所以我們通常取log，將目標(biāo)改寫成：

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

一般用來做參數(shù)估計(jì)的時(shí)候，我們都是通過對待求變量進(jìn)行求導(dǎo)來求極值，在上式中，log函數(shù)中又有求和，若用求導(dǎo)的方法算，方程組將會(huì)非常復(fù)雜，所以我們不直接求導(dǎo)，而是采用EM（Expection Maximization）算法。這與K-means的迭代法相似，都是初始化各個(gè)高斯模型的參數(shù)，然后用迭代的方式，直至波動(dòng)很小，近似達(dá)到極值。

總結(jié)一下，用GMM的優(yōu)點(diǎn)是投影后樣本點(diǎn)不是得到一個(gè)確定的分類標(biāo)記，而是得到每個(gè)類的概率，這是一個(gè)重要信息。GMM每一步迭代的計(jì)算量比較大，大于k-means。GMM的求解辦法基于EM算法，因此有可能陷入局部極值，這與初始值的選取十分相關(guān)。

第三種 層次聚類

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

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

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

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

3. 重新計(jì)算新生成的這個(gè)類與各個(gè)舊類之間的相似度；

4. 重復(fù)2和3直到所有樣本點(diǎn)都?xì)w為一類，結(jié)束。

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

· Single Linkage：又叫做nearest-neighbor ，就是取兩個(gè)類中距離最近的兩個(gè)樣本的距離作為這兩個(gè)集合的距離，也就是說，最近兩個(gè)樣本之間的距離越小，這兩個(gè)類之間的相似度就越大。容易造成一種叫做Chaining 的效果，兩個(gè)cluster 明明從“大局”上離得比較遠(yuǎn)，但是由于其中個(gè)別的點(diǎn)距離比較近就被合并了，并且這樣合并之后Chaining 效應(yīng)會(huì)進(jìn)一步擴(kuò)大，最后會(huì)得到比較松散的cluster 。

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

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

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

另外有一種聚類方法叫做divisive hierarchical clustering（自上而下），過程恰好是相反的，一開始把所有的樣本都?xì)w為一類，然后逐步將他們劃分為更小的單元，直到最后每個(gè)樣本都成為一類。在這個(gè)迭代的過程中通過對劃分過程中定義一個(gè)松散度，當(dāng)松散度最小的那個(gè)類的結(jié)果都小于一個(gè)閾值，則認(rèn)為劃分可以終止。

圖4 自上而下和自下而上的層次聚類

由于這種層次結(jié)構(gòu)，普通的K-means也被稱為一種flat clustering。

以上三種方法為無監(jiān)督算法常用的聚類算法，可以根據(jù)數(shù)據(jù)情況選擇適用的算法。事實(shí)上，在算法的選擇上也十分有講究，不僅要考慮數(shù)據(jù)維度，數(shù)據(jù)類型，還要考慮數(shù)據(jù)分布等等。

總結(jié)

以上是生活随笔為你收集整理的【采用】无监督核心聚类算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。