譜聚類算法對輸入數據順序的敏感性

摘要:結合矩陣分析知識，還原了實施譜聚類算法過程中的矩陣表示#65377;發現了不同數據輸入順序使得相應的Affinity矩陣及Laplacian矩陣是相似的#65377;這樣，Laplacian矩陣的特征向量生成的矩陣Y也是相似的;而以Y的行向量作為輸入數據的K平均算法依賴于初始的k個對象的選擇#65377;由此給出了導致譜聚類算法對數據輸入順序敏感的原因#65377;

關鍵詞:譜聚類; 關聯矩陣; 拉普拉斯矩陣; 順序敏感性

中圖分類號:TP3111文獻標志碼:A

文章編號:10013695(2007)04006202

聚類分析是人工智能#65380;模式識別#65380;數據挖掘#65380;機器學習等領域的重要應用工具#65377;這些年來，出現了很多聚類分析算法#65377;比較常見的有K平均#65380;EM#65380;BIRCH#65380;CURE#65380;DBSCAN#65380;WaveCluster#65380;基于有向樹的算法#65380;二值形態聚類算法等#65377;文獻[1，2]對以上這些算法進行了很好的綜述#65377;譜聚類算法是近幾年研究得比較多#65380;應用逐漸廣泛的一種聚類分析算法#65377;它的中心思想是把對數據集合的聚類映射到對其Laplacian矩陣的前k個特征向量組成的矩陣的行向量聚類#65377;這樣不僅可以把對n維數據的聚類轉換成k維數據聚類(很多時候，kn)，達到維數約減的目的，而且應用說明其有很好的聚類效果#65377;

文獻[1]中對聚類分析應用在數據挖掘中提出幾點典型要求#65377;其中一點談到“很多聚類分析算法對于輸入數據的順序是敏感的#65377;也就是說對于同一個數據集合，當以不同的順序提交給同一個算法時，可能生成差別很大的聚類結果”#65377;例如基本順序聚類算法(BSAS)^[2]，輸入數據的順序不僅會影響聚類數量，而且對聚類本身也會有影響;K平均算法也依賴于初始k個點的選擇;神經網絡內在的特點決定了SOM聚類算法對數據的輸入順序也是敏感的，等等#65377;事實上，譜聚類算法對于數據的輸入順序也敏感#65377;不少文章也對此提出改進辦法^[3]，但是鮮有文章對到底是什么原因導致這種敏感性缺乏討論#65377;本文借助矩陣分析知識，討論了針對不同問題提出的譜聚類算法的順序敏感性的原因#65377;

本文給出了一般的譜聚類算法，并且討論了不同譜聚類算法的區別;討論了不同輸入順序對Affinity矩陣的影響;然后研究了順序對Laplacian矩陣，最后得出結論#65377;這其中還給出了當Laplacian矩陣的特征向量以不同順序生成矩陣Y對聚類結果的影響#65377;

1譜聚類算法

設考慮的數據集合為S={s1，…，sn}#65377;一般的譜聚類算法^[4]如下:

(1)當i≠j時，令Aij=exp(-‖si-sj‖2/2σ2);當i=j時，令Aii=0，這樣形成Affinity矩陣A∈Rn×n#65377;其中σ2是一個控制參數(本文將其看成一個常數)#65377;

(2)構造矩陣L=D-1/2AD-1/2#65377;其中D是對角矩陣，其主對角元素Dii=∑nj=1Aij，即矩陣D的主對角元素為矩陣A的相應各行元素之和#65377;

(3)求出矩陣L前k個特征值的特征向量x1，x2，…，xn(重復特征值取其互相正交的特征向量)，構造矩陣X=(x1，x2，…xn)∈Rn×k#65377;

(4)由矩陣X構造矩陣Y#65377;其中Yij=Xij/(∑jX2ij)1/2#65377;

(5)把矩陣Y的每行當做Rk中的某個點，通過K平均或其他算法聚其為k類#65377;

(6)當且僅當矩陣Y的第i行為第j類，則最初的si點為第j類#65377;

既然算法的步驟(5)運用了K平均算法，那么為什么不直接利用K平均算法，而要利用譜聚類呢?圖1#65380;2分別展示了直接利用K平均算法和譜聚類算法對同一數據集進行聚類得到不同的聚類結果^[5]#65377;從圖中可以看出，K平均算法沒有給出一大一小兩個橢圓的聚類結果，而是分為上下兩部分#65377;這是由K平均算法本身缺點造成的#65377;

