非負矩陣分解模型選擇及其在生物數(shù)據(jù)挖掘中的應(yīng)用

1、分類號密級UDC編號碩士學(xué)位論文非負矩陣分解模型選擇及其在生物數(shù)據(jù)挖掘中的應(yīng)用學(xué)位申請人姓名：鄭佳申請學(xué)位學(xué)生類別：會國制碩士申請學(xué)位學(xué)科專業(yè)：計算機建用技術(shù)指導(dǎo)教師姓名：薦興鵬教授碩士學(xué)位論文非負矩陣分解模型選擇及其在生物數(shù)據(jù)挖掘中的應(yīng)用論文fMh鄭佳指導(dǎo)教師：蔣興鵬教授學(xué)科專業(yè)：計ma應(yīng)用技術(shù)研究方向：生物信息學(xué)華中學(xué)院2018年5月Model Selection ofNon-negative MatrixFactorization and Its Applicationin Biological Data MiningA ThesisSubmitted in Partial Fulfil

2、lment of the RequirementFor the M.S Degree in Computer Application TechnologyByJia ZhengPostgraduate ProgramSchool of ComputerCentral China Normal UniversitySupervisor： Xingpeng JiangAcademic Title： ProfessorSimatuK瘁 3ApprovedMay, 2018華物菟大學(xué)料敝期性聲盼使賤屬說明- 原創(chuàng)性聲明本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下，獨立進行研究工作 所取得的研究成

3、果。除文中已經(jīng)標明引用的內(nèi)容外，本論文不包含任何其他個人或 集體已經(jīng)發(fā)表或撰寫過的研究成果。對本文的研究做出貢獻的個人和集體，均已在 文中以明確方式標明。本聲明的法律結(jié)果由本人承擔(dān)。作者簽名：科勺專日期：年5月28日學(xué)枚論丈版權(quán)使用授權(quán)書學(xué)位論文作者完全了解華中師范大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：研 究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬華中師范大學(xué)。學(xué)校有權(quán)保留并 向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許學(xué)位論文被查閱和借閱; 學(xué)校可以公布學(xué)位論文的全部或部分內(nèi)容，可以允許采用影印、縮印或其它復(fù)制手 段保存、匯編學(xué)位論文。（保密的學(xué)位論文在解密后遵守此規(guī)定） 保密論文注

4、釋：本學(xué)位論文屬于保密，在_年解密后適用本授權(quán)書。 非保密論文注釋：本學(xué)位論文不屬于保密范圍，適用本授權(quán)書。作者簽名：&色導(dǎo)師簽名：的剖畛日期：W年亍月汕日日期：勿似年了月/日本人己經(jīng)認真閱讀CALIS高校學(xué)位論文全文數(shù)據(jù)庫發(fā)布章程”，同意將本人的 學(xué)位論文提交“CALIS高校學(xué)位論文全文數(shù)據(jù)庫中全文發(fā)布，并可按“章程中 的規(guī)定享受相關(guān)權(quán)益。同意論文提交后滯后：口半年；口一年：口二年發(fā)布。作者簽名：理*導(dǎo)師簽名:物務(wù)必日期：年偵月日日期：2。成年偵月7/日摘要機器學(xué)習(xí)中很多重要方法都離不開模型選擇。模型選擇在數(shù)據(jù)聚類、復(fù)雜網(wǎng)絡(luò) 社團發(fā)現(xiàn)及數(shù)據(jù)降維等方面應(yīng)用廣泛。如何準確地進行模型選擇，從而選擇

5、出合理 的目標維度，進而引導(dǎo)出具有可解釋性的分析方案，挖掘出隱含在數(shù)據(jù)中的潛在信 息是機器學(xué)習(xí)中模型選擇所面臨的一個挑戰(zhàn)。矩陣低秩分解是目前應(yīng)用廣泛的數(shù)據(jù)降維和數(shù)據(jù)表示方法，其中非負矩陣分解 是最具有代表性的矩陣低秩分解方法。非負矩陣分解(Nonnegative Matrix Factorization, NMF)作為一種矩陣的低秩逼近方法，它分解的矩陣和最終得到的 結(jié)果矩陣的數(shù)值都是非負的。非負矩陣分解能將高維數(shù)據(jù)降至低維，一個合理的維 度能引導(dǎo)更為理想的分解，使得分解之后的低維矩陣能最大限度的保留原始數(shù)據(jù)的 特性。圍繞非負矩陣分解的維度選擇即模型選擇問題，本文做了以下研究工作：第一、提出基

6、于同趨性的模型選擇方法(Tendency Drive Nonnegative Matrix Factorization,TDNMF)o不同于其他在分解過程中進行模型選擇的方法，該方法從 數(shù)據(jù)分解前后的結(jié)構(gòu)保持情況出發(fā)，基于數(shù)據(jù)點之間的相關(guān)性關(guān)系，提出樣本同趨 性概念，并采用重采樣的方法解決了在樣本容量不一致的情況下比較樣本相關(guān)性的 問題。得益于這兩種數(shù)據(jù)處理技巧，基于同趨性的模型選擇方法(TDNMF)具有 較小的時間復(fù)雜度。第二、提出基于信息均衡的模型選擇方法(Entropy Balanced Nonnegative Matrix Factorization,EBNMF),該方法結(jié)合了非負矩陣

7、的可伸縮分解特性以及高效穩(wěn)定的 維數(shù)選擇標準，在多個模擬數(shù)據(jù)上體現(xiàn)了良好的性能。在此基礎(chǔ)上，本文進一步地 在真實生物數(shù)據(jù)集包括果蠅基因表達數(shù)據(jù)和人類微生物組數(shù)據(jù)集上對提出的方法 進行了驗證，表明了 EBNMF方法的穩(wěn)定性和可解釋性。EBNMF能在信息分解過 程中進行很好的模型選擇，并能有效提取具有噪聲的生物數(shù)據(jù)的有效特征。非負矩陣分解模型符合整體是由局部組成這一客觀規(guī)律而被廣泛應(yīng)用于多個 領(lǐng)域，但其模型選擇仍然是一個難題。本文提出了兩種非負矩陣分解的模型選擇方 法，分別在計算復(fù)雜度和準確性上具有一定的優(yōu)勢，可適用于不同級別的數(shù)據(jù)集。關(guān)鍵詞：非負矩陣分解；生物信息學(xué)；數(shù)據(jù)挖掘；模型選擇；無監(jiān)督學(xué)

