基于C均值聚類和圖轉(zhuǎn)導(dǎo)的半監(jiān)督分類算法

王 娜，王小鳳，耿國華，宋倩楠

(西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，西安 710000)(*通信作者電子郵箱xfwang@nwu.edu.cn)

基于C均值聚類和圖轉(zhuǎn)導(dǎo)的半監(jiān)督分類算法

王 娜，王小鳳*，耿國華，宋倩楠

(西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，西安 710000)(*通信作者電子郵箱xfwang@nwu.edu.cn)

針對傳統(tǒng)圖轉(zhuǎn)導(dǎo)(GT)算法計(jì)算量大并且準(zhǔn)確率不高的問題，提出一個(gè)基于C均值聚類和圖轉(zhuǎn)導(dǎo)的半監(jiān)督分類算法。首先,采用模糊C均值(FCM)聚類算法先對未標(biāo)記樣本預(yù)選取，縮小圖轉(zhuǎn)導(dǎo)算法構(gòu)圖數(shù)據(jù)集的范圍；然后,構(gòu)建k近鄰稀疏圖，減少相似度矩陣的虛假連接，進(jìn)而縮減了構(gòu)圖的時(shí)間，通過標(biāo)記傳播的方式得出初選未標(biāo)記樣本的標(biāo)記信息；最后，結(jié)合半監(jiān)督流形假設(shè)模型利用擴(kuò)充的標(biāo)記數(shù)據(jù)集以及剩余未標(biāo)記數(shù)據(jù)集進(jìn)行分類器的訓(xùn)練，進(jìn)而得出最終的分類結(jié)果。在Weizmann Horse數(shù)據(jù)集下，所提算法分類準(zhǔn)確率均達(dá)到96%以上，和傳統(tǒng)僅使用圖轉(zhuǎn)導(dǎo)的分類方法相比，解決了對初始標(biāo)記集的依賴性問題，將準(zhǔn)確率至少提高了10%；將所提算法直接運(yùn)用到兵馬俑數(shù)據(jù)集，分類準(zhǔn)確度也達(dá)到95%以上，明顯高于傳統(tǒng)的圖轉(zhuǎn)導(dǎo)算法。實(shí)驗(yàn)結(jié)果表明，基于C均值聚類和圖轉(zhuǎn)導(dǎo)的半監(jiān)督分類算法，在圖像分類方面有較好的分類效果，對圖像的精準(zhǔn)分類具有研究意義。

C均值聚類；圖轉(zhuǎn)導(dǎo)；半監(jiān)督分類；相似度矩陣；稀疏圖

0 引言

目前，監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)以及半監(jiān)督學(xué)習(xí)算法為三大熱門學(xué)習(xí)算法?；诂F(xiàn)實(shí)中圖像、模型等領(lǐng)域具有的海量數(shù)據(jù)中只有小部分標(biāo)記樣本的現(xiàn)狀，充分利用標(biāo)記數(shù)據(jù)以及無標(biāo)記數(shù)據(jù)進(jìn)行分類學(xué)習(xí)，成為更主流的研究方式，這也造就了半監(jiān)督學(xué)習(xí)算法在分類算法中炙手可熱的地位。半監(jiān)督學(xué)習(xí)算法擁有兩個(gè)分支，即歸納學(xué)習(xí)算法和轉(zhuǎn)導(dǎo)學(xué)習(xí)算法，其中，是否生成分類器是兩種算法最大的區(qū)別。具體而言，歸納學(xué)習(xí)是利用標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)學(xué)習(xí)得到分類器，進(jìn)而通過分類器進(jìn)行數(shù)據(jù)分類的方法，而圖轉(zhuǎn)導(dǎo)(Graph Transduction,GT)學(xué)習(xí)并不需要形成分類器，直接利用整個(gè)數(shù)據(jù)集便可以進(jìn)行分類。相比而言，圖轉(zhuǎn)導(dǎo)算法更為經(jīng)濟(jì)。在圖轉(zhuǎn)導(dǎo)算法中，聚類假設(shè)、流形假設(shè)以及局部和全局一致性假設(shè)是比較常用的假設(shè)方法，其中，聚類假設(shè)保障了圖轉(zhuǎn)導(dǎo)算法中，數(shù)據(jù)在相鄰位置上相似度較高時(shí)，對應(yīng)節(jié)點(diǎn)趨于相似的標(biāo)記。因此，本文重點(diǎn)研究基于聚類假設(shè)的圖轉(zhuǎn)導(dǎo)學(xué)習(xí)方法，使用圖結(jié)構(gòu)來表示輸入的數(shù)據(jù)集，圖的每個(gè)頂點(diǎn)分別對應(yīng)數(shù)據(jù)集中的一個(gè)樣本數(shù)據(jù)信息，每條邊的權(quán)重代表樣本數(shù)據(jù)之間的相似程度，并且在進(jìn)行構(gòu)圖前，提前進(jìn)行無標(biāo)記樣本的預(yù)選取，結(jié)合半監(jiān)督算法實(shí)現(xiàn)大量未標(biāo)記樣本的分類。

