1.K均值聚類

K均值聚類是最基礎(chǔ)的一種聚類方法。K均值聚類，就是把看起來最集中、最不分散的簇標(biāo)簽分配到輸入訓(xùn)練樣本{xi}中。具體而言就是通過下式計算簇y的分散狀況：
在這里，∑i,yi=y表示的是滿足yi=y的y的和。
μy是指簇y的中心。ny為屬于簇y的樣本總數(shù)。利用上述定義，對于所有的簇y=1,2,3,..,c的下式和最小時，決定其所屬的簇標(biāo)簽。
然而，上述的最優(yōu)化過程的計算時間隨著樣本數(shù)目n的增加呈現(xiàn)指數(shù)級的增長，當(dāng)n為較大的數(shù)值的時候，很難對其進(jìn)行高精度的求解。因此在實際應(yīng)用中，一般將樣本逐個分類到距離最近的聚類中，并重復(fù)這一操作，直到最終求得其局部最優(yōu)解。
K均值聚類的算法流程如下所示：
K均值聚類的一個實例：
K均值聚類算法的實例。方框表示的是簇中心

2.核K均值聚類

由于K均值聚類是依據(jù)歐氏距離||x-μy||的大小來決定樣本所屬的簇，因此只能處理線性可分得聚類問題。 同理，我們可以采用核映射的方法，可以處理非線性可分的聚類問題（核K均值聚類算法）。具體而言，就是把上市的歐式距離的平方用樣本間的內(nèi)積來表示，如下：
接著，把上式的內(nèi)積置換為核函數(shù)K(x,x'),就變成了核K均值聚類算法。
在這里，與（x,x'）相對應(yīng)的K(x,x')是與最小化無關(guān)的常數(shù)，因此實際計算過程中可以忽略。 利用核K均值聚類可以得到非線性的簇的分類結(jié)果。然而，采用核函數(shù)的非線性核K均值聚類的方法，最終的聚類結(jié)果強烈依賴于初始值的選取，因此在實際應(yīng)用中想要得到理想的解并非易事。

3.譜聚類

核K均值聚類方法，最終的聚類結(jié)果強烈以來與初始值的選取，當(dāng)由核函數(shù)決定的特征空間的緯度比較高的時候，這種依賴尤其明顯。對此，可以使用降維的方法來解決這個問題，這種方法稱為譜聚類。 前面也介紹了很多的無監(jiān)督聚類方法。其中也包括可以很好地保護(hù)原始數(shù)據(jù)中的簇構(gòu)造的局部保持投影法，作為聚類分析的前處理是一種很好的選擇。譜聚類，首先在核特征空間中應(yīng)用局部保持投影法，然后直接應(yīng)用常規(guī)的K均值聚類方法（并非核函數(shù)的方法）。 譜聚類的具體算法流程如下：
利用譜聚類的一則實例如下：
a表示的原始二維數(shù)據(jù)應(yīng)用拉普拉斯特征映射法向一維部分空間進(jìn)行映射，就可以得到b所示的只有兩點的數(shù)據(jù)結(jié)果。對得到的b結(jié)果，利用K均值聚類處理后，就可以得到c那樣的兩個點分別代表一個聚類結(jié)果，再把得到的簇標(biāo)簽映射到原始的二維數(shù)據(jù)中，就可以得到d所示的自然地聚類結(jié)果。

4.調(diào)整參數(shù)的自動選取

核K均值聚類法和譜聚類的結(jié)果依賴于高斯核函數(shù)的帶寬等核參數(shù)的選擇。這一塊重點討論聚類方法中根據(jù)更重客觀條件自動決定這些參數(shù)的方法。 聚類算法中，通過d次維的實向量樣本{xi},求得c中標(biāo)量值1,...,c對應(yīng)的簇標(biāo)簽{yi}。這一操作可以被理解為將d次維的實向量中包含的信息，通過標(biāo)量c進(jìn)行壓縮。如下所示：
基于這樣的觀點，一般認(rèn)為簇標(biāo)簽{yi}比原始的樣本{xi}包含更多的信息，可以得到更好的聚類結(jié)果。 簇標(biāo)簽{yi}包含的樣本{xi}的信息量，可以通過互信息來進(jìn)行測算。互信息是信息論中的一個基本概念定義如下：
互信息一般為非負(fù)的數(shù)值，只有當(dāng)變量在統(tǒng)計上相互獨立的時候，互信息為0.因此，可以通過互信息的大小推導(dǎo)出x，y的從屬性的強弱。綜上可知，互信息越大，簇標(biāo)簽{yi}包含樣本{xi}的信息越多。 互信息的值，可以采用KL散度密度比估計法進(jìn)行高精度的計算。但是由于互信息的計算公式中包含對數(shù)函數(shù)，對異常值的反應(yīng)相當(dāng)?shù)拿黠@，所以經(jīng)常采用沒有對數(shù)的平方損失互信息來加以替換（泰勒公式）：
接下來主要討論樣本{xi}和簇標(biāo)簽{yi}之間的平方損失互信息的最小二乘互信息估計法。平方損失互信息最小二乘互信息估計法，不需要計算p(x,y)/p(x)/p(y)等概率，而是對將其組合而成的密度比函數(shù)進(jìn)行學(xué)習(xí)。
為了對上述的密度比函數(shù)進(jìn)行近似，采用與參數(shù)相關(guān)的線性模型：
然后對下式的J(a)為最小時對應(yīng)的參數(shù)a進(jìn)行最小二乘學(xué)習(xí)：
上式中，C是無關(guān)的常數(shù)，計算過程可以忽略。然后，對第一項和第二項中包含的期望值進(jìn)行樣本平均近似，再加上L2正則化項，就可以的帶下面的學(xué)習(xí)規(guī)則：
其中，G是b*b階矩陣；h是b次維向量：
對于上面的凸的二次式，進(jìn)行簡單的偏微分求導(dǎo)即可得到最優(yōu)解：
將上面得到的密度比估計量，帶入與平方損失互信息等價的下式：
就可以得到如下的平方損失互信息的估計量：
正則化參數(shù)λ和基函數(shù)中包含的參數(shù)，可以通過與規(guī)則J相關(guān)的交叉驗證法加以確定。 下面是與各個簇的高斯模型相對應(yīng)的最小二乘互信息估計法的實例：
使用k近鄰相似度的譜聚類中，當(dāng)k=10的時候平方損失互信息的估計值達(dá)到最大值 由此可以得到最優(yōu)的聚類效果

總結(jié)

以上是生活随笔為你收集整理的无监督分类：聚类分析（K均值）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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