8、習(xí)AbstractModel selection is one of the steps in many important methods of .machine learning Model selection is widely used in methods such as data clustering, complex networic community discovery, and data dimensionality reduction. How to accurately select models, so as to select a reasonable target

9、 dimension, and then guide the interpretable analysis program, and tap the hidden information hidden in the date is a challenge fbr the choice of machine learning model.Matrix low-rank decomposition is a widely used data dimension reduction and data representation method. Non-negative matrix factori

10、zation is the most representative low-rank matrix decomposition method. Non-negative matrix factorization (NMF) is a low-rank approximation method for matrices. The values of its decomposition matrix and decomposition result matrix are both non-negative. Non-negative matrix factorization can reduce

11、high-dimensional data to low dimensions. A reasonable dimension can lead to more ideal decomposition, so that the decomposed low-dimensional matrix can retain the characteristics of the original data as much as possible. Focusing on the dimension selection of non-negative matrix factorization, that

12、is, model selection, this paper has done the following research work:First, a model selection method Tendency Drive Nonnegative Matrix Factorization (TDNMF) was proposed. Different from other methods of model selection in the decomposition process, this method starts from the structure preservation

13、before and after the data decomposition. Based on the correlation relationship between data points, the concept of sample homomorphism is proposed, and the method of resampling is used to solve the problem. The sample correlation is compared when the sample sizes are inconsistent Thanks to these two

14、 data processing techniques, the TNDMF based on the same tropism has a smaller time complexity.Second, an infbnnation*-equalized dimension selection method, Entropy Balanced Nonnegative Matrix Factorization (EBNMF) is proposed. This method combines the scalable decomposition properties of nonnegativ

15、e matrices with the unsupervised learning method of efficient and stable dimension selection criteria. The method demonstrated good performance. Further, the proposed method was validated on real biological data sets including Drosophila gene expression data and human microbiome data sets, demonstra

16、ting the stability and interpretability of the EBNMF method. EBNMF can make good model selection in the process of information decomposition, and can effectively extract the effective features of biological data with noise.The non-negative matrix factorization model is widely used in many fields bec

17、ause the overall conformity is formed by local objective laws. However, the model selection is still a difficult problem. This paper presents two non-negative matrix factorization model selection methods, which have certain advantages in computational complexity and accuracy, and can be applied to d

18、ifferent levels of data sets.Key word： Non-negative matrix factorization; Bioinfbrmatics; Data mining; Model selection; Unsupervised learningin目錄 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 摘要1AbstractH HYPERLINK l bookmark24 o Current Document 第一章緒論 1 HYPERLINK l bookmark27 o Current Doc

19、ument 1.1研究背景1 HYPERLINK l bookmark30 o Current Document 1.2研究意義3 HYPERLINK l bookmark33 o Current Document 1.3論文的組織結(jié)構(gòu)4 HYPERLINK l bookmark36 o Current Document 第二章非負矩陣分解方法的研充現(xiàn)狀.5 HYPERLINK l bookmark39 o Current Document 2.1矩陣分解算法簡介 52.1.1矩陣的三角分解52.1.2矩陣的QR分解52.1.3矩陣的奇異值分解52.1.4主成分分析方法6 HYPERLINK

20、l bookmark45 o Current Document 2.2非負矩陣分解算法簡介7 HYPERLINK l bookmark50 o Current Document 2.3非負矩陣分解的相關(guān)研究8 HYPERLINK l bookmark53 o Current Document 2.4非負矩陣分解在生物數(shù)據(jù)挖掘上的應(yīng)用10 HYPERLINK l bookmark56 o Current Document 2.5基于非負矩陣分解的模型選擇方法簡介102.5.1基于非負矩陣分解的聚類一致性模型選擇方法(CPCC) 122.5.2基于非負矩陣分解的分散系數(shù)識別方法(Dispersio

21、n coefficient) . 122.5.3基于樣本相似性的模型選擇方法(Concordance index) 132.5.4基于穩(wěn)定性的非負矩陣分解方法(StaNMF) 13 HYPERLINK l bookmark61 o Current Document 2.6本章小結(jié)14 HYPERLINK l bookmark64 o Current Document 第三章基于同趨性非負矩陣分解模型選擇方法 15 HYPERLINK l bookmark67 o Current Document 3.1TDNMF方法簡介153.1.1同趨性及其度量公式的提出17TDNMF算法的生物意義19 H

22、YPERLINK l bookmark86 o Current Document TDNMF實驗數(shù)據(jù)及結(jié)果分析20TDNMF在模擬數(shù)據(jù)上的表現(xiàn)20TDNMF在人類微生物組計劃數(shù)據(jù)集上的表現(xiàn)21TDNMF的不足24 HYPERLINK l bookmark89 o Current Document TDNMF2 算法243.3.1同趨性度量方法243.3.2樣本間網(wǎng)絡(luò)關(guān)系的保持性度量273.3.3維數(shù)不均衡問題273.3.4信息增益率介紹283.3.5 TDNMF2 算法描述29 HYPERLINK l bookmark113 o Current Document TDNMF2實驗結(jié)果及分析30

