非負矩陣分解及其在多譜信號處理中的應用

1、廣東工業(yè)大學碩士學位論文（工學碩士）非負矩陣分解及其在多譜信號處理中的應用黃司輝二O一八年六月學校代號：11845分類號：UDC：密級：學 號：2111504071廣東工業(yè)大學碩士學位論文（工學碩士）非負矩陣分解及其在多譜信號處理中的應用黃司輝指導教師姓名、職稱：楊祖元教授學科（專業(yè)）或領域名稱：控制科學與工程學生所屬學院：自動化學院論文答辯日期：2018年6月A Dissertation Submitted to Guangdong University of Technologyfor the Degree of Master(Master of Engineering Science)N

2、on-negative Matrix Factorization and Its Applicationin Multispectrum Signal ProcessingCandidate: Huang SihuiSupervisor: Prof. Yang ZuyuanJune 2018School of AutomationGuangdong University of TechnologyGuangzhou, Guangdong, P. R.China, 510006摘要非負矩陣分解算法自被提出到現(xiàn)在將近20年，正因為其具有可提取部分特征 來感知整體的智能數(shù)據描述的特殊能力，它迅速吸引

3、了大量學者、專家對其進行更 深的研究和分析。事實上，對于非負矩陣分解的研究已經遠遠超出數(shù)學探索，非負 矩陣分解的基礎理論試圖為學習對象部分制定一個可行的模型。這種部分表示整體 的思想正是一種基于部分感知構成整體感知的思想，也可以說是一種“智能”化的 思想。因其諸多優(yōu)點，非負矩陣分解算法越來越多樣化、越來越成熟、應用也越來 越廣泛。本文圍繞非負矩陣分解理論，主要針對基于p散度的非負矩陣分解和一種具有 非線性收斂速率的局部平滑約束非負矩陣分解進行了分析和研究。論文的具體安排 如下：首先介紹了課題研究的意義，國內外研究現(xiàn)狀等，簡要說明本論文組織結構; 然后詳細介紹了非負矩陣分解的基本理論，包括非負矩

4、陣分解模型的數(shù)學表達式、 總結非負矩陣分解的已被發(fā)現(xiàn)的特性、詳細闡述非負矩陣分解的上述類別的算法細 節(jié)和一些結論及該領域尚待解決的問題；接著研究將基于0散度的非負矩陣分解應 用于聚類實驗中以測試其性能；再者，重點設計了一個具有非線性收斂速率的局部 平滑約束非負矩陣分解算法；最后對本文種的研究工作進行總結與展望。本文的重 點內容如下：介紹了一種基于0散度的非負矩陣分解算法，首先介紹了 散度的基本理論； 然后詳細描述了該算法的算法模型及其推導過程，并給出了在兩種不同情況下的算 法更新公式；最后對該算法進行基本聚類仿真實驗和文檔聚類仿真實驗，通過實驗 結果來驗證該算法在文檔聚類實驗中較其它主流的NM

5、F算法和聚類算法具有更優(yōu) 的高效性。設計了一種帶有非線性收斂速率的局部平滑約束非負矩陣分解算法，該方法可 應用在光譜信號處理之中，并可用來解決光譜分解問題。我們首先證明了每個變量 矩陣的成本函數(shù)梯度都具有Lipschitz連續(xù)的特性，并以此構建一個近似函數(shù)來優(yōu)化 成本函數(shù)，因此，我們的方法比傳統(tǒng)方法更加快速的實現(xiàn)非線性收斂速率；然后詳 細描述了該算法的模型及推導過程；最后，仿真實驗結果說明了本章中的算法在解決光譜分解問題時相對與之進行比較的方法的優(yōu)勢。關鍵詞：非負矩陣分解；P散度；文檔聚類；局部平滑約束；多譜信號處理AbstractNon-negative matrix factorizati

6、on algorithm has been proposed for nearly 20 years. Due to its special ability to extract part of the characteristics to perceive the overall intelligent data description, it quickly attracted a large number of scholars and experts to carry out deeper research and analysis. In fact, the research on

7、non-negative matrix factorization has gone far beyond the exploration of mathematics. The basic theory of non-negative matrix factorization attempts to develop a feasible model for the learning object part. This idea, which uses the part to represent the whole, is exactly an idea based on partial pe

8、rception that constitutes the overall perception. This is also a kind of smart” thinking. Due to its many advantages, non-negative matrix factorization algorithms are becoming more and more diverse, more and more mature, and more and more widely used.This paper focuses on non-negative matrix factori