1 相關(guān)工作

目前，國內(nèi)外已有很多學(xué)者對圖轉(zhuǎn)導(dǎo)算法進(jìn)行研究，并提出諸多算法。標(biāo)簽傳播(Label Propagation, LP)算法[1]是圖轉(zhuǎn)導(dǎo)算法的基礎(chǔ)，通過圖的邊將標(biāo)記信息傳播到未標(biāo)記節(jié)點(diǎn)，由于圖轉(zhuǎn)導(dǎo)算法是基于聚類假設(shè)，所以權(quán)重大的邊比權(quán)重小的邊標(biāo)記傳播更容易一些，在權(quán)重為0的邊終止標(biāo)記傳播。在此基礎(chǔ)上衍生出調(diào)和高斯場(Harmonic Gaussian Field, HGF)[2]、局部與全局一致性(Learning with Local and Global Consistency, LLGC)[3]、極大極小標(biāo)簽傳播(MiniMax Label Propagation, MMLP)算法[4]、最小代價(jià)路徑標(biāo)簽傳播(Label Propagation through Minimum Cost Path, LPMCP)算法[5]等方法。不論是HGF還是LLGC算法都過于依賴初始標(biāo)記集，若圖中含有噪聲，或者因?yàn)槠渌蛩厥沟幂斎霐?shù)據(jù)集不可劃分類別時(shí)，通過圖轉(zhuǎn)導(dǎo)方法得到的分類結(jié)果缺乏準(zhǔn)確性。

實(shí)際中并不是所有的無標(biāo)記樣本都能對分類提供幫助，因此挑選出對分類有用的無標(biāo)記樣本會提高分類準(zhǔn)確性，也會提高構(gòu)圖的效率。文獻(xiàn)[6]中采用主動學(xué)習(xí)人工標(biāo)注的方式初選未標(biāo)記樣本，但是人工標(biāo)注樣本會增加時(shí)間開銷。為了解決該問題本文利用模糊C均值(Fuzzy C-means, FCM)聚類算法對無標(biāo)記樣本進(jìn)行聚類，然后在聚類結(jié)果基礎(chǔ)上進(jìn)行無標(biāo)記樣本的選取，得出最好的選取方式；將無標(biāo)記樣本中部分含有對分類有用信息的樣本加入到訓(xùn)練樣本集[7]，避免了人工參與標(biāo)注。

傳統(tǒng)圖轉(zhuǎn)導(dǎo)(GT)算法構(gòu)建全相連圖，需要將所有的邊都存儲計(jì)算，而本文構(gòu)建k近鄰稀疏圖，可以自適應(yīng)樣本特征空間中的密度，得到真實(shí)的權(quán)重，不僅阻止了相似度低節(jié)點(diǎn)信息的傳遞，也提高了算法運(yùn)算速度。為了能更進(jìn)一步提高分類的精度，本文進(jìn)一步利用半監(jiān)督學(xué)習(xí)(Semi-Supervised Learning, SSL)算法[8-9]得出最后的分類結(jié)果。具體的思路如圖1所示。

