1、高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解方法重慶大學(xué)碩士學(xué)位論文（專業(yè)學(xué)位）學(xué)生姓名：孫山林指導(dǎo)教師：張?zhí)礁苯淌趯W(xué)位類別：工程碩士（計(jì)算機(jī)技術(shù)領(lǐng)域）重慶大學(xué)計(jì)算機(jī)學(xué)院二0 六年四月Intrinsic Structure Preserving Non-negativeMatrix Factorization Method for HighDimensional DataA Thesis Submitted to Chongqing Universityin Partial Fulfillment of the Requirement for theMaster5s Degree of Enginee

2、ringBySun ShanLinSupervised by Associate Prof. Top ZhangSpecialty: ME (Computer Technology Field)College of Computer Science ofChongqing University, Chongqing, ChinaApril, 2016摘要非負(fù)矩陣分解理論（Nonnegtive Matrix Factorization, NMF）是當(dāng)今學(xué)術(shù)研究 的熱點(diǎn)問題。與其他矩陣分解方法不同，NMF從“個(gè)體構(gòu)成總體，局部構(gòu)成整體” 的角度出發(fā)，將一個(gè)非負(fù)數(shù)據(jù)矩陣分解為兩個(gè)非負(fù)矩陣（一為基矩陣

3、、一為系數(shù) 矩陣）相乘。這種概念正與人類認(rèn)知事物的原理相吻合。由于非負(fù)矩陣分解方法 分解非負(fù)矩陣后得到的基矩陣和系數(shù)矩陣都是非負(fù)的，所以分解的結(jié)果具有很強(qiáng) 的可解釋性，這一點(diǎn)與傳統(tǒng)的矩陣分解（比如奇異值分解Single Value Decomposition, SVD）不同，傳統(tǒng)的矩陣分解會(huì)出現(xiàn)負(fù)數(shù)的情況，以至于缺乏相應(yīng) 的物理解釋。這種可解釋性使得非負(fù)矩陣分解方法在圖像處理，數(shù)據(jù)挖掘，環(huán)境 監(jiān)測(cè)，化學(xué)計(jì)量學(xué)，多媒體分析等領(lǐng)域都得到了廣泛的應(yīng)用。從降維的角度講， 分解后的基向量就是低維空間中新的基，原始數(shù)據(jù)可以表示為這組基的一個(gè)線性 組合，因此可以通過選取適當(dāng)參數(shù)，我們能得到原始高維數(shù)據(jù)的一個(gè)

4、低維描述， 達(dá)到數(shù)據(jù)維數(shù)約簡(jiǎn)的目的。本文深入地研究了非負(fù)矩陣分解方法，在此基礎(chǔ)上， 提出了一種高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解模型以及快速梯度下降求解算 法。本文在標(biāo)準(zhǔn)非負(fù)矩陣分解算法的目標(biāo)函數(shù)上添加一個(gè)正則項(xiàng)，使得新的非負(fù) 矩陣分解算法具有高維內(nèi)在結(jié)構(gòu)在低維空間中得到保持的能力。這個(gè)正則項(xiàng)中使 用核函數(shù)密度估計(jì)的方法來描述原始數(shù)據(jù)和分解后低維描述中的密度分布。本文 分別利用高斯和柯西核密度估計(jì)來估計(jì)原始數(shù)據(jù)和低維表示的數(shù)據(jù)分布，然后利 用K-L（Kullback Leibler divergence）散度作為衡量?jī)蓚€(gè)密度分布的相似性。為了使 分解后低維描述和原始數(shù)據(jù)在結(jié)構(gòu)上（在這里就是密度

5、分布）盡可能地保持一致, 正則項(xiàng)的模型就是最小化兩個(gè)密度分布的K-L散度。然后通過比較人臉圖像聚類 實(shí)驗(yàn)結(jié)果驗(yàn)證了算法具有在低維空間中保持高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)的性質(zhì)。本文提出了一種新的基于梯度下降的快速收斂算法。傳統(tǒng)的梯度下降方法步 長是固定的，如果步長設(shè)置的太小，那么就會(huì)增加迭代的時(shí)間，導(dǎo)致求解的過程 時(shí)間增長，如果步長設(shè)置的太大，那么容易錯(cuò)過最優(yōu)解，對(duì)算法達(dá)不到收斂。本 文提出的算法在每次迭代之前都要計(jì)算本次迭代的最優(yōu)步長。目標(biāo)函數(shù)每次迭代 都按照最優(yōu)步長來下降。本文通過相關(guān)實(shí)驗(yàn)，驗(yàn)證了本文提出的梯度下降方法具 有收斂性，收斂速度快等特點(diǎn)。關(guān)鍵詞：非負(fù)矩陣分解，核密度估計(jì)，K-L散度，內(nèi)在結(jié)構(gòu)

6、保持，梯度下降A(chǔ)BSTRACTNon-negative matrix factorization (NMF) is a hot research topic in the field of pattern recognition and machine learning. Unlike the other matrix decomposition methods. NMF factorizes a nonnegative matrix into the product of two nonnegative matrices (one is basis matrix, another is we

7、ight matrix). The nonnegative constraints lead to a sparsely distributed data coding that might be useful for extracting parts-based representation of data patterns with low feature dimensionality. In this regard, NMF agrees with human visual perceive system. The classical matrix decomposition, such

8、 as Single Value Decomposition (SVD) is to decompose a matrix into the product of three matrices, but the matrices contain negative elements. As the result, there is no physical meaning of the decomposition. Thus, NMF method has been widely used in image processing, data mining, environmental monito

9、ring, chemo-metrics and multimedia analysis. From the perspective view of dimensionality reduction, we may choose a proper parameter such that can obtain a low-dimensional representation by the decomposition. In this work, we focus on NMF model and algorithm. We propose an intrinsic structure preser

10、ving non-negative matrix factorization model and algorithm for dealing with high dimensional data.In this paper, we add a regularization term to the objective function of the standard non negative matrix factorization model, and a new non-negative matrix factorization model is proposed to maintain t

11、he intrinsic structure of high-dimensional data in the low-dimensional space. The regularization term attempts to describe the mismatch between the distribution of the original data and the low-dimensional representation. The Gaussian and Cauchy kernel density estimation is used to estimate the dist

12、ribution of the original data and the low-dimensional representation, respectively. The Kullback Leibler divergence (K-L divergence) is used to measure the mismatch between the distribution of the original data and the low-dimensional representation. In order to preserve the intrinsic structure of t

