半監督免疫克隆選擇圖劃分方法

劉漢強

陜西師范大學計算機科學學院，西安 710119

半監督免疫克隆選擇圖劃分方法

劉漢強

陜西師范大學計算機科學學院，西安 710119

LIU Hanqiang.Semisupervised immune clone selection graph partition algorithm.Computer Engineering and Applications,2014,50（22）：11-16.

1 引言

對聚類方法的研究一直是模式識別領域一個比較活躍而且極負挑戰性的研究方向。聚類算法可分為無監督和半監督聚類，前者在聚類過程中，不利用任何先驗信息；后者利用少量的先驗信息來引導聚類過程，在一定程度上可以克服無監督聚類的盲目性，提高了聚類算法的性能。

近幾年來，利用圖譜劃分理論來解決聚類問題成為一個新的研究熱點。圖譜劃分是一類基于兩點間相似關系的方法[1]，并通過最大化或最小化某一圖譜劃分準則獲得樣本的劃分結果。由于圖譜劃分準則的優化問題是一個NP難的問題，為此許多近似求解圖譜劃分的方法被提出。譜聚類[2-4]是一種常見的解決圖譜劃分的方法，它利用數據的Laplacian矩陣的特征向量進行聚類，獲得聚類準則在放松了的連續域中的全局最優解。此外，采用遺傳算法或免疫算法等自然計算的方法來求解圖譜劃分問題，也是一種新的研究思路。該類方法把圖譜劃分準則作為目標函數進行優化，因此不需要求解相似性矩陣的特征向量來實現圖譜劃分。

在聚類過程中利用一定量先驗信息會顯著提高聚類算法的性能。半監督學習中的先驗信息主要有兩種，一是以樣本點成對限制形式出現的監督信息，二是樣本的類屬信息。對于用戶來說要確定樣本類屬會比較困難，而獲得一些關于樣本點是否可以或不能位于同一類的限制信息將會比較容易。另外，基于限制的先驗信息比類屬信息更一般，可以從類屬信息獲得等價的成對限制信息，反之則不然。由于圖譜劃分方法是基于兩點間相似關系的方法，這使得利用成對限制先驗信息變得非常容易。為此，本文提出一種半監督的免疫克隆選擇圖劃分方法，首先將成對限制信息和最短路徑距離測度引入到圖譜劃分方法樣本點的相似性測度中，使得構造的相似性矩陣一方面充分體現了數據的全局一致性，另一方面實現了成對限制信息在樣本空間的有效傳播，然后在獲得的相應的相似性矩陣的基礎上，利用免疫克隆選擇優化方法[5-6]來優化圖譜劃分準則，此外，在進化過程中利用權核k均值算法的目標函數和圖譜劃分準則的等價性[7]，提出了一個個體修正算子，使得個體以更快的速度向更優的方向進化。在USPS手寫體數字集和UMIST人臉數據集的仿真實驗驗證了方法的魯棒性和有效性。

2 譜圖劃分理論與免疫克隆選擇優化

2.1 譜圖劃分理論

已知給定的任意特征空間中的數據集合X= {x1,x2,…,xn}，傳統的圖劃分方法將這些數據表示成一個帶權無向圖G=(V,E,S)，其中結點vi∈V對應著特征空間中的數據點xi，eij∈E表示連接兩個結點vi和vj的邊，邊的權值為Sij，即為數據點xi和xj的相似性值，因此S為數據間的相似性矩陣。在構造的圖的基礎上，通過優化某種譜圖劃分準則來對該圖進行劃分，獲得這些數據的聚類結果，也就是將數據的聚類問題轉化為在圖G上的圖劃分問題。在圖G上的劃分就是將圖G= (V,E,S)劃分為k個互不相交的子集C1,C2,…,Ck，劃分后保證每個子集Cl(1≤l≤k)內數據點間的相似性大，不同的子集Cp和Cq(1≤p≤k,1≤q≤k,p≠q)之間數據點間的相似性小。常見的劃分準則[2，3，8-10]有最小切準則、率切準則、規范切準則、最小最大切準則等，劃分準則的好壞直接影響到聚類結果的質量。

