王平祿 董昱威

摘 要：聚類算法在圖像分割領(lǐng)域有廣泛的應(yīng)用，本文通過對(duì)四種聚類算法的介紹與分析，深入了解其算法原理，以及其在圖像分割領(lǐng)域中的應(yīng)用效果，通過四種的算法的比較，總結(jié)出了各個(gè)算法的優(yōu)缺點(diǎn)。

關(guān)鍵詞：聚類算法；K均值；模糊聚類；均值漂移；近鄰傳播算法

隨著信息技術(shù)的高速發(fā)展，人們每天都處理大量的圖像信息，然而，不是圖像中的所有信息都是我們需要的，所以，這就需要我們進(jìn)一步對(duì)圖像進(jìn)行處理，得到能夠滿足人們需要的信息。這就需要我們通過技術(shù)手段把圖像中特定的信息從整體中分割出來，這便是圖像分割，即將輸入的圖像分割成若干有意義的目標(biāo)區(qū)域[1]。近年來，聚類算法在圖像分割中有著廣泛的應(yīng)用。目前比較經(jīng)典的聚類算法有：K均值聚類，模糊聚類，均值漂移算法，近鄰聚類算法。

1 聚類算法

⑴K均值聚類。K均值算法是最經(jīng)典的聚類算法。由于其簡(jiǎn)單高效，是應(yīng)用最廣泛的聚類算法。它的基本思想是：預(yù)先設(shè)定K類，隨機(jī)選中K個(gè)元素作為每一類的中心。計(jì)算其它元素與K個(gè)中心之間的聚類，根據(jù)距離的大小，歸入距離最小的類中。然后重新計(jì)算每一個(gè)類的中心值，即所有類中元素的平均值，得到新的中心值后。再次重新分類，不斷重復(fù)此過程，直到目標(biāo)函數(shù)收斂。通常定義的目標(biāo)函數(shù)為：

式中：p為對(duì)象空間中一個(gè)數(shù)據(jù)對(duì)象；mi為類ci的均值。

⑵模糊聚類。模糊聚類算法是由K均值聚類算法發(fā)展而來的。它的基本思想是：把所有元素分為C個(gè)模糊聚簇，求出每個(gè)簇的中心，使得非相似性指標(biāo)的函數(shù)達(dá)到最小值。它在確定每一個(gè)元素時(shí)，不是K均值非0即1，而是使用0～1之間的數(shù)字來賦予元素隸屬于某一簇的程度。它的目標(biāo)函數(shù)為：FCM聚類算法目標(biāo)函數(shù)為：

式中：Xj表示樣本；N表示樣本數(shù)目，通常表示圖像像素?cái)?shù)；C表示聚類數(shù)目； 是矢量Xj隸屬于第i類的隸屬度函數(shù)，滿足uij∈[0，1]且 ；Z表示聚類中心。

⑶均值漂移算法。均值漂移是一種不需要參數(shù)的無監(jiān)督聚類方法。它的主要思想是，在概率空間中求解概率密度極值的最優(yōu)算法。它讓每一個(gè)點(diǎn)漂移到密度函數(shù)局部最大值出，即均值漂移向量的方向是數(shù)據(jù)的密度梯度估計(jì)方向一致。[2]文獻(xiàn)[3]中對(duì)均值漂移算法原理的描述如下：假設(shè)核函數(shù)H如果滿足一定的統(tǒng)計(jì)矩約束概率密度函數(shù)，可以用于非參數(shù)概率密度估計(jì)，若樣本集{xi}n是依密度函數(shù)f（x）經(jīng)過n次獨(dú)立抽樣得到的，則給出的密度函數(shù)估計(jì)為[4]：

其中，核函數(shù)滿足：

⑷近鄰聚類算法。近鄰傳播聚類算法是一種基于近鄰信息傳播的聚類算法，其目的是找到最優(yōu)的類代表點(diǎn)集合，一個(gè)類代表點(diǎn)對(duì)應(yīng)為實(shí)際數(shù)據(jù)集中的一個(gè)數(shù)據(jù)點(diǎn)，使得所有數(shù)據(jù)點(diǎn)到最近的類代表點(diǎn)的相似度之和最大。如果設(shè)數(shù)據(jù)點(diǎn)的相似度為數(shù)據(jù)點(diǎn)的歐式距離的負(fù)數(shù)，則妙算法的目標(biāo)函數(shù)與經(jīng)典的K中心聚類算法的目標(biāo)函數(shù)一致。近鄰傳播聚類算法還有兩個(gè)重要的信息量參數(shù)，分別是responsibility和availability，r（i，k）表示從點(diǎn)i發(fā)送到候選聚類中心k的數(shù)值消息，反映k點(diǎn)是否適合作為i點(diǎn)的聚類中心。a（i，k）則從候選聚類中心k發(fā)送到i的數(shù)值消息，反映i點(diǎn)是否選擇k作為其聚類中心。r（i，k）與a（i，k）越強(qiáng)，則k點(diǎn)作為聚類中心的可能性就越大，并且i點(diǎn)隸屬于以k點(diǎn)為聚類中心的聚類的可能性也越大。對(duì)于任意數(shù)據(jù)點(diǎn)xi，計(jì)算所有數(shù)據(jù)點(diǎn)的r（i，k）和a（i，k）。

3 小結(jié)

K均值聚類由于其簡(jiǎn)單高效，是應(yīng)用最廣泛的聚類算法。但是它也有很多局限性，其中聚類類別的數(shù)目需要先驗(yàn)知識(shí)，而初試聚類中心的選擇不同也對(duì)聚類最終結(jié)果有很大的影響，所以聚類的穩(wěn)定性欠缺。

模糊聚類算法，也是比較普遍使用的聚類算法。一般情況下不需要人為干預(yù)和設(shè)定閾值，就可使圖像分割區(qū)域自動(dòng)化。但是模糊聚類數(shù)目的確定也是個(gè)難題，需要先驗(yàn)知識(shí)，而算法本身迭代過程計(jì)算量非常大，而算法對(duì)噪音比較敏感，所以，時(shí)常會(huì)出現(xiàn)過分割現(xiàn)象。

均值漂移算法是一種無需任何參數(shù)的聚類算法，對(duì)噪音有很好的魯棒性，可以處理任意形狀和特征空間的圖像，非常適用于真實(shí)世界中的圖像。但是該算法受核函數(shù)的影響比較大，由于核函數(shù)參數(shù)的設(shè)置問題，圖像會(huì)產(chǎn)生過分割或欠分割現(xiàn)象。

近鄰傳播聚類算法，相比較其它算法能更快的處理大規(guī)模數(shù)據(jù)，得到較好的聚類結(jié)果。它對(duì)數(shù)據(jù)形成的相似矩陣的對(duì)稱性沒有任何要求，所以其應(yīng)用的范圍很大。但是對(duì)于一些本書具有復(fù)雜結(jié)構(gòu)的數(shù)據(jù)集，近鄰傳播算法通常得不到合理的聚類結(jié)果。

[參考文獻(xiàn)]

[1]Gonzalez Rafael C，Woods Richard E，Eddins Steven L.Digital Image Processing.阮秋琦，等，譯.電子工業(yè)出版社，2005.

[2]王爽，夏玉，焦李成.基于均值漂移的自適應(yīng)紋理圖像分割方法[J]. Journal of Software，2010，21（6）：1451-1461.

[3]沈占鋒，駱劍承，胡曉東，孫衛(wèi)剛.高分辨率遙感影像多尺度均值漂移分割算法研究[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2010，03：313-316.

[4]Comaniciu D， Meer P.Mean Shift： a Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）：603-619.