劉漢強

陜西師范大學(xué)計算機科學(xué)學(xué)院，西安 710119

半監(jiān)督免疫克隆選擇圖劃分方法

劉漢強

陜西師范大學(xué)計算機科學(xué)學(xué)院，西安 710119

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

1 引言

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

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

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

2 譜圖劃分理論與免疫克隆選擇優(yōu)化

2.1 譜圖劃分理論

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

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

2000年，Shi和Malik提出了規(guī)范切（Normalized Cut，NCut）準(zhǔn)則[2]，該準(zhǔn)則的目標(biāo)函數(shù)為：

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

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

2.2 免疫克隆選擇優(yōu)化方法

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

免疫克隆優(yōu)化算法的基本流程如下：

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

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

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

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

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

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

3 半監(jiān)督免疫克隆選擇優(yōu)圖劃分算法

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

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

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

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

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

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

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

3.2 半監(jiān)督免疫克隆選擇圖劃分方法

根據(jù)3.1部分定義的相似性測度，可以得到對應(yīng)的無向圖G，下面利用免疫克隆選擇優(yōu)化方法對該圖進(jìn)行劃分得到劃分結(jié)果。

3.2.1 親和度函數(shù)

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

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

3.2.2 編碼及免疫算子設(shè)計

由譜圖劃分準(zhǔn)則可知，劃分的目標(biāo)是獲得數(shù)據(jù)集X的k個劃分。這里將每個數(shù)據(jù)點的類別作為優(yōu)化求得的解，認(rèn)為數(shù)據(jù)集的一個劃分結(jié)果就是一個抗體，每個抗體中的基因位是由該數(shù)據(jù)點的歸屬類別確定，抗體的編碼長度為數(shù)據(jù)集中數(shù)據(jù)點的數(shù)目。已知數(shù)據(jù)集的規(guī)模為n，聚類的類別數(shù)為k，因此種群中第i個抗體ai的編碼方式為：

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

假設(shè)種群的規(guī)模為N?？贵w的克隆操作就是在適應(yīng)度最高的抗體中選擇m個抗體進(jìn)行克隆，克隆規(guī)模是Nc。傳統(tǒng)的進(jìn)化算法一般保持種群規(guī)模不變，強調(diào)了自然選擇中的個體競爭。而克隆操作通過最優(yōu)抗體復(fù)制使得對該抗體同時進(jìn)行多種操作提供了可能。

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

對抗體進(jìn)行克隆和變異后，對得到的新抗體按照適應(yīng)度值進(jìn)行選擇。最終選擇N個最優(yōu)抗體進(jìn)入下一代中。

3.2.3 抗體修正算子的設(shè)計

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

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

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

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

4 驗證實驗及結(jié)果評價

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

4.1 USPS數(shù)據(jù)集

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

表1 USPS手寫體數(shù)據(jù)集

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

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

圖1 USPS手寫體數(shù)字集的實驗對比結(jié)果

4.2 UMIST人臉數(shù)據(jù)集

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

表2 UMIST人臉數(shù)據(jù)集

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

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

5 結(jié)束語

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

圖2 UMIST人臉數(shù)據(jù)集的實驗對比結(jié)果

[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]高尚兵，周靜波，嚴(yán)云洋.一種新的基于超像素的譜聚類圖像分割算法[J].南京大學(xué)學(xué)報：自然科學(xué)版，2013，49（2）：169-175. [5]焦李成，杜海峰，劉芳，等.免疫優(yōu)化計算學(xué)習(xí)與識別[M].北京：科學(xué)出版社，2006.

[6]劉漢強.免疫克隆選擇圖劃分方法[J].計算機應(yīng)用研究，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]楊光軍.基于文化免疫克隆算法的關(guān)聯(lián)規(guī)則挖掘研究[J].計算機工程與應(yīng)用，2013，49（15）：113-115.

[12]馬玉新，解建倉，羅軍剛.基于免疫克隆選擇算法的馬斯京根模型參數(shù)估計[J].計算機工程與應(yīng)用，2010，46（34）：208-212. [13]王玲，薄列峰，焦李成.密度敏感的半監(jiān)督譜聚類[J].軟件學(xué)報，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難的問題并合理地利用一定量的先驗信息，將成對限制信息引入到圖譜劃分方法中樣本點的相似性測度，并在獲得的相應(yīng)的相似性矩陣的基礎(chǔ)上，利用免疫克隆選擇優(yōu)化方法來優(yōu)化圖譜劃分準(zhǔn)則，提出了半監(jiān)督免疫克隆選擇圖劃分方法。USPS手寫體數(shù)字集和UMIST人臉數(shù)據(jù)集識別的仿真實驗證明了新方法的有效性。

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

A

TP391；TN911.73

10.3778/j.issn.1002-8331.1402-0449

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

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

2014-03-03

2014-06-03

1002-8331（2014）22-0011-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-06-26,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0449.html