在譜圖劃分理論中，將圖G劃分成C1和C2兩個互不相交的子圖的目標函數定義為兩個子圖之間的切(Cut)，其具體形式如下：

2000年，Shi和Malik提出了規范切（Normalized Cut，NCut）準則[2]，該準則的目標函數為：

其中，degree(C1)=Cut(C1,G)表示子圖C1中的結點到圖G中所有結點的權值之和。當需要對圖進行多類劃分時，可以采用多路譜圖劃分準則。下式為多路規范切（Multiway Normalized Cut，MNCut）準則[2，10]的定義：

規范切準則通過引入容量的概念來規范化類間相關性，從而不僅能夠衡量樣本集類間的相似程度，也能衡量類內數據間的相似程度。較好地解決了已有準則將少數樣本點孤立為一類的偏斜劃分問題。

2.2 免疫克隆選擇優化方法

對于圖劃分問題而言，求解圖譜劃分準則是一個NP難的問題[2]。傳統的優化算法由于本身存在一些局限性和不足，已經很難達到這種復雜問題的優化求解要求。作為一種新的全局優化搜索算法，免疫克隆選擇算法[5]在算法實現上兼顧全局搜索和局部搜索，它模擬了生物學抗體克隆選擇過程中的學習、記憶、抗體多樣性等特性，并利用相應的算子保證了該算法能快速地收斂到全局最優解，至今該算法已在模式識別、數據挖掘和組合優化等領域得到了廣泛的應用[5-6，11-12]。

免疫克隆優化算法的基本流程如下：

步驟1初始化抗體種群A(k)，k=0，初始化算法參數，計算初始種群種個體的親和度。

步驟2依據親和度和設定的抗體克隆規模，對抗體種群A(k)依據克隆比例進行克隆操作，得到克隆后的種群Y(k)。

步驟3以概率pm對Y(k)實現免疫基因操作，得到新的抗體種群Z(k)。

步驟4對Z(k)進行克隆選擇操作，得到新的抗體種群A′(k)。

步驟5若滿足終止條件，輸出A′(k)，否則A(k+1)=A′(k)，k=k+1，返回步驟2。

克隆操作有效地實現了搜索空間的擴張；免疫基因操作實現了抗體親和度的成熟和多樣性的產生[5]；克隆選擇操作通過局部擇優，有效地壓縮了種群的大小。

3 半監督免疫克隆選擇優圖劃分算法

為了解決譜圖劃分準則的優化問題，引入成對限制信息和最短路徑距離來構造相似性矩陣，并采用免疫克隆選擇算法來優化圖譜劃分準則，提出了半監督免疫克隆選擇圖劃分方法。

3.1 融合成對限制信息的最短路徑距離相似性測度

把譜圖劃分理論用于數據聚類前的首要工作是構造相似性矩陣，相似性矩陣中的每一個元素表示的是兩個數據點之間相似性。由前面介紹的譜圖劃分理論可知，數據集中的樣本點可以看做是圖G中結點，因此樣本點間的相似性可以采用結點間的距離來衡量。此外，為了在分類問題中既考慮已有的半監督信息（成對限制信息），又充分考慮數據的全局一致和局部一致性，在本文中，引入融合成對限制信息的最短路徑距離測定來構造樣本間的相似性。設X={x1,x2,…,xn}是特征或數據點的集合，兩個樣本點xi和xj之間的最短路徑距離具體定義如下：

其中，Pij表示連接數據點xi和xj的所有路徑的集合，p表示該路徑集合中的任意一條路徑，len為該路徑的長度，ph表示該路徑上的第h個結點。L(ph,ph+1)為連接路徑上相鄰兩點間的距離，其定義如下：

其中，dist(ph,ph+1)為ph與ph+1之間的歐氏距離，ρ＞1為伸縮因子。為了有效地利用成對限制信息，采用mustlink和cannot-link這兩種類型的成對點限制來輔助樣本點間的距離的計算，其中，must-link限制規定兩個樣本必須在同一聚類中，cannot-link限制規定兩個樣本不能在同一聚類中。具體來說，就是對式（5）中的兩點之間的歐式距離dist(xi,xj)施加成對限制信息。如果(xi,xj)∈must-link，則dist(xi,xj)=0；如果(xi,xj)∈cannot-link，則dist(xi,xj)=inf。

