白本督, 范九倫

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

基于稀疏分解的局部全局一致性學(xué)習(xí)算法

白本督, 范九倫

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

提出一種基于稀疏分解的l0構(gòu)圖法，通過稀疏分解系數(shù)矩陣得到圖中鄰接矩陣和邊的權(quán)重。將l0構(gòu)圖法應(yīng)用到局部全局一致性學(xué)習(xí)(Learning with Local and Global Consistency，LLGC)算法中，并通過K-均值聚類優(yōu)化稀疏分解所需字典，以降低計(jì)算復(fù)雜度。在8個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明，與經(jīng)典LLGC算法相比，新算法能在消耗時(shí)間不增加的情況下提高分類精度，提升算法性能。

稀疏分解；局部全局一致性學(xué)習(xí)；K-均值

同時(shí)使用少量有標(biāo)記數(shù)據(jù)和大量無標(biāo)記數(shù)據(jù)的半監(jiān)督學(xué)習(xí)，在提高分類器性能的同時(shí)降低了人工標(biāo)注成本，其研究成果已廣泛應(yīng)用到網(wǎng)頁檢索、圖像分類等各個(gè)領(lǐng)域?，F(xiàn)有的半監(jiān)督學(xué)習(xí)方法有Self-training算法[1]、Co-training算法[2]、半監(jiān)督SVM[3]以及基于圖的半監(jiān)督分類方法[4]等。

基于圖的半監(jiān)督學(xué)習(xí)方法通常先定義一個(gè)圖，結(jié)點(diǎn)是有標(biāo)記和無標(biāo)記數(shù)據(jù)的集合，根據(jù)某種相似度準(zhǔn)則確定邊的權(quán)重，然后定義能量函數(shù)優(yōu)化框架并求解，能量函數(shù)由損失項(xiàng)和正則項(xiàng)構(gòu)成。此類算法本質(zhì)上是一種無參的、可判別的、直推的學(xué)習(xí)方法，直接或間接地利用了流形假設(shè)，基礎(chǔ)理論比較完善，是半監(jiān)督學(xué)習(xí)的一個(gè)研究熱點(diǎn)[5]。半監(jiān)督學(xué)習(xí)方法可被看作圖的最小分割問題[6]，高斯隨機(jī)場(chǎng)以及諧波函數(shù)可應(yīng)用于圖上的半監(jiān)督學(xué)習(xí)[7]。采用了不同的損失函數(shù)和正則項(xiàng)，可以得出局部全局一致性學(xué)習(xí)(Learning with Local and Global Consistency，LLGC)算法[8]。

在基于圖的半監(jiān)督學(xué)習(xí)中，構(gòu)造一個(gè)合適的圖比選擇優(yōu)化方法更重要。基于稀疏分解的l1構(gòu)圖法[9]，就充分利用了稀疏分解，可以有效捕捉信號(hào)的各種結(jié)構(gòu)特征和內(nèi)在屬性的特性，能通過系數(shù)矩陣確定出鄰接矩陣和邊的權(quán)值，獲得較好的實(shí)驗(yàn)結(jié)果。

本文將根據(jù)l1構(gòu)圖法的原理，提出了一種基于稀疏分解的l0構(gòu)圖法，并將其與K-均值聚類過程結(jié)合，應(yīng)用到LLGC算法中。先用K-均值對(duì)整個(gè)數(shù)據(jù)集進(jìn)行粗分類，以分類結(jié)果中同類樣本的集合作為l0構(gòu)圖法的字典，優(yōu)化字典結(jié)構(gòu)，得出高質(zhì)量的圖，從而提高LLGC算法的性能。

1 基于稀疏分解的l1構(gòu)圖方法

稀疏表示是一種新的信號(hào)表示理論，稀疏分解是得到信號(hào)稀疏表示的過程，它主要利用超完備字典的冗余特性來有效地捕捉信號(hào)的各種結(jié)構(gòu)特征和內(nèi)部屬性，實(shí)現(xiàn)圖像的有效表示。

過完備字典是指,當(dāng)字典中原子個(gè)數(shù)L大于信號(hào)維數(shù)N,且字典中包含N個(gè)線性無關(guān)的向量時(shí)，字典為過完備或冗余的[10]。在圖像處理與計(jì)算機(jī)視覺中，許多問題的有效解決都依賴于稀疏表示理論，如圖像去噪[11]、壓縮[12]和模式分類[13]等。目前，信號(hào)稀疏分解的主要方法有匹配追蹤MP[14]、正交匹配追蹤OMP[15]、基追蹤BP[16]以及Focuss算法[17]等。