9、zation theory, and mainly analyzes and studies the non-negative matrix factorization based on p divergence and a local smoothness constrained nonnegative matrix factorization with nonlinear convergence rate. The specific arrangement of this paper is as follows: Firstly, this paper introduces the sig

10、nificance of the research on the topic, the research status at home and abroad, and briefly explains the organizational structure of this paper. Secondly, the basic theory of non-negative matrix factorization is introduced in detail, including the mathematical expression of the non-negative matrix f

11、actorization model, summary of the discovered features of the non-negative matrix factorization, the details of the above categories of non-negative matrix factorization and some of the conclusions and unresolved issues in this area. Besides, this paper will study the application of non-negative mat

12、rix factorization with the p-divergence in cluster experiments to test its performance. Furthermore, a local smoothing constrained nonnegative matrix algorithm with nonlinear convergence rate is designed. Finally, the research work of this paper is summarized and prospected. The focus of this paper

13、is as follows:A non-negative matrix factorization algorithm based on p-divergence is introduced. The basic theory of p-divergence is introduced first. Then the algorithm model and its derivation process are described in detail. Finally, a basic clustering simulation experiment and a document cluster

14、ing simulation experiment are performed on the algorithm. The experimental results verify that this algorithm is more efficient than other mainstream NMF algorithms and clustering algorithms in document clustering experiments.A local smoothness constrained nonnegative matrix factorization with nonli

15、near convergence rate for spectral decomposition is designed. This method can be used in spectral signal processing and can be used to solve the spectral decompose problem. Firstly, we prove that the gradient of the cost function of each variable matrix has Lipschitz continuity characteristics, then

16、 we construct an approximate function to optimize the cost function. Therefore, our method can implement a faster nonlinear convergence rate than the traditional method. Secondly, the algorithm model and the derivation process of this algorithm are described in detail. Finally, the simulation experi

17、ment results demonstrate the advantages of the algorithm in this chapter in solving the spectral decompose method.Keywords: Nonnegative Matrix Factorization; p-Divergence; Document Clustering; Local Smoothness Constrained; Multi spectrum Signal Processing目錄 TOC o 1-5 h z HYPERLINK l bookmark13 o Cur

18、rent Document 摘要I HYPERLINK l bookmark16 o Current Document AbstractIll HYPERLINK l bookmark19 o Current Document 目錄V HYPERLINK l bookmark29 o Current Document ContentsVll HYPERLINK l bookmark76 o Current Document 第一章緒論1 HYPERLINK l bookmark79 o Current Document 研究背景及意義1 HYPERLINK l bookmark82 o Cur

19、rent Document 1.2國內外研究現(xiàn)狀3 HYPERLINK l bookmark85 o Current Document 1.3課題的研究內容和主要貢獻5 HYPERLINK l bookmark90 o Current Document 1.4本文組織結構5 HYPERLINK l bookmark93 o Current Document 第二章非負矩陣分解基礎理論6 HYPERLINK l bookmark96 o Current Document 2.1引言6 HYPERLINK l bookmark102 o Current Document 2.2非負矩陣分解的概念和

20、性質7 HYPERLINK l bookmark105 o Current Document 2.3基本非負矩陣分解算法9 HYPERLINK l bookmark108 o Current Document 2.3.1目標函數(shù)10 HYPERLINK l bookmark111 o Current Document 2.3.2基本非負矩陣分解優(yōu)化框架10 HYPERLINK l bookmark114 o Current Document 2.3.3經典算法11 HYPERLINK l bookmark117 o Current Document 2.4改進的非負矩陣分解算法12 HYPER

21、LINK l bookmark120 o Current Document 2.4.1帶約束的非負矩陣分解算法12 HYPERLINK l bookmark123 o Current Document 2.4.2結構化的非負矩陣分解算法14 HYPERLINK l bookmark126 o Current Document 2.5非負矩陣分解算法擴展16 HYPERLINK l bookmark129 o Current Document 2.5.1半非負矩陣數(shù)據類型16 HYPERLINK l bookmark132 o Current Document 2.5.2高維數(shù)據類型17 HYP

22、ERLINK l bookmark135 o Current Document 2.5.3非線性非負矩陣分解模型18 HYPERLINK l bookmark138 o Current Document 2.6本章小結19 HYPERLINK l bookmark144 o Current Document 第三章 基于0散度的非負矩陣分解算法20 HYPERLINK l bookmark147 o Current Document 3.1引言20 HYPERLINK l bookmark51 o Current Document p散度基本理論21 HYPERLINK l bookmark5

