王 磊

（商洛學(xué)院 現(xiàn)代教育技術(shù)中心，陜西商洛 726000）

近年來有關(guān)譜聚類算法的應(yīng)用研究受到了國內(nèi)外學(xué)者的廣泛關(guān)注，并且已經(jīng)在多個(gè)領(lǐng)域得到了較好的應(yīng)用,如：圖像分割[1-2]，文本語義分析[3-4]等。但該算法在實(shí)際應(yīng)用中仍然存在一些亟待解決的問題，例如：由于傳統(tǒng)譜聚類通常采用K-means算法對特征向量進(jìn)行聚類，導(dǎo)致算法對初始聚類中心較敏感[5]，穩(wěn)定性較低、準(zhǔn)確性不高，并難以應(yīng)用于大規(guī)模數(shù)據(jù)處理等，這些問題極大的阻礙了該算法的進(jìn)一步應(yīng)用與發(fā)展。由此，本文在深入研究譜聚類算法、Bayes決策理論及半監(jiān)督學(xué)習(xí)方法的基礎(chǔ)上，提出了一種結(jié)合Bayes決策的半監(jiān)督譜聚類算法。其主要思想是利用Bayes決策的距離學(xué)習(xí)理論對相似度矩陣的內(nèi)容進(jìn)行適當(dāng)調(diào)整；然后，利用半監(jiān)督K-means聚類對調(diào)整后的特征向量進(jìn)行聚類劃分，進(jìn)一步提高譜聚類算法的穩(wěn)定性與準(zhǔn)確性。

1 譜聚類算法

譜聚類算法是建立在譜圖理論基礎(chǔ)之上，其基本內(nèi)容是：首先根據(jù)給定的數(shù)據(jù)集按照一定的相似度測量規(guī)則定義一個(gè)描述成對數(shù)據(jù)點(diǎn)相似度的相似度矩陣，并計(jì)算矩陣的特征向量和特征值，然后選擇合適的特征向量聚類成不同的數(shù)據(jù)點(diǎn)[6-7]，是一種點(diǎn)對聚類算法，對數(shù)據(jù)聚類具有很好的應(yīng)用前景。由于譜聚類算法建立在圖論中的譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題，即：成求解Laplacian矩陣或相似度矩陣的譜分解問題[8]。與傳統(tǒng)的聚類算法相比，它具有能在任意形狀的樣本空間上聚類并且收斂于全局最優(yōu)解的優(yōu)點(diǎn)。譜聚類算法最初用于計(jì)算機(jī)視覺、VLSI設(shè)計(jì)等領(lǐng)域，最近才開始用于機(jī)器學(xué)習(xí)中，并迅速成為國際上機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。

在譜聚類算法中，設(shè) X={x1，x2，…，xn}為待聚類的樣本集，相似度矩陣通常被定義為

其中d(xi,xj)一般取歐式距離（即||xi-xj||2），σ為事先確定的參數(shù)。

根據(jù)不同的譜映射方法及準(zhǔn)則函數(shù)，譜聚類算法衍生出許多具體實(shí)現(xiàn)方法，這里給出當(dāng)前較為常用的一種實(shí)現(xiàn)方法——NJW算法[9],該算法為：首先選取Laplacian矩陣的前k個(gè)最大特征值所對應(yīng)的特征向量，并使其與原樣本集在 Rk空間中構(gòu)成一一對應(yīng)關(guān)系，然后在Rk空間中進(jìn)行聚類。算法的具體描述如下：

輸入：樣本集 X={x1，x2，…，xn}及聚類數(shù)目 k

1）建立相似度矩陣 W∈Rn×n，其中 Wij=exp(d(xi，xj)/2σ2),i≠j，且 Wij=0；

2）構(gòu)造 Laplacian 矩陣 L=D-1/2WD-1/2，其中為對角矩陣；

3）計(jì)算Laplacian矩陣L的特征向量與特征值，選取其前k個(gè)最大特征值所對應(yīng)的特征向量z1，z2，…，zn，構(gòu)造矩陣 Z=[z1，z2，…，zk]∈Rn×k；

5）將矩陣Y中的每一行視為空間Rn*k中的一個(gè)樣本，使用K-means算法對其進(jìn)行聚類，將其劃分為k類；

6）將初始樣本點(diǎn)xi劃分為第j類，當(dāng)且僅當(dāng)矩陣Y 的第i行被劃分到聚類j中；

輸出：輸入樣本集X中所有樣本點(diǎn)對應(yīng)的類標(biāo){l1，l2，…，lN}。

2 結(jié)合Bayse決策的半監(jiān)督譜聚類算法

2.1 基于Bayes決策的距離學(xué)習(xí)方法

特征向量分布情況的好壞直接影響著譜聚類算法的穩(wěn)定性強(qiáng)弱，而決定特征向量分布的關(guān)鍵因素在于相似度矩陣的取值是否合適，即使不同類的樣本間相似度足夠小，而同類的樣本間相似度足夠大。針對該問題，本文在深入研究Bayes決策理論及半監(jiān)督學(xué)習(xí)理論的基礎(chǔ)上，提出了一種新的基于距離的半監(jiān)督學(xué)習(xí)方法——基于Bayes決策的距離學(xué)習(xí)方法，目的是改善用于進(jìn)行聚類的特征向量的分布情況。