23、TDNMF2在模擬數(shù)據(jù)上的表現(xiàn)30TDNMF2在果蠅的基因表達圖譜數(shù)據(jù)上的結(jié)果32TDNMF2在人類微生物組計劃數(shù)據(jù)上的結(jié)果33TONMF和TDNMF2的性能分析37 HYPERLINK l bookmark116 o Current Document 3.5本章小結(jié):37 HYPERLINK l bookmark119 o Current Document 第四章基于信息均衡的非負矩陣分解模型選擇方法 .39 HYPERLINK l bookmark122 o Current Document 4.1 EBNMF-基于信息均衡的維數(shù)選擇方法394.1.1 EBNMF 簡介394.1.2EBN

24、MF 算法描述41 HYPERLINK l bookmark128 o Current Document 4.2實驗數(shù)據(jù)及結(jié)果分析414.2.1模擬數(shù)據(jù)的構(gòu)建及實驗結(jié)果414.2.2在果蠅基因表達圖譜數(shù)據(jù)上的應(yīng)用分析434.2.3在人類微生物組計劃數(shù)據(jù)集上的應(yīng)用分析44 HYPERLINK l bookmark131 o Current Document 4.3本章小結(jié)47 HYPERLINK l bookmark134 o Current Document 第五章總結(jié)與展望48 HYPERLINK l bookmark137 o Current Document 5.1論文總結(jié)48 HYPE

25、RLINK l bookmark140 o Current Document 5.2下一步工作展望48 HYPERLINK l bookmark222 o Current Document 攻讀碩士期間發(fā)表的論文和參加的科研項目54致謝.55第一章緒論1.1研究背景模型選擇是機器學(xué)習(xí)中非常重要的方法，模型選擇旨在從各種替代方案中選擇 特定的候選者。其目的是通過某種數(shù)據(jù)驅(qū)動的指導(dǎo)來區(qū)分好的和不好的模型。模型 選擇在機器學(xué)習(xí)領(lǐng)域應(yīng)用廣泛，如：聚類個數(shù)的確定，復(fù)雜網(wǎng)絡(luò)中社團結(jié)構(gòu)提取 叫 矩陣低秩分解中，分解維度的選擇等【3%本文將圍繞著矩陣低秩分解中的非負 矩陣分解技術(shù)，針對性地研究該技術(shù)在數(shù)據(jù)降維

26、過程中的模型選擇問題。大數(shù)據(jù)時代，各行各業(yè)的數(shù)據(jù)量呈現(xiàn)爆炸式增長。這意味著在處理這些數(shù)據(jù)時, 計算量也會隨之呈指數(shù)倍增長。如何有效的將高維復(fù)雜數(shù)據(jù)進行降維并提取信息成 為人們重點關(guān)注的問題。矩陣的低秩逼近是最為常見的數(shù)據(jù)處理方法，非負矩陣分 解(Nonnegative Matrix Factorization, NMF)便是其一，非負矩陣分解的思想最早由 P. Paatero和U. Tapper提出四，到1999年，Lee和SeungJ在其發(fā)表在Nature 的文章中，對非負矩陣分解方法作了系統(tǒng)的介紹。作者利用NMF通過對基矩陣和 系數(shù)矩陣的約束重構(gòu)人臉圖像，將原始圖像表示成一系列基圖像的非負

27、疊加組合。 NMF對圖像的分解過程被認為是局部組合成整體的純加和過程，這符合人們對事 物的感知過程。同時，NMF又不同于其它主流的模式識別方法，比如：主成分分 析(Principal Component Analysis, PCA)仞、獨立分量分析(Independent Component Analysis, ICA)lI0 奇異值分解(Singular Value Decomposition, SVD)等。上述這 些方法在生物信息、文本挖掘、圖像處理等特殊領(lǐng)域的應(yīng)用都會因為無法對數(shù)據(jù)進 行合理地約束而受限制。在表示圖像時，上述方法對像素點的正負不加約束，描述 原始圖像的線性組合可能包含相減

28、關(guān)系，這將使得分解過程中缺乏明確可解釋性的 物理意義。而NMF分解的結(jié)果具有稀疏性和非負性，這些特性使得它的分解過程 兼具心理學(xué)和物理學(xué)的解釋意義。在模式識別，信號處理，計算機視覺等領(lǐng)域，定義一個好的數(shù)據(jù)表示方法對多 維數(shù)據(jù)作較好的描述至關(guān)重要。一個好的數(shù)據(jù)表示化方法應(yīng)該具備兩個基本特點： 能使數(shù)據(jù)的維數(shù)得到一定程度地約減；(2)可清晰化數(shù)據(jù)的某種潛在結(jié)構(gòu)凹。NMF 因其不同于線性判別式分析(Linear Discriminant Analysis, LDA)】獨立分量分析、 主成分分析等方法的特點(不允許負分解量，能從非負性角度實現(xiàn)數(shù)據(jù)的多維度描 述)而被越來越廣泛的應(yīng)用。在其他領(lǐng)域，如：主

29、題恢復(fù)、功能學(xué)習(xí)、聚類、時間 序列分割等，NMF也都能發(fā)揮其獨特優(yōu)勢。這吸引著越來越多的人對其進行探索 和研究。非負矩陣分解的維度對應(yīng)著分解之后得到的低秩矩陣的維數(shù)，該維數(shù)對于分解 起著十分重要的作用。一般情況下，維數(shù)需要根據(jù)實際問題進行選取。維數(shù)反映著 分解的深度和意義，確定維數(shù)的過程也稱為非負矩陣分解的模型選擇問題或維度選 擇問題。多年來，NMF的收斂方法、多視角的非負矩陣分解、和維度選擇等一直 是NMF研究領(lǐng)域中的研究熱點和難題。而維度的選擇問題，由于其對分解結(jié)果的 直接影響作用，又成為這些研究問題中比較重要的一個。在初始化條件確定后，非 負矩陣分解的結(jié)果完全取決于維度的選擇，選擇一個好