23、4 o Current Document 散度21 HYPERLINK l bookmark150 o Current Document 3.2.2基于0散度的非負矩陣分解21 HYPERLINK l bookmark153 o Current Document 3.3算法描述22 HYPERLINK l bookmark156 o Current Document P-NMF 優(yōu)化22 HYPERLINK l bookmark160 o Current Document p-NMF的自主相關決策算法模型23 HYPERLINK l bookmark171 o Current Document

24、 ARD P-NM 算法25 HYPERLINK l bookmark177 o Current Document 3.4實驗仿真28 HYPERLINK l bookmark180 o Current Document 3.4.1基本聚類實驗28 HYPERLINK l bookmark192 o Current Document 3.4.2文檔聚類實驗32 HYPERLINK l bookmark195 o Current Document 3.5本章小結36 HYPERLINK l bookmark198 o Current Document 第四章局部平滑約束非負矩陣算法及其在多譜信號

25、處理中的應用38 HYPERLINK l bookmark202 o Current Document 4.1引言38 HYPERLINK l bookmark205 o Current Document NMF-NCR 算法39 HYPERLINK l bookmark208 o Current Document 4.2.1算法模型39 HYPERLINK l bookmark214 o Current Document 4.2.2算法推導41 HYPERLINK l bookmark217 o Current Document 4.3實驗仿真43 HYPERLINK l bookmark2

26、20 o Current Document 4.3.1計算機產生的數(shù)據集43 HYPERLINK l bookmark223 o Current Document 4.3.2多光譜圖像數(shù)據集44 HYPERLINK l bookmark226 o Current Document 4.4本章小結46 HYPERLINK l bookmark229 o Current Document 總結與展望49 HYPERLINK l bookmark232 o Current Document 總結49 HYPERLINK l bookmark238 o Current Document 后續(xù)研究計劃5

27、0 HYPERLINK l bookmark244 o Current Document 參考文獻51 HYPERLINK l bookmark314 o Current Document 攻讀學位期間發(fā)表的論文58 HYPERLINK l bookmark320 o Current Document 學位論文獨創(chuàng)性聲明59 HYPERLINK l bookmark323 o Current Document 學位論文版權使用授權聲明59 HYPERLINK l bookmark326 o Current Document 致謝60ContentsContents TOC o 1-5 h z

28、Abstract(in Chinese)IAbstract(in English) IllContents(in Chinese) VContents(in English) VHChapter 1 Introduction1Research background1Researching status in domestic andoverseas3The content and contribution5The structure and plan5Chapter 2 Fundamental theory of nonnegative matrix factorization6Introdu

29、ction6Concept and properties of NMF7Basic NMF algorithms9Objective functions10Classic Basic NMF optimization frameword10Paragon algorithms11Improved NMF algorithms 12Constrained NMF algorithms12Structured NMF algorithms14Generalized NMF algorithms16Semi-NMF data types16High dimensional data types17N

30、onlinear NMF model18Summary19Chapter 3 Nonnegative matrix factorization with the p-divergence20Introducti on20 TOC o 1-5 h z Fundamental theory of p-divergence21p-divergence21NMF with p-divergence21Algorithm description22Majorization for p-divergence22Model for automatic relevance determinationinp-d

31、ivergence.23ARD p-divergence algorithm25Experiments28Basic clustering experiments28Document clustering experiments32Summary36Chapter 4 Local smoothness constrained nonnegativematrixfactorization and HYPERLINK l bookmark10 o Current Document its application in multispectrum signalprocessing38Introduc

32、tion38NMF-NCR algorithm39Models39Derivation ofalgorithm41Simulations43Computer-generated data43Multispectrumimage data set44Summary46Conclusion and Prospects49Conclusion49Follow-up study plan50References51Achievements Researched During the Study for Master Degree58Originality Statement59Promethean D

33、eclaration59Acknowledgments60第一章緒論1.1研究背景及意義隨著科學技術的不斷創(chuàng)新與高速發(fā)展，人類社會巳經快速步入了數(shù)字世界，迎 來了大數(shù)據時代。人們在日常生活中的各種行為會產生非常龐大而復雜的數(shù)據，而 這些超大數(shù)據集對于各行各業(yè)的運營有著極大的作用，例如在商業(yè)方面，人們可以 通過已有的消費者網上消費、瀏覽記錄等行為產生的數(shù)據來估計產品的銷售量、預 判產品銷售走勢并及時調整適度的倉庫存儲量以避免缺貨或積貨等情況。在社會建 設方面，大數(shù)據的應用更是引領了一大批新型“智慧”行業(yè)（如智慧交通、智慧城 市等）的興起，極大的方便了人們的日常生活。數(shù)據處理也是人工智能的核心問題

