非負矩陣分解及其改進方法

劉志揚

(廣東科技學院 基礎部， 廣東 東莞 523083)

?

非負矩陣分解及其改進方法

劉志揚

(廣東科技學院 基礎部， 廣東 東莞 523083)

首先,給出非負矩陣分解的數(shù)學形式，分析歐式距離和相對熵(KL)散度兩種分解誤差評價函數(shù).然后,針對3種特殊形式的非負矩陣進行分解方法的改進，優(yōu)化函數(shù)和迭代過程分別適用于正交非負矩陣、凸非負矩陣、投影非負矩陣的分解.結果表明:提出的改進方法簡化了非負矩陣分解的過程.

非負矩陣; 非負分解; 優(yōu)化函數(shù); 迭代方程

非負矩陣分解，是數(shù)據(jù)挖掘領域的一個關鍵問題.通過非負矩陣分解，原始矩陣的維度得以降低，且分解結果中的非負表達更適用于實際問題.由于非負矩陣分解的重要性，許多學者對這一領域開展了理論和實踐研究，尤其在分解過程的收斂速度、分解過程的復雜性方面更加關注[1-4].非負矩陣分解理論建立之初，是針對用非負矩陣來表達的多維數(shù)據(jù)[5].同時，非負矩陣分解要求分解后的矩陣也要滿足非負的特征.顯然，這種約束的存在使得分解結果表現(xiàn)出一定的稀疏性，但這種稀疏性也可以有效地抵制來自外部的干擾.稀疏性特征也反映出非負矩陣分解只能清晰地表達多維數(shù)據(jù)的部分特征[6].隨著非負矩陣分解的應用日益增多，學者們又發(fā)現(xiàn)了其聚類功能，從而拓寬了非負矩陣分解的應用領域[7-8].Kitamura等[9]在一般非負矩陣分解過程中進一步添加新的約束條件，使分解得到的結果可以成為另一個分解結果上的投影.在此基礎上，正交性約束條件也被添加進來，非負矩陣分解的迭代過程得到更新，從而加快了拉格朗日最優(yōu)解獲得的收斂速度.Ludena等[10]在一般非負矩陣分解過程中添加了一個凸性約束，從而構建了一種凸非負矩陣的分解方法.這種方法獲得的分解結果更加稀疏，但也增強了對凸非負矩陣多維數(shù)據(jù)的解釋能力.本文在一般非負矩陣分解過程的基礎上，探尋幾種改進分解方法.

1 非負矩陣分解的理論基礎

對于實際問題而言，非負的向量表達、非負的矩陣分解往往更有意義.正是這種實際需求，催生了非負矩陣分解方法的出現(xiàn).從數(shù)學形式上看，高維數(shù)據(jù)矩陣經(jīng)過非負矩陣分解后，求得的低維矩陣中的元素都應該是非負的.因為非負性要求的存在，也必然會使分解結果在一定程度上只能采用稀疏表達的結果.稀疏表達并不一定是不利的，在很多情況下甚至可以抵御外部的干擾.

至此，給出一個非負矩陣分解的一般性描述.設定Y是一個非負矩陣，它可以進一步分解為兩個非負矩陣A和B，并且可以滿足Y≈AB.如果矩陣A的列數(shù)少于矩陣B的列數(shù)，那么，就只能實現(xiàn)對矩陣Y的稀疏表達.這時，如果要盡可能地實現(xiàn)對矩陣Y的表達，就必須找到原始矩陣的類似結構，矩陣A和矩陣B的乘積才能實現(xiàn)對矩陣Y的最佳擬合.還需要指出，非負矩陣分解獲得的投影系數(shù)，不會出現(xiàn)有正有負的情況，這一點和主成分分析方法存在明顯不同.

假設給定的原始矩陣Y的維度是p×q，矩陣中全部元素都是非負的，同時，維度p大于維度q.經(jīng)過非負矩陣分解的處理，原始矩陣Y被分解為兩個非負矩陣A和B.其中，非負矩陣A的維度是p×s，非負矩陣B的維度是p×s.這里，維度s一般是一個先行給定的參數(shù)，且這個參數(shù)需滿足s

對于矩陣A和矩陣B而言，因為非負屬性的限制條件的存在，對于非負矩陣Y而言 ，很難做出準確性分解，一般都是帶有一定誤差的分解.因此,分解后3個矩陣的關系是Y≈AB.雖然很難實現(xiàn)非負矩陣的準確分解，但還是希望分解結果和原始矩陣之間的誤差盡可能小些.為了分析這種誤差的大小，一般要設定一個評價函數(shù)，用以判斷非負矩陣Y的非負分解結果誤差是否足夠小.

第1種常見的評價函數(shù)，一般用歐式距離設計，具體形式為

(1)

由歐式距離評價函數(shù)，可評價非負矩陣分解結果和原始非負矩陣的近似情況，可得優(yōu)化函數(shù)為

(2)

優(yōu)化過程中，每一步驟的迭代操作為

(3)

第二種常見的評價函數(shù)，一般用相對熵(KL)散度設計，具體形式為

(4)

根據(jù)KL散度評價函數(shù)，可以評價非負矩陣分解結果和原始非負矩陣的近似情況，據(jù)此設計出的優(yōu)化過程的2個迭代操作為

(5)

2 非負矩陣分解的改進方法

在實際應用中，非負矩陣存在一些特殊的形式，需要對原有的分解方法進行有針對性的改進.文中將分別探討3類特殊的非負矩陣：正交非負矩陣、凸非負矩陣、投影非負矩陣.

2.1 正交非負矩陣的對應分解方法