13、he original data, the regularization term needs to be minimized. A gradient descent algorithm is proposed to solve the regularized NMF model. The proposed algorithm is to calculate the optimal step size in each iteration such that the objective function is the largest descent.Keywords: Non-negative

14、Matrix Factorization, Kernel Density Estimation, Kullback Leibler Divergence, Intrinsic Structure Preserving, Gradient Descent目錄 TOC o 1-5 h z 中文摘要I英文摘要II HYPERLINK l bookmark19 o Current Document 1緒論1 HYPERLINK l bookmark22 o Current Document 1.1選題背景及研究意義1 HYPERLINK l bookmark25 o Current Document

15、1.2研究現(xiàn)狀及難點(diǎn)問題3 HYPERLINK l bookmark28 o Current Document 1.2.1國內(nèi)外研究現(xiàn)狀3 HYPERLINK l bookmark35 o Current Document 1.2.2研究的難點(diǎn)問題9 HYPERLINK l bookmark41 o Current Document 1.3本文的主要工作及內(nèi)容安排10 HYPERLINK l bookmark44 o Current Document 1.3.1本文主要工作10 HYPERLINK l bookmark47 o Current Document 1.3.2本文結(jié)構(gòu)安排10 HY

16、PERLINK l bookmark52 o Current Document 2非負(fù)矩陣分解基本理論12 HYPERLINK l bookmark55 o Current Document 2.1非負(fù)矩陣分解理論122.1.1問題闡述122.1.2目標(biāo)函數(shù)12 HYPERLINK l bookmark62 o Current Document 2.1.3迭代規(guī)則13 HYPERLINK l bookmark72 o Current Document 2.1.4 NMF解的性質(zhì)15 HYPERLINK l bookmark102 o Current Document 2.2非負(fù)矩陣分解的原理1

17、9 HYPERLINK l bookmark105 o Current Document 2.3非負(fù)矩陣分解的應(yīng)用22 HYPERLINK l bookmark108 o Current Document 2.3.1非負(fù)矩陣分解算法在數(shù)據(jù)壓縮中的應(yīng)用22 HYPERLINK l bookmark111 o Current Document 2.3.2非負(fù)矩陣分解算法在聚類中的應(yīng)用23 HYPERLINK l bookmark114 o Current Document 2.3.3非負(fù)矩陣分解算法在分類中的應(yīng)用24 HYPERLINK l bookmark117 o Current Docume

18、nt 2.3.4非負(fù)矩陣分解算法在具體領(lǐng)域中的應(yīng)用25 HYPERLINK l bookmark124 o Current Document 2.4本章小結(jié)25 HYPERLINK l bookmark130 o Current Document 3高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解方法27 HYPERLINK l bookmark133 o Current Document 3.1引言27 HYPERLINK l bookmark136 o Current Document 3.2高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解的模型27 HYPERLINK l bookmark139 o Current

19、 Document 3.2.1基于核密度估計(jì)的正則項(xiàng)27 HYPERLINK l bookmark142 o Current Document 3.2.2高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解模型28 HYPERLINK l bookmark145 o Current Document 3.3 一種快速的梯度下降法28 HYPERLINK l bookmark148 o Current Document 3.3.1梯度下降方法29 HYPERLINK l bookmark151 o Current Document 3.3.2 一種快速的梯度下降法29 HYPERLINK l bookmark16

20、3 o Current Document 3.4求解高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解問題31 HYPERLINK l bookmark166 o Current Document 3.4.1求基矩陣可的迭代更新公式31 HYPERLINK l bookmark172 o Current Document 3.4.2系數(shù)矩陣丑的迭代更新方法33 HYPERLINK l bookmark182 o Current Document 3.5. 算法過程36 HYPERLINK l bookmark191 o Current Document 3.6本章小結(jié)36 HYPERLINK l bookma

21、rk194 o Current Document 4試驗(yàn)與結(jié)果分析37 HYPERLINK l bookmark197 o Current Document 4.1引言37 HYPERLINK l bookmark200 o Current Document 4.2試驗(yàn)數(shù)據(jù)集374.3實(shí)驗(yàn)與結(jié)果38 HYPERLINK l bookmark203 o Current Document 4.3.1高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解算法的收斂性38 HYPERLINK l bookmark207 o Current Document 4.3.2基向量分析40 HYPERLINK l bookmar

22、k210 o Current Document 4.3.3原始圖像的重構(gòu)41 HYPERLINK l bookmark213 o Current Document 4.3.4高維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解算法的聚類性能42 HYPERLINK l bookmark222 o Current Document 4.3.5新的快速梯度下降方法實(shí)驗(yàn)45 HYPERLINK l bookmark225 o Current Document 4.3.6新的梯度下降法與乘性迭代方法聚類性能實(shí)驗(yàn)46 HYPERLINK l bookmark228 o Current Document 4.4本章小結(jié)47

23、 HYPERLINK l bookmark231 o Current Document 5總結(jié)與展望48 HYPERLINK l bookmark234 o Current Document 5.1本文工作總結(jié)48 HYPERLINK l bookmark240 o Current Document 5.2未來工作展望49致謝50 HYPERLINK l bookmark252 o Current Document 參考文獻(xiàn)51附錄551緒論1.1選題背景及研究意義隨著互聯(lián)網(wǎng)和信息化的發(fā)展，各行各業(yè)的應(yīng)用都產(chǎn)生很多大規(guī)模的數(shù)據(jù)，比 如web互聯(lián)網(wǎng)信息數(shù)據(jù)，基因數(shù)據(jù)，衛(wèi)星傳回的氣象數(shù)據(jù)，地圖數(shù)據(jù)

24、等，這無疑 給數(shù)據(jù)分析、數(shù)據(jù)處理和數(shù)據(jù)存儲(chǔ)帶來了新的挑戰(zhàn)。這些大規(guī)模數(shù)據(jù)有以下幾個(gè) 共同點(diǎn)，數(shù)據(jù)量大，包含冗余信息，包含數(shù)據(jù)噪聲，信息分布不均勻，數(shù)據(jù)的內(nèi) 在結(jié)構(gòu)特征不明顯。由于數(shù)據(jù)包含以上特點(diǎn)，我們不能直接對(duì)數(shù)據(jù)進(jìn)行分析。這些信息數(shù)據(jù)通常是以矩陣的形式表示的，矩陣的每一個(gè)元素都有其相應(yīng)的 現(xiàn)實(shí)意義，比如表示圖像的矩陣每個(gè)元素表示相應(yīng)位置上的像素值，視頻的存儲(chǔ) 可以看作是時(shí)間軸和圖像幀組成的三維矩陣，同樣地這個(gè)三維矩陣中每個(gè)元素代 表了相應(yīng)時(shí)刻下，圖像幀中像素點(diǎn)的數(shù)值大小。在文檔分類中，不同文檔中不同 的關(guān)鍵字出現(xiàn)的頻率可以組成一張二維表，這樣的二維表就是用矩陣形式存儲(chǔ)的。 由此可見，常見的應(yīng)

