基于加權非負矩陣分解的非負張量分解算法

劉路路,劉亞楠，王　凡

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

?

基于加權非負矩陣分解的非負張量分解算法

劉路路,劉亞楠，王凡

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

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

[關鍵詞]圖像分類；非負矩陣分解；非負張量分解

1引言

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

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

2背景介紹

2.1張量幾何相關運算

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

定義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)有的張量分解模型一般分為兩類：標準分解模型[8]和Tucker分解模型[9]。這兩種分解模型都是對矩陣奇異值分解的高階推廣，并且第一種分解模型是第二種分解模型的特例。非負Tucker模型(NTF)的目標是把非負張量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)構造目標函數(shù)：

(5)

對(5)求偏導可得：

(6)

(7)

(8)

(9)

其中，G(n)為對應張量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=(V,E)模擬數(shù)據(jù)集合X={X1,X2,...,XN}∈RI1×I2×N(Xn∈RI1×I2,n=1,2,...,N)的幾何結構，定義G的權重矩陣W如下：

(14)

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

算法1加權NMF

(1) 針對數(shù)據(jù)集合X，X∈RI1×I2×N構造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對應子空間中的Yi，(i=1,2,...,N)：

(16)

4實驗結果

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

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

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

‖U1TXiU2-U1TXjU2‖

(17)

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

5總結

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

[參考文獻]

[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)，合肥師范學院科研項目(2015QN15)

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

[中圖分類號]TP391.4

[文獻標識碼]A

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