基于加權(quán)非負矩陣分解的非負張量分解算法

劉路路,劉亞楠，王　凡

(合肥師范學(xué)院 計算機科學(xué)與技術(shù)系，安徽 合肥 230601)

?

基于加權(quán)非負矩陣分解的非負張量分解算法

劉路路,劉亞楠，王凡

(合肥師范學(xué)院 計算機科學(xué)與技術(shù)系，安徽 合肥 230601)

[摘要]提出一種基于加權(quán)非負矩陣分解的非負張量分解算法。為了充分利用圖像本身的結(jié)構(gòu)信息與內(nèi)在幾何結(jié)構(gòu)，首先根據(jù)圖像類別構(gòu)造權(quán)值矩陣，把圖像集合構(gòu)造成三階張量，然后，針對該三階張量利用張量幾何運算與非負矩陣分解得到非負張量分解算法的初值，最后實現(xiàn)圖像的分類。實驗結(jié)果表明該算法應(yīng)用于手寫數(shù)字圖像庫中能有效改善圖像分類的準(zhǔn)確性。

[關(guān)鍵詞]圖像分類；非負矩陣分解；非負張量分解

1引言

非負矩陣分解(NMF)[1]被廣泛應(yīng)用于圖像處理、計算機視覺、數(shù)據(jù)挖掘等領(lǐng)域中[2] [3]，它使分解后的所有分量均為非負值，并且同時實現(xiàn)非線性的維數(shù)約減。然而在很多情況下，需要處理的數(shù)據(jù)是高于二維即為多維(張量)數(shù)據(jù)，如果在圖像處理領(lǐng)域中采用NMF方法，需要把圖像數(shù)據(jù)拉直成向量形式，在轉(zhuǎn)換過程中會丟失圖像數(shù)據(jù)本身的結(jié)構(gòu)信息，破壞圖像的空間幾何結(jié)構(gòu)，為了避免這些問題，Welling等人[4]把NMF推廣到非負張量分解(NTF)，NTF被應(yīng)用廣泛于圖像處理與模式識別領(lǐng)域[5] [6]。

本文提出一種基于加權(quán)NMF的NTF的算法，將張量空間的結(jié)構(gòu)模擬成一個近鄰圖，根據(jù)圖像的類別構(gòu)造權(quán)值矩陣，并將圖像集合構(gòu)造成三階張量，利用張量幾何運算和NMF算法得到NTF的初值，最后利用迭代算法求解NTF，并將其應(yīng)用于手寫數(shù)字數(shù)據(jù)庫分類中。

2背景介紹

2.1張量幾何相關(guān)運算

本文算法中用到的張量幾何[7]的相關(guān)定義和定理如下：

定義1(張量矩陣展開)是將一個張量中的元素重新排列，得到一個矩陣的過程，張量X∈RI1×I2×…×IN的n模展開矩陣表示為X(n)∈RIn×(I1...In-1In+1...IN)。

定義2(張量乘法)張量與矩陣的乘法由n模乘積所定義。具體地，張量X∈RI1×I2×…×IN和矩陣U∈RJn×In的n模乘積表示為X×nU，這是一個I1×I2×...×In-1×Jn×In+1×...×IN階張量，定義如下：

(1)

2.2NMF

定義1NMF是發(fā)現(xiàn)非負的m×r的基矩陣W和r×n的系數(shù)矩陣H使[1]

V≈WH

(2)

2.3NTF

現(xiàn)有的張量分解模型一般分為兩類：標(biāo)準(zhǔn)分解模型[8]和Tucker分解模型[9]。這兩種分解模型都是對矩陣奇異值分解的高階推廣，并且第一種分解模型是第二種分解模型的特例。非負Tucker模型(NTF)的目標(biāo)是把非負張量X∈RI1×I2×…×IN分解為

(3)

其中：G∈RJ1×J2×…×JN，Un∈RIn×Jn(Jn?In，n=1,2,…N)。該分解可通過求解最優(yōu)化問題式(4)得到：

(4)

3基于NMF的NTF算法

由(4)構(gòu)造目標(biāo)函數(shù)：

(5)

對(5)求偏導(dǎo)可得：

(6)

(7)

(8)

(9)

其中，G(n)為對應(yīng)張量G的n模展開矩陣。

由公式(6)可得G的迭代規(guī)則：

(10)

由公式(7)可得U1的迭代規(guī)則：

(11)

由公式(8)可得U2的迭代規(guī)則：

(12)

由公式(9)可得U3的迭代規(guī)則：

(13)

由 (10)-(13)可知，迭代求解G、U(n)必須首先已知G、U(n)的初值，傳統(tǒng)的方法是隨機給G、U(n)賦初值，這樣直接影響到圖像最終的分類性能。為了避免這種隨機性對分類性能的影響，本文構(gòu)建近鄰圖G=(V,E)模擬數(shù)據(jù)集合X={X1,X2,...,XN}∈RI1×I2×N(Xn∈RI1×I2,n=1,2,...,N)的幾何結(jié)構(gòu)，定義G的權(quán)重矩陣W如下：

(14)

本文利用該W與張量數(shù)據(jù)集合X做加權(quán)NMF，以得到U(n)(n=1,2,3)的初值。具體算法思路見算法1。

算法1加權(quán)NMF

(1) 針對數(shù)據(jù)集合X，X∈RI1×I2×N構(gòu)造3階張量

(2) 求得X∈RI1×I2×N與W∈RN×N的3模乘積X×3W，記為A，A∈RI1×I2×N

(3) 對A進行n模展開，得到A(n)，(n=1,2,3)

(4) 對A(n)分別進行NMF分解得到U(n)，(n=1,2,3)

隨后，利用U(n)的值根據(jù)公式(10)得到G的初值。

(15)