基于稀疏分解的SRC方法[13]在人臉識(shí)別中可以取得較好效果。在足夠多訓(xùn)練樣本情況下，若以訓(xùn)練樣本作為稀疏分解的字典，則測(cè)試樣本可用訓(xùn)練樣本的線性組合來表示，而且理想情況下，每個(gè)測(cè)試樣本對(duì)應(yīng)的系數(shù)非零樣本將屬于同一類。

基于稀疏分解的l1構(gòu)圖法[9]，采用基追蹤算法,以l1范數(shù)度量信號(hào)表示的稀疏性，即系數(shù)矩陣是通過求l1最小范數(shù)下的最優(yōu)化問題得到，使得在最小化信號(hào)重建誤差的同時(shí)更稀疏的表示信號(hào)。

最小范數(shù)下稀疏分解模型可表示為

其中f為待分解信號(hào),α為系數(shù)矩陣,Φ是字典。

l1構(gòu)圖過程中，先定義了一個(gè)由所有已標(biāo)記和未標(biāo)記部分組成的集合，取其中一個(gè)元素作為待分解信號(hào)，其它元素構(gòu)成過冗余字典，通過l1優(yōu)化過程得到待分解信號(hào)的系數(shù)向量，然后再根據(jù)系數(shù)向量定義圖，圖中結(jié)點(diǎn)是所有樣本的集合。如果頂點(diǎn)j和i間的系數(shù)aij≠0，則樣本xj和xi相似。邊的權(quán)重

基追蹤算法是信號(hào)稀疏表示領(lǐng)域的新方法，它通過尋求信號(hào)在過冗余字典中的最稀疏表示，用盡可能少的原子盡可能精的表示信號(hào)，獲得信號(hào)的內(nèi)在本質(zhì)特征。但由于該方法要在字典的所有原子中極小化一個(gè)全局目標(biāo)函數(shù)，計(jì)算量非常大，目前只在一維信號(hào)中有比較廣泛的應(yīng)用[18]。

2 基于稀疏分解的LLGC算法

LLGC算法的本質(zhì)是對(duì)分類結(jié)果進(jìn)行平滑，主要思想是讓每個(gè)樣本的標(biāo)記信息迭代地向其近鄰樣本點(diǎn)傳播，直到達(dá)到全局穩(wěn)定狀態(tài)[8]。

假設(shè)數(shù)據(jù)集

X={x1,x2,…,xl,xl+1,…,xn}?d

的類標(biāo)簽集為

Y={1，2，…,c}，

在X中前l(fā)個(gè)數(shù)據(jù)為已標(biāo)記數(shù)據(jù)集，標(biāo)記信息滿足

{y1,y2,…,yl}∈Y,

剩下的n-l(l?n)部分為無標(biāo)記數(shù)據(jù)集。LLGC算法的目標(biāo)就是預(yù)測(cè)無標(biāo)記數(shù)據(jù)的類屬信息yu。該算法將優(yōu)化目標(biāo)項(xiàng)的權(quán)值范圍約束到有限值，對(duì)已標(biāo)記樣本的標(biāo)記有一定的容錯(cuò)能力，并可以用于改善監(jiān)督學(xué)習(xí)的分類結(jié)果。

將基于稀疏分解的構(gòu)圖法應(yīng)用到LLGC算法。由于l1構(gòu)圖法使用的基追蹤算法計(jì)算量較大，故考慮以匹配追蹤MP作為稀疏分解算法，它是一種貪婪算法，原理簡(jiǎn)單且易于實(shí)現(xiàn)，主要通過逐步逼近來求信號(hào)的稀疏分解。由于該方法通過l0范數(shù)求解最優(yōu)化問題，故稱其為l0構(gòu)圖法。此外，若以所有樣本集合作為字典，計(jì)算量會(huì)比較大，故改用K-均值算法對(duì)所有樣本先進(jìn)行粗分類，而字典就是分類結(jié)果中同類樣本的集合。為方便，不妨將所提算法簡(jiǎn)稱為LLGC(l0,K)算法。

l0構(gòu)圖法的主要流程可描述如下。

輸入 樣本X={x1,x2,…,xN}

輸出 鄰接矩陣W

步驟1 令粗分類結(jié)果

kmeans_label=Kmeans(X)。

步驟2 fori=1:N

(1) 找到kmaens_label與kmeans_label(i)值相等的樣本點(diǎn)，存儲(chǔ)到Position；

(2) 找到X中屬于集合Position，但不是位置i的樣本存儲(chǔ)到矩陣B；

(3) 對(duì)X(i)進(jìn)行MP稀疏分解，使所得系數(shù)矩陣滿足

a′=arg min‖a‖0, s.t.Ba=X(i)。

(4) 將a′的絕對(duì)值存儲(chǔ)到鄰接矩陣W中對(duì)應(yīng)的位置。