Bayes決策理論的基本思路[10]：已知類別數(shù)為c，樣本x屬于每一類的先驗(yàn)概率P(ωi)及類條件概率密度函數(shù)P(x|ωi)(各類別狀態(tài)用ωi來表示，i=1，2，…，c）,根據(jù) Bayes 公式得到屬于每類的后驗(yàn)概率P(ωi|x)，然后由后驗(yàn)概率的大小值確定每個(gè)樣本x的類屬。

設(shè) D1，D2，…，Dc為樣本空間S的一個(gè)劃分,如果以 P(ωi)表示事件 Di發(fā)生的概率，且 P(ωi)＞0,(i=1，2，…，c)。對于任一事件 x，如果 P(x)＞0 則有[11]

由此可以得出一種使錯(cuò)誤率最小的分類規(guī)則，稱之為基于最小錯(cuò)誤率的Bayes決策。其具體描述如式(3)。

這里給出基于Bayes決策的距離學(xué)習(xí)方法的基本思路如下：

設(shè)有樣本集 X={x1，x2，…，xn}，其中 n 為樣本數(shù)，xi=[xi1，xi2，…，xim]T，m 為樣本的特征數(shù)或維數(shù)。已知的成對約束信息分別用M和C來表示，其中M表示must-links集合，C表示cannot-links集合，其定義如下：

設(shè)已知樣本集X的相似度矩陣W，定義集合U為矩陣W中除對角線元素之外的其他所有元素的并集，集合WM及WC分別表示集合M與集合C中所有點(diǎn)對在矩陣W中對應(yīng)數(shù)值的并集，集合WV為集合WM與WC的并集，其數(shù)學(xué)描述如下：

其中Wij為W矩陣中樣本xi和樣本xj的d(xi,xj)距離。

1）計(jì)算所有樣本點(diǎn)之間的相似度矩陣W:Wij=exp(d(xi,xj)/2σ2)

2）按照式(6)分別計(jì)算集合 U、WM、WC、WV；

3）分別計(jì)算集合WV中任意元素屬于集合 WM 的先驗(yàn)概率 P(ωm)、條件概率 P(w|ωm)以及屬于集合WC的先驗(yàn)概率P(ωc)、條件概率 P(w|ωc)；

綜上所述，基于Bayes決策的距離測度函數(shù)的基本思想是：把集合WV的元素作為訓(xùn)練樣本，建立基于最小錯(cuò)誤率的Bayes決策分類器；利用該分類器對相似度矩陣W中可分元素（即可計(jì)算其后驗(yàn)概率）進(jìn)行分類，將其劃分至集合WM及WC中；利用類別信息及后驗(yàn)概率，依據(jù)所示距離測度函數(shù)對矩陣W的內(nèi)容進(jìn)行調(diào)整。

2.2 成對約束的K-means聚類算法

經(jīng)分析，傳統(tǒng)譜聚類算法穩(wěn)定性較低，其中一個(gè)很重要的原因是進(jìn)行特征向量聚類的聚類算法（通常是K-means）對初始聚類中心較敏感引起的。針對該問題，本文采用一種經(jīng)典的基于成對約束的半監(jiān)督聚類算法——成對約束的K-means聚類（Constrained-K-means）[12]來完成特征向量的聚類。該算法首先利用少量的標(biāo)記樣本產(chǎn)生初始聚類中心；然后，使用前述標(biāo)記的樣本以出成對約束的形式來引導(dǎo)整個(gè)算法的迭代過程（如表2）。由于其效率較高，實(shí)現(xiàn)簡單，并且能夠一定程度上提高K-means算法的穩(wěn)定性，因而已被廣泛應(yīng)用于各個(gè)領(lǐng)域。帶約束的K-means聚類算法的具體描述如下：

2）若x∈S，則其類標(biāo)簽不變；否則，根據(jù)相似度規(guī)則，將其分配到離它最近的聚類中，并修改類標(biāo)簽；

4）若聚類中心不再發(fā)生改變，算法結(jié)束；否則跳轉(zhuǎn)到步驟2）;

輸出：樣本集X中所有樣本點(diǎn)對應(yīng)的類標(biāo)簽{l1，l2，…，lN}。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

選取兩幅人工合成紋理圖像作為實(shí)驗(yàn)圖像（如圖1、表1）。所有的實(shí)驗(yàn)都是在相同的硬件環(huán)境中進(jìn)行的（硬件環(huán)境：Intel Core(TM)2，1.86GHz With 1G memory），實(shí)驗(yàn)軟件：MATLAB 7.8.0(R2009a)。

其中，對于這兩幅實(shí)驗(yàn)圖像，提取三個(gè)圖像特征，分別是：3維RGB顏色特征、2維空間特征及3維紋理特征，其中紋理特征采用灰度共生矩陣法，分別取能量、熵和對比度在 0°、45°、90°、1350這四個(gè)方向上的均值所構(gòu)成的3維紋理特征，圖像的量化等級為8灰度級，滑動(dòng)窗口的大小為9*9；相似度函數(shù)如式(9)所示，其中各高斯參數(shù)的確定方法為經(jīng)驗(yàn)值與網(wǎng)格法相結(jié)合：顏色參數(shù)σc=0.03、空間參數(shù)σs=70、紋理參數(shù)σt的取值范圍為0.03-0.30；具體參數(shù)設(shè)置見表2。

其中，Wij表示樣本i和j之間的相似度，Wcij、Wsij及 Wtij分別表示樣本 i和 j之間的顏色、空間及紋理相似度，C、S及T分別表示顏色特征、空間特征及紋理特征。

圖1 實(shí)驗(yàn)用圖

表1 人工合成紋理圖

表2 實(shí)驗(yàn)參數(shù)

3.2 實(shí)驗(yàn)結(jié)果

在圖2中，可以清楚的看到，傳統(tǒng)譜聚類在兩副圖像上的分割效果都很一般，存在著大量錯(cuò)分情況；而采用本文方法的分割效果要明顯優(yōu)于傳統(tǒng)譜聚類算法，尤其是對二類人工合成紋理圖像的分割結(jié)果和理想的人工分割結(jié)果相差無幾，很明顯本文方法較傳統(tǒng)譜聚類在背景部分具有更好的區(qū)域一致性與更少的離散點(diǎn)分布。

在圖3中，為了體現(xiàn)本文算法穩(wěn)定性的優(yōu)勢，對三幅人工合成圖像進(jìn)行22次試驗(yàn)統(tǒng)計(jì)其正確率分布情況。顯然，本文算法在22次圖像分割實(shí)驗(yàn)中正確率變化幅度較傳統(tǒng)譜聚類更加平穩(wěn)。

在表3中，可以看出本文算法的平均正確率較傳統(tǒng)譜聚類算法有了明顯的提高，同時(shí)正確率方差也控制在較低水平上，穩(wěn)定性得到了數(shù)倍的提高。

圖2 聚類結(jié)果

圖3 正確率分布

表3 對比試驗(yàn)結(jié)果

4 結(jié)論

針對譜聚類算法穩(wěn)定性較低、準(zhǔn)確性不高的缺點(diǎn)，本文深入研究譜聚類算法、Bayes決策理論以及半監(jiān)督學(xué)習(xí)方法，提出了一種結(jié)合Bayes決策的半監(jiān)督譜聚類算法。經(jīng)仿真實(shí)驗(yàn)證明，本文方法較傳統(tǒng)譜聚類在穩(wěn)定性及準(zhǔn)確率方面都有顯著提高，達(dá)到了預(yù)期目的。但該方法仍然存在不足之處，例如，如何選取半監(jiān)督信息、如何選擇最優(yōu)核參數(shù)等，還需要進(jìn)一步探討。

[1]高 倩,戴月明.用于文本聚類的模糊譜聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(3):142-144.

[2]林 立,胡 俠,朱俊彥.基于譜聚類的多文檔摘要新方法[J].計(jì)算機(jī)工程,2010,36(22):64-66.

[3]Hebert P,Macaire L.Spatial-color pixel classification by spectral clustering for color image segmentation[C]//information and communication technologies ICTTA 3rd International Conference on,2008:1-5.

[4]Feng Sun,Jinpeng He.The remote-sensing image segmentation using textons in the Normalized Cuts framework [C].Mechatronicsand Automation,2009 ICMA 2009 International Conference on,2009:1877-1881.

[5]朱強(qiáng)生,何華燦,周延泉.譜聚類算法對輸入數(shù)據(jù)順序的敏感性[J].計(jì)算機(jī)應(yīng)用研究,2007,24(4):62-63.

[6]施培蓓,郭玉堂,胡玉娟.初始化獨(dú)立的譜聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(25):134-137.

[7]沈亞田,沈夏炯,張 磊.基于圖劃分的譜聚類算法在文本挖掘中應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(5):96-98.

[8]Von Luxburg U.A Tutorial on spectral clustering[J].Statistics and Computing,2007:395-416.

[9]Ng A Y,Jordan M I,Weiss Y.On spectral clustering:analysis and an algorithm[M].Advances in Neural Information Processing Systems,Cambridge,MIT Press,2002:849-856.

[10]邊肇祺,張學(xué)工.模式識別[M].2版.北京:清華大學(xué)出版社,2000.

[11]Huan Ruohong,Yun Pan,KejiMao.SAR image target recognition based on NMF feature extraction and Bayesian decision fusion[C].Geoscience and Remote Sensing(IITA-GRS),2010 Second IITA International Conference on,2010:496-499.

[12]Basu S,Banerje e A,Mooney R.Semi-supervised clustering by Seeding[C].Machine learning-international workshop then conference on,2002:19-26.