劉展杰，陳曉云

(福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院, 福建 福州　350116)

基于二維最小二乘回歸的子空間分割

劉展杰，陳曉云

(福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院, 福建 福州350116)

摘要：現(xiàn)實中有很多樣本數(shù)據(jù)是二維的，且多數(shù)聚類方法需將二維樣本數(shù)據(jù)向量化，從而導(dǎo)致二維數(shù)據(jù)的內(nèi)部幾何信息丟失. 針對這一問題，提出二維最小二乘回歸子空間分割方法直接對二維數(shù)據(jù)進(jìn)行聚類, 將一維最小二乘回歸子空間分割方法推廣到二維，使得原始數(shù)據(jù)的結(jié)構(gòu)信息得以保留. 在人臉數(shù)據(jù)集和哥倫比亞大學(xué)圖像數(shù)據(jù)集上進(jìn)行實驗，結(jié)果表明該方法是有效的.

關(guān)鍵詞：聚類； 最小二乘回歸； 子空間分割； 二維樣本

0引言

隨著計算機(jī)及網(wǎng)絡(luò)應(yīng)用的不斷發(fā)展，越來越多的多維樣本數(shù)據(jù)被產(chǎn)生，如圖像、 視頻. 現(xiàn)有的許多方法在處理數(shù)據(jù)之前，需要將一幅圖像或一段視頻表示成一維向量，即用32×32二維矩陣表示的圖像按行(或列)連接成1×1 024的一維向量. 若這類樣本具有特殊的空間結(jié)構(gòu)，對其做向量化處理難以避免地會導(dǎo)致數(shù)據(jù)信息的損失. 針對這類不足，近年來許多學(xué)者開始研究如何將樣本向量的輸入形式轉(zhuǎn)化成原二維矩陣的輸入形式，甚至是更高維的形式. 比如經(jīng)典的子空間學(xué)習(xí)方法LDA[1]和PCA[2]等都有上述不足，因此2D-PCA[3]、 2D-LDA[4]、 MPCA[5]等方法被提出，且都取得較好的實驗結(jié)果.

子空間分割又稱子空間聚類，被廣泛應(yīng)用到運(yùn)動分割[6-7]、 圖像聚類[6-9]等. 子空間分割方法已經(jīng)在圖像研究領(lǐng)域取得了巨大成功[6-9]. 將同類圖像視為一個子空間，利用子空間分割方法對圖像數(shù)據(jù)進(jìn)行聚類，其中典型的子空間分割方法有稀疏表示子空間分割(SSC)[6]、 低秩表示子空間分割(LRR)[7]、 最小二乘回歸子空間分割(LSR)[8]等. 除此之外，層次聚類(HC)[10]、 自組織映射(SOM)[11-12]和非負(fù)矩陣分解(NMF)[13]及其擴(kuò)展模型[14-16]等也成功應(yīng)用于圖像數(shù)據(jù)聚類，但非負(fù)矩陣分解要求所處理的矩陣對象非負(fù)，這無疑限制了NMF的應(yīng)用.

無論是子空間分割方法還是非負(fù)矩陣分解法，共同的缺陷就是需要將二維矩陣樣本或更高維樣本向量化. 針對這一問題，推廣了最小二乘回歸子空間分割方法(LSR)[15]，提出二維最小二乘回歸子空間分割方法(two-dimensional least square regression, 2D-LSR).

1子空間分割

子空間分割是聚類問題研究的熱點，已經(jīng)成功應(yīng)用在機(jī)器學(xué)習(xí)和機(jī)器視覺等領(lǐng)域[6-8].

許多子空間分割方法已經(jīng)被提出，根據(jù)不同的算法可粗略分為四類[8]： 代數(shù)方法、 迭代方法、 統(tǒng)計方法和譜聚類方法. 更多的子空間分割方法參見綜述[9]. 本文重點研究基于譜聚類的子空間分割方法.

(1)

LSR的目標(biāo)函數(shù)是最小化Z的Frobenius范數(shù)：

(2)

對于有噪聲的模型，可以擴(kuò)展為：

(3)

去掉限制條件diag(Z)=0，還可以擴(kuò)展為：

(4)