圖1 本文算法思路

2 算法描述

假設(shè)有n個(gè)樣本點(diǎn)的數(shù)據(jù)集參與分類，即X={x1,x2,…,xn}，已標(biāo)記數(shù)據(jù)集Xl={x1,x2,…,xl}，未標(biāo)記數(shù)據(jù)集為Xu={xl+1,xl+2,…,xn}，其中n=l+u，且l?u，類別數(shù)量已知為c。Yl={y1,y2,…,yl},yi∈{1,2,…,c}為已標(biāo)記數(shù)據(jù)集Xl所對應(yīng)的標(biāo)記集，并且假設(shè)Yl中包含所有的類別標(biāo)記。

在此定義的基礎(chǔ)之上，本文算法主要分為3步：

步驟1 使用FCM聚類算法對未標(biāo)記樣本進(jìn)行聚類，根據(jù)聚類結(jié)果選取聚類的邊界點(diǎn)作為訓(xùn)練集的未標(biāo)記樣本集；

步驟2 對訓(xùn)練集樣本使用GT算法進(jìn)行構(gòu)圖，得出訓(xùn)練集中未標(biāo)記樣本類別信息；

步驟3 采用半監(jiān)督流形學(xué)習(xí)框架[10]對步驟1中沒有選入訓(xùn)練集的未標(biāo)記樣本進(jìn)行分類。

2.1 FCM聚類算法

參與FCM聚類的數(shù)據(jù)為Xu中的所有樣本數(shù)據(jù)，c為預(yù)定類別數(shù)，ui(i=1,2,…,c)為每一個(gè)聚類的中心，準(zhǔn)則函數(shù)定義為：

(1)

其中：‖xj-ui‖表示樣本點(diǎn)xj與ui之間的歐氏距離，模糊加權(quán)冪指數(shù)m，依據(jù)經(jīng)驗(yàn)取m=2，U是樣本集Xu的隸屬度矩陣；uij代表樣本xj對于ui的隸屬度；V是樣本集Xu的ui組成的聚類中心集合；通過使J(U,V)達(dá)到最小來獲得U和V。

(2)

i=1,2,…,c,j=l+1,l+2,…,n

(3)

依據(jù)迭代的方法得到最終的聚類結(jié)果。由于不能保證FCM聚類得到的解是全局最優(yōu)解，需要運(yùn)行多次，來選擇最優(yōu)解[11]。

這里yi∈{+1,-1}，選取聚類邊界的未標(biāo)記樣本，具體選取步驟如下：

第1步 所有未標(biāo)記樣本進(jìn)行FCM聚類；

第2步 根據(jù)第1步得到的聚類結(jié)果，計(jì)算每一個(gè)樣本到聚類中心的距離，存儲于數(shù)組A中，并將數(shù)組A進(jìn)行排序，由大到小存儲；另外計(jì)算這些樣本到另一聚類中心的距離，并存儲于數(shù)組B，并將數(shù)組B按從小到大的順序存儲。

第3步 選擇數(shù)組A和數(shù)組B中前m個(gè)共同的樣本作為預(yù)選樣本集合Xu′中的元素。

圖2 無標(biāo)記樣本預(yù)選圖

如圖2以正標(biāo)記樣本聚類中心附近的無標(biāo)記樣本為例，其一無標(biāo)記樣本a，距離正標(biāo)記樣本聚類中心的距離為a2，距離負(fù)聚類中心的距離為a1，將a2存儲于數(shù)組A，a1存儲于數(shù)組B；無標(biāo)記樣本b，距離正標(biāo)記樣本聚類中心的距離為b2，距離負(fù)標(biāo)記樣本聚類中心的距離為b1，將b2存儲于數(shù)組A，b1存儲于數(shù)組B。依次計(jì)算出所有未標(biāo)記樣本到達(dá)正、負(fù)聚類中心的距離，依據(jù)第2步、第3步的步驟選擇聚類邊界的無標(biāo)記樣本，作為初選未標(biāo)記樣本集中的元素。