25、用中需要處理的大規(guī)模數(shù)據(jù)，都可以簡(jiǎn)化為對(duì)數(shù)據(jù)矩陣的處 理。在實(shí)際的應(yīng)用中，數(shù)據(jù)矩陣維數(shù)往往很大，由于維數(shù)災(zāi)難的原因，數(shù)據(jù)處理 中用到的分類和聚類方法，其計(jì)算量會(huì)越來越大，在某些實(shí)時(shí)性要求較高的系統(tǒng) 上，這些算法已不能滿足應(yīng)用程序?qū)r(shí)間的要求。甚至還有一些算法不能直接處 理高維數(shù)的數(shù)據(jù)矩陣。因此對(duì)高維數(shù)據(jù)矩陣分解E是處理高維數(shù)據(jù)的一個(gè)有效方 法。通過對(duì)高維數(shù)據(jù)矩陣分解不但可以降低數(shù)據(jù)矩陣的維數(shù)，便于數(shù)據(jù)的處理， 提高效率，對(duì)冗余的數(shù)據(jù)壓縮和概括，減小占用的存儲(chǔ)空間，還可以使數(shù)據(jù)中某 些潛在的結(jié)構(gòu)變得清晰。矩陣分解的目的就是將對(duì)高維數(shù)據(jù)矩陣的分析和處理這 樣較復(fù)雜的問題轉(zhuǎn)換為規(guī)模較小的、結(jié)構(gòu)特征明

26、顯的低維數(shù)據(jù)矩陣分析與處理的 問題。傳統(tǒng)的矩陣分解方法有奇異值分XSingle Value Decomposition, SVD)、矢量量 化(Vector Quantization, VQ)、主成分分析(Principal Component Analysis, PC A)等, 這些矩陣分解的方法將原始的高維數(shù)矩陣V近似分解為低秩的V = 形式。值得 注意的一點(diǎn)是，即使輸入的初始矩陣元素全是正的，因式矩陣I和H中的元素也 可能為正值或負(fù)值或者0。也就是說，傳統(tǒng)的矩陣分解方法允許負(fù)的分解矩陣存在, 在數(shù)學(xué)上這些分解后存在的負(fù)值是正確的，而在現(xiàn)實(shí)的應(yīng)用中矩陣分解出來的負(fù) 值很難用其物理含義來解釋

27、。例如對(duì)圖像矩陣分解后產(chǎn)生的負(fù)值，我們就不能用 圖像的像素值來解釋，同樣的，對(duì)于文本的數(shù)據(jù)挖掘應(yīng)用中，矩陣分解產(chǎn)生的負(fù) 值也不能用文字編碼來解釋。負(fù)值在這里場(chǎng)景下是沒有實(shí)際意義的，無法用實(shí)際 的含義去解釋。所以，研究非負(fù)矩陣的非負(fù)分解方法在理論和現(xiàn)實(shí)中都具有較大 大的意義。另一方面，傳統(tǒng)的矩陣分解方法從整體的角度出發(fā)，分解后得到的基 矩陣也是由整體所組成的，他們是以整體為基本單位，通過對(duì)整體的加權(quán)和來表 示原始矩陣。這種方法不能清晰地刻畫出矩陣數(shù)據(jù)的內(nèi)在結(jié)構(gòu)信息和特征。而非 負(fù)矩陣分解恰好彌補(bǔ)了這一缺點(diǎn)，算法分解后得到的基矩陣是由構(gòu)成整體部件的 “部分組件組成的。原始矩陣正是通過這些部分的加權(quán)

28、和構(gòu)成的。非負(fù)矩陣分解方 法反映了“部分構(gòu)成整體思想囹。這種思想也符合我們?nèi)祟愓J(rèn)知事物的基本方 式。通過這種方式，非負(fù)矩陣分解方法具有揭示數(shù)據(jù)矩陣的本質(zhì)特性的功能。所 以，NMF方法有區(qū)別于傳統(tǒng)矩陣分解的優(yōu)點(diǎn)，研究NMF分解很有意義。從非負(fù)矩陣分解算法的實(shí)現(xiàn)簡(jiǎn)單，結(jié)構(gòu)清晰，收斂速度快等特點(diǎn)看，研究非 負(fù)矩陣分解對(duì)處理實(shí)時(shí)性要求較高，程序簡(jiǎn)單的應(yīng)用非常合適。這些優(yōu)點(diǎn)，給非 負(fù)矩陣分解理論增加了研究的價(jià)值。非負(fù)矩陣分解最早可追溯至1994年P(guān)aatero和Tapper提出的Positive matrix factorization% 該理論是將n x m原始數(shù)據(jù)X分成為兩個(gè)正矩陣G,F的乘積和一

29、個(gè)誤差矩陣之和的形式，表達(dá)式為：X = GF + E, G是n X p的正矩陣，F(xiàn)是p X m的正矩陣，E是n X m的誤差矩陣。通過加權(quán)最小二乘法，使E的F范數(shù)逐元 素除以原始矩陣的標(biāo)準(zhǔn)差最小來確定G和F矩陣。文章中通過環(huán)境數(shù)據(jù)應(yīng)用的結(jié) 果，說明了 Positive matrix factorization 在一些應(yīng)用中的效果比 factor analysis 和 PCA 要好。而使非負(fù)矩陣分解真正流行起來是1999年Lee和Seung兩位科學(xué)家在 Nature上提出了非負(fù)矩陣因式分解（Nonnegative Matrix Factorization, NMF）的思 想和算法。同樣的，和Po

30、sitive matrix factorization理論一樣，NMF算法分解矩陣 后的分量均為非負(fù)值，同時(shí)兩者都可以產(chǎn)生兩個(gè)可以相乘的因子矩陣。NMF算法是將一個(gè)高維矩陣分解為兩個(gè)低維矩陣相乘的形式，這兩個(gè)低維矩 陣一個(gè)稱為基矩陣，一個(gè)稱為系數(shù)矩陣。其中，基矩陣是由高維矩陣中的局部信 息組成。這些局部信息正是高維數(shù)據(jù)矩陣潛在的局部特征。基矩陣通過將“局部 數(shù)據(jù)加權(quán)和來得到原矩陣。系數(shù)矩陣正是由這些權(quán)重系數(shù)構(gòu)成。系數(shù)矩陣可以保 持高維數(shù)據(jù)矩陣中潛在的某些本質(zhì)的信息。這些本質(zhì)信息可以用來作為聚類應(yīng)用 中的特征信息。不論分解后得到的基矩陣還是系數(shù)矩陣，他們的元素都滿足非負(fù) 約束條件。從數(shù)學(xué)表達(dá)式的