顯然，采用了成對限制信息的最短路徑距離測度仍然滿足距離度量的三個條件，即對于結點xi，xj和xk：

這種距離測度可以度量沿著流形上的最短路徑，使得位于同一流形上的兩點可以用許多較短的邊相連接，而位于不同流形上的兩點要用較長的邊相連接，從而實現了放大位于不同流形上的數據點間的距離，而縮短位于同一流形上的數據點間的距離的目的。因此，在此距離測度的基礎上定義樣本點間的相似性度量：

3.2 半監督免疫克隆選擇圖劃分方法

根據3.1部分定義的相似性測度，可以得到對應的無向圖G，下面利用免疫克隆選擇優化方法對該圖進行劃分得到劃分結果。

3.2.1 親和度函數

為了方便起見，且不失一般性，本文僅以規范切準則為例介紹半監督免疫克隆選擇圖劃分算法，關于其他準則的半監督免疫克隆選擇圖劃分框架可以類似得到。對多路規范切準則進行化簡，其公式可以進一步表示為：

因此，多路規范切準則的最小化問題轉化為了最大化問題，其中D為度矩陣，其對角元素Dpp是相似性矩陣S的第p行的元素之和，其余元素為零。根據公式（7）給定的多路規范切準則的等價形式，將公式（7）作為半監督免疫克隆選擇圖劃分的親和度函數。

3.2.2 編碼及免疫算子設計

由譜圖劃分準則可知，劃分的目標是獲得數據集X的k個劃分。這里將每個數據點的類別作為優化求得的解，認為數據集的一個劃分結果就是一個抗體，每個抗體中的基因位是由該數據點的歸屬類別確定，抗體的編碼長度為數據集中數據點的數目。已知數據集的規模為n，聚類的類別數為k，因此種群中第i個抗體ai的編碼方式為：

基于免疫克隆選擇優化的圖劃分方法中主要包括克隆、變異和選擇三個操作算子。在這些算子的作用下，使得群體不僅能夠維持多樣性，防止“早熟收斂”，并且還能迅速地向可行解方向進化。

假設種群的規模為N。抗體的克隆操作就是在適應度最高的抗體中選擇m個抗體進行克隆，克隆規模是Nc。傳統的進化算法一般保持種群規模不變，強調了自然選擇中的個體競爭。而克隆操作通過最優抗體復制使得對該抗體同時進行多種操作提供了可能。

抗體的變異操作是為了產生具有多樣性的抗體，從而得到問題的全局最優解。變異操作就是產生1到n之間的一個隨機整數，然后對其對應的基因的位置進行變異。由于每個基因位對應于該數據點的類別，因此產生一個0和1之間的隨機數，如果該隨機數小于變異概率，則該基因位就被變異為1到k之間的任意整數，且該整數不能和原來基因位上的數相同。

對抗體進行克隆和變異后，對得到的新抗體按照適應度值進行選擇。最終選擇N個最優抗體進入下一代中。

3.2.3 抗體修正算子的設計

值得指出的是，在本文中每個個體是由各個數據點的類別組成的，這種編碼方式使得個體的編碼過長，而且產生的個體具有很大的隨機性，更重要的是圖譜劃分準則的優化是一個NP難的問題。免疫克隆選擇算法要想獲得較好的解，需要很大的迭代次數。

在權核k均值算法的框架中，在給定初始劃分的基礎上，一般根據每個數據點xi與各個聚類中心的距離來產生數據的新劃分，實際上這個處理恰恰是利用了數據之間的關系來產生新的劃分。為了克服提出的算法收斂過慢的缺點，受權核k均值算法框架的這一處理的啟發，定義一個個體修正算子，對隨機產生的個體進行修正，使得個體以更快的速度向更優的方向進化。

注意到式（9）中的第一項對于數據點xi來說是常數，式（9）可以被進一步簡化為：

在對初始種群中的每個個體進行克隆操作之前，先利用式（10）按照數據點xi與各個聚類中心的距離產生一個修正后的新個體，然后計算修正后的個體的適用度函數值，如果修正后的個體的適用度函數值大于修正前的，那么就用修正后的個體替代修正前的個體，否則保持不變。對于變異后的個體，在進行選擇操作之前，也可進行上述操作，如果修正后的個體的適用度函數值大于修正前的，那么就用修正后的個體替代修正前的個體，否則保持不變。通過實驗發現，通過這一操作大大加快了算法的收斂速度。