2.2 圖轉(zhuǎn)導(dǎo)算法

圖轉(zhuǎn)導(dǎo)算法定義了一個(gè)無向圖G={X′,E}，圖中的節(jié)點(diǎn)為數(shù)據(jù)集X′={Xl,Xu′}，節(jié)點(diǎn)間通過E={(xi,xj)}連接。X′代表一個(gè)新組合的集合，其中包含原已標(biāo)記集合Xl和預(yù)選出的未標(biāo)記集合Xu′，則剩余的未標(biāo)記樣本集為{Xu-Xu′} 。由于稀疏圖得到的稀疏相似度矩陣中節(jié)點(diǎn)間的虛假連接較少，更利于真實(shí)權(quán)重的獲得，所以文中采用稀疏的k近鄰圖來構(gòu)建圖[12]，生成的相似度矩陣為W={wij}。使用高斯核函數(shù)來計(jì)算得到W，即：

wij=exp(-‖xi-xj‖2/σ2)

(4)

其中，σ為帶寬參數(shù)，且滿足σ>0。

建立圖結(jié)構(gòu)后，利用已有樣本標(biāo)記信息預(yù)測出未標(biāo)記樣本隱含的標(biāo)記信息，期間通過將標(biāo)記信息按照樣本之間的相似度進(jìn)行傳遞[13]。樣本之間的相似度越大，即邊上的wij值越大，越容易傳遞。

同時(shí)，轉(zhuǎn)移概率矩陣為Pn×n，具體i行j列的元素為：

(5)

表示樣本xi將標(biāo)記信息傳遞到樣本xj的概率。定義矩陣fL，大小為l×c，fU大小為u×c，其中l(wèi)表示標(biāo)記樣本的數(shù)目，u表示未標(biāo)記樣本的數(shù)目，c表示類別數(shù)目。fL，fU的第j個(gè)元素定義為：

(6)

表示只有當(dāng)與樣本xi類別相同的序列號對應(yīng)元素為1，其余均為0。L、U分別表示標(biāo)記數(shù)據(jù)集和未標(biāo)記數(shù)據(jù)集。用n×c的矩陣fX表示所有數(shù)據(jù)的類別：

(7)

由于未標(biāo)記樣本的標(biāo)記信息來源于近鄰樣本的傳遞，則可表示為：

(8)

具體步驟描述如下：

第2步 根據(jù)式(5)計(jì)算出概率轉(zhuǎn)移矩陣P；

2.3 半監(jiān)督流形學(xué)習(xí)框架

假設(shè)決策函數(shù)為f，半監(jiān)督流形學(xué)習(xí)框架定義如下：

(9)

(10)

將式(10)代入式(9)中，得：

(11)

根據(jù)定理(文獻(xiàn)[14]中已證明)，式(11)的解可由如下形式表示：

(12)

將式(12)代入式(5)中，得到：

(13)

對式(13)求導(dǎo)并等于0，進(jìn)一步得到：

(14)

3 實(shí)驗(yàn)及結(jié)果

3.1 數(shù)據(jù)及參數(shù)選擇

首先使用Weizmann Horse數(shù)據(jù)集對算法進(jìn)行驗(yàn)證，選取horse322(250×205)、horse288(350×276)、horse238(800×571)、horse074(627×800)圖像。因?yàn)閃eizmann Horse數(shù)據(jù)集本身有理想分類，所以本文對各種分類方法的效果和理想分類效果進(jìn)行比較。為了驗(yàn)證本算法實(shí)際應(yīng)用效果，本文進(jìn)一步選取西北大學(xué)可視化所兵馬俑數(shù)據(jù)集中G3-I-a-16俑(322×359)、84L864唐胡人俑(545×691)、569彩色騎馬俑(1 023×849)、556彩色馬俑(690×517)、557彩色馬俑(690×517)進(jìn)行實(shí)驗(yàn)驗(yàn)證。