31、角度看，NMF的基本方法是：對(duì)于任意給定的n個(gè)m 維數(shù)據(jù)矩陣X, NMF方法試圖尋找到一個(gè)大小為m*r的非負(fù)矩陣（基矩陣）W和 一個(gè)大小為r*n的非負(fù)矩陣（系數(shù)矩陣）H,使得X=WH,其中rvn。即將一個(gè)非 負(fù)矩陣X分解為兩個(gè)低維矩陣相乘的形式：WH,可以看出如果原始矩陣X與WH 的乘積越接近，那么重建效果就越好，原始數(shù)據(jù)的信息損失越少，反正則效果越 差，信息損失越多。對(duì)r值的選取要適中，如果r值偏小，分解得到的基矩陣中 的基向量個(gè)數(shù)偏少，提取的特征數(shù)目也會(huì)較少，可能會(huì)丟失一些本質(zhì)特征。而如 果r值選取的偏大，NMF分解后得到的系數(shù)矩陣維數(shù)也會(huì)比較大，這樣不能滿足 降維的需要。同時(shí)，由于分解后

32、基向量比較多，有些基向量并不是原矩陣的局部 特征，不能表達(dá)原矩陣的局部特征，這些基向量是冗余向量。從幾何角度來說， 原始矩陣的每一個(gè)列向量x可以解釋為左側(cè)矩陣W中所有基向量的加權(quán)和，這從 矩陣乘法原理中可以很容易看出，而每個(gè)基向量的權(quán)重值就是右側(cè)矩陣H中對(duì)應(yīng) 行的元素值。當(dāng)利用基矩陣和系數(shù)向量h (系數(shù)矩陣H中的一列)來重建原始數(shù) 據(jù)矩陣X中對(duì)應(yīng)的一個(gè)數(shù)據(jù)樣本時(shí)，x=Wh,這種通過向量加權(quán)和的表示方式，反 映了 NMF分解與人類認(rèn)知事物方式的一致性，艮卜部分構(gòu)成整體的概念。高維 數(shù)據(jù)通過NMF分解后，得到的系數(shù)矩陣H的維數(shù)遠(yuǎn)小于原始矩陣X的維數(shù)，這 樣就可以實(shí)現(xiàn)對(duì)高維數(shù)據(jù)的降維，對(duì)原始矩陣X的

33、壓縮。目前，NMF方法已經(jīng)被應(yīng)用到圖像識(shí)別5,圖像處理叫 文本挖掘，日志分 析，語音處理瑚，文本分類和聚類1112,模式識(shí)別，生物工程Ml,數(shù)據(jù)壓縮mi 等各個(gè)領(lǐng)域。它具有傳統(tǒng)矩陣分解方法無法替代的優(yōu)點(diǎn)：收斂速度快，實(shí)現(xiàn)簡(jiǎn)單, 分解結(jié)果的可解釋性，算法的穩(wěn)定性等。它已經(jīng)引起了國內(nèi)外很多科學(xué)家的關(guān)注， 成為科學(xué)家們研究矩陣分解的主流方向。在不遠(yuǎn)的未來，使用非負(fù)矩陣分解方法 來處理實(shí)際問題的領(lǐng)域?qū)⒑w各行各業(yè)。所以研究NMF方法很有意義。1.2研究現(xiàn)狀及難點(diǎn)問題1.2.1國內(nèi)外研究現(xiàn)狀經(jīng)過十多年的發(fā)展，NMF矩陣分解理論已經(jīng)引起了各界廣泛的關(guān)注。與NMF 方法有關(guān)的理論，對(duì)非負(fù)矩陣分解各種改進(jìn)算法

34、，優(yōu)秀的算法不斷地提出，對(duì)非 負(fù)矩陣分解算法的討論越來越多。基于NMF方法的應(yīng)用正在不斷的涌現(xiàn)出來。這 些現(xiàn)象使得NMF方法成為學(xué)術(shù)界和工程界的研究熱點(diǎn)。當(dāng)前對(duì)NMF矩陣分解理論研究的敘述可以發(fā)現(xiàn)，非負(fù)矩陣分解方法其實(shí)質(zhì)仍 然是約束優(yōu)化問題。這些約束優(yōu)化問題包含諸多方面，比如對(duì)目標(biāo)函數(shù)的選取， 對(duì)目標(biāo)函數(shù)增加正則項(xiàng)，迭代規(guī)則的推導(dǎo)，NMF初始化方法的選擇以及矩陣初始 值的選擇，對(duì)基矩陣的稀疏性和正交性的約束方法等很多方面。根據(jù)NMF中目標(biāo)函數(shù)的個(gè)數(shù)，可以將NMF方法分成(1)單目標(biāo)函數(shù)NMF方 法和(2)多目標(biāo)函數(shù)NMF方法兩大類。其中單目標(biāo)函數(shù)的NMF方法比較常見。下 面就按照這種分類方式，

35、并列舉一些具有重要意義的算法。基于單個(gè)目標(biāo)函數(shù)的NMF方法Lee和Seung于1999年，提出NMF算法，該算法提供了兩個(gè)不同的目標(biāo)函數(shù)，分別是:frobenius 范數(shù)：f =11 XWHIP尸XKullback-Leibler 散度：Q(X IIWH) = (Xlog而X+(WH)ijWrL )司其中W是基矩陣，H是系數(shù)矩陣。利用目標(biāo)函數(shù)，獲得W和H的迭代規(guī)則。 文中假設(shè)原始數(shù)據(jù)矩陣X的每個(gè)元素X”是獨(dú)立的，并且在X中添加了服從泊松 分布的噪聲，并建立概率模型，根據(jù)最大似然估計(jì)生成目標(biāo)函數(shù)。在非負(fù)約束下， 即X0, W0和H20時(shí)，目標(biāo)函數(shù)能夠收斂到其局部最小值。這種NMF方法 稱為標(biāo)準(zhǔn)N