34、 之一，其在軍事上、財經上、科技上占據的重要地位使得這些高新科學技術都直接 影響、代表著一個國家的綜合國力，自然而然也是各國之間相互競爭的重要方面。 隨著大數(shù)據越來越受到人類的重視與關注，如何對龐大而復雜的數(shù)據進行有效地提 取、準確地分析、處理等問題也逐漸成為很多數(shù)據工作者的工作重點。處理數(shù)據的工作主要通過計算機來完成，而在計算機中大多數(shù)的數(shù)據都是以矩 陣的形式來儲存的，比如一個表格中的數(shù)據就可以寫成一個矩陣數(shù)據，數(shù)字圖像數(shù) 據也可以用矩陣來表示。圖1-1是灰度圖像對應矩陣元素示意圖，在數(shù)字圖像中所 有像素組合起來就類似于一個單位為像素的矩陣，圖像的高度即為矩陣的行數(shù)，圖 像的寬度則為矩陣的列

35、數(shù)，圖像的每一個像素的灰度值就轉化為矩陣中的對應元素 值。圖片越清晰、包含的內容越多，則所轉變成的矩陣維數(shù)越高、數(shù)據量越大。如 果不對這些數(shù)據進行簡化便直接處理或應用這些數(shù)據，即便處理工具是強大的計算 機，也會大大降低其工作效率，且處理結果也可能不盡人意。因此，對這些數(shù)據進 行適當?shù)慕稻S處理是處理這些矩陣數(shù)據的有效方法，而矩陣分解便是能達到這一目 的的有效工具。通過對矩陣數(shù)據進行矩陣分解處理，可以大大降低其維數(shù)，并提取 出有效信息數(shù)據，去掉冗余無效信息數(shù)據，以此達到降維、概括數(shù)據信息、提高工 作效率、節(jié)省計算和存儲空間的目的。N列數(shù)字圖像(MXN)M行V0,0V0,lVl,oVl,l 1:,

36、. :圖像矩陣(MXN)圖1-1灰度圖像對應矩陣元素示意圖Fig.1-1 Grayscale image corresponding matrix element diagram正是因為矩陣分解在處理大型數(shù)據上的明顯優(yōu)勢，使其廣泛地應用于文本聚 類、圖像處理、信號處理、機器視覺等諸多領域。目前，矩陣分解算法主要包括主 成分分析法(Principal component analysis, PCA) C1,獨立分量分析法(Independent component analysis, ICA)、奇異值分解法(Singular value decomposition, SVD)、 矢量量化法(Ve

37、ctor quantization, VQ)等。上述矩陣分解方法的基本原理是將原始 的矩陣近似分解為兩個或多個低秩矩陣的乘積，通過分解后得到的矩陣中的元素有 正有負。從數(shù)學理論的角度來看，這樣的分解結果是正確的，然而在實際應用中， 比如在文本、圖像等信息中，負值元素沒有物理意義、不具有可解釋性。為了解決 這個問題，學術工作者紛紛將研究重心移至非負矩陣分解上來。1999年Lee和Seung 在Nature雜志發(fā)表了文章，正式提出了非負矩陣分解方法(Non-negative factorization, NMF) 3,給出了兩種目標函數(shù)和更新公式，并證明了其收斂性。該 方法的提出立即引起了廣泛的關

38、注。非負矩陣分解旨在將一個非負矩陣V表示成兩個低秩非負矩陣W和H的乘積， 即V WH o NMF解決了傳統(tǒng)矩陣分解方法中結果存在負值元素的問題，并獲取了 原始數(shù)據的潛在特征。通常我們認為H矩陣為系數(shù)矩陣，W矩陣為特征矩陣，W矩 陣的列向量與H矩陣對應的加權系數(shù)相乘后再相加獲得的加權和即可表示出V矩 陣中的對應的一個列向量。這正是一種通過局部來感知整體的思想，這一思想可以 被廣泛應用于許多實際問題中，比如分析期貨價格走勢、數(shù)據挖掘、文本聚類等。 此外，NMF非負性約束使其具有一定程度上的稀疏性，即在分解矩陣W和H中會 出現(xiàn)多個0元素，不僅達到了降維效果，還大大節(jié)省了計算機存儲空間，獲得了更 優(yōu)的