30、的維度k,能引導(dǎo)出更加合 理的數(shù)據(jù)分解。一個小的維度k,能使得分解的過程更加簡單，快速，對應(yīng)的參數(shù) 也更加容易調(diào)整，分解之后的數(shù)據(jù)規(guī)模也更小。但是，最終分解的結(jié)果與原始的數(shù) 據(jù)也可能會有更大的差異，分解的精度則會偏底。反之，如選取的維數(shù)比較大，其 分解的精度則有所提升，但模型也隨之趨于復(fù)雜，計算復(fù)雜度也會隨之增大。一個 合理的維度，應(yīng)該取決于原始的數(shù)據(jù)矩陣的數(shù)據(jù)結(jié)構(gòu)和矩陣分解過程中的自適應(yīng)過 程。一個合理的維度，既能使得分解模型不至于過分復(fù)雜，也能使得分解結(jié)果能最 大程度映射出原始數(shù)據(jù)的特性。很多情況下非負矩陣分解的維度是事先固定的，維度的值要么依賴于直觀的選 擇，要么基于一些先驗知識（例如，

31、已知簇的數(shù)量）來確定，或者是在NMF過程 中自動估算珂。而在實際情況中，待處理數(shù)據(jù)往往是沒有標簽或者未知聚類數(shù)量的, 他們的所有特征或規(guī)律都需要我們?nèi)ネ诰?。于是，如何通過無監(jiān)督的方法，自適應(yīng) 地選擇出最合理的分解標準，換而言之，如何選出最優(yōu)的分解維度是一個很值得研 究的問題。近年來，生物數(shù)據(jù)的暴漲帶給了人們機遇和挑戰(zhàn)，通過研究生物數(shù)據(jù)揭示出各 種生物現(xiàn)象和生物機理的意義越來越受到重視。這其中包括微生物間的群落關(guān)系、 蛋白質(zhì)網(wǎng)絡(luò)的預(yù)測、致病基因的預(yù)測、復(fù)雜疾病的致病機理研究等等。而高維度甚 至超高維度的生物數(shù)據(jù)的處理和分析，又是研究過程中的“攔路虎”，怎么樣去清 洗、降維、提煉這些復(fù)雜的、具有高

32、噪聲的生物數(shù)據(jù)，提取數(shù)據(jù)特征，降低分析成 本，提高分析效率是首先要解決的問題。鑒于非負矩陣分解的優(yōu)良特性，用NMF 來研究生物數(shù)據(jù)，使得生物數(shù)據(jù)能更有效地被觀察、解釋、分類，進而使人們更加 了解、確定生物體或生物分子的結(jié)構(gòu)和功能是很有意義的5,悶，同時如何使用最有 效的方式進行非負矩陣分解過程的模型選擇，引導(dǎo)更加合理的數(shù)據(jù)分解，保證在降 維的同時最大限度的保持生物數(shù)據(jù)的原始結(jié)構(gòu)，也是具有研究價值的問題。L2研究意義矩陣低秩逼近(Low Rank Approximation, LRA )是一種尋求大規(guī)模數(shù)據(jù)的低秩 近似表示的技術(shù)。非負矩陣分解方法(Nonnegative Matrix Facto

33、rization, NMF)作為 一種典型的矩陣低秩逼近方法，能從大規(guī)模復(fù)雜數(shù)據(jù)中提取有用信息，自被開發(fā) 以來，便以其獨特的優(yōu)勢在降維、聚類、特征提取等方面得到廣泛的應(yīng)用。目前對 于非負矩陣分解的研究集中于以下幾個方面：1初始點的選擇,大多數(shù)基于NMF的算法均為局部極小值算法，初始點的選 擇是一個非常重要的問題，好的初始點選擇策略不僅能改善分解結(jié)果的質(zhì) 量，也能加快算法的收斂性，所以初始點選擇策略是非常值得研究的一個 課題。2非負矩陣分解是一個逆問題，是不適定的，因此，非負解的存在性、穩(wěn)定 性、唯一性值得進行深入研究。3另外，高階非負矩陣一非負張量分解算法，作為近年來研究的一個熱點， 也引起人

34、們的注意，正被逐步應(yīng)用到各個研究領(lǐng)域。4非負矩陣分解模型的目標函數(shù)是非凸的，無法保證分解結(jié)果的唯一性，所 以非負矩陣分解不一定有唯一解。且不同的算法得到的分解因子不同，甚 至同一個算法由于初始點的選擇不同導(dǎo)致最終得到的分解因子也不盡相同。 故對分解數(shù)據(jù)的約束或者正則化，也成為了研究的熱點。本文的研究聚焦點是非負矩陣分解的模型選擇問題。非負矩陣分解的主要目的是要 將高維數(shù)據(jù)降維，換而言之，非負矩陣將高維數(shù)據(jù)矩陣按照最合理的方式，分解為 低秩矩陣。進一步地，人們可以通過研究低秩矩陣的結(jié)構(gòu)特性來映射原始數(shù)據(jù)的結(jié) 構(gòu)特性。由于合理分解后的低秩矩陣保留了絕大部分原始矩陣的特征，很多情境下， 也稱這種方式

35、為特征提取。特征提取使得原本高維的數(shù)據(jù)得到有效的降維，能有效 避免維數(shù)災(zāi)難，使得大數(shù)據(jù)能得到有效的處理。而對合理分解起決定作用的因素， 便是分解維度的大小。所以，維度選擇是NMF面臨的一個重要問題。一個好的維度 能使分解后的數(shù)據(jù)更加貼近原始數(shù)據(jù)的特征，從而保證最少的信息丟失，進一步使 得對降維后低秩矩陣的分析研究更有意義。由于分解因子中的維度要小于或遠小于 原數(shù)據(jù)矩陣的維數(shù)，一般都是根據(jù)實際問題的不同而選擇不同的維數(shù)，沒有一個固 定的標準，所以能否給出一個維度的選擇標準仍然是當(dāng)前研究的挑戰(zhàn)。13論文的組織結(jié)構(gòu)本文針對非負矩陣分解的模型選擇問題展開研究，全文共分為五章：第一章，主要介紹非負矩陣分