36、MF方法。解這兩個(gè)目標(biāo)函數(shù)的方法分別是(1)最小化常規(guī)最小二乘法誤 差和(2)最小化Kullback-Leibler散度，文中通過輔助函數(shù)證明了這兩個(gè)算法的收斂 性，并通過這個(gè)證明分別得到了基矩陣W和系數(shù)矩陣H的更新迭代規(guī)則。單個(gè)目標(biāo)函數(shù)的NMF方法是指目標(biāo)函數(shù)的形式是確定的，有確定的表達(dá)式， 不通過參數(shù)來改變目標(biāo)函數(shù)。這類NMF算法充分利用了目標(biāo)函數(shù)的約束條件和優(yōu) 化方式，構(gòu)造出帶有稀疏性約束，正交性約束，F(xiàn)isher限制，流形約束，判別信息， 加權(quán)特性，全變差約束，拉普拉斯約束等約束條件的多種擴(kuò)展NMF方法。帶有稀疏約束的NMF方法標(biāo)準(zhǔn)NMF方法，具有天然的稀疏特性。但是在某些應(yīng)用中，其稀

37、疏性仍然不 夠。因此，很多人將稀疏約束限制加入到NMF方法中。Li等人在標(biāo)準(zhǔn)NMF分解 算法的基礎(chǔ)上添加了對(duì)基矩陣的稀疏約束，基向量元素的和為1,并且使如最小 (其中u = uij = wTw , w為基矩陣)o提出了局部非負(fù)矩陣分解算法(local nonnegative matrix factorization ,LNMF)16O這個(gè)方法使得基矩陣更加稀疏，提高了算法的識(shí)別 率。但是由于該算法為了保留基向量中重要信息，導(dǎo)致系數(shù)矩陣H稀疏性降低。Hoyer等人將稀疏編碼的思想添加到NMF中，提出了非負(fù)稀疏編碼方法 (Non-negative Sparse Coding ) 17 o 該方法的

38、目標(biāo)函數(shù)為 F(W,H) =XWHII+后，其中人為稀疏系數(shù)。它對(duì)系數(shù)矩陣添加稀疏約束。同時(shí)，Zij利用梯度下降法來解目標(biāo)函數(shù)，并將基矩陣W的負(fù)值設(shè)置為0來提高基矩陣W的 稀疏度。隨后，Hoyer等人又提出另外一種帶有稀疏約束的非負(fù)矩陣分解算法邸】。 它利用L1范數(shù)和L2范數(shù)之間的關(guān)系，給出了稀疏度的度量公式 次w心心)=正弓片王，其中n為x的維數(shù)，根據(jù)不同的應(yīng)用，來選擇對(duì)W 或者H或者兩者都加這種稀疏約束。算法仍然使用梯度下降法來迭代，根據(jù)約束 的矩陣選擇L2范數(shù)不變或者單位化，改變L1范數(shù)的大小來滿足稀疏度要求。Heiler等人對(duì)目標(biāo)函數(shù)為/ =11 X-WH 11的標(biāo)準(zhǔn)NMF算法的求解方

39、法進(jìn)行改 善。他們利用目標(biāo)函數(shù)的展開式，形式如下，將求解目標(biāo)函數(shù)的最小化問題轉(zhuǎn)化 為對(duì)凸二次規(guī)劃(Convex Quadratic Programs, CQP)的求解問題。他將一個(gè)非凸 問題，轉(zhuǎn)化為凸問題，得到了一個(gè)單調(diào)下降并且收斂的NMF方法I。這種方法的 優(yōu)點(diǎn)是求解凸二次規(guī)劃問題的方法已經(jīng)很成熟，其算法推導(dǎo)過程比較簡(jiǎn)單，思路 清晰，容易理解。另外，該算法可以處理大規(guī)模數(shù)據(jù)，可以適用在常見的機(jī)器學(xué) 習(xí)，計(jì)算機(jī)視覺和工程等領(lǐng)域。同時(shí)，在該方法中為了方便用戶和增加算法的魯 棒性，而沒有引入像步長，迭代次數(shù)這樣多余的優(yōu)化參數(shù)。這樣做也減少了出錯(cuò) 和低效率的可能點(diǎn)。而算法的缺點(diǎn)是算法實(shí)現(xiàn)起來比較困難

40、，求得的解可能是局 部最優(yōu)解，而不一定全局最優(yōu)解。同時(shí)，Heiler等人在稀疏性約束優(yōu)化等方面做 了許多工作RS,并給出算法收斂性的證明。Ding等人通過探索矩陣分解因子與K-Means聚類結(jié)果之間的關(guān)系，發(fā)現(xiàn)了矩 陣分解的因子之間隱含的可解釋性。他們對(duì)標(biāo)準(zhǔn)NMF放寬約束條件，對(duì)數(shù)據(jù)矩陣 X不再約束其元素為非負(fù)值情況下，提出了半非負(fù)矩陣分解(Semi-NMF, SNMF) 和凸非負(fù)矩陣分解(Convex-NMF, CNMF) 21o其中，半非負(fù)矩陣分解對(duì)數(shù)據(jù)矩 陣和基矩陣W元素的正負(fù)都沒有約束，而系數(shù)矩陣H仍然具有非負(fù)的約束。它將 K-Means的目標(biāo)函數(shù)看作是矩陣逼近的目標(biāo)函數(shù)。在凸非負(fù)矩陣

41、分解中，基矩陣 W被看作是數(shù)據(jù)矩陣的線性組合，這樣做的一個(gè)優(yōu)點(diǎn)是可以合理的解釋基矩陣是 某些數(shù)據(jù)點(diǎn)的權(quán)重組合，尤其是質(zhì)點(diǎn)數(shù)據(jù)點(diǎn)的組合。這類放松對(duì)數(shù)據(jù)矩陣非負(fù)約 束的NMF算法在現(xiàn)實(shí)應(yīng)用中仍有其特殊意義的地位，文中對(duì)算法的推導(dǎo)過程詳細(xì) 透徹，解釋合理。為研究NMF方法提供了一種新思路。此外，Zhao22等人，Liu等人R3, Xul等人也把稀疏表示的思想加入到NMF 算法中，得到了各種各樣的改進(jìn)的NMF算法。帶有正交約束的非負(fù)矩陣分解如果在目標(biāo)函數(shù)中增加約束條件，使基矩陣W和系數(shù)矩陣H滿足= /和 hth = i ,那么基矩陣W和系數(shù)矩陣H滿足正交約束。傳統(tǒng)的正交限制只能對(duì)基矩 陣W或稀疏矩陣H

