基于C均值聚類和圖轉導的半監督分類算法

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

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

基于C均值聚類和圖轉導的半監督分類算法

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

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

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

C均值聚類；圖轉導；半監督分類；相似度矩陣；稀疏圖

0 引言

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

1 相關工作

目前，國內外已有很多學者對圖轉導算法進行研究，并提出諸多算法。標簽傳播(Label Propagation, LP)算法[1]是圖轉導算法的基礎，通過圖的邊將標記信息傳播到未標記節點，由于圖轉導算法是基于聚類假設，所以權重大的邊比權重小的邊標記傳播更容易一些，在權重為0的邊終止標記傳播。在此基礎上衍生出調和高斯場(Harmonic Gaussian Field, HGF)[2]、局部與全局一致性(Learning with Local and Global Consistency, LLGC)[3]、極大極小標簽傳播(MiniMax Label Propagation, MMLP)算法[4]、最小代價路徑標簽傳播(Label Propagation through Minimum Cost Path, LPMCP)算法[5]等方法。不論是HGF還是LLGC算法都過于依賴初始標記集，若圖中含有噪聲，或者因為其他因素使得輸入數據集不可劃分類別時，通過圖轉導方法得到的分類結果缺乏準確性。

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

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

圖1 本文算法思路

2 算法描述

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

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

步驟1 使用FCM聚類算法對未標記樣本進行聚類，根據聚類結果選取聚類的邊界點作為訓練集的未標記樣本集；

步驟2 對訓練集樣本使用GT算法進行構圖，得出訓練集中未標記樣本類別信息；

步驟3 采用半監督流形學習框架[10]對步驟1中沒有選入訓練集的未標記樣本進行分類。

2.1 FCM聚類算法

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

(1)

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

(2)

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

(3)

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

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

第1步 所有未標記樣本進行FCM聚類；

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

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

圖2 無標記樣本預選圖

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

2.2 圖轉導算法

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

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

(4)

其中，σ為帶寬參數，且滿足σ>0。

建立圖結構后，利用已有樣本標記信息預測出未標記樣本隱含的標記信息，期間通過將標記信息按照樣本之間的相似度進行傳遞[13]。樣本之間的相似度越大，即邊上的wij值越大，越容易傳遞。

同時，轉移概率矩陣為Pn×n，具體i行j列的元素為：

(5)

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

(6)

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

(7)

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

(8)

具體步驟描述如下：

第2步 根據式(5)計算出概率轉移矩陣P；

2.3 半監督流形學習框架

假設決策函數為f，半監督流形學習框架定義如下：

(9)

(10)

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

(11)

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

(12)

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

(13)

對式(13)求導并等于0，進一步得到：

(14)

3 實驗及結果

3.1 數據及參數選擇

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

本實驗以這些數據的二維圖像模型為對象，對本文提出的分類算法進行驗證。對這些二維圖像本身進行分類，分為背景和目標對象。每幅圖像以畫線方式選取已標記點，具體選取結果如表1所示。

表1 實驗圖像像素點選擇情況

實驗具體過程如下：

首先運用FCM聚類算法進行聚類，由于FCM聚類算法選取的聚類中心會對實驗產生影響，所以進行10次實驗，取平均結果作為最后的聚類結果。

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

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

表2 三種方法的參數選擇

3.2 結果及對比分析

本文采用三種評價方式對文中方法的分類效果進行評價：

1)PCR評價方式。

本文所述算法的分類效果使用圖像中被正確分類的像素數與總像素數的比值進行評價，如以下公式：

PCR=正確分類像素數/圖像總像素數

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

2)APCR評價方式。

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

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

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

3)Time評價方式。

進一步依據算法的執行時間，對算法效率進行評估。

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

圖3 不同方法分類結果(Weizmann Horse數據集)

圖4 不同方法分類結果(兵馬俑數據集)

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

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

此外標記樣本數量的多少也會對分類的準確度產生影響，分別選取horse238、horse074、556俑圖像進行以下分類實驗。表4分別給出不同標記樣本數的實驗結果對比。

表3 GT方法、GT(R)+SSL方法、GT(C)+SSL方法、GT(B)+SSL(本文方法)實驗結果對比

表4 選擇不同標記樣本數的實驗結果對比

分類結果較優的數據已在表格中加粗顯示，從表4 知：隨著標記像素數的增多，分類準確度也會隨著提高。GT(B)+SSL算法與其他幾種分類算法相比，即使在標記像素數稀少的情況下，也具有較好的分類準確度。

4 結語

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

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] 汪西莉,藺洪帥.最小代價路徑標簽傳播算法[J].計算機學報,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] 晉小玲.圖轉導理論的研究與應用[D].北京:華北電力大學,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] 白藝娜.基于圖的半監督圖像分類[D].西安:陜西師范大學,2014:10-17.(BAI Y N. Semi-supervised image classification based on graph [D]. Xi’an: Shaanxi Normal University, 2014: 10-17.)

[11] 陳永健.半監督支持向量機分類方法研究[D].西安:陜西師范大學,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。

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

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

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.