36、解方法以及基于非負矩陣分解的模型選擇方法的 研究背景，并介紹了模型選擇的研究意義。第二章，概述了非負矩陣分解方法的研究現(xiàn)狀、研充動向及其在相關(guān)領(lǐng)域的應(yīng) 用，并著重介紹了幾種基于非負矩陣分解的模型選擇方法。第三章，考慮了數(shù)據(jù)在分解前后的特性保持情況，提出了同趨性的概念，并提 出基于同趨性的非負矩陣分解模型選擇方法（TDNMF）,同時考慮到傳統(tǒng)的相關(guān)性 計算方法對樣本容量的限制，提出在樣本容量較少的特殊條件下，利用重采樣的方 法解決維度不平衡問題，并在真實和模擬數(shù)據(jù)集上驗證了 TDNMF的性能。第四章，提出基于信息均衡的維數(shù)選擇方法的非負矩陣分解。章通過度量分解 迭代過程中，作為結(jié)果的低秩矩陣的穩(wěn)

37、定性和純度，提出基于信息均衡的模型選擇 方法的非負矩陣分解方法（EBNMF）,討論了信息均衡的算法原理，并在多個模擬 數(shù)據(jù)和真實生物學(xué)數(shù)據(jù)上進行了實驗，證明了 EBNMF算法的穩(wěn)定性和普適性。第五章，全文的分析和總結(jié)。結(jié)合目前在研究中遇到的問題，提出自己對相關(guān) 問題的一些想法，并對下一步的研究工作進行了規(guī)劃和展望。第二章非負矩陣分解方法的研究現(xiàn)狀2.1矩陣分法簡介矩陣低秩分解是處理復(fù)雜數(shù)據(jù)時常用的手段。把矩陣分解為形式比較簡單或性 質(zhì)比較熟悉的若干個目標矩陣的和或乘積，這些目標矩陣能清晰反映原矩陣數(shù)字特 征或能夠進行有效的數(shù)值計算和理論分析。矩陣低秩分解在圖像處理、文本分析、詞曲分離、去燥、智