42、之一來限制，并不能同時(shí)使基矩陣和系數(shù)矩陣H都正交。為了 解決此問題，Ding等人改進(jìn)了基于F-范數(shù)的目標(biāo)函數(shù)，提出了目標(biāo)函數(shù)為 殆理Pg/x-fsg，IP 的三因子 NMF 算法(Orthogonal Nonnegative Matrix Tri-factorizations) 25,約束條件為f = i和g，g = /,其中 I 為單位矩陣。Pompili 等人從數(shù)學(xué)的角度，闡述了正交非負(fù)矩陣分解與加權(quán)的球型k-means變體的等價(jià) 性。從而產(chǎn)生了解正交非負(fù)分解問題的EM-like算法。此外，文中還提出了另一種 基于增廣拉格朗日方法來解決正交非負(fù)矩陣分解的問題。Ding等人證明了w = hh

43、t 分解與核K-means聚類具有等價(jià)性，設(shè)置目標(biāo)函數(shù)為：嗽八四-劇輯尸其中w是 對(duì)稱核表示。同時(shí)，針對(duì)非負(fù)非半正定矩陣給出了改進(jìn)的目標(biāo)函數(shù) 嗯w- HSWA,從而將核函數(shù)引入到非負(fù)矩陣分解中mi。此外，還有藥等人針 對(duì)現(xiàn)有正交的非負(fù)矩陣分解算法中計(jì)算復(fù)雜度大，或者必須結(jié)合先驗(yàn)知識(shí)來達(dá)到 正交目的的問題，提出了將wTw-n或iwW/II約束直接加入到基于歐氏距離和K-L 散度目標(biāo)函數(shù)中，得到正交子空間的非負(fù)矩陣分解算法(Nonnegative Matrix Factorization on Orthogonal Subspace, NMFOS)27。含有鑒別信息的NMF方法標(biāo)準(zhǔn)NMF方法中不含

44、有樣本的類別信息，為了提高分類的精度，很多研究者 將樣本的類別信息加入到NMF方法中。Fisher鑒別準(zhǔn)則是，數(shù)據(jù)在降維后，使得屬于同一類的樣本數(shù)據(jù)之間的距離越 小，而不屬于同一類的樣本數(shù)據(jù)之間的距離越大。這樣可以使降維后的數(shù)據(jù)分布 利于分類，從而提高分類精度。Wang等人將Fisher鑒別信息加入到非負(fù)矩陣分解 中，得到了 Fisher 非負(fù)矩陣分解(Fisher non-negative matrix factorization,FNMF)28o 該算法基于K-L散度，并給出了收斂性的證明。隨后，Y.Wang等人提出通過在矩 陣分解中添加NMF約束和分類器約束構(gòu)建了人臉識(shí)別的基本框架，并在

45、此框架的 基礎(chǔ)上提出了 Fisher Linear Discriminant Analysis (FLDA)的非負(fù)矩陣分解方法河。 Nikitidis等人針對(duì)線性判別分析中不能處理的數(shù)據(jù)分布為多峰的情況，提出了子類 判別非負(fù)矩陣分解(subclass discriminant NMF, SDNMF) 30o該方法將判別信息 與NMF方法的目標(biāo)函數(shù)結(jié)合在一起，增強(qiáng)了低維投影空間中不同類別之間的區(qū)分 性。這樣對(duì)空間結(jié)構(gòu)復(fù)雜的分類問題轉(zhuǎn)換為轉(zhuǎn)換為低維子類空間分類的問題，提 高了算法的分類正確率。其他思想改進(jìn)的NMF算法許多研究者將一些流行的思想與非負(fù)矩陣分解算法融合，得到了較好的效果, 改進(jìn)和優(yōu)化了

46、 NMF算法。這為研究NMF提供了新的思路。由于基于最小化平方誤差(基于L2范數(shù))的非負(fù)矩陣分解算法在處理尋找局 部結(jié)構(gòu)特征問題時(shí)，并不能將局部結(jié)構(gòu)特征信息更明顯化，清晰化。在國內(nèi)Zhang 等人探索了出現(xiàn)這種問題的原因。并針對(duì)這個(gè)問題提出了一種新的方法：基于全 變差范數(shù)的非負(fù)矩陣分解方法。同時(shí)，也給出了全變差非負(fù)矩陣分解的迭代更 新公式，證明了算法具有收斂性和穩(wěn)定性的特質(zhì)，分析了算法的收斂速度。最后， 其結(jié)合標(biāo)準(zhǔn)NMF算法和基于最小平方誤差NMF算法在圖像去噪方面的應(yīng)用實(shí)驗(yàn) 中展示了基于全變差范數(shù)的非負(fù)矩陣分解方法的去噪效果。同時(shí)，實(shí)驗(yàn)也表現(xiàn)出 該算法對(duì)分解后數(shù)據(jù)的局部結(jié)構(gòu)細(xì)節(jié)有突出表現(xiàn)，對(duì)

47、原始數(shù)據(jù)的重建也有優(yōu)異的 表現(xiàn)。隨后，Zhang等人提出了一種新的非負(fù)矩陣分解算法，拓?fù)浔３值腘MF算法 32】。該算法在標(biāo)準(zhǔn)非負(fù)矩陣分解算法的基礎(chǔ)上填加了對(duì)系數(shù)矩陣H的約束。使高 維空間中梯度距離最小。這樣的約束條件會(huì)使高維數(shù)據(jù)的局部拓?fù)浣Y(jié)構(gòu)信息得到 保留。文中推導(dǎo)了該拓?fù)浔３諲MF算法的解，獲得了迭代更新公式。通過比較發(fā) 現(xiàn)，這種拓?fù)浔３值姆秦?fù)矩陣分解算法比萬距離具有更強(qiáng)的發(fā)現(xiàn)潛在流形結(jié)構(gòu)特 征(如邊緣和紋理)的能力。由于局部流形結(jié)構(gòu)特征對(duì)于模式識(shí)別和分類來說很 重要，所以該方法在有光照變化影響，表情變化等情景下對(duì)人臉識(shí)別應(yīng)用具有良 好的效果。Zhang等人提出了一種局部性保持的非負(fù)矩陣分

48、解方法(Locality Preserving Nonnegative Matrix Factorization,LPNMF) 33O這種方法能夠發(fā)現(xiàn)嵌入在高維數(shù)據(jù) 結(jié)構(gòu)中的流形特征。它通過將局部特征保持約束模型與NMF目標(biāo)函數(shù)結(jié)合的方法 來實(shí)現(xiàn)的。因此，該算法擁有一些局部性保持的特性。文中給出了該算法目標(biāo)函 數(shù)推導(dǎo)過程,并通過優(yōu)化目標(biāo)函數(shù)得到了基矩陣W和系數(shù)矩陣H的迭代更新公式。 最后文中分別通過在CBCL數(shù)據(jù)集，yale人臉數(shù)據(jù)集，CMU-PIE人臉數(shù)據(jù)集上的 實(shí)驗(yàn)證明了這種局部性保持的非負(fù)矩陣分解的方法在發(fā)現(xiàn)高維數(shù)據(jù)中嵌入的流形 結(jié)構(gòu)方面，非常有效。Zhang等人通過將數(shù)據(jù)局部信息在人臉