本實(shí)驗(yàn)以這些數(shù)據(jù)的二維圖像模型為對象，對本文提出的分類算法進(jìn)行驗(yàn)證。對這些二維圖像本身進(jìn)行分類，分為背景和目標(biāo)對象。每幅圖像以畫線方式選取已標(biāo)記點(diǎn)，具體選取結(jié)果如表1所示。

表1 實(shí)驗(yàn)圖像像素點(diǎn)選擇情況

實(shí)驗(yàn)具體過程如下：

首先運(yùn)用FCM聚類算法進(jìn)行聚類，由于FCM聚類算法選取的聚類中心會對實(shí)驗(yàn)產(chǎn)生影響，所以進(jìn)行10次實(shí)驗(yàn)，取平均結(jié)果作為最后的聚類結(jié)果。

然后在聚類結(jié)果基礎(chǔ)上選取聚類邊界(Border)的100個(gè)未標(biāo)記點(diǎn)加入訓(xùn)練集，接著使用GT算法進(jìn)行構(gòu)建k近鄰圖，確定出未標(biāo)記點(diǎn)的類別信息，加入到已標(biāo)記數(shù)據(jù)集，需要確定k近鄰圖的近鄰數(shù)N，以及參數(shù)高斯核函數(shù)的帶寬σ，其中根據(jù)多次實(shí)驗(yàn)的經(jīng)驗(yàn)值，將近鄰數(shù)N取值為10；選取加入訓(xùn)練集的未標(biāo)記樣本的方式還可以采用隨機(jī)(Random, R)、靠近聚類中心(Center, C)的方式，本文對比了這三種效果。

最后采用半監(jiān)督算法對其余未標(biāo)記點(diǎn)進(jìn)行分類，得到分類結(jié)果。需要確定控制在希爾伯特空間(RKHS)函數(shù)復(fù)雜性的參數(shù)γ1，控制內(nèi)在幾何結(jié)構(gòu)的函數(shù)復(fù)雜性參數(shù)γ2。本文采用三層網(wǎng)格搜索[15-16]的方式，將找到的分類正確率最高的參數(shù)格點(diǎn)作為最優(yōu)的參數(shù)對，即在lbσ={-10∶1∶10}、lgγ1={-5∶1∶5}和lgγ2={-5∶1∶5}參數(shù)范圍內(nèi)的三層網(wǎng)格中搜索得到。參數(shù)值的設(shè)定如表2所示。

表2 三種方法的參數(shù)選擇

3.2 結(jié)果及對比分析

本文采用三種評價(jià)方式對文中方法的分類效果進(jìn)行評價(jià)：

1)PCR評價(jià)方式。

本文所述算法的分類效果使用圖像中被正確分類的像素?cái)?shù)與總像素?cái)?shù)的比值進(jìn)行評價(jià)，如以下公式：

PCR=正確分類像素?cái)?shù)/圖像總像素?cái)?shù)

其中，PCR(Pixel Classification Rate)即像素分類正確率。

2)APCR評價(jià)方式。

使用每個(gè)類的像素分類正確率的均值，作為第二個(gè)衡量算法分類效果的指標(biāo)[17]，公式如下：

APCR=(背景分類正確率+目標(biāo)對象分類正確率)/2

其中，APCR(Average Pixel Classification Rate)表示兩類分類正確率的平均正確率。

3)Time評價(jià)方式。

進(jìn)一步依據(jù)算法的執(zhí)行時(shí)間，對算法效率進(jìn)行評估。

幾種分類方法的分類效果如圖3、圖4所示。

圖3 不同方法分類結(jié)果(Weizmann Horse數(shù)據(jù)集)