步驟3 轉(zhuǎn)化有向圖W為無向圖，并保證對(duì)角線元素為0。

定義一個(gè)n×c的矩陣Y來存儲(chǔ)初始類標(biāo)信息，如果xi的類標(biāo)信息為yi=j,Yij=1，否則Yij=0。對(duì)所有的測(cè)試樣本，則令Yij=0。定義一個(gè)n×c的矩陣F來存儲(chǔ)每個(gè)數(shù)據(jù)屬于某一類的概率，如Fic指的是第i個(gè)數(shù)據(jù)屬于c類的概率。

LLGC(l0,K)算法的主要流程可描述如下。

步驟1 根據(jù)l0構(gòu)圖方法構(gòu)造鄰接矩陣W，初始化矩陣Y，并令

F(0)=Y。

步驟2 生成矩陣

S=D-1/2WD-1/2,

其中D對(duì)角線上的元素

步驟3 迭代計(jì)算

F(t+1)=αSF(t)+(1-α)Y(0≤α<1)。

步驟4 記序列{F(t)}的極限為F*，那么每個(gè)數(shù)據(jù)點(diǎn)的類別信息滿足

為了分析算法收斂性，初始令

F(0)=Y，

通過t次迭代可得

其中α∈(0,1)，S的特征值屬于[-1,1]，對(duì)上式右側(cè)的兩項(xiàng)分別求極限可得

則該迭代過程最終收斂于

F*=(1-α)(I-αS)-1Y,

它等價(jià)于

F*=(I-αS)-1Y。

直接用此式求F*，無需多次迭代。

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)以及參數(shù)設(shè)置

為了驗(yàn)證所提算法LLGC(l0,K)的有效性，使用UCI[19]數(shù)據(jù)庫中的8個(gè)數(shù)據(jù)集對(duì)經(jīng)典LLGC算法、LLGC(l1)算法、 LLGC(l0)算法以及LLGC(l0,K)算法進(jìn)行測(cè)試，數(shù)據(jù)集的信息如表1所示。

表1 數(shù)據(jù)集

經(jīng)典LLGC算法用RBF核函數(shù)計(jì)算鄰接矩陣,基于l0的構(gòu)圖法中最大迭代次數(shù)為5次。

3.2 仿真結(jié)果及分析

對(duì)每個(gè)實(shí)驗(yàn)數(shù)據(jù)集，隨機(jī)抽取l個(gè)樣本組成已標(biāo)記樣本集，滿足每類至少有一個(gè)，剩下的n-l個(gè)樣本組成未標(biāo)記樣本集。本實(shí)驗(yàn)取標(biāo)記樣本的個(gè)數(shù)分別為5、10、15、20、25、30，每種情況下重復(fù)上述樣本選擇20次，取其平均值作為各數(shù)據(jù)集的分類準(zhǔn)確率。8個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果比較如圖1所示。

(a) Ecoli數(shù)據(jù)集

(c) Diabetes數(shù)據(jù)集

(e) Ionosphere數(shù)據(jù)集

(b) Dermatology數(shù)據(jù)集

(d) Hepatitis數(shù)據(jù)集

(f) Iris數(shù)據(jù)集

(h) Wine數(shù)據(jù)集

表2給出了Diabetes數(shù)據(jù)集和Ionoshpere數(shù)據(jù)集在4種算法上的計(jì)算機(jī)耗時(shí)對(duì)比。

表2 Diabetes和Ionosphere數(shù)據(jù)集耗時(shí)

從圖1可以看出，對(duì)所有實(shí)驗(yàn)數(shù)據(jù)集，LLGC(l0,K)算法的分類精度較經(jīng)典LLGC算法有明顯的提高，其中很多數(shù)據(jù)集的改進(jìn)都很明顯。LLGC(l0,K)算法先用K-均值進(jìn)行粗分類，然后運(yùn)行LLGC(l0)算法,分類精度要明顯高于LLGC(l1)算法和LLGC(l0)算法。比較4種算法的計(jì)算機(jī)耗時(shí)，從表2可以看出，LLGC(l0,K)算法消耗的時(shí)間比LLGC(l1)算法要少很多，在Ionosphere數(shù)據(jù)集中,LLGC(l0,K)算法所耗時(shí)間也要比經(jīng)典LLGC算法少。這些事實(shí)說明，基于稀疏分解的K-均值構(gòu)圖法對(duì)提高LLGC算法的性能是很有效的。

4 結(jié)語

將稀疏表示理論應(yīng)用到基于圖的半監(jiān)督學(xué)習(xí)過程中，可得出一種K-均值構(gòu)圖法，實(shí)驗(yàn)結(jié)果表明，這種算法比經(jīng)典LLGC算法好，是一種比較有效的半監(jiān)督學(xué)習(xí)算法。