文獻(xiàn)[8]的實驗結(jié)果顯示，SSC，LRR和LSR三者中，LSR運(yùn)行的時間最少，且LSR是魯棒的，有較好的聚集性能并且可以得到解析解，可以快速得到表示系數(shù)[8]. 但是針對樣本為矩陣數(shù)據(jù)的聚類問題，便要將其向量化，為此提出二維最小二乘回歸子空間分割方法(2D-LSR).

2二維最小二乘回歸子空間分割

由n個二維矩陣樣本Xi(i=1, 2, …,n)組成的原始數(shù)據(jù)集為XM=[X1, …, Xn]∈d1×(d2n)，將所有圖像按一行排過去. 向量化后變成XV=[x1, …,xn]∈d×n，其中d1×d2=d，n為樣本數(shù). 對于矩陣向量化后的數(shù)據(jù)，容易失去樣本內(nèi)部結(jié)構(gòu)的幾何信息，影響聚類效果.

2.12D-LSR目標(biāo)函數(shù)

由式(1)推廣：

(5)

將原來一維的模型推廣到二維的. Zij是一個矩陣，其現(xiàn)實意義是對矩陣的每個點都賦予一個權(quán)重.

且根據(jù)線性LSR模型(4)可知：

(6)

其中： Zi=[zi1, …,zin]T∈n；xi∈d(i=1, …,n).

由于模型(6)中的xi是一行向量，若以二維矩陣樣本Xi作為輸入，則模型(6)需推廣如下：

(7)

由(7)式得出2D-LSR目標(biāo)函數(shù)為：

(8)

(9)

(10)

(11)

模型(8)與模型(6)對比，模型(6)的解析解為：

(12)

2.22D-LSR算法

算法： 二維最小二乘回歸子空間分割算法.

Input： 數(shù)據(jù)矩陣X∈d1×d2n，正則參數(shù)λ，類數(shù)k.

Output：k個類簇.

Step1： 利用公式(9)和(11)解2D-LSR問題，求得Z*；

Step3： 應(yīng)用標(biāo)準(zhǔn)分割方法將數(shù)據(jù)分成k個子空間.

值得注意的是，算法輸入的類別數(shù)k都是事先已知的，即實驗的數(shù)據(jù)集都帶有類標(biāo)簽，因此實驗也不討論k的選擇.

3實驗

實驗在Win7系統(tǒng)，2G內(nèi)存環(huán)境下完成，所有方法都用Matlab2010b編程實現(xiàn). 為驗證 2D-LSR方法的有效性，將2D-LSR和LSR[8]、LRR[7]兩種線性子空間分割方法以及傳統(tǒng)的K均值(K-means)[18]和層次聚類(HC)[6]算法的聚類準(zhǔn)確率進(jìn)行對比. 聚類準(zhǔn)確率采用文獻(xiàn)[18-19]的計算方法，2D-LSR、LSR和LRR的正則參數(shù)為{0.000 1, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1, 5, 10}. 為避免隨機(jī)性，每種方法運(yùn)行50次，取平均值作為最終聚類準(zhǔn)確率.

3.1數(shù)據(jù)集

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

選用4個人臉圖像數(shù)據(jù)集和哥倫比亞圖像數(shù)據(jù)集. 4個人臉圖像數(shù)據(jù)集分別是orlraws10P、 pixraw10P、 warpPIE10P和warpAR10P, 這些數(shù)據(jù)集來自http://featureselection.asu.edu/datasets.php； 哥倫比亞大學(xué)圖像數(shù)據(jù)(COIL20)[20]包含20個對象(類)，每個對象在水平上旋轉(zhuǎn)360°，每隔5°拍攝一張照片，因此每個對象共72幅圖，每個圖像的大小是32×32像素, 像素灰度值為256. 這5個數(shù)據(jù)集的共同點是每張圖片都由向量表示，每條向量的長度是圖像長與寬的乘積. 將5個數(shù)據(jù)集整理歸納在表1. 實驗將向量恢復(fù)成矩陣的形式，并且對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，即

(13)

受到實驗環(huán)境的限制，對每個數(shù)據(jù)集只取每類的前5個樣本數(shù)據(jù)作為實驗樣本.

3.2實驗結(jié)果與分析

實驗結(jié)果如表2所示，為避免隨機(jī)性，每種方法運(yùn)行50次取聚類準(zhǔn)確率的均值±方差(正則參數(shù)λ). 值得注意的是，LSR、 LRR和2D-LSR的準(zhǔn)確率是取所有參數(shù)中最好的結(jié)果.