圖4 不同方法分類結(jié)果(兵馬俑數(shù)據(jù)集)

利用Weizmann Horse數(shù)據(jù)集驗(yàn)證的分類效果如圖3所示，通過各分類算法的分類結(jié)果與理想分類結(jié)果進(jìn)行直觀比較，可以看出GT(B)+SSL算法的分類效果更接近于理想分類效果。如圖4所示，本文算法實(shí)際運(yùn)用于兵馬俑數(shù)據(jù)時(shí)，仍保持了很好的分類效果。

表3具體從PCR、APCR、Time三種評價(jià)角度對幾種分類方法進(jìn)行對比。由表3可知：1)傳統(tǒng)的圖轉(zhuǎn)導(dǎo)方法沒有對未標(biāo)記樣本進(jìn)行初選操作，直接對所有的樣本進(jìn)行構(gòu)圖分類得到最終分類結(jié)果，運(yùn)行時(shí)間低，但是分類效果不佳。2)GT(B)+SSL算法運(yùn)行時(shí)間較GT算法而言明顯加長，是因?yàn)楸疚乃惴▽?biāo)記樣本進(jìn)行了預(yù)選取，增加了運(yùn)行時(shí)間，雖然選取結(jié)束后還需要構(gòu)建k近鄰圖以及半監(jiān)督分類兩個(gè)階段，但是由于構(gòu)建的是稀疏圖，訓(xùn)練樣本數(shù)大大減少，所以后兩個(gè)階段并不會對運(yùn)行時(shí)間產(chǎn)生多大影響，但是極大地提高了分類的準(zhǔn)確率。3)GT(B)+SSL與GT(C)+SSL、GT(R)+SSL相比，由于執(zhí)行的階段相同，所以運(yùn)行時(shí)間相近，但是選取聚類邊界的數(shù)據(jù)作為構(gòu)圖前的未標(biāo)記樣本集，比隨機(jī)選取數(shù)據(jù)或靠近聚類中心選取數(shù)據(jù)的方式，更能找到含有隱含信息的數(shù)據(jù)，所以GT(B)+SSL分類準(zhǔn)確率明顯高于其他兩種方法。4)不論從PCR指標(biāo)，還是APCR指標(biāo)對幾種算法評估，GT(B)+SSL算法分類準(zhǔn)確率都優(yōu)于其他幾種分類算法。

此外標(biāo)記樣本數(shù)量的多少也會對分類的準(zhǔn)確度產(chǎn)生影響，分別選取horse238、horse074、556俑圖像進(jìn)行以下分類實(shí)驗(yàn)。表4分別給出不同標(biāo)記樣本數(shù)的實(shí)驗(yàn)結(jié)果對比。

表3 GT方法、GT(R)+SSL方法、GT(C)+SSL方法、GT(B)+SSL(本文方法)實(shí)驗(yàn)結(jié)果對比

表4 選擇不同標(biāo)記樣本數(shù)的實(shí)驗(yàn)結(jié)果對比

分類結(jié)果較優(yōu)的數(shù)據(jù)已在表格中加粗顯示，從表4 知：隨著標(biāo)記像素?cái)?shù)的增多，分類準(zhǔn)確度也會隨著提高。GT(B)+SSL算法與其他幾種分類算法相比，即使在標(biāo)記像素?cái)?shù)稀少的情況下，也具有較好的分類準(zhǔn)確度。

4 結(jié)語

通過對未標(biāo)記樣本進(jìn)行預(yù)選，挑出攜帶對分類有幫助的未標(biāo)記樣本加入訓(xùn)練集，然后構(gòu)建k近鄰稀疏圖，使得構(gòu)圖的數(shù)據(jù)節(jié)點(diǎn)大大減少，提高構(gòu)圖的效率。利用圖轉(zhuǎn)導(dǎo)的方式將未標(biāo)記樣本進(jìn)行分類，得到更多可靠的標(biāo)記樣本數(shù)據(jù)，再使用半監(jiān)督方式利用增多的標(biāo)記樣本和剩余未標(biāo)記樣本進(jìn)行分類器的訓(xùn)練，這樣得到的訓(xùn)練分類器分類精度更好。此外，本文算法不論對于背景單一的圖像，還是背景復(fù)雜的圖像，分類準(zhǔn)確率都明顯高于其他三種分類算法。目前本文算法只針對二分類問題，未來研究將二分類問題延伸到多分類問題。