事實上，譜聚類算法在不同文獻中有些區別，主要在于針對不同的應用在構造矩陣L時的一些調整#65377;文獻[6]中，L=D-1A;文獻[7]中，L=A;文獻[4]中，L=D-1/2AD-1/2;文獻[8]中，L=(A+dmaxI-D)/dmax#65377;其中dmax是矩陣A的最大的行和，即dmax=max(∑jAil，i=1，2，…，n)#65377;

下面將結合譜聚類算法，對以上的四種不同的L矩陣分別進行討論#65377;

2順序敏感性

2.1輸入順序與Affinity矩陣的關系

引理1設矩陣A和矩陣B相似，那么A的特征值和B的特征值相同，并且其特征向量滿足xA=PxB#65377;其中A=P-1BP#65377;

證明略#65377;

設考慮的數據集合為S={s1，…，sn}，按照第1章中的方法構造矩陣A#65377;當順序輸入s1，…，sn時，其Affinity矩陣如下:

這兩個矩陣不妨記為An和A′n#65377;由矩陣分析知識可知，這兩個矩陣是相似的#65377;

這是比較特殊的情形，事實上可以證明以任意順序輸入數據s1，…，sn，得到的矩陣都與An相似#65377;

更進一步說，這里An=P-1A′nP#65377;其中P是第一類初等矩陣的乘積，即交換某兩行(列)對應的初等矩陣#65377;我們知道P=P-1，結合引理1得到如下定理#65377;

定理1設數據集為S={s1，…，sn}，以不同順序輸入得到Affinity矩陣分別為A和B，那么有A=P-1BP，并且兩個矩陣的特征向量存在關系xA=PxB#65377;

由P的特殊性知道，特征向量xB是特征向量xA的若干次第一類初等變換#65377;

2.2輸入順序與L矩陣關系

引理2設矩陣A和B相似并且有A=P-1BP，則DA=P-1DBP，且dmax A=dmax B#65377;

證明略#65377;

針對上面四種不同的L矩陣，分三種情形討論:

(1)當L=A時，此時不同的輸入順序得到的矩陣A和B就是LA和LB#65377;它們當然滿足如下關系LA=P-1LBP#65377;

(2)當L=D-1/2AD-1/2或L=(A+dmaxI-D)/dmax時，由引理2知道，此時不同的輸入順序得到L矩陣LA和LB滿足關系LA=P-1LBP#65377;

(3)當L=D-1A時，由Ax=λx得到D-1Ax=λD-1x#65377;那么不同的輸入順序得到的L矩陣LA和LB也滿足關系LA=P-1LBP#65377;

分為三種情形，主要是因為前面兩種情形得到的L矩陣都是對稱矩陣，最后一種是非對稱的#65377;至此，對L矩陣的討論全部結束#65377;有如下結論:數據的不同輸入順序得到的不同L矩陣是相似的，滿足關系LA=P-1LBP#65377;因此其特征向量也滿足關系xA=PxB，即向量xB是向量xA的若干次第一類初等變換#65377;這樣具體到譜聚類算法中，就導致相應的矩陣Y滿足YA=P-1YBP#65377;

K平均算法的準則函數為E=∑ki=1∑s∈Si|s-mi|2#65377;其中Si為第k類，mi為其均值#65377;該函數的第二個求和是沒有順序關系的#65377;結合第1章中的算法，當選定Laplacian矩陣并求得其前k個特征向量構成矩陣X時，有如下定理:

定理2設矩陣L的前k個特征向量分別為x1，x2，…，xk，那么當以x1，x2，…，xk的任意一個置換xi1，xi2，…，xik的順序構成矩陣X，不會影響最后聚類的結果#65377;

由上分析譜聚類算法#65377;那么其順序敏感性就依賴于算法的步驟(5)采用什么樣的算法#65377;該算法不但要求對輸入順序不敏感，而且可以規避前面的算法中由于不同數據輸入順序得到的不同矩陣Y對聚類結果的影響#65377;K平均算法依賴于初始隨機選擇的k個對象，因此找到了譜聚類算法對于初始數據的不同輸入順序敏感的真正原因#65377;

3結束語

本文中討論了譜聚類算法對于數據輸入順序的敏感性;還原了算法的每一步矩陣表示，發現不同的輸入順序使得相應的Affinity矩陣和Laplacian矩陣是不同的，因此其生成的矩陣Y也是不同的#65377;進一步由于K平均算法依賴于初始隨機選擇的k個對象，這樣本文揭示了譜聚類算法對于數據輸入順序敏感的真正原因#65377;

本文可以作為進一步改良譜聚類算法，使其與數據的輸入順序無關，從而為提高聚類效果提供理論基礎#65377;筆者下一步的想法是針對文本聚類問題，在算法的步驟(5)采用其他對初始化沒有依賴關系的算法改進譜聚類算法#65377;

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。