在數(shù)據(jù)分類等實際應用中，正交非負矩陣有著非常高的實用價值.正交非負矩陣又可以分為水平單側方向上的正交非負矩陣、垂直單側方向上的正交非負矩陣、雙向正交非負矩陣等3種類型.

1) 水平單側方向上的正交非負矩陣分解.水平單側方向上的非負矩陣，在非負分解過程中的優(yōu)化函數(shù)為

(6)

在水平單側方向上非負矩陣分解的過程中，所用的迭代公式分別為

(7)

2) 垂直單側方向上的正交非負矩陣分解.垂直單側方向上的非負矩陣，在非負分解過程中的優(yōu)化函數(shù)為

(8)

在垂直單側方向上非負矩陣分解的過程中，所用的迭代公式分別為

(9)

3) 水平垂直雙向上的正交非負矩陣分解.水平垂直雙向上的非負矩陣，在非負分解過程中的優(yōu)化函數(shù)為

(10)

在水平垂直雙向上非負矩陣分解的過程中，所用的迭代公式分別為

(11)

(12)

(13)

2.2 凸非負矩陣的對應分解方法

凸非負矩陣分解，一般是在考慮原始矩陣不受任何限制條件下展開的.在這種情況下，只要求分解出的矩陣有一部份是非負的，對另一部分則沒有限制.

假設要求分解出的矩陣B是非負的，對矩陣A沒有要求，那么，優(yōu)化問題轉變?yōu)?/p>

(14)

此時，可以對A施加一個凸性約束，即

(15)

式(15)也可以寫為

(16)

至此，可以將凸非負矩陣分解優(yōu)化過程的迭代公式設計為

(17)

(18)

2.3 投影非負矩陣的對應分解方法

投影非負矩陣的非負分解，可以寫為

(19)

對于上述優(yōu)化問題，優(yōu)化過程中的迭代公式為

(20)

對于投影非負矩陣的非負分解，還可以進一步施加一個正交性約束，此時優(yōu)化問題變?yōu)?/p>

(21)

對應的迭代公式變?yōu)?/p>

(22)

至此，給出了3種不同非負矩陣的非負分解方法，以及具體的優(yōu)化函數(shù)和迭代操作過程.

3 結束語

針對非負矩陣的分解效果評價，提出歐式距離評價函數(shù)和KL散度評價函數(shù).對正交非負矩陣、凸非負矩陣、投影非負矩陣的分解方案進行改進，分別建立分解過程的優(yōu)化函數(shù).分解結果顯示，文中改進的分解方法，不僅使3種非負矩陣的分解過程得到簡化，分解效率得到提升，分解誤差也符合兩種評價函數(shù)的檢驗標準.

[1] 李磊，李靜.三端點區(qū)間數(shù)的判斷矩陣分解及基于Fermat的算法集結研究[J].數(shù)學的實踐與認識,2015,45(17):214-221.

[2]NEDUNGADIP,SMRUTHYTK.Personalizedmulti-relationalmatrixfactorizationmodelforpredictingstudentperformance[J].AdvancesinIntelligentSystemsandComputing,2016,38(4):163-172.

[3] 方蔚濤，馬鵬，成正斌，等.二維投影非負矩陣分解算法及其在人臉識別中的應用[J].自動化學報,2012,38(9):1503-1512.

[4] 涂丹丹，舒承椿，余海燕.基于聯(lián)合概率矩陣分解的上下文廣告推薦算法[J].軟件學報,2013,24(3):454-464.

[5]MESAROSA,HEITTOLAT,DIKMENO,etal.Soundeventdetectioninrealliferecordingsusingcoupledmatrixfactorizationofspectralrepresentationsandclassactivityannotations[C]∥InternationalConferenceonAcoustics,SpeechandSignalProceeding.London：AEAT，2015:151-155.

[6] 劉維湘，鄭南寧，游屈波.非負矩陣分解及其在模式識別中的應用[J].科學通報,2006,51(3):241-250.

[7] 楊粵濤，朱明，賀柏根，等.采用改進投影梯度非負矩陣分解和非采樣Contourlet變換的圖像融合方法[J].光學精密工程,2011,19(5):1143-1151.

[8] 宋海州，徐強，田朝薇.計算非負不可約矩陣譜半徑的新算法[J].華僑大學學報(自然科學版),2011,32(3):348-351.

[9]KITAMURAD,ONON,SAWADAH,etal.Efficientmultichannelnonnegativematrixfactorizationexploitingrank-1spatialmodel[C]∥InternationalConferenceonAcoustics,SpeechandSignalProceeding.London:AEAT，2015:276-280.

[10] LUDENA C J,GALLARDO A A.Acoustic event classification using spectral band selection and non-negative matrix factorization-based features[J].Expert Systems with Applications,2016,46(8):77-86.

(責任編輯： 錢筠 英文審校： 黃心中)

Research on Non Negative Matrix Factorization and It′s Improvement Method

LIU Zhiyang

(Basic Course Department， Guangdong University of Science and Technology, Dongguan 523083, China)

First of all, mathematical form of non negative matrix factorization is presented, and two decomposition error evaluation functions of Euclidean distance and relative entropy divergence are presented. Then, we improve the decomposition method for 3 kinds of non negative matrix, the used optimization function and the iteration process can respectively applied to the decomposition of orthogonal nonnegative matrix, convex nonnegative matrix and projection non negative matrix. The results show that the improved method simplifies the process of non negative matrix factorization.

non negative matrix; non negative decomposition; optimization function; iterative equation

10.11830/ISSN.1000-5013.201606025

2016-10-13

劉志揚(1964-)，男，副教授，主要從事非負矩陣分解算法的研究.E-mail:nbxylzy@163.com.

廣東省教育廳、財政廳立項資助課題(2013WYXM0136)

O 151.21

A

1000-5013(2016)06-0782-04