References)

[1] ZHU X , GHAHRAMANI Z. Learning from labeled and unlabeled data with label propagation [EB/OL]. [2016- 12- 14]. http://pages.cs.wisc.edu/～jerryzhu/pub/CMU-CALD-02-107.pdf.

[2] ZHU X, GHAHRAMANI Z, LAFFERTY J. Semi-supervised learning using Gaussian fields and harmonic functions [C]// Proceedings of the 20th International Conference on Machine Learning. Menlo Park, CA: AAAI Press, 2003: 912-919.

[3] ZHOU D, BOUSQUET O, LAL T N, et al. Learning with local and global consistency [C]// Proceedings of the 16th International Conference on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2003: 321-328.

[4] KIM K H, CHOI S. Label propagation through minimax paths for scalable semi-supervised learning [J]. Pattern Recognition Letters, 2014, 45(1): 17-25.

[5] 汪西莉,藺洪帥.最小代價(jià)路徑標(biāo)簽傳播算法[J].計(jì)算機(jī)學(xué)報(bào),2016,39(7):1407-1418.(WANG X L, LIN H S. Label propagation through minimum cost path [J]. Chinese Journal of Computers, 2016,39(7):1407-1418.)

[6] 晉小玲.圖轉(zhuǎn)導(dǎo)理論的研究與應(yīng)用[D].北京:華北電力大學(xué),2011:6-15.(JIN X L. Research and application of graphic conduction theory [D]. Beijing: North China Electric Power University, 2011: 6-15.)

[7] KUMAR D M, PRASHANTH K, PERURU P K, et al. A novel technique for edge detection using Gabor transform andk-means with FCM algorithms [M]// Emerging Trends in Electrical, Communications and Information Technologies, LNEE 394. Berlin: Springer, 2017: 273-280.

[8] TANHA J, SOMEREN M V, AFSARMANESH H. Semi-supervised self-training for decision tree classifiers [J]. International Journal of Machine Learning & Cybernetics, 2017, 8(1): 355-370.

[9] KIM K I, TOMPKIN J, PFISTER H, et al. Semi-supervised learning with explicit relationship regularization [C]// Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2016: 2188-2196.

[10] 白藝娜.基于圖的半監(jiān)督圖像分類[D].西安:陜西師范大學(xué),2014:10-17.(BAI Y N. Semi-supervised image classification based on graph [D]. Xi’an: Shaanxi Normal University, 2014: 10-17.)

[11] 陳永健.半監(jiān)督支持向量機(jī)分類方法研究[D].西安:陜西師范大學(xué),2014:17-18.(CHEN Y J. Research on classification method of semi-supervised support vector machine [D]. Xi’an: Shaanxi Normal University, 2014: 17-18.)

[12] SONG W, LI S, KANG X, et al. Hyperspectral image classification based onKNN sparse representation [C]// Proceedings of the 2016 IEEE International Geoscience and Remote Sensing Symposium. Piscataway, NJ: IEEE, 2016: 2411-2414.

[13] JING L, YANG L, YU J, et al. Semi-supervised low-rank mapping learning for multi-label classification [C]// Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2015: 1483-1491.

[14] BELKIN M, NIYOGI P, SINDHWANI V. Manifold regularization: a geometric framework for learning from examples [J]. Journal of Machine Learning Research, 2004, 7(1): 2399-2434.