4 驗證實驗及結果評價

在文獻[6]中，已經驗證了免疫克隆選擇圖劃分方法比傳統的譜聚類算法要具有更好的性能。在文獻[13]中，作者也已用實驗證明了密度敏感的半監督譜聚類（DS_SSC）[10]的性能要優于文獻[14]的受限的完全連接層次聚類算法和文獻[15]的受限的譜聚類算法。因此在實驗中，僅將提出的新算法（ICS-SGP）與DS_SSC進行比較。本文所有實驗中成對限制的數目取自0～200之間。對于每一個給定的限制數目進行20次實驗，對平均結果進行比較。由于所選限制的不同對于聚類算法的性能有著很大的影響，為了實驗的公平性，對于同一個限制數目產生的20組限制必須是不同的。在文獻[6]中，指定免疫克隆選擇圖劃分算法（ICS-GP）和密度敏感譜聚類（DS-SC）采用同樣的參數設置，確保了各個算法競爭的公平性，對于USPS數據集和UMIST人臉數據集，ρ=erho，rho參數變化范圍分別為[2-9,2-8.9,…,2-5]和[2-8,2-7.9,…,2-4]。同樣的，ICS-SGP和DS-SSC算法也涉及到參數選擇問題。對于所有實驗，采用ICS-GP在每個數據集上取得最優性能（利用聚類正確率[16]來衡量算法的性能）下的參數作為ICS-SGP和DS-SSC算法的參數。為了公平起見，還給出了兩種算法在DS-SC算法的最優參數（DS-SC算法取得最優性能下的參數）下的實驗結果。

4.1 USPS數據集

本節選擇了USPS數據集作為測試數據，將新算法應用于手寫體數字識別中。USPS數據集是由9 298個灰度圖像構成，其中包含7 291個訓練樣本，2 007個測試樣本。實驗取全部測試樣本作為聚類數據集，從中挑選三組較難識別的{0，8}、{3，5，8}、{3，8，9}數字集合進行識別，表1給出了這三個手寫體數據集的描述。對于這三個數據集，ICS-GP算法的最優參數rho1分別為2-6.1、2-5.7和2-5.6，DS-SC算法的最優參數rho2分別為2-6.0、2-5.7和2-5.8。圖1中給出了ICS-SGP和DS-SSC對這三組手寫體數字集合的識別性能隨成對限制信息數目變化的曲線。

表1 USPS手寫體數據集

從圖1可以看出，當不提供成對限制信息時（即在圖中的初始點處），對于所有數字集合，ICS-GP算法在參數rho1下的聚類性能要優于其在參數rho2下的結果，但是相差無幾，表明對于USPS數據集，ICS-GP算法對于參數相對不敏感；DS-SC算法在參數rho2下的聚類性能要優于其在參數rho1下的結果，對于除了{0，8}以外的其他的數據集，DS-SC算法在兩個參數下的結果相差很多，表明對于USPS數據集，DS-SC算法對于參數相對較敏感。在圖中的初始點處，ICS-GP在任一參數下的聚類性能都要明顯優于DS-SC算法在任一參數下的結果。

當逐步加入成對限制信息后，ICS-SGP在兩個參數下的聚類性能都得到了逐步提高的同時，在兩個參數下的聚類性能仍保持相差不多；DS-SSC算法隨著成對限制信息的增多，對于除了{0，8}以外的其他的數據集，在參數rho2下的聚類性能還是明顯優于其在參數rho1下的結果。可以看到，DS-SSC在任一參數下的聚類性能還是要低于ICS-SGP在任一參數下的聚類性能，表明對于手寫體數據集，ICS-SGP的性能明顯優于DS-SSC算法。需要注意的是，隨著成對限制數目的增加，兩個算法的聚類正確率并不總是隨之增加，有時甚至出現了聚類準確率下降的現象。這主要是因為在此限制數目下，20次實驗隨機產生的限制信息不夠理想，如果增加重復實驗的次數，性能曲線會變化的平坦一點。

