一種改進的半監(jiān)督譜聚類算法

王 磊

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

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

1 譜聚類算法

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

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

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

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

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

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

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

3）計算Laplacian矩陣L的特征向量與特征值，選取其前k個最大特征值所對應的特征向量z1，z2，…，zn，構造矩陣 Z=[z1，z2，…，zk]∈Rn×k；

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

6）將初始樣本點xi劃分為第j類，當且僅當矩陣Y 的第i行被劃分到聚類j中；

輸出：輸入樣本集X中所有樣本點對應的類標{l1，l2，…，lN}。

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

2.1 基于Bayes決策的距離學習方法

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

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

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

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

這里給出基于Bayes決策的距離學習方法的基本思路如下：

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

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

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

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

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

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

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

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

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

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

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

輸出：樣本集X中所有樣本點對應的類標簽{l1，l2，…，lN}。

3 實驗分析

3.1 實驗數(shù)據(jù)

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

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

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

圖1 實驗用圖

表1 人工合成紋理圖

表2 實驗參數(shù)

3.2 實驗結果

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

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

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

圖2 聚類結果

圖3 正確率分布

表3 對比試驗結果

4 結論

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

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

[2]林 立,胡 俠,朱俊彥.基于譜聚類的多文檔摘要新方法[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]朱強生,何華燦,周延泉.譜聚類算法對輸入數(shù)據(jù)順序的敏感性[J].計算機應用研究,2007,24(4):62-63.

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

[7]沈亞田,沈夏炯,張 磊.基于圖劃分的譜聚類算法在文本挖掘中應用[J].計算機技術與發(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]邊肇祺,張學工.模式識別[M].2版.北京:清華大學出版社,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.