39、分解效果?；贜MF的這些特性和優(yōu)點，NMF已經被廣泛應用于語音處理、 數(shù)據挖掘、模式識別、圖像處理、生物醫(yī)學等眾多領域，對NMF的進一步研究極 具實際意義。1.2國內外研究現(xiàn)狀在明顯的混亂和復雜情況下，必須有一些簡單、緊湊、優(yōu)雅的基本角色，這一 基本概念一直深深根植于科學工作者的內心。對于信號處理、數(shù)據分析、數(shù)據挖掘、 模式識別和機器學習等領域，也是如此。在這個傳感器和計算機技術飛速發(fā)展的時 代，各行各業(yè)產生的原始數(shù)據量驟增，怎樣通過降維技術快速處理大型數(shù)據并獲得 有效特征是當今世界備受關注的問題，也是極具挑戰(zhàn)性的問題。一般來說，應該滿 足兩個基本屬性：第一，減少原始數(shù)據的維度；其次，數(shù)據的

40、主要組成部分、隱藏 概念、突出特征或潛在變量等應該被有效識別。原始數(shù)據集一般以矩陣或張量的形式存儲于計算機之中。原始數(shù)據集越大，則 其存儲的矩陣數(shù)據或張量數(shù)據則越大。因此使用降維技術將大型原始數(shù)據矩陣適當 降維成兩個因子矩陣的方法在數(shù)據處理領域一直處于優(yōu)勢地位。諸如主成分分析 (PCA)、線性判別分析(Linear discriminant analysis, LDA)、獨立分量分析(ICA)、 矢量量化(VQ)等典型方法正是這種低秩近似的例子。它們在統(tǒng)計屬性上彼此不同， 歸因于對組件矩陣及其基礎結構施加的不同約束；然而，他們有一個共同點，就是 分解矩陣中元素的符號沒有限制。換句話說，在表示中

41、允許負分量或減法組合。相 比之下，一個新的因式分解范式-非負矩陣分解(NMF),包含非負性約束，從 而獲得基于部分的表示并相應地提高問題的可解釋性。事實上，NMF首先由Paatero和Tapper引入，作為正矩陣分解(Positive Matrix Factorization)的概念，其中重點介紹了拜占庭算法的具體應用。Lee和Seung對正 矩陣分解算法進行了更深入的理論研究分析，解決了其收斂性等問題叫并成功的 將NMF推廣到了圖像處理等更廣闊的領域中，因為他們貢獻了一個簡單而有效的 算法程序，更重要的是強調了其基于部分表示的潛在價值。遠遠超出數(shù)學探索，NMF的基礎理論試圖為學習部分對象制定

42、一個可行的模 型，這種思想直接影響到感知機制的建立。這種部分表示整體的思想作為絕大多數(shù) 識別問題算法理論的核心理論之一是具有理論依據的-基于部分的感知構成整體 的感知氣一方面，在許多現(xiàn)實世界的數(shù)據中，如圖像、光譜和基因數(shù)據以及分析 任務、觀察和潛在成分的負值在物理上沒有意義。而原始模型大多數(shù)情況下都具有 其對應的部分特征，可以用來對其進行語義解釋。例如在人臉識別應用中，計算機 對于基礎人臉圖像的學習均是基于臉頰、嘴巴、鼻子、眼睛等這些部分特征的氣 而不是對于一張完整的人臉的整體學習。另一方面，感興趣的物體最自然的特點是其部分的庫存，而專有的加性組合意 味著它們可以通過將所需的部分一起添加到類似

43、于識別器的零件中來重新組裝。正 因如此，非負矩陣分解被成功地應用于各個領域中。例如在文檔聚類中，非負矩陣 分解有效地提高了聚類精度，同時還提高了識別文檔中的潛在語義的強度。由于非負矩陣分解本身具備非負性，故決定了它必定會導致其稀疏性。事實 上，稀疏性使得非負矩陣分解的結果能夠更加具體的展現(xiàn)出原數(shù)據的特征，語義解 釋能力有所提升，是一種更有效的表示形式。此外，非負矩陣分解也是一個由隱 藏變量產生可見變量的過程，基于部分的表示便可從加性模型中獲得，因此非負矩 陣分解也是神經網絡領域采用的核心學習算法。正數(shù)表示存在，零值表示沒有某個 事件或組件。這很好地符合神經活動的二元性質神經生理學突觸強度：無興

