馬婷婷

(遼寧師范大學，遼寧　大連　116000)

在模式識別和機器學習的學習[1-3]中，數(shù)據(jù)的內(nèi)在特征結(jié)構(gòu)可以通過矩陣分解得以發(fā)現(xiàn)，并且使得數(shù)據(jù)特征維數(shù)很大程度的降了.Lee等[4]發(fā)表了非負矩陣分解(non-negativematrixfactorization,NMF)算法，它將一個正定矩陣分解為兩個正定矩陣乘積，由于分解后的矩陣是正定的所以只包含非負元素，原矩陣中列向量可稱為所有列向量的加權(quán)和，矩陣中對應(yīng)列向量中的元素稱為權(quán)重系數(shù).因為其分解的結(jié)果中都是正數(shù)和零即不會有負值出現(xiàn)所以具有非常簡便的算法，具有廣泛的物理意義，所以可以運用于語音辨識、圖像識別、腦電信號提取等等各種問題中[3-6].這篇文章就是將正定矩陣分解算法模型轉(zhuǎn)化為凸二次規(guī)劃模型求解，從而使處理速度得到了很大的提高。

一、正定矩陣分解的概念與計算

對于m×n階的實正定矩陣A和正整數(shù)k

A≈WH(1)

下面就是歐式距離優(yōu)化模型：

正定矩陣秩分解有很多種的方法[6-11]，一般可以分為兩種.第一個是優(yōu)化逼近法.對于模型(2)可以直接采用優(yōu)化方法求解，可以選擇廣義既約梯度法、廣義乘子法、梯度投影法等的局部最優(yōu)化方法[11-16].這些方法的優(yōu)點是算法都比較成熟，收斂性也已經(jīng)得到證明；但缺點是不能保證全局最優(yōu)解.也就是說可選擇區(qū)間方法、微分進化算法、隨機投點與隨機方向算法等這些全局最優(yōu)化方法求解[15-16].這類方法的缺點是計算量遠大于一般的局部最優(yōu)化方法。

第二個是公式逼近法，根據(jù)式(1)，構(gòu)造出來某種迭代公式，通過同時迭代或交替迭代的方式，將Hk與Wk更新到Hk+1與Wk+1，并希望當k→+∞時，WkHk→A.這種方法優(yōu)點是，具有很簡單的迭代公式，公式中的運算一般簡單非常基本的運算等，實現(xiàn)起來非常容易；但是其缺點是收斂性很難得到證明，并且收斂速度比較慢。

二、正定矩陣低秩分解的交替二次規(guī)劃算法

在對模型(2)采用局部優(yōu)化計算時，這里f(x)是一個四次代數(shù)多元(p=m×k+k×n個變元)多項式函數(shù)，因為其高度復(fù)雜的極值點，運用模型(2)這種傳統(tǒng)優(yōu)化算法是很不容易得出結(jié)果來的.那么對于這種模型，如果我們令W=W1也就是讓W選定為某個常數(shù)陣W1，那么有

這是一個關(guān)于H的二次規(guī)劃模型.

具體計算步驟為

步驟1令基矩陣W的初始值為W=Wk(k=1)，求Hk(k=1)，其中試探性地取參數(shù)λ值，然后限制對Hk取值為非負，記下Wk與H”k(k=1)中零元素的個數(shù)；

步驟2令H=HK，求Wk+1，得到Wk+1后再一次限制非負的，注意試探性的取值參數(shù)μ，使得NWk+1z≥NW”kz，然后再計算總誤差E2k(k=1)；

步驟3檢查是否滿足迭代終止條件：若E2k-1≥E2k(k=1)與NW2x≥NW1x同時成立，則令k+1→k繼續(xù)步驟1，否則停止，那么最優(yōu)分解就是上一輪的結(jié)果.

注：①.初始基陣W1(k=1)的選取方法：只需W1中，盡可能多的零元素存在。無論W1取何值，交替二次規(guī)劃算法迭代的收斂性都不會受到影響，但如果想要減少迭代次數(shù)，那么W1選取得好是至關(guān)重要的。

②.參數(shù)λ與μ選取方法：滿足以下兩個條件即可：

(1)從Hk到Hk+1中零元素的個數(shù)NHkz到NWk+1z滿足NHkz≤NHk+1z；

(2)計算出的前后兩次總誤差值E2k-1到E2k滿足E2k-1≥E2k≥E2k+1。