表2　聚類準(zhǔn)確率和運(yùn)行時間的對比

由表2的實驗結(jié)果發(fā)現(xiàn)： 在算法聚類質(zhì)量方面，2D-LSR在所有測試數(shù)據(jù)集上都取得了較好的聚類效果. 在5個數(shù)據(jù)集中的3個2D-LSR的聚類準(zhǔn)確率最高，在pixraw10P上比LRR和LSR略低，在COIL20則僅低于HC算法. 對比2D-LSR和LSR，2D-LSR在orlraws10P、 pixraw10P、 warpPIE10P和warpAR10P 上的準(zhǔn)確率均高于LSR，特別在orlraws10P和COIL20上2D-LSR準(zhǔn)確率比LSR高出5%. 在時間方面，大部分情況下HC是最快的，K-means是最慢的. 2D-LSR與LSR相比，后者更快，這是由于二者計算復(fù)雜度不一樣所致； 但是2D-LSR與LRR相比，前者更快. 且隨著數(shù)據(jù)集圖像大小的變化，5種算法都會受到一定程度的影響，且LSR受的影響較小. 說明在維數(shù)高的圖像上，各個算法會更耗時； 而對于維數(shù)小的圖像上，算法需要識別處理的數(shù)據(jù)少，從而提升算法的運(yùn)行時間.

表3　比較不同參數(shù)下的平均聚類準(zhǔn)確率

由上可知，2D-LSR算法不能同時保證算法準(zhǔn)確率高和運(yùn)行時間快. 為了權(quán)衡算法的準(zhǔn)確率與效率，比較實驗方法的穩(wěn)定性，10個不同參數(shù)下的整體穩(wěn)定性，表3列出不同參數(shù)下所獲得的聚類準(zhǔn)確率的均值.

可以看出，在pixraw10P數(shù)據(jù)，2D-LSR的聚類準(zhǔn)確率略低于LRR和LSR的準(zhǔn)確率； 而在另外4個數(shù)據(jù)里，2D-LSR的聚類準(zhǔn)確率明顯高于LRR和LSR. 這說明2D-LSR比LRR和LSR更穩(wěn)定，整體效果更好.

3.3參數(shù)選擇

2D-LSR算法與LSR、 LRR算法一樣，都僅有一個正則參數(shù)λ. 對于2D-LSR與LSR，正則參數(shù)起到能夠降低樣本相關(guān)性的作用. 圖1描述了3種算法在人臉數(shù)據(jù)集下，參數(shù)λ的變化對聚類準(zhǔn)確率的影響. 可以從整體觀察聚類準(zhǔn)確率受參數(shù)不同取值的影響. 參數(shù)λ為0.005和1附近，LRR的聚類效果較為理想； 參數(shù)λ為0.1～1之間時，2D-LSR和LSR的聚類效果較為理想； 當(dāng)參數(shù)λ<0.1時，LSR的準(zhǔn)確率較低，甚至比LRR低，這與文獻(xiàn)[8]的結(jié)論是一致的. 在所有除pixraw10P外其它數(shù)據(jù)集上，2D-LSR在不同參數(shù)下的準(zhǔn)確率最穩(wěn)定，受λ取值影響最小.

圖1　人臉數(shù)據(jù)集中不同參數(shù)下的聚類結(jié)果Fig.1　The results of accuracy with different parameters setting on face databases

4結(jié)論

提出二維最小二乘回歸子空間分割方法(2D-LSR)，并將其成功應(yīng)用于二維圖像樣本數(shù)據(jù)的聚類. 實驗結(jié)果表明, 2D-LSR可以很好地刻畫二維數(shù)據(jù)的結(jié)構(gòu)信息且具有良好的聚合能力. 雖然在運(yùn)行時間上處于劣勢，但是與現(xiàn)有的LSR、 LRR子空間分割模型相比，2D-LSR更穩(wěn)定、 更精確，是一種有效的二維矩陣樣本集聚類算法. 當(dāng)然, 2D-LSR也存在如何高效選取正則參數(shù)的問題，將在以后的研究中給出.

參考文獻(xiàn)：

[1] WOLD S, ESBENSEN K, GELADI P. Principal component analysis[J]. Chemometrics and Intelligent Laboratory Systems, 1987, 2(1): 37-52.