44、奮或抑 制則不改變符號。正因為非負矩陣分解上述的優(yōu)點，使其成為眾多領域中大型數(shù)據分析和處理的 重要工具，例如：化學計量學光譜分析、數(shù)學、數(shù)據信息處理皿、優(yōu)化、神經 網絡、機器學習吐計算機視覺皿、生物信息學地球物理學購和財經等。更具 體地說，這些應用包括語音識別、盲源信號分離質、文本數(shù)據挖掘面部幻覺、 人臉識別偵、圖像去噪、圖像分割的、圖像分類、光譜學“基因表達分類物、 EEG信號處理響、電子郵件監(jiān)測如、在線討論參與預測、網絡安全、自動個性化摘 要、大氣中化合物識別偵、地震預測、股市定價或等等。自被提出和被推廣以來，NMF的研究成果眾多。來自各個領域的研究人員、數(shù) 學家、統(tǒng)計學家、計算機科學家、

45、生物學家和神經科學家從不同的角度探索了 NMF 概念。NMF理論到現(xiàn)在巳經有了長足的發(fā)展，但仍然是一項正在進行的工作。具 體來說：1)NMF本身的性能已經被深入探索；而像傳統(tǒng)分解方法PCA或LDA那 樣的堅實統(tǒng)計基礎尚未得到充分發(fā)展(部分原因是因為它的可靠性)。2)已經解決 了像25中提到的那些問題，特別是那些有附加約束的問題，盡管如此，還是有很 多其他問題尚未得到解決。1.3課題的研究內容和主要貢獻本文圍繞非負矩陣理論，主要針對基于p散度的非負矩陣分解和一種具有非線 性收斂速率的局部平滑約束非負矩陣分解進行了分析和研究。主要貢獻如下：將基于3散度的非負矩陣分解應用于聚類實驗中并取得較好的實驗

46、結果。設計了一個具有非線性收斂速率的局部平滑約束非負矩陣算法。1.4本文組織結構本文各章內容安排如下：第一章緒論，主要內容包括本課題研究的意義、國內外研究現(xiàn)狀，最后簡要說 明本論文的研究內容和論文結構。第二章主要內容是根據非負矩陣分解的設計原理、特性、問題、關系及其演化 對這些算法進行了全面的介紹和分析，首先總結了非負矩陣分解算法的基礎模型及 其已被挖掘出的特性；然后詳細闡述了上述類別的非負矩陣分解算法細節(jié)；最后得 出結論，并討論一些尚待解決的問題。第三章介紹了一種基于&散度的非負矩陣分解算法，首先介紹了 散度的基本 理論；然后詳細描述了該算法的算法模型及其推導過程；最后對該算法進行基本聚 類

47、仿真實驗和文檔聚類仿真實驗，通過實驗結果來驗證該算法的性能。第四章設計了一個具有非線性收斂速率的局部平滑約束非負矩陣算法。首先介 紹了該算法的算法模型；然后詳細闡述了該算法的推導過程；最后通過實驗仿真來 驗證該算法的性能及優(yōu)勢。第五章是總結和展望，主要總結了本文的主要內容以及所做的工作和研究成 果，并對后續(xù)的研究工作進行了展望和新的規(guī)劃。第二章非負矩陣分解基礎理論2.1引言非負矩陣分解是一種相對新穎的降維方式，自被提出以來一直處于該領域的優(yōu) 勢地位。它包含了非負性約束，通過非負性可以讓分解出的結果獲得可以表示部分 的能力。這在實際應用中是極為有用的。本章內容主要包括非負矩陣分解算法近幾 年來的

48、理論研究，系統(tǒng)地總結了非負矩陣分解的原理、基本模型、性質、算法及其 各種改進和擴展。根據一些統(tǒng)一的標準，現(xiàn)有的非負矩陣分解算法可被分為三大類：1、基本非負矩陣分解(Basic NMF,BNMF)?；痉秦摼仃嚪纸馐亲钤嫉?非負矩陣分解模型，只包含一些非負性約束，是所有非負矩陣分解的基礎，現(xiàn)今己 有的非負矩陣分解都是基于基本非負矩陣分解而構建起來的。2、改進的非負矩陣分解(Improved NMF, INMF)。改進的非負矩陣分解囊括 了絕大多數(shù)非負矩陣分解算法的變體，主要包括約束非負矩陣分解和結構化非負矩 陣分解。其中，約束非負矩陣分解是在基本非負矩陣分解的模型中加入了一些正則 化的約束條件

49、，可獲得一些具有特殊意義的解。3、非負矩陣分解算法擴展。非負矩陣分解算法擴展主要是在非負矩陣分解的 數(shù)據類型上有了質的飛躍，將非負矩陣分解理論推向了更加廣泛的應用領域中。其中每一類非負矩陣分解的具體分類如圖2-1所示。本章的內容組織如下：首先，介紹了非負矩陣分解模型的數(shù)學表達式，總結了 非負矩陣分解的已被發(fā)現(xiàn)的特性；然后詳細闡述非負矩陣分解的上述類別的算法細 節(jié)；最后，得出結論，并討論一些尚待解決的問題。非負矩陣分解（NMF）改進的非負矩陣分解基本非負矩陣分解非負矩陣分解算法擴展VVVV圖2-1非負矩陣分解模型和算法分類Fig.2-1 Non-negative matrix factoriza