49、子空間中保持的方法來達(dá)到提取辨別 信息的目的。他們提出了拉普拉斯非負(fù)矩陣分解方法(Laplacian Nonnegative Matrix Factorization, LNMF)拉普拉斯非負(fù)矩陣分解方法在分解后的人臉子空間中 保留了獨(dú)有的拉普拉斯特征。因此，這種非負(fù)矩陣分解方法比標(biāo)準(zhǔn)NMF方法有更 多的辨別信息。和其他改善的非負(fù)矩陣分解算法一樣，拉普拉斯非負(fù)矩陣分解方 法同樣是在標(biāo)準(zhǔn)非負(fù)矩陣分解目標(biāo)函數(shù)上加上一個(gè)正則約束，然后通過優(yōu)化目標(biāo) 函數(shù)而求出該方法的迭代更新公式。最后，作者通過在耶魯數(shù)據(jù)庫上的對(duì)比實(shí)驗(yàn)， 比較了拉普拉斯非負(fù)矩陣分解方法與特征臉方法、Fisher臉方法和標(biāo)準(zhǔn)非NMF方

50、法的識(shí)別效果。流形學(xué)習(xí)的思想35】是將高維數(shù)據(jù)映射低維空間中。從而獲得高維數(shù)據(jù)本質(zhì)的 流形結(jié)構(gòu)。國內(nèi)的Cai等人將流形思想引入到NMF中，提出了基于流形的非負(fù)矩 陣分解算法(Non-negative Matrix Factorization on Manifold, NMFM) 36O 標(biāo)準(zhǔn) NMF 方法在數(shù)據(jù)表示時(shí)，沒有考慮到數(shù)據(jù)的幾何結(jié)構(gòu)信息。NMFM方法通過構(gòu)建關(guān)系 圖來編碼幾何信息，從而克服這種限制。國外的Kim等人針對(duì)不完整數(shù)據(jù)矩陣分 解問題，提出了權(quán)重非負(fù)矩陣分解方法(Alternating Nonnegative Least Squares,ANLS-WNMF )和(Genera

51、lized Expectation-Maximization,GEM-WNMF)算 法37】。國內(nèi)的Guan等人將流形規(guī)則化和邊緣最大化引入到非負(fù)矩陣分解中，得到 了流形規(guī)則化判別 NMF (manifold regularized discriminative NMF,MD-NMF)算法 38o它解決了標(biāo)準(zhǔn)NMF中忽視數(shù)據(jù)局部幾何特征和不同類別具有的判別信息的問 題。并且針對(duì)乘性迭代算法收斂慢的特點(diǎn)，提出了一種快速收斂的快速梯度下降 法來優(yōu)化MD-NMF算法。基于梯度下降的可行方向算法優(yōu)點(diǎn)是局部搜索能力強(qiáng)，收斂速度快，但是其 容易陷入局部極小值。而模擬退火算法是一種有效的全局優(yōu)化算法。國內(nèi)的

52、陳衛(wèi) 剛等人結(jié)合二者的優(yōu)缺點(diǎn)，針對(duì)Frobenius范數(shù)的目標(biāo)函數(shù)，提出了一種新的NMF 方法。這種方法可以得到全局最優(yōu)解。從收斂速度的角度來講，這種NMF方法 比起標(biāo)準(zhǔn)的NMF方法，初始階段收斂速度慢于標(biāo)準(zhǔn)NMF方法，但是最后階段收 斂速度快，并且誤差更小，所以這種方法的重建效果要優(yōu)于標(biāo)準(zhǔn)NMF方法。但是 其算法要更加復(fù)雜。此外，有研究者將當(dāng)前流行的多維數(shù)據(jù)矩陣處理的張量分解思想4。】與非負(fù)矩 陣分解思想融合產(chǎn)生了一系列效果較好的分解算法。國外的Welling等人提出了正 張量分解(Positive Tensor Factorization,PTF) 41o Bonettini 等人將循環(huán)塊

53、坐標(biāo)下降 法引入到非負(fù)矩陣分解中，提出了循環(huán)塊梯度投影方法I,該方法可以解決非負(fù) 矩陣分解中出現(xiàn)的大尺度(large-scale )問題。Zhou等人將最小卷積約束加入到 非負(fù)矩陣分解中，提出了最小卷積約束的非負(fù)矩陣分解算法 (minimum-volume-constrain NMF, MVCNMF) 43O 它能提高 NMF 分解因子的稀 疏度。國內(nèi)的翟亞利等人從NMF初始化的方面來研究非負(fù)矩陣分解，針對(duì)文本分類, 得到了效果較好的有監(jiān)督PCA初始化方法(SPCA) I。很多研究者也從非負(fù)矩陣分解的其他方面入手，包含收斂速度、梯度下降的 初始化方法、梯度下降步長的選擇，解非負(fù)矩陣問題的方法等

54、方面對(duì)NMF展開大 量研究工作，并取得了很好的效果。基于多個(gè)目標(biāo)函數(shù)的NMF方法多目標(biāo)函數(shù)是指非負(fù)矩陣分解中目標(biāo)函數(shù)形式確定，但在某些項(xiàng)上會(huì)有系數(shù) 因子，不會(huì)具體到某一個(gè)函數(shù)。我們可以根據(jù)不同的應(yīng)用來確定不同的系數(shù)因子， 從而確定出目標(biāo)函數(shù)。它在探索NMF分解問題中的目標(biāo)函數(shù)的一般形式具有重要 意義。國外的Cichocki等人通過研究一般的散度函數(shù)(包括Amari a- divergence, Relative entropy 相對(duì)炳，Bose-Einstein divergence 和 B - divergence 等)探索出了 NMF目標(biāo)函數(shù)的更一般性形式Si：在標(biāo)準(zhǔn)NMF目標(biāo)函數(shù)上加上兩