Hk與Wk中元素非負性要求的實現(xiàn)：當模型取(2)這種一般的約束非線性規(guī)化時，則模型(2)可行域的邊界為H≥0,W≥0。為了上述方法中這些問題出現(xiàn)，這篇文章在交替二次規(guī)劃迭代計算過程中用零元素代替Hk與Wk中出現(xiàn)的負元素，從而減小了難度。

三、交替二次規(guī)劃算法的收斂性

由于交替二次規(guī)劃所產(chǎn)生的總誤差值列單調(diào)遞減并且有下界的數(shù)列{Ep}(p=1,2,3,…)一定有極限即：E1≥E2≥E3≥…≥Ep≥0,所以算法是收斂的，但是事實上很少算法在有限步終止，我們可以根據(jù)WH逼近A的精度E值的要求不同，每一步的結(jié)果，都可以作為需要分解的結(jié)果。

四、結(jié)語

因為有很多種正定矩陣低秩分解的方法，所以針對同一個問題可以用這些不同的方法，那么又怎樣來評定它們的優(yōu)點和缺點呢？這篇文章的作者認為這就需要存在某些的評定標準，而這個評定標準中主要當然包含三個方面其一為總誤差E=Ea+Eb的大小，總誤差值當然是越小越好；其二為基矩陣W中列向量W1,W2,W3,…,線性獨立的Wi×Wj≈0(i≠j)程度，這種程度是用內(nèi)積來描述的，當然是越接近0越好；其三為基矩陣W與系數(shù)矩陣H稀疏的程度.

交替二次規(guī)劃算法的提出，這篇文章的優(yōu)點在于作者注意到了直接求解是非常困難并且非常復(fù)雜。所以作者在學習以前別人的基礎(chǔ)上，并且滿足評定標準中要求，經(jīng)過長時間刻苦學習與專研給出了解決這樣問題的方法。我們通過了大量實際例子都可以了解到，這個方法與上面的要求大致上可以很好的完成。不僅僅算法非常明確，實現(xiàn)起來也很方便，并且由于簡單的迭代過程，使得有很小的計算量，這一點對特別是大型數(shù)據(jù)模型來說是至關(guān)重要的，也很容易證明算法的收斂性。

缺點是對Hk與Wk中的元素非負性要求，在迭代過程中如果出現(xiàn)了負元素直接用零元素取代的方案，但是對于普遍性的問題，是否存在特別情況不適用，目前還不是很不清楚，有待進一步的研究。

參考文獻：

[1]GAO Yuan CHURCHG G.Improving molecular cancer class discovery through sparse non-negative matrix factorization[J].Bioinformatics，2005，21(21)：3970-3975.

[2]Hoyer P O.Non-negative matrix factization with sparseness constraints[J].TheJournal of Machine Learning Reseaarch，2004，5：1457-1469.

[3]“10000個科學難題”數(shù)學編委會.10000個科學難題數(shù)學卷[M].北京：科學出版社，2009.

[4]LeeD D，SeungH S.Learingthepartsofobjectsbynon-negativematrixfactorization[J].Nature，1999，401(6755)：788-791.

[5]Lee D D，Seung H S.Algorithms for Non-negative matrix factorization[C]// A dvances in Neural Information Processing Systems.Cambridge：MIT Press，2001.

[6]蔣嬌嬌.非負矩陣分解算法的改進及應(yīng)用[D].北京：北京工業(yè)大學，2001.

[7]楊洪禮.非負矩陣與張量分解及其應(yīng)用[D].青島：山東科技大學，2011.

[8]張宇飛.加稀疏約束的非負矩陣分解[D].大連：大連理工大學，2010.

[9]趙燕斌.強噪聲中誘發(fā)電位信號的快速提取研究[D].大連：大連理工大學，2008.

[10]郭立.增量式非負矩陣分解方法研究[D].上海：復(fù)旦大學，2009.

[11]殷海青.圖象分析中的非負矩陣分解理論及其最優(yōu)化和正則化方法研究[D].西安：西安電子科技大學，2011.

[12]王德人.非線性方程組解法與最優(yōu)化方法[M].北京：人民教育出版社，1979.

[13]施吉林，張宏偉，金光日.計算機科學計算[M].北京：高等教育出版社，2005.

[14]席少霖，趙鳳治.最優(yōu)化計算方法[M].上海：上海科學技術(shù)出版社，1983.

[15]張可村，李換琴.工程優(yōu)化方法及其應(yīng)用[M].西安：西安交通大學出版社，2007.

[16]陽明盛，羅長童.最優(yōu)化原理、方法及求解軟件[M].北京：科學出版社，2006.