50、tion model and algorithm classification2.2非負矩陣分解的概念和性質定義：給定一個M維隨機向量V ,該向量中的元素全為非負數(shù)。若有N個觀察數(shù)據， 則記為*j=l,2,.,N 數(shù)據矩陣匕/=麟,山爭弋川。非負矩陣分解力求將V 分解為非負的MxL維的基矩陣與非負的LxN維的系數(shù) 矩陣Hjj=hl,h2,.,hNIRN ,因此有VWH,其中IR”代表MxN維非負數(shù)據 集很顯然，外是W的列向量觀察值.的權重系數(shù)，基本向量或V的潛在特征向量。 因此，非負矩陣分解將每個數(shù)據分解為基本向量的線性組合。由于LM, LN, 所以從非負矩陣分解模型中學到的基數(shù)據集是不完整的

51、，如果NMF得到的W中包 含原始數(shù)據的特征，這樣的分解結果既達到了降維的目的，又可以適用于很多的應 用場景，可進行廣泛推廣。要完成基本的矩陣分解，首先就要注意以下這三個方面。第一點，要注意這個 非負矩陣分解是否有解，或者是否會出現(xiàn)特殊解。這個問題已在文獻27中得到了 證明，使用的是完全正分解理論。第二點，要注意已存在的解是否是唯一的，或者 說在某些特定的條件下可保證其唯一性。第三點，要注意及時檢測非負矩陣分解的 結果，了解該結果能否有效重構出原始矩陣。這兩點最早在文獻28中有被提到。一般平凡解是以W = V和11 =九的形式存在。通過將NMF與典范Polyadic(Canonical Poly

52、adic, CP)分解相關聯(lián)，Vasiloglou等人表明每個非負矩陣都有一個 非平凡的完全NMF2TO如果非負矩陣V 能以v = ww，W w 釁l的形式來 分解，則它是CP的，故CP因式分解是一種特殊情況。最小乙被稱為V的CP-秩。 當CP矩陣集合形成一個凸錐體并且NMF的解屬于一個CP錐體時，求解NMF就 是一個凸優(yōu)化問題。然而，對CP錐的實際描述仍然是開放的，且盡管在27中 提出了使用凸松弛來降級的理論上的優(yōu)點，但仍然很難將NMF表示為凸優(yōu)化問題。使用雙線性模型，完全NMF可以被重寫為單秩的非負矩陣的線性組合： TOC o 1-5 h z LLV =(2.1)r=lr=lW.j是W的第

53、，個列向量，Hj.是H的第，行向量，。表示兩個向量的外積。使該分解 可能存在的最小乙稱為非負矩陣V的非負秩，記為rank+ (V) o它滿足以下條件或：rank(V) rank*(V) min(M, N)(2.2)當V的維數(shù)和分解秩增加時，實際上這是一個NP困難問題(Non-deterministic polynomial-hard, NP-hard) , Vavasis的證明了其與NP-hard中間單一形問題相關聯(lián)。 這也是CP設計的必然結果，因為CP錐雖然具有凸性，但不能用多項式時間來描述。 在sv) = l的特例中，完全NMF可以用多項式時間求解。然而，固定分解秩的 完整NMF的復雜性一

54、般還不清楚另一個相關的工作是所謂的非負秩分解，其重點在于rank(V)= q相(V)的情 況，即選擇rang作為最小/河。這并不總是可能的，只有具有相應單純錐的非負 矩陣存在非負秩分解。在大多數(shù)情況下，NMF的近似結果V WH被廣泛使用，而不是完整的因式分 解。另一種生成模式是：V = WH+E(2.3)其中E e IRMxN是表示近似誤差的噪聲矩陣。NMF的這兩種模式本質上是相互耦合的，盡管學術界對后者的關注更多。完整 NMF的理論結果將有助于設計更高效的NMF算法險卸。如果獲得更緊密的非負等 級的界限，NMF的分解等級L的選擇可能更可信物。從本質上講，NMF是一個非單純解決方案的不適定問題