最后，由(11)、(12)可以得到U1、U2，由U1、U2可得Xi對應(yīng)子空間中的Yi，(i=1,2,...,N)：

(16)

4實驗結(jié)果

為了驗證本文算法的有效性，采用手寫數(shù)字數(shù)據(jù)庫USPS Handwritten Digits和Binary Alphadigits[10]。

第一個數(shù)據(jù)庫包含0～9等十個數(shù)字共10類，每類有1100幅圖像，圖像為20×20的灰度圖像，從中隨機選取400幅圖像做兩組實驗。第一組實驗是隨機選取100幅圖像做訓(xùn)練，其余圖像做測試；第二組實驗是從每類中隨機選取200幅圖像做訓(xùn)練，其余圖像做測試。第二個數(shù)據(jù)庫包含0～9等十個數(shù)字，以及“A”～“Z”等26個英文字母，共36類，每類有39幅圖像，圖像為20×16的灰度圖像。對該數(shù)據(jù)庫同樣做兩組實驗，第一組實驗是從每類中隨機選取10幅圖像做訓(xùn)練，其余圖像做測試；第二組實驗是從每類中隨機選取20幅圖像做訓(xùn)練，其余圖像做測試。

本文選用PCA[11]、2D-PCA[12]、NTF與本文提出的基于NMF的NTF方法做對比，每一種方法均采用最近鄰分類器進行分類。對本文方法、NTF來說，兩幅圖像之間的距離：

‖U1TXiU2-U1TXjU2‖

(17)

對PCA、2D-PCA來說，兩幅圖像之間的距離是主成分子空間的歐幾里德距離。分類結(jié)果如圖1、2所示，橫軸為維數(shù)，縱軸為分類準(zhǔn)確度。從圖中可以看出本文算法優(yōu)于其他三種對比算法，并且NTF算法明顯優(yōu)于2D-PCA、PCA。

5總結(jié)

為了保持圖像數(shù)據(jù)空間的幾何結(jié)構(gòu)，鑒于非負張量分解的優(yōu)勢，本文提出一種基于高階非負矩陣分解的非負張量分解算法，對數(shù)據(jù)進行維數(shù)約減，并應(yīng)用于手寫體數(shù)據(jù)庫中，實驗結(jié)果表明本文算法可以有效提高分類準(zhǔn)確率。后續(xù)將繼續(xù)研究譜圖理論在張量空間中的應(yīng)用。

[參考文獻]

[1]Lee D D, Seung H S. learning the parts of objects by non-negative matrix factorization [J]. Nature, 1999, 401(6755):788-791.

[2]Deng Cai, Xiaofei He and Jiawei Han. Graph Regularized Non-negative Matrix Factorization for Data Representation[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2011,33(8):1548-1560.

[3]Mohamed Ouhsain A. Ben Hamza. Image watermarking scheme using nonnegative matrix factorization and wavelet transform [J]. Expert Systems with Applications. 2009, 36(2): 2123-2129.

[4]Welling M, Weber M. Positive tensor factorization [J]. Pattern Recognition Letters, 2001, Vol.22 (12):1255-1261.

[5]Ji Liu, Jun Liu, Peter Wonka , Jieping Ye. Sparse non-negative tensor factorization using columnwise coordinate descent [J]. Pattern Recognition, 2012,45(1): 649-656.

[6]Fengyu Cong, Anh Huy Phan, Piia Astikainen. Multi-domain Feature of Event-Related Potential Extracted by Nonnegative Tensor Factorization: 5 vs. 14 Electrodes EEG Data [J]. Lecture Notes in Computer Science, 2012, 7(9): 502-510.

[7]Lathauwer LD. Signal processing based on multilinear algebra [D], [Ph.D Thesis], Belgium: Katholieke Universiteit Leuven, 1997.

[8]R.A.Harshman. Foundations of the PARAFAC procedure: models and conditions for an "explanatory" mul-modal factor analysis [J]. UCLA working papers in phonetics, 1970, Vol.(16):1-84.

[9]L.R.Tueker. Some mathematical notes of three-mode factor analysis [J]. Psychometrika, 1966, 31 (3):279-311.

[10][Online]http://www.cs.nyu.edu/～roweis/data.html.

[11]Hotelling H. Analysis of a complex of statistical variables into principal components[J]. Journal of Educational Psychology, 1933, 24(6):417-441.

[12]Jian Y, David Z, Frangi A F, et al. Two-dimensional PCA: a new approach to appearance-based face representation and recognition.[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2004, 26(1):131-7.

Non-negative Tensor Factorization Based on Weighted Non-negative Matrix Factorization

LIU Lulu, LIU Yanan, WANG fan

(SchoolofComputerScienceandTechnology,HefeiNormalUniversity,Hefei230039,China)

Abstract：This paper proposes a non-negative tensor factorization based on weighted non-negative matrix factorization. In order to fully use the structural information of the data and their intrinsic geometry, the weighted matrix is constructed according to the label of images and the set of images is constructed to a third order tensor first. Then using tensor geometry operation and non-negative matrix factorization can get the original values. Finally, image classification is realized. Experimental results on the handwritten digital image database show that the proposed algorithm can effectively improve the accuracy of the image classification.

Key words：image classification; non-negative matrix factorization; non-negative tensor factorization

[收稿日期]2016-01-18

[基金項目]安徽省高校省級優(yōu)秀青年人才基金重點項目 (2011SQRL129ZD)，合肥師范學(xué)院科研項目(2015QN15)

[第一作者簡介]劉路路(1982-)女，碩士，合肥師范學(xué)院計算機科學(xué)與技術(shù)系教師。研究方向：圖像處理。

[中圖分類號]TP391.4

[文獻標(biāo)識碼]A

[文章編號]1674-2273(2016)03-0024-04