38、能分析等領(lǐng)域應(yīng)用 相當(dāng)廣泛。常見的矩陣低秩分解方法有：矩陣的三角分解（LR分解）、矩陣的QR分 解、SVD算法、PCA算法等。2.1.1矩陣的三角分解若方陣A可分解為A = LR,其中L為單位下三角矩陣，R為上三角矩陣，則稱 A可三角分解。三角分解的前提是矩陣A必須是方陣，且A的前n-l個順序主子式 上丈 0,1 k 也尤2，,xmE Rdxm;低維空間維數(shù)d，過程：.中心化所有樣本:=計算樣本的協(xié)方差矩陣XX對協(xié)方差矩陣XX7*做特征值分解取最大的d個特征值所對應(yīng)的特征向量31，32，“，3小輸出：投影矩陣W = (0it kk；重采樣次數(shù)runs：重采樣系數(shù)radi；過程：計算重采樣維數(shù)n

39、ums = radi * d;1計算原始數(shù)據(jù)中樣本間網(wǎng)絡(luò)關(guān)系矩陣W。；fork inklist do(U, V=NMF(X),其中，V為kXm的低秩矩陣；fbri = l, 2, runs do對X按照維度nums進行采樣。采樣后的數(shù)據(jù)集大小為numsXm；計算采樣后數(shù)據(jù)集的樣本相關(guān)矩陣CotmPiiCotmp = Cotmp + Cotmpi；對X按照維度nums-k維進行采樣。采樣后的數(shù)據(jù)集大小為(nums-k)Xm；將采樣后的數(shù)據(jù)集和V組合成numsXm大小的數(shù)據(jù)集TmpMatrix；計算TmpMatrix數(shù)據(jù)集中的樣本相關(guān)矩陣Cvtmpt；Cvtmp = Cvtmp + Cvtmpii

40、end forruns次采樣后的平均相關(guān)矩陣 = Cotmp/runs, Cv = Cvtmp/runsiruns次采樣后的樣本間網(wǎng)絡(luò)關(guān)系矩陣Wvx計算C, C”經(jīng)H(x)映射之后的矩陣E。，Ev；計算趨向性度量：TD1；計算網(wǎng)絡(luò)關(guān)系保持率：TO2；計算信息增益率IGR；TD系數(shù)：TD = TD1 * TD2 *1GRend for輸出：滿足最大化趨TD指標的k3.4 TDNMF2實驗結(jié)果及分析3.4.1 TDNMF2在模擬數(shù)據(jù)上的表現(xiàn)這里使用的模擬數(shù)據(jù)如本章33.2節(jié)所述，有關(guān)模擬數(shù)據(jù)的詳細信息可參照表 3.1。實驗證明，TDNMF2即使在模塊數(shù)很少的條件下，也能夠選擇出最切合的數(shù) 據(jù)分解維

41、度。圖3.8列出了 TDNMF2在包含模塊數(shù)不同的模擬數(shù)據(jù)上的維數(shù)選擇 能力。數(shù)據(jù)樣式實驗結(jié)果維數(shù)k=5維數(shù)k=6維數(shù)k二8圖3.8TDNMF2在包含模塊數(shù)不同的模擬數(shù)據(jù)上的維數(shù)選擇能力3.4.2 TDNMF2在果蠅的基因表達圖譜數(shù)據(jù)上的結(jié)果Wu等開發(fā)了 StaNMF并利用其解釋空間基因表達和構(gòu)建果蠅的局部基因網(wǎng) 絡(luò)。該數(shù)據(jù)集（果蠅的基因表達圖譜）在其網(wǎng)站上的“主體模式”下提供： /downloads。 StaNMF分解果蠅基因表達模式數(shù)據(jù)并選擇出k = 21 （主要模式（PP）。TDNMF2在果蠅基因表達圖譜分解時的維度選擇結(jié)果如圖3.9所示，實驗過程

42、中，設(shè)定重采樣系數(shù)radi分別為0.6、0.7、0.8及0.9,在不同的重采樣系數(shù)下TDNMF2 同樣很好的選擇出k= 21作為最優(yōu)分解模式。采樣系數(shù)radi = 0.6采樣系數(shù)radi =0.7圖3.9 TDNMF2在基因表達數(shù)據(jù)上的表現(xiàn)3.4.3 TDNME2在人類微生物組計劃數(shù)據(jù)上的結(jié)果我們也將TDNMF2應(yīng)用于微生物組學(xué)數(shù)據(jù)上，這里我們?nèi)匀徊捎?.2.2所用的 人類微生物組計劃數(shù)據(jù)。圖3.10展示出采樣系數(shù)分別在0.6、0.7、0.8及0.9下 TDNMF2的模型選擇能力，可以看出不同采樣系數(shù)下，TDNMF2都能選擇出具有 代表意義的維度k = 4o圖3.1OTDNMF2在人類微生物組

43、計劃數(shù)據(jù)上的表現(xiàn)我們將TDNMF2運用在人類微生物組計劃數(shù)據(jù)上時發(fā)現(xiàn)，除選擇出維度k = 4 外，k- 11也有相應(yīng)的體現(xiàn)。為了驗證維度k=ll下，NMF分解得到的數(shù)據(jù)是否 能發(fā)現(xiàn)一些具有生物學(xué)意義的信息，我們嘗試去尋找與每個類（H的特征行）最相 關(guān)的微生物（如圖3.11所示）：1 NMF分解人類微生物組計劃數(shù)據(jù)，并取分解后的結(jié)果矩陣H；2歸一化H矩陣，進一步構(gòu)建樣本相似性矩陣S,歸一化并可視化S,通過該 步驟我們發(fā)現(xiàn)有小部分（五個樣本）原本屬于gastrointestinal_tract的樣本 單獨進行了聚類。3 為探究該小類數(shù)據(jù)的特性，本文繼續(xù)可視化H矩陣；4 通過熱圖中的行排列信息（R語

44、言gplots包下heatmap.2函數(shù)可返回對應(yīng)的 行排列信息）比對出步驟2中單獨的小類在結(jié)果矩陣H中對應(yīng)的特征行（紅 色矩形框內(nèi)部分）。5根據(jù)該特征行回溯至原始數(shù)據(jù)，找出與之相關(guān)性在0.5以上的3個微生物,其信息如下表：相 關(guān) 性DomainPhylumClassOrderFamily Genus0.94Campylo Campylo Campylo . Epsilonproteo CampyJobactBacteria Proteobadenabacterace bacter （彎 bacter cobactenaerales曲曲閩、ae曲菌屬）ncisus0.94Prevotella

45、Prevotella Bacteroidale PrevotellaBacteria Bacteroidetes Bacteroidia（普雷沃 buccalissceae氏菌屬）0.83Alistipes Alistipes_BacteroidaleRikenella（理研菌unciassifiBacteria Bacteroidetes Bacteroidia_sceae科某菌ed屬）我們發(fā)現(xiàn)這三種微生物在某些特性上的相似性，因為不管是Campylobacter concisus細菌，還是Prevotella buccalis還是Alistipes菌屬都是嚴格厭氧的網(wǎng)，這可 能解釋了為什么

46、這五個腸道標本聚類在一起的現(xiàn)象。圖3.11在維數(shù)為k=l, NMF分解人類微生物組計劃數(shù)據(jù)。該圖上部分為樣本相似性矩陣熱圖，下部 分為結(jié)果矩陣可視化熱圖（行代表特征微生物，列代表樣本），紅色矩形框標出的是一個獨特的腸道樣 本聚類所對應(yīng)的特征。我們通過改變隨機種子節(jié)點的值，創(chuàng)建包含不同數(shù)量不同數(shù)值的模塊，大小為 1000X200的數(shù)據(jù)集各100份。進一步驗證TDNMF2算法在較大規(guī)模數(shù)據(jù)上的準確 性，圖3.12展示出在不同的采樣系數(shù)下（0.60.9）, TDNMF2對最優(yōu)維度的選擇 能力。同時，我們在具有其他數(shù)量模塊的較大規(guī)模數(shù)據(jù)集上也做了驗證實驗，我們發(fā) 現(xiàn)，隨著模塊的增多，TDNMF2的準確

47、率會有所下降，這可能與NMF本身的收斂 法則和其自身的穩(wěn)定性有關(guān)系。下一章，我們將針對迭代過程中數(shù)據(jù)的變化，提出 更加可靠的基于NMF的模型選擇方法。采樣系數(shù)準確率0.60.720.70.860.80.870.90.86包含三個pattern的模擬數(shù)據(jù)，大小為1000*200圖3.12 TDNMF2在具有三個模塊的高維數(shù)據(jù)上的模型選擇表現(xiàn)3.4.4 TDNMF和TDNMF2的性能分析上述實驗結(jié)果表明，在不同條件下，TDNMF和TDNMF2具有很好的性能。并 且，由于其設(shè)計上的改進，兩者在時間復(fù)雜度上明顯要低于傳統(tǒng)的非負矩陣分解模 型選擇方法。傳統(tǒng)的非負矩陣分解模型選擇方法基于分解結(jié)果的穩(wěn)定性或

48、其它分類特性。這 使得算法需要很高的時間復(fù)雜度。假設(shè)候選維度集合中元素個數(shù)為N, 一般地，傳 統(tǒng)算法會運行B次NMF, B100o然后兩兩比較分解結(jié)果的關(guān)聯(lián)關(guān)系。假設(shè)單次 運行非負矩陣分解的時間復(fù)雜度為O(NMF),單次比較分解結(jié)果的關(guān)聯(lián)關(guān)系的時間 復(fù)雜度為O(COMP),那么傳統(tǒng)的非負矩陣分解模型選擇方法時間復(fù)雜度為 Nx (Bx O(NMF) +里mO(COMP)。TDNMF和TDNMF2由于只考察分解前后數(shù) 據(jù)特性的保持，在同樣的前提下，其時間復(fù)雜度為Nx(0(NMF) + 0(COMP)。所 以TDNMF和TDNMF2算法時間復(fù)雜度要遠遠低于傳統(tǒng)的模型選擇方法。3.5本章小結(jié)本章基于N

49、MF分解前后，數(shù)據(jù)特性保持不變或?qū)⒏语@著的思想，首次提出 “同趨性”的概念，同趨性表示在分解前保持正相關(guān)或負相關(guān)的樣本點在分解之后 應(yīng)該依舊保持這樣的相關(guān)性或不發(fā)生很大的變化。通過考察在每一次候選維度的非 37 負矩陣分解后，樣本點數(shù)據(jù)在保持同趨性的前提下，同時對彼此近鄰性質(zhì)的保持情 況，以及分解之后提取到的特征對樣本集分類純度的增益情況，提出了 TD系數(shù)概 念，TD系數(shù)用來綜合度量同趨性、近鄰保持性、信息增益量這三個指標。實驗結(jié) 果表明，基于同趨性維度選擇方法能有效進行非負矩陣分解的模型選擇，從而使得 分解結(jié)果更加穩(wěn)定、合理同時也更具解釋性。第四章基于信息均衡的非負矩陣分解模型選擇方法在第

50、三章中，我們提出了一種通過直接考察收斂后NMF算法的結(jié)果矩陣對原始 矩陣數(shù)據(jù)特性的保持程度，從而進行模型選擇的方法，這種方法由于不用進行多次 矩陣分解，能夠極大地降低模型選擇的時間復(fù)雜度，該算法可以用于大規(guī)模的數(shù)據(jù) 集。在本章中，我們將介紹一種性能更加優(yōu)異方法-基于嫡平衡的維度選擇方法 -EBNMF(Entropy balanced Normegative Matrix Factorization) 進一步的，我們將 EBNMF應(yīng)用于模擬數(shù)據(jù)、果蠅基因表達數(shù)據(jù)和人類微生物組學(xué)數(shù)據(jù)。實驗結(jié)果表 明EBNMF能有效且穩(wěn)定地進行維度選擇。4.1 EBNMF-基于信息均衡的維數(shù)選擇方法4.1J EBN

51、MF 簡介本文認為，對形于XWH的非負矩陣分解，一個好的k,應(yīng)該使得分解的過程具 有最高的“穩(wěn)定性”和“純度”。換而言之，一個好的k,應(yīng)該使得在多次初始化 迭代后，NMF輸出的結(jié)果矩陣W或H (本章研究H矩陣的變化)非常穩(wěn)定或高度重 現(xiàn)，或者是使得“特征”的聚類效果非常穩(wěn)定。理想情況下，分解之后的“特征” 只存在“相關(guān)”或者“不相關(guān)”兩種關(guān)系。為了刻畫上述的“穩(wěn)定性”和“純度”，本文在此引入炳的概念，具有概率質(zhì) 量函數(shù)p(x)的隨機變量X的香農(nóng)炳【68被定義為：H(X) = - 了尸】。卯(x)圖4.1相關(guān)性與燔的對應(yīng)關(guān)系可以看出，計算炳會得到一個很好的轉(zhuǎn)化性質(zhì)。如圖4.1所示，在計算各相關(guān)

52、性的燔之后，相關(guān)和不相關(guān)的關(guān)系對應(yīng)的炳值將無限接近或等于0。一般的，炳度量隨機變量的不確定性。因此，采用最小炳作為聚類的標準是 很合理的閥。炳能測量系統(tǒng)的“無序”情況。因為同一集群中的數(shù)據(jù)點應(yīng)該是相 似的，故每個聚類都應(yīng)該具有低嫡。于是我們使用在相關(guān)矩陣上測量的炳作為NMF 的聚類標準，即上文描述的“純度”。此外，最大炳和最小燔之間的距離還反映 了最大相關(guān)性和最小相關(guān)性之間的分布程度。因此，又可以用這個特點來衡量“穩(wěn) 定性”。具體過程描述如下：在某個k下，NMF對原始數(shù)據(jù)X進行B次分解，假設(shè)每次分解得到的結(jié)果矩陣為 風(fēng)，若之間能彼此高度重現(xiàn)，則Hb之間的互相關(guān)矩陣也應(yīng)該是穩(wěn)定的。假設(shè)中 的特征

53、為K毓（即的行），雖然在不同次分解后的排列順序不同（不同次分解得 到的結(jié)果矩陣中，各個特征的順序不是一致的），但整體的相關(guān)性也應(yīng)該是穩(wěn)定的。 由于k反應(yīng)了原始數(shù)據(jù)行的聚類情況，理想情況下，之間應(yīng)該盡可能僅存在“相 關(guān)和“不相關(guān)”這兩種關(guān)系。通過對或之間按行兩兩構(gòu)建交叉相關(guān)矩陣并求嫡值 E。,不論K成的排列順序如何變化，Eb最大值Ebinax與最小值Ebmin的差值d都能體 現(xiàn)出“穩(wěn)定性”和“純度”。且“穩(wěn)定性”和“純度”越高，對應(yīng)差值d越大。另外，還應(yīng)該考慮這樣一種極端情況：當(dāng)之間出現(xiàn)完全不相關(guān)，或者相關(guān)性 很小的情況下，d也會很大，進而對結(jié)果造成擾亂，換言之，EBNMF是基于H。之間 必須有

54、相關(guān)關(guān)系且至少有較強相關(guān)關(guān)系的前提下進行度量的，為此我們以最大相關(guān) 性的作為系數(shù)，避免這樣的擾亂產(chǎn)生。如上所述，我們定義出分解質(zhì)量公式：EB =& 5（酪聰-醐眼，）瞄他川K+ 】（理終Ek, j minEk,rncuCk, j在每個候選義下，對B次分解之后得到的B*（B-l）/2個交叉相關(guān)矩陣計算EB并取 均值EB_,選取最大對應(yīng)的k。結(jié)合“穩(wěn)定性”和“純度”的度量標準，我們提出了基于嫡平衡的非員矩陣分 解（EBNMF）方法。該算法描述如下：4.1.2 EBNMF算法描述i對手每個k,運行麗?拿法b次。在本章中,我們?yōu)樗稊?shù)據(jù)集選擇日= 100o2 對于每個NMF過程XWH,取矩陣H,其中列