[15] HUANG Q, MAO J, LIU Y. An improved grid search algorithm of SVR parameters optimization [C]// Proceedings of the 2012 IEEE 14th International Conference on Communication Technology. Piscataway, NJ: IEEE, 2013: 1022-1026.

[16] PONTES F J, AMORIM G F, BALESTRASSI P P, et al. Design of experiments and focused grid search for neural network parameter optimization [J]. Neurocomputing, 2016, 186: 22-34.

[17] FU W, LI S, FANG L. Spectral-spatial hyperspectral image classification via superpixel merging and sparse representation [C]// Proceedings of the 2015 IEEE International Geoscience and Remote Sensing Symposium. Piscataway, NJ: IEEE, 2015: 4971-4974.

Semi-supervisedclassificationalgorithmbasedonC-meansclusteringandgraphtransduction

WANG Na, WANG Xiaofeng*, GENG Guohua, SONG Qiannan

(CollegeofInformationScienceandTechnology,NorthwestUniversity,Xi’anShaanxi710000,China)

Aiming at the problem that the traditional Graph Transduction (GT) algorithm is computationally intensive and inaccurate, a semi-supervised classification algorithm based on C-means clustering and graph transduction was proposed. Firstly, the Fuzzy C-Means (FCM) clustering algorithm was used to pre-select unlabeled samples and reduce the range of the GT algorithm. Then, thek-nearest neighbor sparse graph was constructed to reduce the false connection of the similarity matrix, thereby reducing the time of composition, and the label information of the primary unlabeled samples was obtained by means of label propagation. Finally, combined with the semi-supervised manifold hypothesis model, the extended marker data set and the remaining unlabeled data set were used to train the classifier, and then the final classification result was obtained. In the Weizmann Horse data set, the accuracy of the proposed algorithm was more than 96%, compared with the traditional method of only using GT to solve the dependence problem on the initial set of labels, the accuracy was increased by at least 10%. The proposed algorithm was applied directly to the terracotta warriors and horses, and the classification accuracy was more than 95%, which was obviously higher than that of the traditional graph transduction algorithm. The experimental results show that the semi-supervised classification algorithm based on C-means clustering and graph transduction has better classification effect in image classification, and it is of great significance for accurate classification of images.

C-means clustering; Graph Transduction (GT); semi-supervised classification; similarity matrix; sparse map

2017- 04- 01;

2017- 06- 01。

國家自然科學(xué)基金青年科學(xué)基金資助項(xiàng)目(61602380)；國家自然科學(xué)基金面上項(xiàng)目(61373117, 61673319);陜西省國際合作項(xiàng)目(2013KW04-04)。

王娜(1993—)，女，陜西榆林人，碩士研究生，主要研究方向：圖像處理、模式識別； 王小鳳(1979—)，女，陜西渭南人，副教授，博士， CCF會員，主要研究方向：數(shù)據(jù)挖掘、三維模型檢索、模式識別； 耿國華(1955—)，女，山東萊西人，教授，博士，CCF會員，主要研究方向：科學(xué)計(jì)算可視化、模式識別、智能信息處理； 宋倩楠(1994—)，女，山西運(yùn)城人，碩士研究生，主要研究方向：圖像處理、模式識別。

1001- 9081(2017)09- 2595- 05

10.11772/j.issn.1001- 9081.2017.09.2595

TP391.4

A

This work is partially supported by Youth Science Foundation of the National Natural Science Foundation of China (61602380), the General Program of the National Natural Science Foundation of China (61373117, 61673319), Shaanxi Province International Cooperation Project (2013KW04-04).

WANGNa, born in 1993, M. S. candidate. Her research interests include image processing, pattern recognition.

WANGXiaofeng, born in 1979, Ph. D., associate professor. Her research interests include data mining, 3D model retrieval, pattern recognition.

GENGGuohua, born in 1955, Ph. D., professor. Her research interests include scientific computing visualization, pattern recognition, intelligent information processing.

SONGQiannan, born in 1994, M. S. candidate. Her research interests include image processing, pattern recognition.