55、個(gè)合適的正則 化項(xiàng)。具體的函數(shù)可以根據(jù)不同的應(yīng)用來確定。一個(gè)特殊的案例是可以用來控制 分解因子矩陣W和H平滑度或稀疏度。他們通過令改進(jìn)后的目標(biāo)函數(shù)對(duì)分解因子 矩陣的梯度等于0,得到了定點(diǎn)(FixedPoint, FP)的更新規(guī)則。這就是定點(diǎn)NMF 算法(Fixed Point NMF algorithm) o算法的優(yōu)點(diǎn)是思路清晰，容易理解。但是更 新規(guī)則不是單調(diào)下降的，所以可能會(huì)出現(xiàn)不收斂的情況。國外的Dhillon等人提出了解非負(fù)矩陣逼近問題的算法Ml,這個(gè)算法使用乘性 更新規(guī)則來解一般性的非負(fù)矩陣逼近問題。也就是目標(biāo)函數(shù)是最小化輸入矩陣和 其低秩逼近的Bregman divergences

56、散度。122研究的難點(diǎn)問題由上述可以看出，隨著NMF分解思想的應(yīng)用越來越廣泛，將來會(huì)提出更多更 有效的改進(jìn)的NMF算法。目前大部分算法思路都是將某一特征表達(dá)式加入到NMF 目標(biāo)函數(shù)中，對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，通過借助輔助函數(shù)的方法求出基矩陣W和系 數(shù)矩陣H的更新迭代公式，同時(shí)，也會(huì)證明在得到的更新迭代公式的情況下算法 的收斂性。對(duì)NMF分解方法研究中，很少有人打破這種固定體系結(jié)構(gòu)，從一個(gè)新 的角度去闡述，解釋，表達(dá)，理解NMF算法。現(xiàn)在NMF算法的研究處于火熱的 階段，一些的重要的問題，難點(diǎn)問題還需要進(jìn)一步的討論與分析。這些問題涉及 到非負(fù)矩陣分解整個(gè)流程中有：非負(fù)矩陣分解算法中在計(jì)算迭代公式時(shí)，

57、輔助函數(shù)不容易確定，算法的收斂 速度很慢。輔助函數(shù)是解非負(fù)矩陣分解問題的核心部件。輔助函數(shù)可以證明算法 的收斂性，可以用來計(jì)算算法的迭代公式，而算法迭代公式的好壞直接影響都算 法的收斂速度。另外，不同的輔助函數(shù)，導(dǎo)致算法收斂到的結(jié)果也不同，可能有 的算法收斂到全局最小值，有的算法收斂到局部最小值。因此，探索尋找合適的 輔助函數(shù)，對(duì)解非負(fù)矩陣分解問題具有重要意義。非負(fù)矩陣分解算法的迭代過程中基矩陣W和系數(shù)矩陣H初始化方法網(wǎng)4748 對(duì)于迭代的次數(shù)具有很大的關(guān)系，好的初始化算法可以使算法迭代次數(shù)減少，算 法運(yùn)行時(shí)間大大縮短。并且，這兩個(gè)矩陣不同的初始值，可能導(dǎo)致收斂的結(jié)果也 不同。也就是說，不同初

58、始值，會(huì)導(dǎo)致收斂到的結(jié)果可能不是全局最優(yōu)解，而是 局部最小值。因此，探索尋找合適的初始化方法，對(duì)解非負(fù)矩陣分解問題具有重 要意義。非負(fù)矩陣分解后基向量的個(gè)數(shù)r的確定關(guān)系到矩陣分解后得到的基向量的 個(gè)數(shù)，同時(shí)，也是每個(gè)系數(shù)向量的維數(shù)。由此可見，基向量的個(gè)數(shù)r越大，分解后 得到的基向量越多，這可能導(dǎo)致有的基向量對(duì)原始數(shù)據(jù)中某些特征的冗余表示。 同時(shí)，系數(shù)向量的維數(shù)也增加了，這會(huì)影響數(shù)據(jù)的降維和壓縮。反之，r過小，基 向量的個(gè)數(shù)較少，原始數(shù)據(jù)中某些特征可能會(huì)丟失。但是系數(shù)向量的維數(shù)就會(huì)減 少，這對(duì)降維是有利的。有些在依靠系數(shù)矩陣H保持?jǐn)?shù)據(jù)矩陣X中特征的非負(fù)矩 陣分解算法中，系數(shù)矩陣H中保持的原始數(shù)據(jù)

59、中的結(jié)構(gòu)信息就會(huì)變少。所以，在 非負(fù)矩陣分解中，r值的選擇是重要方面。在非負(fù)矩陣分解中，除了上述這些核心的問題外，還有一些需要考慮和完善 的地方，還有更好的解決方法去發(fā)現(xiàn)。1.3本文的主要工作及內(nèi)容安排1.3.1本文主要工作本文參考了大量非負(fù)矩陣分解方面的文獻(xiàn)和資料。學(xué)習(xí)了 NMF分解方法的整 體框架和流程。熟悉非負(fù)矩陣分解的思想。根據(jù)NMF分解理論的知識(shí)，提出了高 維數(shù)據(jù)內(nèi)在結(jié)構(gòu)保持的非負(fù)矩陣分解方法。另外，還提出了一種解非負(fù)矩陣分解 問題的梯度下降方法。具體如下：提出了一種新的非負(fù)矩陣分解的方法，該方法可以將高維空間中的內(nèi)在結(jié)構(gòu) 保持到低維空間中，也就是說，分解后的系數(shù)矩陣能夠保持?jǐn)?shù)據(jù)矩陣

60、的內(nèi)在結(jié)構(gòu)。 這種特性保持的方法，在聚類應(yīng)用中作用尤為突出。因?yàn)闃颖局袑儆谕活惖臄?shù) 據(jù)樣本之間內(nèi)在結(jié)構(gòu)具有一定的聯(lián)系和相似性，而這些特征在低維空間中可以保 持。這樣當(dāng)使用聚類算法在低維空間中進(jìn)行聚類時(shí)，這些特征可以幫助聚類算法 來得到更好的聚類效果。所以這種內(nèi)在結(jié)構(gòu)保持的矩陣分解算法，給聚類應(yīng)用帶 來其他矩陣分解算法無法替代的優(yōu)點(diǎn)。同時(shí)，本文還提出了一種快速的梯度下降方法，由于該方法在每次迭代的時(shí) 候，都會(huì)選取最優(yōu)的下降步長值，所以，這種方法比標(biāo)準(zhǔn)的梯度下降方法（默認(rèn) 的梯度下降步長為1,很多時(shí)候步長為1并不是最優(yōu)步長），收斂速度要快的多， 迭代次數(shù)會(huì)減少，分解矩陣的速度也會(huì)減小。該方法不僅