55、表示微生物，行數(shù)k為觀 察對象。B次運行NMF生成輸出矩陣Hb，(b = l, B)o 現(xiàn)在，測量分解的純度和穩(wěn)定性：3令CGRKXK是兩個矩陣Hi和 也的行之間的互相關(guān)矩陣。在這里，珀和 &具有相同的行虹令EcRKxk為炳矩陣，每個元素對應(yīng)于C中元素的嫡。計算EB當(dāng)Hi和出相同(Hi = H2)或高度重現(xiàn)時，EB=1.當(dāng)Ht和H?完全不 相同時，EB = 0.計算B次運行后的平均EB,對于每個k, B次EBNMF后:EB茹與 Z EBM，HQl,bb MB該算法將取EBJ1最大時對應(yīng)的k值。4.2實驗數(shù)據(jù)及結(jié)果分析4.2.1模擬數(shù)據(jù)的構(gòu)建及實驗結(jié)果首先在模擬數(shù)據(jù)上檢測EBNMF和其它四種主流

56、方法的效果。采用第三章類彳以 的模擬數(shù)據(jù)構(gòu)建方法，生成8份包含重疊特征(pattern)的模擬數(shù)據(jù)。此外，我們 還創(chuàng)建了一個特殊的模擬數(shù)據(jù)SimulatedData9用來驗證EBNMF不同于另外一種 模型選擇方法同taNMF另的分解特性。Sinwlated_Data9的大小為250*150,它 包含了五個主要的模塊，其中五個主模塊又可以分解為八個更小的模塊。 Siinulated_Data9的結(jié)構(gòu)如圖4.2所示。圖4.2 Simulated_Data9數(shù)據(jù)（包含五個主要模塊，右下角的主模塊又可以分為三個模塊）我們分別在八種模擬數(shù)據(jù)上用EBNMF和其它經(jīng)典的4中維數(shù)選擇方法作對比, 實驗結(jié)果如表

