非負(fù)矩陣分解及其改進(jìn)方法

劉志揚(yáng)

(廣東科技學(xué)院 基礎(chǔ)部， 廣東 東莞 523083)

?

非負(fù)矩陣分解及其改進(jìn)方法

劉志揚(yáng)

(廣東科技學(xué)院 基礎(chǔ)部， 廣東 東莞 523083)

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

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

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

1 非負(fù)矩陣分解的理論基礎(chǔ)

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

2 非負(fù)矩陣分解的改進(jìn)方法

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

2.1 正交非負(fù)矩陣的對應(yīng)分解方法

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

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

(12)

(13)

2.2 凸非負(fù)矩陣的對應(yīng)分解方法

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

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

(14)

此時(shí)，可以對A施加一個(gè)凸性約束，即

(15)

式(15)也可以寫為

(16)

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

(17)

(18)

2.3 投影非負(fù)矩陣的對應(yīng)分解方法

投影非負(fù)矩陣的非負(fù)分解，可以寫為

(19)

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

(20)

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

(21)

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

(22)

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

3 結(jié)束語

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

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

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

[3] 方蔚濤，馬鵬，成正斌，等.二維投影非負(fù)矩陣分解算法及其在人臉識(shí)別中的應(yīng)用[J].自動(dòng)化學(xué)報(bào),2012,38(9):1503-1512.

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

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

[6] 劉維湘，鄭南寧，游屈波.非負(fù)矩陣分解及其在模式識(shí)別中的應(yīng)用[J].科學(xué)通報(bào),2006,51(3):241-250.

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

[8] 宋海州，徐強(qiáng)，田朝薇.計(jì)算非負(fù)不可約矩陣譜半徑的新算法[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版),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.

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

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

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

廣東省教育廳、財(cái)政廳立項(xiàng)資助課題(2013WYXM0136)

O 151.21

A

1000-5013(2016)06-0782-04