圖1 USPS手寫體數字集的實驗對比結果

4.2 UMIST人臉數據集

UMIST人臉庫是由20個人在相同的光照、不同的姿態（從側面到正面）條件下，總共564張灰度圖像組成，圖像大小均為92×112。為了下面實驗敘述方便，對Umist_cropped中的20個人按照{1，2，…，20}進行排序。在本文實驗中，將人臉圖像下采樣為46×56像素大小，從中挑選兩組連續的人臉數據集{1，2，3，4，5}和{6，7，8，9，10}，以及隨機抽取的兩組數據集{4，9，12，14，16}和{8，13，14，16，17}作為測試數據，表2給出了這人臉數據集的描述。對于這四個數據集，ICS-GP算法的最優參數rho1分別為2-5.7、2-4.1、2-5.0和2-4.2，DS-SC算法的最優參數rho2分別為2-4.3、2-4.6、2-5.2和2-4.8。在圖2中給出了DS-SSC和ICS-SGP對這四組人臉數據集的識別性能隨成對限制信息數目變化的曲線。

表2 UMIST人臉數據集

從圖3可以看出，在圖中的初始點處，ICS-GP在rho1參數下的聚類性能要優于其在rho2參數下的結果；DS-SC在rho2參數下的聚類性能要優于其在rho1參數下的結果。在rho1參數下，ICS-GP的聚類正確率要高于DS-SC；在rho2參數下，DS-SC的聚類正確率要高于ICS-GP。除了{1，2，3，4，5}數據集以外，ICS-GP在rho1參數下的聚類性能都優于DS-SC算法在任一參數下的結果。

隨著成對限制信息的增加，ICS-SGP在rho1參數下的聚類性能仍保持優于其在rho2參數下的結果；除了{1，2，3，4，5}數據集之外，DS-SSC算法在參數rho2下的聚類性能基本上還是優于其在參數rho1下的結果。對于這四個數據集，在rho1參數下，對于每一個限制信息數目，ICS-SGP的聚類正確率幾乎都要高于DS-SSC。然而除了{1，2，3，4，5}數據集以外，在每一個限制信息數目下，rho2參數下的ICS-SGP的聚類正確率幾乎都要高于DS-SSC。另外，rho1參數下的ICS-SGP在每一個限制信息數目下的聚類結果基本上都是這兩個算法在任一參數下最優的，而且除了{1，2，3，4，5}數據集以外，ICS-SGP在rho2參數（DS-SC的最優參數）下的結果也都基本上要優于DS-SSC在任一參數下的結果，這充分表明了ICS-SGP在人臉識別問題中具有優于DS-SSC的性能。和前面的手寫體數據集實驗一樣，隨著成對限制數目的增加，兩個算法的聚類正確率也出現了聚類準確率下降的現象，同樣如果增加重復實驗的次數，性能曲線會變化的平坦一點。

5 結束語

本文提出了一種新的半監督聚類算法：半監督免疫克隆選擇圖劃分算法。新方法利用成對限制信息和最短路徑距離測度來構造樣本點之間的相似性測度，并采用免疫克隆選擇優化方法來優化圖譜劃分準則來獲得最終的聚類結果，手寫體數字和人臉數據集上的仿真實驗表明了新算法具有的良好性能。值得指出的是，給定的成對限制信息理想與否對于聚類結果有很大的影響，這一點可以從實驗結果中明顯看出。因此，將信息量更豐富的限制信息，例如相對比較限制信息，引入到半監督免疫克隆選擇圖劃分算法中是下一步的工作。

圖2 UMIST人臉數據集的實驗對比結果

[1]Fiedler M.Algebraic connectivity of graphs[J].Czechoslovak Mathematical Journal，1973，23（98）：298-305.

[2]Shi J，Malik J.Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888-905.

[3]Ng A Y，Jordan M I，Weiss Y.On spectral clustering：Analysis and an algorithm[C]//Dietterich T G，Becker S，Ghahramani Z.Advances in Neural Information Processing Systems（NIPS）14.Cambridge：MIT Press，2002.

