基于核自調整進行半監督聚類
2009-01-01 00:00:00崔鵬張汝波
計算機應用研究 2009年5期
(1.哈爾濱工程大學 計算機學院 哈爾濱 150001； 2.哈爾濱理工大學 計算機學院 哈爾濱 150080)
摘 要：半監督聚類是通過在無監督算法的基礎上加入有限的背景知識來實現的?，F有的基于核的半監督聚類算法對于核參數的設定仍需人工進行調節，其選擇值會極大地影響最終的結果。通過將關聯加入到聚類目標函數中，在聚類過程反復地優化高斯核參數，自動確定最佳RBF核，并將最佳核計算與SSKK算法結合起來得到SSKKOK算法。實驗結果表明，該算法能在利用基于核半監督聚類算法功能的基礎上自動設置有關的參數。
關鍵詞：半監督聚類； 關聯； 馬爾可夫隨機域； K均值； 高斯核
中圖分類號：TP181文獻標志碼：A
文章編號：1001-3695(2009)05-1719-04
Kernelbased adaptation for semisupervised clustering
CUI Peng1，2 ZHANG Rubo1
(1.School of Computer Science Harbin Engineering University Harbin 150001 China； 2.School of Computer Science Harbin University of Science Technology Harbin 150080 China)
Abstract:Semisupervised clustering combines unsupervised clustering algorithms with limited background knowledge. However setting of kernel parameters involved in SSKK(semisupervised kernelbased kmeans) is still needed to manually regularize. The chosen value of critical parameters will largely effect on the result. The pair constraints were incorporated into clustering object function and kernel parameters were optimized iteratively during clustering process till to determine optimal RBF kernel. Furthermore SSKKOK algorithm was proposed which was based on optimal kernel computation and SSKK algorithm. The experiment demonstrates the algorithm can not only utilize the effect of SSKKbut also automatically set involved parameters.
Key words：semisupervised clustering; constraint; HMRF; Kmeans; Gassian kernel
0 引言
近年來，在機器學習和數據挖掘領域半監督聚類算法受到極大的關注。在傳統的聚類算法中，只有標記的數據能用于生成聚類；而在半監督聚類中，通過將有關聚類的先驗信息加入到算法中改進聚類效果[1，2]。Basu等人[2]提出的一種基于馬爾可夫隨機域并利用成對關聯進行半監督聚類結構，此結構基于HMRFKmeans；然而，HMRFKmeans只能以向量形式聚類輸入數據?；诤朔椒ㄍㄟ^將輸入空間的數據映射到一個新的（通常是更高維度）特征空間來提高學習算法的建模能力，核方法已成功用于解決分類、聚類以及回歸問題等許多應用中。核方法的關鍵是針對具體問題的最優核選擇，估計最優核函數及其參數的解決辦法在監督環境下曾提出過，當不提供標記數據時可以利用成對的關聯。Cristianini等人[3]提出了用核調整的概念來度量特征空間數據組間的相關性以及要學習的標簽分布；Chapelle等人[4]提出了自動調節可支持向量機的多個參數的思想，可通過梯度下降法估計最小泛化誤差；Wang等人[5]提出了用Fisher判別規則估計最佳高斯核分布參數；Huang等人[6]提出了在核Fisher判別分析結構內選擇核參數用于人臉識別，并在梯度下降算法的基礎上得到了優化高斯核的新公式。
上述的研究都利用了已標記數據進行分類。
本文提出了核自調整半監督聚類方法，直接根據數據以及給定的關聯自動評估混合高斯核的最優參數值。將關聯加入到目標函數中，通過使正關聯（mustlink）點彼此更近、負關聯（cannotlink）點彼此更遠，優化了核映射，能在特征空間中自動嵌入非線性相似性。這使得此調整能夠在輸入空間準確地發現非線性相似的聚類（可從實驗中驗證）。通過自動設置相關的參數，使基于核的半監督聚類法得到了實際的應用。
1 基本背景與相關工作
1.1 基于核的K均值法
令X為有N個樣本、D維的數據集，X={Xi}Ni=1RD。令:RD→RD′為一個非線性映射函數，將數據從數據（D維）輸入空間映射到一個（D′維）特征空間，且D′＞D?；诤说腒均值法產生X的一個劃分{πc}kc=1（πc為第c個聚類），以使目標函數∑kc=1∑xi∈πc‖(xi)-mc‖最小。其中mc=(1/｜πc｜)∑xi∈πc(xi)表示特征空間中聚類πｃ的質心。核K均值法[1]的關鍵是計算特征空間中的測度。在特征空間中，點xi到mc的測度平方表示為
‖(xi)-mc‖2=(xi)#8226;(xi)-（2/｜πc）｜∑xj∈πc(xi)#8226;
(xj)+（1/｜πc｜2）∑xj，x′j∈πc(xj)#8226;(x′j) （1）
令Aii=(xi)#8226;(xi)，Dic=（2/｜πc｜）∑xj∈πc(xi)#8226;(xj)，Bcc=（1/｜πc｜2）∑
xj，x′j∈πc(xj)#8226;(xj′)。按照標準SVM法，可用一種合適的Mercer核表示核空間中數據點的內積[5]。由于數據點總以內積的形式出現，測度計算項可表示為
K(xi，xj)=(xi)#8226;(xj)[7]，即Aii=K(xi，xj)，則
Dic=（2/｜πc｜）∑xi∈πcK(xi，xj)，Bcc=（1/｜πc｜2）∑xj，x′j∈πcK(xj，xj′)
Aii為每個聚類所共有，無須計算它，而Bcc在每次迭代中必須要進行計算。
1.2 基于核的半監督聚類
在半監督聚類中，給定一個成對關聯的集合：正關聯ML={(xi，xj)}和負關聯CL={(xi，xj)}。為將數據劃分為k個聚類，使每點和對應的聚類表示間給定的扭曲度最小，并獲得違反關聯的最少個數，Basu等人[2]提出了基于隱馬爾可夫隨機域(HMRF)?？紤]到歐式測度平方可作為一種聚類扭曲的度量，并且泛化的Potts勢可作為違反關聯的勢，半監督聚類的目標函數可表示為
Jobj({πc}kc=1)=∑kc=1 ∑xi∈πc‖xi-mc‖2+
∑xi，xj∈ML，li≠ljwij+∑xi，xj∈CL，li=lj wij（2）
其中:mc為聚類πc的質心，ML是正關聯集，CL是負關聯集，wij和wij為違反正關聯和負關聯的懲罰值，li表示聚類xi的聚類標簽。
Kulis等人在此框架下提出了一種基于核的半監督聚類。不是增加違反正關聯的懲罰項，而是給滿足關聯的數據進行補償，并通過從目標函數中減去對應的懲罰項來實現。
Jobj({πc}kc=1=∑kc=1∑xi∈πc‖xi-mc‖2-
∑xi，xj∈ML，li=ljwij+∑xi，xj∈CL，Ii=Ij wij（3）
此算法可從文獻[8~10]中得到，稱為半監督核K均值SSKK（semisupervised kernelbased Kmeans）算法。當與高斯核結合到一起時，它的性能要優于HMRFKmeas法，并與線性核相結合。但其核參數的設置需人工調整，并且值的選擇會很大程度地影響結果的質量。因而，當只有有限監督可用的情況下，核參數的選擇是一個重要的問題。這也是筆者建立此方法的初衷。
2 基于核自調整的半監督聚類
2.1 可調整核半監督K均值法的目標函數
在基于核的學習算法中，關鍵是建立滿足學習目標的核函數。在半監督聚類中，希望學習一種核函數使在特征空間中服從正關聯約束關系點對的映射值彼此接近，而服從負關聯約束關系點對的映射值彼此遠離。
在文獻[10~12]中提出了用核調整的概念來度量特征空間中數據組的相關性及學習的標記。在文獻[6]中，用一種Fisher判別規則來估計一種高斯核的最優分布參數。核參數的選擇是一個關鍵的問題。實驗結果表明高斯核的分布參數值σ會極大地影響SVM的泛化性能。σ值過大或過小均會導致泛化能力的降低。當σ→0，核矩陣變為單位陣。在這種情況下，產生的最佳結果使拉氏函數值均為1，并且每點均為一個SVM；另一方面，當σ→∞，核矩陣的元均為1，因而特征空間中每點都極大相似。在此兩種情況下，機器的泛化能力都比較差。
當沒有已標記的數據時，設置核參數并找到特征空間中一個合適映射更難，所有可用的只有一個成對關聯的集合。在本文中，根據給定的關聯獲得一種能自動估計最優核參數的最佳標準，通過將關聯與聚類目標函數相結合，在發現聚類結構時反復優化核參數。具體地說，就是通過度量特征空間中違反正關聯以及負關聯來控制搜索最佳參數值。按照文獻[2，3]中的方法，筆者取特征空間中違反關聯的點測度為懲罰項。其中，違反正關聯mustlink(xi，xj)，在特征空間中，點xi和點xj間測度將更大；違反負關聯cannotlink(xi，xj)，在特征空間中，點xi和點xj間測度將更小。具體如下：
PML(xi，xj)=wij‖(xi)-(xj)‖2 l(li≠lj)（4）
PCL(xi，xj)=wij((Djmax)2-‖(xi)-(xj)‖2) l(li=lj)（5）
其中：l為指示函數（l[true]=1，l[1]=0），Dmax為特征空間中任意點對間測度最大值，它確保違反負關聯的懲罰值是非負的。通過將這兩個懲罰項與核K均值目標函數合并，得到一種可調整核的半監督K均值(kernelbased adaptation semisupervised Kmeans)方法的目標函數：
Jobj=∑kc=1 ∑xi∈πc(‖(xi)-mc‖2)+∑(xi，xj)∈ML，li≠ljwij(‖(xi)-(xj)‖2)+
∑(xi，xj)∈CL，li=ljwij((Dmax)2-‖(xi)-(xj)‖2)（6）
設xa和xb為特征空間中的最遠點，本文用
∑kc=1 ∑xi∈πc‖xi-mc‖2=∑kc=1 ∑xi，xj∈πc‖xi-xj‖2/（2｜πc｜）
重新計算式（6）可得
Jobj=∑kc=1∑(xi，xj)∈πc‖(xi)-mc‖2/（2｜πc｜)+
∑(xi，xj)∈ML，li≠ljwij(‖(xi)-(xj)‖2)+
∑(xi，xj)∈CL，li=ljwij((xa-xb)2-‖(xi)-(xj)‖2) （7）
通過擴展得到在特征空間的測度計算‖(xi)-(xj)‖2，利用核方法K(xi，xj)=(xi)#8226;(xj)，得到
Jobj=∑kc=1∑(xi，xj)∈πc(K(xi，xj)+K(xj，xj)-2K(xi，xj))/（2｜πc｜）+
∑(xi，xj)∈ML，li≠ljwij(K(xi，xj)+K(xj，xj)-2K(xi，xj))+
∑(xi，xj)∈CL，li=ljwij(K(xa，xa)+K(xb，xb)-2K(xa，xb)-
K(xi，xi)-K(xj，xj)+2K(xi，xj)) （8）
取高斯核函數K(xi，xj)=exp(-‖xi-xj‖2/(2σ2))。由于它良好的學習特性，筆者利用核參數σ來最小化Jobj。如前所述，當σ→ ∞時，特征空間中的所有點彼此都極大相似，式（8）中的目標函數為最小值。為了避免這種退化，加入下述的約束條件：
∑xi∈X‖(xi)-(xr)‖2≥const（9）
其中xr是從數據集X中隨機選擇的點。通過將約束條件（式(10)）加入到目標函數中，并應用在特征中間的核方法，最后可得
Jobj=∑kc=1∑(xi，xj)∈πc(1-K(xi，xj)）/｜πc｜+∑(xi，xj)∈ML，li≠lj2wij(1-
K(xi，xj))+∑(xi，xj)∈CL，li=lj2wij(K(xi，xj)-K(xa，xb))-
[∑xi∈X2(1-K(xi，xr))-const]（10）
對高斯核函數K(xi，xj)=exp(-‖xi-xj‖2/(2σ2))求σ的偏導，可得K(xi，xj)/σ=exp(-‖xi-xj‖2/（2σ2)）(‖xi-xj‖2/σ3）。計算:
Jkernel-obj/σ=∑kc=1∑xi，xj∈πc（1/｜πc｜）exp(-‖xi-xj‖2/（2σ2)）×(‖xi-xj‖2/σ3)-∑k(xi，xj)∈ML，li≠lj2wijexp(-‖xi-xj‖2/(2σ2))×
(‖xi-xj‖2/σ3)+∑k(xi，xj)∈CL，li=lj2wij×exp(-‖xi-xj‖2/(2σ2))
(‖xi-xj‖2/σ3)-exp(-‖xa-xb‖2/(2σ2)(‖xa-xb‖2/σ3)+
∑xi∈X2 exp(-‖xi-xr‖2/(2σ2))(‖xi-xr‖2/σ3)
（11）
下面采用基于EM策略，用梯度下降法來優化核函數Jkernelobj。
2.2 基于EM優化策略的SSKOK算法
為最小化目標函數Jkernelobj，基于EM策略，利用文獻[11，12]中提出的方法：取關聯的傳遞閉包來形成鄰居，然后在這些鄰居上進行最遠優先遍歷以得到k個初始聚類，確保相同的關聯集加入實驗中的競爭算法中。
E步：將數據點分配到聚類中去，將M步得到的目標函數的第一項代入，以使目標函數Jkernelobj最小。由于目標函數包含正關聯與負關聯，通過將每個數據點分配到距離最近的質心（目標函數第一項）的聚類中去，并且違反關聯僅得到最小懲罰（目標函數的第二、三項），從而使目標函數值最小。目標函數的第四項在數據點分配期間的每次迭代中為常數。當更新一個給定點的聚類分配時，其他點的分配保持不變[5，9，12]。每次迭代期間，數據點隨機地重新整理，此過程一直重復進行直到在數據點分配中沒有變化時為止。需要說明的是，此步中利用了基于核函數的隱馬爾可夫Kmeans算法，找到最近質心并求出目標函數。
M步：重新計算聚類表示。
a）由于在核空間映射數據，沒有訪問聚類表示的坐標，需要重新計算Bcc，其用于重新分配數據點到E步中的聚類。在這個步驟中沒有使用關聯，因而只實現了目標函數的第一項最小化。
b）由于所有這些步驟都是關于當前特征空間執行的，可通過優化核參數σ來優化特征空間。用梯度下降規則來更新高斯核參數：σ(new)=σ(old)-ρ(Jkernelobj /σ)。其中ρ是一個由線性搜索法優化的標量步長參數的表達式在式(11)給出。
本文提出了一種利用最佳核的半監督核K均值算法(semisupervised kernel Kmeans with optimal kernel，SSKKOK)，其描述如下：
輸入：
數據點集X={xi}Ni=1；
正關聯集 ML；
負關聯集 CL；
聚類的個數k；
違反關聯的代價wij與wij。
輸出：
X劃分成k個聚類。
方法：
a)利用給定的關聯初始化聚類{π(0)c}kc=1，令t=0。
b)重復步驟c)~f)直到收斂。
c)E步：分配每個數據點xi到一個聚類π(t)c中去，將M步得到的目標函數的第一項代入，并使Jkernelobj最小。
d)M步a)：重新計算B(t)cc，for c=1 2 …k。
e)M步b)：采用梯度下降法，根據規則σ(new)=σ(old)-ρ( Jkernel-obj/σ)優化核參數σ。
f)t←(t+1)。
3 實驗驗證
3.1 評價標準
為評估聚類結果，筆者采用隨機統計指數RSI（rand statistic index）。隨機統計是一種外部聚類有效性度量，它用于估算聚類結果的質量。令P1是應用一種聚類算法后數據X的劃分，P2是數據的實際類結構。用下面的項表示點對(xu，xv)∈X×X。
a)A：兩點在P1中分到的相同聚類，在實際的類結構P2中為同一組。
b)B：兩點在P1中分到的相同聚類，在實際的類結構P2中為不同組。
c)C：兩點在P1中分到的不同聚類，在實際的類結構P2中為同一組。
d)D：兩點在P1中分到的不同聚類，在實際的類結構P2中為不同組。
若用NA，NB，NC和ND分別表示A、B、C、D的對數，那么NA+NB+NC+ND=Npais。其中Npais為數據集中所有點對的最大數。隨機統計指數度量P1與P2間的相似程度。
RSI=(NA+ND)/Npais
3.2 實驗結果分析
在Vowel、Wine兩個UCI數據集上進行了實驗。為評價筆者提出的SSKKOK算法的有效性，將其與SSKK算法進行了比較：
SSKK需要輸入一個高斯核參數σ的預定義值。由于缺少有標記數據，參數不能進行交叉校驗。通過對不同σ值的多輪結果聚類質量的平均來估算SSKK期望的精確性。在實驗中，采用不同的σ2測試SSKK算法，分別取σ2為0.05、0.5、5、50、500、5 000。報告了根據六個不同σ值得到的平均隨機統計指數和關于獲得的三個最佳性能的平均值，以此來說明本文方法在后面實例中的優勢。方程（4）中的違反代價wij和wij設置為N/KC。其中N為數據點的個數，K為聚類數，C是關聯的總數。K的值設置為數據中實際類別的數目。
圖1、2是經過對每個數據集20輪的雙重交叉校驗（30%用于訓練，70%用于測試）后的學習曲線，這些圖表明測試集聚類質量的改進為成對關聯增量的函數。為研究關聯在聚類中的效果，在圖中隨機地畫出作為訓練集，并且關聯只能由關聯集產生。聚類算法運行在整個數據集上，但只能在測試集上計算RSI。學習曲線上的每一點都為20輪結果的平均值。
圖1、2中的結果清楚地表明SSKKOK算法的有效性。對Vowel和Wine兩個數據集，獲得的關于不同測試σ值的平均聚類質量要明顯優于由SSKK產生的結果，表明此算法能從給定的關聯中估算出最佳核參數。在只有少量的關聯可用時，SSKKOK算法提供的聚類質量也要明顯高于只有SSKK法提供的聚類質量。由于實際上只有有限數量的監督信息可用，此種方法是非常有意義的。
4 結束語
本文提出了一種能自動調整半監督核聚類中混合高斯核參數的方法，此優化策略能與任意一種基于核聚類的算法相結合，通過將最佳核函數與SSKK算法結合，得到了SSKKOK算法。實驗結果表明，該方法能自動、有效地設置關鍵參數以進行核半監督聚類。在將來的工作中，將測試與其他核聚類技術相關的最優核，并研究不同的混合核函數對可用關聯的作用。
參考文獻：
［1］DHILLON I GUAN Yuqiang KULIS B et al. Kernel Kmeans: spectral clustering and normalized cuts[C]//Proc of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press 2004:345-347.
[2]BASU S BILENKO M MOONEY R et al. A probabilistic framework for semisupervised clustering[C]//Proc of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press. 2004:1248-1252.
[3]CRISTIANINI N SHAWETAYLOR J ELISSEEFF A et al. On kerneltarget alignment[J]. Neural Information Processing Systems，2001，36(9):103-110.
[4]CHAPELLE O VAPNIK V. Choosing mutiple parameters for support vector machines[J]. Machine Learning 2002，46(1-3):131-159.
[5]WANG Wenjian XU Z LU W， et al. Determination of the spread parameter in the gaussian kernel for classification and regression[J]. Neuro Computing 2002 55(3): 645-650.
[6]HUANG Jian YUEN P C CHEN Wensheng et al. kernel subspace LDA with optimized Kernel parameters on face recognition[C]//Proc of the 6th IEEE International Conference on Automatic Face and Gesture Recognition. 2004: 2115-2118.
[7]NATESH S WU Qiang LIANG Feng. Characterizing the function space for Bayesian kernel models[J]. Machine Learning Research 2007，46(8):1770-1778.
[8]LOWE D G. Similarity metric learning for a variablekernel classifier[J]. Neural Computation 1995，7(1):72-85.
[9]BASU S BANERJEE A MOONEY R. Semisupervised clustering by seeding[C]//Proc of the 19th International Conference on Machine Learning. San Francisco:Morgan Kaufmann Publishers 2002:19-26.
[10]KIRI W CLAIRE C. Constrained Kmeans clustering with background knowledge[C]//Proc of the 18th International Conference on Machine Learning.San Francisco:Morgan Kaufmann Publishers 2001:577-584.
[11]KULIS B BASU S DHILLON I et al.Semisupervised graph clustering: a kernel approach[C]//Proc of the 22nd International Conference on Machine Learning. San Francisco:Morgan Kaufmann Publishers 2005:454-461.
[12]PENG Jing HEISTERKAMP D R DAI H K. Adaptive kernel metric nearest neighbor classification[C]//Proc of the 16th International Conference on Pattern Recognition. 2002:33-36.
[13]SKABAR A JUNEJA N. A kernelbased method for semisupervised learning[C]//Proc of the 6th International Conference on Computer and Information Science. 2007:225-230.