55、28 3,o從幾何學上講， NMF是一個找尋出包含所有非負數(shù)據點的單純錐的問題。從代數(shù)的角度來看，如果 存在解V就珥H。，令WaWD、HD *H0,則VWHO對因子矩陣添加約束或 對W的列(或H的行)標準化，有利于減少NMF在實際應用中不確定性。此外，當使用歐幾里得距離的平方(Squared of Euclidean distance, SED) 時， NMF相當于K-means聚類，這就等同于當使用廣義Kullback-Leibler (KL)散度作 為目標函數(shù)肉時的概率潛在語義分析。到目前為止，可以得出結論：NMF的優(yōu)點包括基于部分的可解釋性和稀疏性， 得到更復雜的價值信息。而SVD或PC

56、A的頻譜總是比NMF更緊湊。你無法擁有 兩全其美的世界。2.3基本非負矩陣分解算法本節(jié)將首先總結基本非負矩陣分解算法的目標函數(shù)，然后介紹基本NMF框架 和經典算法的細節(jié)。2.3.1目標函數(shù)首先定義D(V|WH)為NMF優(yōu)化模型的目標函數(shù)，即代價函數(shù)。最常用的目標 函數(shù)是SED (即Frobenius范數(shù)，如式(2.4)和廣義KL散度(Generalized kullback-leibler divergence, GKLD,如式(2.5) ) 1,1 : TOC o 1-5 h z 2(V|WH)*V WL(Hf)(3.6)同時，對于所有的H*均滿足：G(HjHr)=L(Hf)(3.7)其中非

57、負矩陣H,是H-迭代一次后更新的值，是迭代次數(shù)。假如存在這樣的輔助 函數(shù)，那么想要對HH)實現(xiàn)由修正珥的優(yōu)化會變得很簡單，優(yōu)化后將由 G(H,|H_J代替 L(H)O顯然，對任意一個滿足G(HHm)G(HHm)的H,值，都有：乙(H,) 0如果Hr=H ,不等式(3.8)能取到等號，從而獲得一個局部最小值。由于目標函 數(shù)可以看作是一個凸項與凹項的和，并且可以分別對這兩項進行詹森不等式和一階 泰勒近似處理51 52o定義V,)=wh,則其凸項與凹項分別為：Pm 三就2(3.10)tnq 三，v v_1(3.11)-i-rn 匕mr mn /m然后分別對其凸項與凹項進行上述處理，即得其簡單的更新規(guī)

58、則，為：hm=hn-(3.12)其中：1/(2),p,/(“)= 1,1/30,都有 HN（|JI）= fexpf-；而 x0 時，則 HN（xR）=O。7rk J 2k /如果X是一個高斯（正）隨機變量，則國是半正定的。當W和H滿足指數(shù)先驗時則 有：P（七 k） = Eg*.）p） = E（么 k.）（3.15）對于所有的xNO,都有E（x|#）全：exp-j）；而x0時，貝任（琲）=0。當如很小時， 與之對應的W的列及H的行將不相關，反之亦然。當一行與一列不相關時，他們的 基準將接近零，則該值可以從分解中去除，而不會對數(shù)據保真度造成太大影響。這 種將對應的行和列移除的操作使得模型更加簡潔。

59、最后，我們對每個相關權重參數(shù)&.處以反伽馬先驗，艮bap (kra,b) = 3 (kr a, /?) =F(a+,)(b exp、k , r 7(3.16)其中。是非負形狀超參數(shù)，人是非負標量超參數(shù)。和人對于任何一個幻值都是一個 恒量，且都是相互獨立的。目標函數(shù)Cichocki等人在文獻12 53中說明了 T分布與P散度之間的聯(lián)系。T分布是 一種特殊的指數(shù)分布模型，是自然指數(shù)模型的擴展形式，T分布比自然指數(shù)模型更 為人熟知。它的特征在于其均值和方差之間的簡單多項式關系，艮var x = cd82p（3.17）其中s=IEx是其平均值，月是形狀參數(shù)，。是離散參數(shù)。T分布只在小,/3 = hx,

60、在 L2-ARD P-NMF 算法中，/? 2 ,0 ,函數(shù)g、,(。= Z(-1)在l u IR單調非減，在v=l時單調上升。如果令Lemma 1中的v= hrJhrn,則有：21(hp 一-1 -1h i-n 7h i-n /2丫(3.23)對上式進行適當變形，可得:h2 h22k k Prr*+ cst(3.24)由此可以構建輔助函數(shù)j(h|h),即:(h|h)=1g(h|h)+?(3.25)然后令j(h|h)對入,“的偏導數(shù)等于零，并求解，便可得到更新公式:hn. =hrn(3.26)、S)頂”+(/幻)&皿 下面是L2-ARD P-NMF算法卸的具體過程。Input：矩陣V,超參數(shù)a