[2] FISHER R A. The use of multiple measurements in taxonomic problems[J]. Annals of Eugenics, 1936, 7(2): 179-188.

[3] YANG J, ZHANG D, FRANGI A F,etal. Two-dimensional PCA: a new approach to appearance-based face representation and recognition[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2004, 26(1): 131-137.

[4] LI M, YUAN B. 2D-LDA: a statistical linear discriminant analysis for image matrix[J]. Pattern Recognition Letters, 2005, 26(5): 527-532.

[5] LU H, PLATANIOTIS K N, VENETSANOPOULOS A N. Multilinear principal component analysis of tensor objects for recognition[C]//Proceedings of the 18th International Conference on Pattern Recognition. Hong Kong: [s.n.], 2006: 776-779.

[6] ELHAMIFAR E, VIDAL R. Sparse subspace clustering[C]//Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Miami: IEEE，2009: 2 790-2 797.

[7] LIU G, LIN Z, YU Y. Robust subspace segmentation by low-rank representation[C]//Proceedings of the 27th International Conference on Machine Learning (ICML). Haifa: [s.n.], 2010: 663-670.

[8] LU C Y, MIN H, ZHAO Z Q,etal. Robust and efficient subspace segmentation via least squares regression[C]//12th European Conference on Computer Vision-ECCV. Florence： Springer, 2012: 347-360.

[9] VIDAL R. A tutorial on subspace clustering[J]. IEEE Signal Processing Magazine, 2010, 28(2): 52-68.

[10] JOHNSON S C. Hierarchical clustering schemes[J]. Psychometrika, 1967, 32(3): 241-254.

[11] KOHONEN T. The self-organizing map[J]. Proceedings of the IEEE, 1990, 78(9): 1 464-1 480.

[12] TAMAYO P, SLONIM D, MESIROV J,etal. Interpreting patterns of gene expression with self-organizing maps: methods and application to hematopoietic differentiation[J]. Proceedings of the National Academy of Sciences, 1999, 96(6): 2 907-2 912

[13] LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization[C]//Proceedings of Neural Information Processing Systems. Denver: [s.n.], 2001: 556-562.

[14] GAO Y, CHURCH G. Improving molecular cancer class discovery through sparse non-negative matrix factorization[J]. Bioinformatics, 2005, 21(21): 3 970-3 975

[15] WANG Y, JIA Y. Fisher non-negative matrix factorization for learning local features[C]//Proceedings of the Sixth Asian Conference on Computer Vision. Jeju: [s.n.], 2004: 27-30.

[16] BRUNET J P, TAMAYO P, GOLUB T R,etal. Metagenes and molecular pattern discovery using matrix factorization[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(12): 4 164-4 169

[17] SHI J, MALIK J. Normalized cuts and image segmentation[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2000, 22(8): 888-905.

[18] CAI D, HE X, WU X,etal. Non-negative matrix factorization on manifold[C]//Proceedings of the 8th IEEE International Conference on Data Mining. Pisa: [s.n.], 2008: 63-72.

[19] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Los Angeles: [s.n.],1967, 1: 281-297.

[20] CAI D, HE X, HAN J,etal. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1 548-1 560.

(責(zé)任編輯： 洪江星)

Two-dimensional least square regression based subspace segmentation

LIU Zhanjie, CHEN Xiaoyun

(College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350116, China)

Abstract:In reality, most of data is two-dimensional, and most of clustering methods process the data with vectorization first. This practice leads to loss internal geometry information of data. To solve this problem, a two-dimensional least square regression method based subspace segmentation is put forward for clustering on 2-dimensional data. 1-dimensional space is extended to 2-dimensional space, and it keeps the structure information of original data. Experimental results show that this method is effective on face databases and the Columbia University Image Library.

Keywords:clustering; least square regression; subspace segmentation; 2-dimensional space

DOI:10.7631/issn.1000-2243.2016.03.0431

文章編號：1000-2243(2016)03-0431-06

收稿日期:2014-12-18

通訊作者:陳曉云(1970-)，教授，主要從事數(shù)據(jù)挖掘、 模式識別等方面的研究，c_xiaoyun@21cn.com

基金項目：國家自然科學(xué)基金資助項目(71273053)； 福建省自然科學(xué)基金資助項目(2014J01009)

中圖分類號：TP311； TP371

文獻(xiàn)標(biāo)識碼：A