[4]高尚兵，周靜波，嚴云洋.一種新的基于超像素的譜聚類圖像分割算法[J].南京大學學報：自然科學版，2013，49（2）：169-175. [5]焦李成，杜海峰，劉芳，等.免疫優化計算學習與識別[M].北京：科學出版社，2006.

[6]劉漢強.免疫克隆選擇圖劃分方法[J].計算機應用研究，2012，29（9）：3516-3520.

[7]Dhillon I S，Guan Y，Kulis B.Weighted graph cuts without eigenvectors：a multilevel approach[J].IEEE TransactionsonPatternAnalysisandMachineIntelligence，2007，29（11）：1944-1957.

[8]Hagen L，Kahng A B.New spectral methods for ratio cut partitioning and clustering[J].IEEE Transactions on Computer-Aided Design，1992，11（9）：1074-1085.

[9]Ding C，He X，Zha H，et al.A min-max cut algorithm for graphpartitioninganddataclustering[C]//Proceedings of ICDM，2001：107-114.

[10]Meila M，Xu M.Multiway cuts and spectral clustering[R]. U.Washington Tech Report，2003.

[11]楊光軍.基于文化免疫克隆算法的關聯規則挖掘研究[J].計算機工程與應用，2013，49（15）：113-115.

[12]馬玉新，解建倉，羅軍剛.基于免疫克隆選擇算法的馬斯京根模型參數估計[J].計算機工程與應用，2010，46（34）：208-212. [13]王玲，薄列峰，焦李成.密度敏感的半監督譜聚類[J].軟件學報，2007，18（10）：2412-2422.

[14]Klein D，Kamvar S D，Manning C D.From instance-level constraints to space-level constraints：Making the most of prior knowledge in data clustering[C]//Sammut C，Hoffmann A G.Proc of the 19th Int’l Conf on Machine Learning. Sydney：Morgan Kaufmann Publishers，2002：307-314.

[15]Xu Q J，DesJardins M，Wagstaff K.Constrained spectral clustering under a local proximity structure assumption[C]// Russell I，Markov Z.Proc of the 18th Int’l Conf of theFloridaArtificialIntelligenceResearchSociety，Clearwater Beach.Florida：AAAI Press，2005.

[16]Wu M，Sch?lkopf B.A local learning approach for clustering[C]//Sch?lkopf B，Platt J，Hofmann T.Advances in Neural Information Processing Systems.USA：MIT Press，2007：1529-1536.

LIU Hanqiang

School of Computer Science,Shaanxi Normal University,Xi’an 710119,China

Using some prior information can significantly improve the performance of clustering algorithms.In order to solve the NP-hard graph partitioning problems and utilize some prior information,a semisupervised immune clone selection graph partition algorithm the pairwise constraint information is introduced into the similarity measure in the graph partitioning algorithms,then the immune clonal selection algorithm is utilized to optimal the criterion of the graph partitioning based on the corresponding similarity matrix to obtain the solution.The experimental results on the USPS handwritten digit datasets and UMIST face datasets show that the novel method is effective.

pairwise constraint information;immune clonal selection algorithm;graph partition

在聚類過程中利用一定量先驗信息會顯著提高聚類算法的性能。為了解決求解圖譜劃分方法NP難的問題并合理地利用一定量的先驗信息，將成對限制信息引入到圖譜劃分方法中樣本點的相似性測度，并在獲得的相應的相似性矩陣的基礎上，利用免疫克隆選擇優化方法來優化圖譜劃分準則，提出了半監督免疫克隆選擇圖劃分方法。USPS手寫體數字集和UMIST人臉數據集識別的仿真實驗證明了新方法的有效性。

成對限制信息；免疫克隆選擇算法；圖劃分

A

TP391；TN911.73

10.3778/j.issn.1002-8331.1402-0449

國家自然科學基金（No.61202153，No.61102095）；陜西省自然科學基礎研究計劃資助項目（No.2012JQ8045，No.2014JQ8336）；陜西省科學技術研究發展計劃資助項目（No.2014KJXX-72）。

劉漢強（1981—），男，博士，副教授，研究領域為模式識別，圖像處理。E-mail：liuhq@snnu.edu.cn

2014-03-03

2014-06-03

1002-8331（2014）22-0011-06

CNKI網絡優先出版：2014-06-26,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0449.html