57、格（表4.1）所示。實驗中，通過修改種子節(jié)點，我們生成規(guī)模如表 3.1所示的模擬數(shù)據(jù)各100份，在生成的模擬數(shù)據(jù)上進行五種方法的對比試驗。實 驗結(jié)果表明，在整體上，EBNMF方法優(yōu)于其它四種方法（Dispersion, CPCC, Concordance 及 StaNMF ）。表4.1五種雄度選擇方法的比較Accuracy (%)AigoninmS DatalS Data2S Data3S Data4S Data5S Data6S Data7S Data8EBNMF0.%10.98110.970.960.97StaNMF0.93110.99110.910.96dispersion0.9110.

58、820.780.690.6S0.520.17CPCC30.30.11Concordance110.830.730.10.070.160.03為了發(fā)現(xiàn)EBNMF不同于StaNMF的特性，我們進一步對Simulated_Data9進行 分析，實驗表明，StaNMF在維數(shù)選擇的時候，傾向于選擇最細化的分類。而EBNMF 選擇的k在保持分解特性的同時，能夠更好地使分解后的結(jié)果保持原始數(shù)據(jù)的本質(zhì) 特征和聚類效果。如圖4.3所示，分別用StaNMF和EBNMF方法在模擬數(shù)據(jù)Simulated_Data9 上進行矩陣分解，可以看出，作用于Simulated_Data

59、9時，StaNMF方法偏向于找到 最小分類維數(shù)k = 8（此時樣本依據(jù)最小的分類模塊分成8類），而方法EBNMF傾向 于找到大模塊的整體分類維數(shù)k = 5,同時也能體現(xiàn)出最細分類維數(shù)k = 8的合理性。STANMFEBNMF圖43 EBNMF與StaNMF的不同分解特性4.2.2在果蠅基因表達圖譜數(shù)據(jù)上的應(yīng)用分析如第三章所述，Wu等閔提出StaNMF分解果蠅基因圖譜數(shù)據(jù)。我們也在此數(shù) 據(jù)上運用EBNMF進行模型選擇并分解數(shù)據(jù)，很好地再現(xiàn)了其實驗結(jié)果（圖4.4）, 即EBNMF能夠準確地選擇21作為其最優(yōu)維度。15202530rank圖4.4EBNMF重現(xiàn)StaNMF分解結(jié)果4.2.3在人類微生

60、物蛆計劃效據(jù)集上的應(yīng)用分析回顧第三章描述的人類微生物組計劃數(shù)據(jù)集，我們可以發(fā)現(xiàn)，人類微生物組計 劃數(shù)據(jù)集跟模擬數(shù)據(jù)Simulated_Data9具有類似的特性一即數(shù)據(jù)的層次結(jié)構(gòu)，人類 微生物組計劃數(shù)據(jù)集中樣本可以粗分為5個大類進而細分為13小類?；谶@樣的 特性，我們將EBNMF應(yīng)用于人類微生物組計劃數(shù)據(jù)，希望發(fā)現(xiàn)這樣的層次結(jié)構(gòu)。 結(jié)果發(fā)現(xiàn)，在k = 6時，EB達到最優(yōu)，同時，k = 4也體現(xiàn)了較優(yōu)的EB（如圖4.5所 示）。圖4.5EBNMF在HMSMCP數(shù)據(jù)集上的維數(shù)識別（算法選擇最優(yōu)維數(shù)k為6,另外，很明 顯的，算法還體現(xiàn)出維數(shù)k為4時具有較好的特性）進而，我們分別對k = 6和k =