[1] Wang B, Spencer B, Ling C X, et al. Semi-supervised self-training for sentence subjectivity classification[J]. Lecture Notes in Computer Science, 2008,5032:344-355.

[2] Chan J, Koprinska I, Poon J. Co-training with a single natural feature set applied to email classification[C]//Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence. Beijing: IEEE Computer Society, 2004: 586-589.

[3] Li Y Q, Guan C T, Joint feature re-extraction and classification using an iterative semi-supervised support vector machine algorithm[J]. Machine Learning, 2008,71(1):33-53.

[4] Zha Z J, Mei T, Wang J D, et al. Graph-based semi-supervised learning with multiple labels[J]. Journal of Visual Communication and Image Representation, 2009, 20(2): 97-103.

[5] 王雪松, 張曉麗, 程玉虎. 一種簡(jiǎn)潔局部與全局一致性學(xué)習(xí)[J].控制與決策, 2011, 34(11):1379-1387.

[6] Blum A, Chawla S. Learning from labeled and unlabeled data using graph mincuts[C]//Proceedings of the 18th International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 2001:19-26.

[7] Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using Gaussian fields and harmonic functions[C]//The 20th International Conference on Machine Learning. Washington: American Association for Artificial Intelligence, 2003:912-919.

[8] Zhou D Y, Bousquet O, Lal T N, et al. Learning with local and global consistency[C]//Advances in Neural Information Processing Systems 16. MA Cambridge: MIT Press, 2004: 321-328.

[9] Yan Shuicheng, Wang Huan. Semi-supervised Learning by Sparse Representation[C]//Proceedings of the Ninth SIAM International Conference on Data Mining. Philadelphia: Society for Industrial and Applied Mathematics Publications, 2009:792-801.

[10] 孫玉寶，肖亮，韋志輝,等 基于Gabor感知多成份字典的圖像稀疏表示算法研究[J].自動(dòng)化學(xué)報(bào), 2008, 34(11): 1379-1387.

[11] Elad M, Aharon M. Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries[J]. IEEE Transactions on Image Processing, 2006, 15(12): 3736-3745.

[12] Ventura R M, Vandergheynst P, Frossard P. Low-Rate and Flexible Image Coding With Redundant Representations[J]. IEEE Transactions on Image Processing, 2006, 15(3):726-739.

[13] Wright J, Ganesh A, Yang A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009,31(2): 210-227.

[14] Mallat S, Zhang Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12):3397-3415.

[15] Davis G, Mallat S, Zhang S. Adaptive time-frequency decompositions[J]. Journal.of Optical Enginneering, 1994, 33(7):2183-2191.

[16] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit[J]. SIAM Journal on Scientific Computing, 1999, 20(1):33-61.

[17] Gorodnitsky I F, Rao B D. Sparse signal reconstruction from limited data using FOCUSS: re-weighted minimum norm algorithm[J]. IEEE Transactions on Signal Processing, 1997,45(3):600-616.

[18] 傅霆,堯德中.稀疏分解的加權(quán)迭代方法及其初步應(yīng)用[J].電子學(xué)報(bào),2004,32(4):567-570.

[19] Blake C, Keogh E, Merz C. UCI Machine Learning Repository[EB/OL]. (2014-09-08)[2014-10-10]. http://archive.ics.uci.edu/ml.

[責(zé)任編輯:瑞金]

Learning with local and global consistency based on sparse representation

BAI Bendu, FAN Jiulun

(School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

A graph construction method by the sparse representation is proposed in this paper. This method derives graph adjacency structure and the graph weights from coefficient matrix simultaneously. The graph is introduced into Learning with Local and Global Consistency (LLGC) algorithm. The dictionary is optimized byK-means algorithm. Computing complexity can then be reduced and the performance of LLGC can be improved. Experimental results on UCI datasets indicate that the proposed algorithm can improve the precision of classification and maintain consumed time invariant. Therefore the performance of LLGC is improved.

sparse representation, learning with local and global consistency(LLGC),K-means

2014-10-30

公安部技術(shù)研究計(jì)劃重點(diǎn)資助項(xiàng)目(2014JSYJA018);陜西省教育廳專項(xiàng)科研計(jì)劃資助項(xiàng)目(12JK0731 )

白本督 (1972-)，男，博士，講師，從事圖形圖像處理研究。E-mail：baibendu@xupt.edu.cn 范九倫(1964-)，男，博士，教授，博導(dǎo)，從事圖像處理、信息安全研究。E-mail：jiulunf@xupt.edu.cn

10.13682/j.issn.2095-6533.2015.03.011

TN911.74

A

2095-6533(2015)03-0065-06