非負矩陣分解及其在非均衡數據分類中的應用

1、、碩士學位論文非負矩陣分解及其在非均衡數據分類中的應用作者姓名范笑宇 導師姓名、職稱 姬紅兵教授一級學科信息與通信工程二級學科信號與信息處理申請學位類別工學碩士提交學位論文日期 2014年12月西安電子科技大學學位論文獨創(chuàng)性（或創(chuàng)新性）聲明秉承學校嚴謹的學風和優(yōu)良的科學道德，本人聲明所呈交的論文是我個人在 導師指導下進行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標 注和致謝中所羅列的內容以外，論文中不包含其他人己經發(fā)表或撰寫過的研究成 果；也不包含為獲得西安電子科技大學或其它教育機構的學位或證書而使用過的 材料。與我一同工作的同志對本研究所做的任何貢獻均己在論文中作了明確的說 明并

2、表示了謝意。學位論文若有不實之處，本人承擔一切法律責任。本人簽名：他親號 日 期：K山-以牛西安電子科技大學關于論文使用授權的說明本人完全了解西安電子科技大學有關保留和使用學位論文的規(guī)定，即：研究 生在校攻讀學位期間論文工作的知識產權單位屬于西安電子科技大學。學校有權 保留送交論文的復印件，允許查閱、借閱論文；學?？梢怨颊撐牡娜炕虿糠?內容，允許采用影印、縮印或其它復制手段保存論文。同時本人保證，獲得學位 后結合學位論文研充成果撰寫的文章，署名單位為西安電子科技大學。保密的學位論文在年解密后適用本授權書。本人簽名，他父導師簽名:日 期：u心.s 期:鏟/每mResearch on Non-

3、negative MatrixFactorization and its Application toUnbalanced Data ClassificationA thesis submitted toXIDIAN UNIVERSITYin partial fulfillment of the requirementsfor the degree of Masterin Information and Communication EngineeringByFan XiaoyuSupervisor: Prof. Ji HongbingDecember 2014摘要摘要非負矩陣分解(NMF)是一

4、種處理大規(guī)模高維數據的矩陣分解方法，它以非負約 束和局部表示等獨特的優(yōu)勢吸引了眾多研究者的關注，并被廣泛地應用于數據挖 掘、計算機視覺和模式識別等領域。此外，實際的分類問題中存在很多非均衡數 據，包括密度不均衡、類別不均衡和常見的樣本數目不均衡等情況?；诖耍?文重點研究了基于數據結構信息的非負矩陣分解算法和面向非均衡數據分類的非 負矩陣分解算法。首先，概述了非負矩陣分解及非均衡數據分類的基礎理論。給出了NMF基本 算法、數學求解方法，以及經典的衍生算法；并總結了數目不均衡數據的分類難 點及常用的抽樣處理方法。其次，針對基于圖信息的非負矩陣分解僅用歐式距離來衡量樣本鄰域結構的 局限性，將鄰域

5、樣本相似度引入非負矩陣分解，提出一種基于鄰域樣本相似度的 非負矩陣分解算法(NSS-NMF)。該方法通過引入鄰域協(xié)方差矩陣來計算鄰域樣本 相似度，對于鄰域結構相似的樣本點，其分解所得的系數矩陣的約束項被賦予較 高的權值，以適應于樣本密度不均衡的情況；進一步，引入鄰域類標相似度，并 考慮基向量的正交性，提出一種基于鄰域相似度的非負矩陣分解算法(NS-NMF)o 該方法在考慮鄰域樣本相似度的基礎上，根據鄰域樣本的已知類標信息構建鄰域 類標分布矩陣，這樣組合得到的鄰域相似度有效地兼顧到數據類別分布不均衡的 情況。實驗結果表明，上述基于數據結構信息的非負矩陣分解算法可以獲得比傳 統(tǒng)方法更好的聚類分類性

6、能。最后，針對常見的非均衡數據問題(即樣本數目不均衡)，提出一種新的加權 非負矩陣分解算法(WNMF)。該方法通過計算每類樣本數在總樣本數中的比例，求 其倒數作為訓練樣本的權值引入非負矩陣分解，因此在保持了多數類分類準確性 的同時，有效地提升了少數類樣本的分類性能。此外，結合NS-NMF算法考慮了 鄰域結構信息的優(yōu)點，提出一種基于非負矩陣分解的混合重采樣算法(HS-NMF)o 該方法先通過NS-NMF將數據集映射到更加可分的子空間，再通過經典的過采樣、 欠采樣技術改善數據的不均衡程度。實驗結果表明，將非負矩陣分解應用于非均 衡數據分類中，可獲得比傳統(tǒng)重采樣方法更高的分類準確率。關鍵詞：非負矩陣

7、分解，非均衡數據分類，鄰域相似度，重采樣 論文類型：應用基礎研究類ABSTRACTABSTRACTNon-negative Matrix Factorization(NMF) is a kind of matrix factorization method for dealing with large-scale and high-dimension data. With the unique advantages of non-negative constraints and local expression, NMF catches many researchers5 eyes, and

8、has been widely used in data mining, computer vision and pattern recognition, etc. In addition, many practical classification problems involve unbalanced data, which is of uneven density, unbalanced category or common seen unqueal number of samples. Therefore, this thesis mainly studies the Nonnegat

9、ive Matrix Factorization based on data structure information and its application to unbalanced data classification.Fiistly, the basic theories of Nonnegative Matrix Factorization and unbalanced data classification are introduced, with emphasis on conventional NMF algorithms, their mathematics models

10、 and some classic derivative algorithms. Then the difficulties of unbalanced data classification and the common sampling methods are summaiized.Secondly, aiming at the limitation of Graph Regularized Non-negative Matrix Factorization, which only measures the samples neighborhood structure with Eucli

11、dean distance, we introduce the metric of Neighborhood Sample Similarity and propose a Non-negative Matrix Factorization algorithm based on Neighborhood Sample Similarity (NSS-NMF). This method uses the neighborhood covariance matrix to compute Neighborhood Sample Similarity, and assigns higher weig

12、hts to the constraints of the coefficient matrix of the decomposited sample points whose neighborhood structure are more similar, so as to adapt to the uneven sample density. Further, by introducing Neighborhood Label Similarity and taking the orthogonality of the basis vectors into account, we prop

13、ose a Non-negative Matrix Factorization algorithm based on Neighborhood Similarity (NS-NMF). Inheriting Neighborhood Sample Similarity, NS-NMF constructs the neighborhood class distribution matrix according to the prior label information of the neighborhood samples. This combined neighborhood simila

14、iity effectively takes into consideration the unbalanced data density and label distribution simultaneously. The experiments vertify that the proposed algorithms outperform traditional methods in terms of clustering and classification performance.Lastly, in view of the common situation of unbalanced

15、 data, i.e., the number of samples is not balanced, we put forward a new Weighted Non-negative Matrix Factorization algorithm (WNMF). It calculates the proportion of the number of samples which belong to the same category to the total number of samples, and takes its inverse to weight the NMF. Conse

16、quently WNMF not only keeps the classification accuracy of the majority class samples but also effectively improves the classification performance for the minority class samples. In addition, combined the advantages of NS-NMF algorithm which respects neighborhood structure information, a Hybrid re-S

17、ampIing algorithm based on the Non-negative Matrix Factorization(HS-NMF) is put forward. It first maps the data into a more separable subspace thiough NS-NMF, then uses the classic over-sampling and under-sampling schemes to alleviate the degree of data imbalance. The experimental results show that

18、the application of NMF related methods to the unbalanced data can lead to better classification performance than traditional pure re-sampling methods.Keywords: Non-negative Matrix Factorization, unbalanced data classification, NeighborhoodSimilarity, re-samplingType of Dissertation: Applied Basic Re

19、search插圖索引插圖索引 TOC o 1-5 h z 圖1.1 NMF模型及算法分類示意圖3圖2.1 NMF, VQ, PCA分別實現(xiàn)人臉的部分基表示囪10圖2.2 SMOTE算法合成少數類樣本點示意圖18圖2.3 SMOTE算法效果圖18圖2.4分界線不明顯的SMOTE算法效果圖19圖2.5 Tomek links清理數據示意圖19圖3.1密度不均衡的數據分布示意圖22圖3.2 ORL數據庫的圖像樣本25圖3.3 ORL數據庫各算法性能比較26圖3.4 YALE數據庫的圖像樣本27圖3.5 YALE數據庫各算法性能比較27圖3.6數據1中1-6類樣本信號模糊函數切片特征28圖3.7雷達輻

20、射源數據庫各算法性能比較29圖3.8樣本點鄰域類標分布模擬示意圖30圖3.9 ORL數據庫各算法性能比較33圖3.10 Yale數據庫各算法性能比較34圖3.11雷達輻射源數據庫各算法性能比較35圖4.1 UMIST數據庫的圖像樣本42 HYPERLINK l bookmark159 o Current Document 圖4.2 NMF降維混合重采樣算法框圖44表格索引表格索引 TOC o 1-5 h z 表3.1 ORL數據聚類準確率(%)26表3.2 ORL數據歸一化互信息(%)26表3.3 Yale數據聚類準確率(%)27表3.4 Yale數據歸一化互信息(%)27表3.5雷達輻射源數

21、據聚類準確率(%)28表3.6雷達輻射源數據歸一化互信息(%)28表3.7 ORL數據聚類準確率(%)33表3.8 ORL數據歸一化互信息(%)33表3.9 Yale數據聚類準確率(%)34表3.10 Yale數據歸一化互信息(%)34表3.11雷達輻射源數據聚類準確率(%)35表3.12雷達輻射源數據歸一化互信息(%)35表4.1二分類數據集混淆矩陣40表4.2 Breast Cancer原始數據集SMOTE算法性能指標(%)41表4.3 Breast Cancer數據集各降維算法性能指標(%)41表4.4 UMIST數據庫SMOTE算法性能指標(%)42表4.5 UMIST數據庫各降維算法

22、性能指標(%)42表4.6 Breast Cancer原始數據集各抽樣算法性能指標(%)45表4.7 Breast Cancer數據集各降維算法性能指標(%)45表4.8 UMIST數據庫各抽樣算法性能指標(%)45表4.9 USIMT數據庫各降維算法性能指標(%)45符號對照表符號MNX符號名稱向量維數樣本個數M維隨機向量XUV“201M維隨機向量的N個觀察值構成的矩陣，樣本集 基矩陣系數矩陣（特征矩陣）MxL維非負實矩陣空間 降維所選特征維數D(XIIUV)IIMWu*V*UT相似度度量矩陣的Frobenius范數目標函數梯度基矩陣最優(yōu)解系數矩陣（特征矩陣）最優(yōu)解矩陣間的Hadamard積

23、U的轉置矩陣a0Rir2tr(.)LNMF算法中基向量約束項的參數LNMF算法中系數矩陣約束項的參數GNMF基于SED的約束項GNMF基于GKLD的約束項矩陣的跡mkrand(0,l)w(嚀，勺)CiC商叱w(w)N2SMOTE算法過取樣倍數近鄰點個數區(qū)間（0,1）內的一個隨機數樣本點X., Xj基于歐氏距離的相似性估計樣本點氣的近鄰點協(xié)方差矩陣Ci樣本點習的近鄰點協(xié)方差矩陣Ci的簡化：G的對角元素 鄰域樣本相似度最近鄰個數參數包含鄰域結構信息的約束項調節(jié)參數bnssWK) 叫%)YL鄰域樣本相似度調節(jié)參數鄰域類標相似度鄰域相似度基向量正交項調節(jié)參數 拉普拉斯矩陣甲成，代b”/sQ拉格朗日乘子

24、鄰域類標相似度調節(jié)參數對角權值矩陣縮略語對照表縮略語英文全稱中文對照PCAPi incipal Component Analysis主成分分析LDALinear Discriminant Analysis線性判別分析VQVector Quantization矢量量化NMFNonnegative Matrix Factorization非負矩陣分解BNMFBasic Nonnegative Matrix Factorization基本非負矩陣分解CNMFConstrained Nonnegative Matrix Factorization約束非負矩陣分解SNMFStructure Nonneg

25、ative Matrix Factorization結構化非負矩陣分解GNMFGraph Regularized Nonnegative MatrixFactorization for Data Representation圖正則非負矩陣分解SPNMFSparsed Nonnegative Matrix Factorization稀疏非負矩陣分解ONMFOrthogonal Nonnegative Matrix Factorization正交非負矩陣分解DNMFDiscriminant Nonnegative Matrix Factorization判別非負矩陣分解MNMFNonnegativ

26、e Matrix Factorization on manifold復合非負矩陣分解CVNMFConvolutive Nonnegative Matrix Factorization卷積非負矩陣分解NMTFNonnegative Matrix Tri-factorization三系數非負矩陣分解NTFNonnegative Tensor Factorization非負張量分解NMSFNonnegative Matrix-Set Factorization非負矩陣集分解KNMFKernel Nonnegative Matrix Factorization核非負矩陣分解AAAIthe Associ

27、ation for the Advancement of美國人工智能發(fā)展協(xié)Ailificial Intelligence會ICMLthe International Conference on MachineLearning workshop機器學習國際會議ACMthe Association for Computing美國計算機協(xié)會NCRNeighborhood Cleaning Rule鄰域清理技術CNNEdited Neaiest Neighbor Rule編輯最近鄰規(guī)則SMOTESynthetic Minority Over-sampling Technique合成少數類過取樣SEDS

28、quai e of Euclidian Distance平方歐式距離GKLDGeneralized Kullback-Leibler Divergence廣義KL散度KKTKarush-Kuhn-Tucker求解矩陣最優(yōu)性條件LNMFLocal Non-negative Matrix Factorization局部非負矩陣分解NSSNeighborhood Sample Similaiity鄰域樣本相似度NLSNeighborhood Label Similaiity鄰域類標相似度NSNeighborhood Similaiity鄰域相似度ACAccuracy聚類準確率NMINormalize

29、d Mutual Information歸一化互信息KNNk-Nearest Neighbor algorithmK最近鄰算法WNMFWeighted Nonnegative Matrix Factorization加權非負矩陣分解HS-NMFHybrid Sampling based on NMFNMF降維混合取樣算 法目錄目錄摘要 TOC o 1-5 h z HYPERLINK l bookmark25 o Current Document ABSTRACTIll HYPERLINK l bookmark28 o Current Document 插圖索引V HYPERLINK l boo

30、kmark31 o Current Document 表格索引VII符號對照表IX HYPERLINK l bookmark34 o Current Document 縮略語對照表XI HYPERLINK l bookmark37 o Current Document 目錄XIII HYPERLINK l bookmark40 o Current Document 第一章緒論1 HYPERLINK l bookmark43 o Current Document 1.1課題研究背景及意義1 HYPERLINK l bookmark46 o Current Document 1.2國內外研究現(xiàn)狀2

31、 HYPERLINK l bookmark49 o Current Document 1.2.1非負矩陣分解研究進展2 HYPERLINK l bookmark52 o Current Document 1.2.2非均衡數據分類研究進展4 HYPERLINK l bookmark55 o Current Document 1.3論文內容及章節(jié)安排6 HYPERLINK l bookmark58 o Current Document 第二章 非負矩陣分解及非均衡數據分類概述9 HYPERLINK l bookmark61 o Current Document 2.1引言9 HYPERLINK l

32、 bookmark64 o Current Document 2.2非負矩陣分解概述9 HYPERLINK l bookmark67 o Current Document 221非負矩陣分解基本算法9 HYPERLINK l bookmark70 o Current Document 2.2.2非負矩陣分解的數學求解10 HYPERLINK l bookmark82 o Current Document 2.2.3非負矩陣分解衍生算法12 HYPERLINK l bookmark93 o Current Document 2.3非均衡數據分類概述16 HYPERLINK l bookmark9

33、6 o Current Document 2.3.1非均衡數據分類難點16 HYPERLINK l bookmark99 o Current Document 2.3.2非均衡數據分類常用方法17 HYPERLINK l bookmark102 o Current Document 2.4本章小結20 HYPERLINK l bookmark105 o Current Document 第三章基于數據結構信息的非負矩陣分解21 HYPERLINK l bookmark108 o Current Document 3.1引言21 HYPERLINK l bookmark111 o Current

34、 Document 3.2基于鄰域樣本相似度的非負矩陣分解算法21 HYPERLINK l bookmark114 o Current Document 3.2.1鄰域樣本相似度(NSS)22 HYPERLINK l bookmark117 o Current Document 3.2.2基于鄰域樣本相似度的NMF算法(NSS-NMF)23 HYPERLINK l bookmark120 o Current Document 3.2.3實驗結果與分析24 HYPERLINK l bookmark126 o Current Document 3.3基于鄰域相似度的非負矩陣分解算法29 HYPER

35、LINK l bookmark129 o Current Document 3.3.1鄰域類標相似度(NLS)29 HYPERLINK l bookmark132 o Current Document 3.3.2基于鄰域相似度的NMF算法(NS-NMF)30 HYPERLINK l bookmark135 o Current Document 3.3.3實驗結果與分析32 HYPERLINK l bookmark138 o Current Document 3.4本章小結36 HYPERLINK l bookmark144 o Current Document 第四章面向非均衡數據分類的非負矩

36、陣分解37 HYPERLINK l bookmark147 o Current Document 4.1引言37 HYPERLINK l bookmark150 o Current Document 4.2加權非負矩陣分解算法37 HYPERLINK l bookmark153 o Current Document 4.2.1加權非負矩陣分解算法(WNMF)37 HYPERLINK l bookmark156 o Current Document 4.2.2實驗結果與分析394.3 NMF混合重采樣算法43 HYPERLINK l bookmark162 o Current Document

37、4.3.1 NMF混合重采樣算法(HS-NMF)43 HYPERLINK l bookmark165 o Current Document 4.3.2實驗結果與分析44 HYPERLINK l bookmark168 o Current Document 4.4本章小結46 HYPERLINK l bookmark171 o Current Document 第五章總結與展望47 HYPERLINK l bookmark174 o Current Document 5.1全文總結47 HYPERLINK l bookmark180 o Current Document 5.2未來展望48 HY

38、PERLINK l bookmark186 o Current Document 參考文獻49 HYPERLINK l bookmark268 o Current Document 致謝55 HYPERLINK l bookmark271 o Current Document 作者簡介57第一章緒論1.1課題研究背景及意義一個深深根植于科學和工程學研究者心目中的基本信念，是在明顯的混亂和 復雜中，一定有一些簡單、緊湊和典雅的東西扮演著最基本的角色。在信號處理、 數據分析、數據挖掘、模式識別和機器學習中也是這樣。近年來科學技術的飛速 發(fā)展使得原始數據的數量增多和可用性增強以爆炸的速度發(fā)生。隨著傳

39、感器和計 算機技術的發(fā)展，我們擁有了越來越多可用的原始數據，如何從如此海量的數據 中提取出有用的信息成為人們非常關注的焦點。人工智能領域中的機器學習是研 究如何將機器智能化的技術，而機器智能化的方式就是深入分析數據改善系統(tǒng)自 身性能，因此機器學習成為數據分析領域的一項主要技術。數據降維是機器學習的一個重要研究領域。通過適當的降維技術來獲取一種 有效的表示方式，在多元數據分析中已經成為一個重要的、必要的和具有挑戰(zhàn)性 的問題。降維一般來說應該滿足兩個基本性質：第一，原始數據的尺寸應該減?。?第二，主成分、隱藏的概念、突出的特性或潛在的變量的數據，根據應用程序上 下文，應該有效地識別。在許多情況下，

40、原始數據集或觀察數據會被構成數據矩 陣或張量，會被描述為線性或多重線性組合模型，所以，從代數的角度來看，降 維可以被看做：將原始數據矩陣分解為兩個因子矩陣。規(guī)范化方法，如主成分分 析(Principal Component Analysis, PCA),線性判 別分析(Linear Discriminant Analysis, LDA),獨立分量分析(Independent Component Analysis, ICA),矢量量化(Vector Quantization, VQ)等等都是一些低秩近似的范本。這些方法的統(tǒng)計特性各不相同， 是因為它們對因子矩陣及其底層結構有不同的約束條件，它們也

41、有一些共性：對 因子矩陣中的元素沒有任何約束。換句話說，在這些方法中，允許出現(xiàn)負數因子 矩陣和減法運算。相比之下，一個新的分解方法-非負矩陣分解(Nonnegative MatrixFactorization, NMF),它包含非負約束，具有局部表示特性，同時加強了相 應問題的可解釋性。這種方法及模型最早由Paatero和Tapper提出，在Lee和 Seung4之后引起了廣泛的關注。非負矩陣分解有兩個互補的優(yōu)點非負約束和加性結合。一方面，在現(xiàn)實世界的許多種數據，如圖像、光譜和基因數據的分析任務中，不管是表面還是潛 在的結構，負值都是缺乏物理意義的。而原型通常都與特定的語義解釋相對應。 例如在

42、人臉識別中，基圖像通常是局部的而非整體的，類似人臉的一部分，如眼 睛、鼻子、嘴巴或臉頰。另一方面，人們最感興趣的地方自然是構成物體的局部 特點，加性結合意味著這些感興趣的局部可以組裝在一起拼湊出整體。于是NMF 在真實環(huán)境的場景和任務中取得了極大的成功。如在文本聚類中，不管是在提高 精度還是在潛在語義識別上，NMF已經超越了譜聚類等經典的方法叫目前，NMF 已經成功地應用于人臉識別血、文本挖掘聚類1215社區(qū)發(fā)現(xiàn)、基因數據分析 回等問題中。從另外一個角度來說，分類技術是機器學習的核心技術之一。分類就是將樣 本劃分到相應的類別，從數學角度來說，分類就是確定對象屬于哪一個預定義的 目標類。近年來，

43、隨著分類問題的研究不斷深入，人們發(fā)現(xiàn)現(xiàn)實生活中存在很多 數據類別不均衡的情況，如醫(yī)療診斷1引、信用卡欺詐檢測成2。、網絡入侵檢測21 等領域中存在典型的非均衡數據集?？梢钥闯鲈谶@些問題中，不常出現(xiàn)的少數類 樣本往往顯得更為重要。對于傳統(tǒng)分類器來說，它們的首要目標都是減小其分類 錯誤，即最大化它的整體精度，且大多基于數據平衡分布的假設。但這并不適用 于非平衡數據集，由于非均衡數據集中少數類的誤判損失往往更大，傳統(tǒng)分類方 法應用于非平衡數據時，少數類的分類性能明顯下降。因此，尋求有效的方法來 提高非平衡數據中少數類的分類性能顯得急迫而有意義。非均衡數據集通常具有兩個特點：一是數據類別數目差異大；二

44、是誤分類代 價不同。兩個主要特點決定了它與之前基于均衡數據的分類問題是完全不同的， 現(xiàn)有的分類算法不能或者不能直接應用其上。但均衡數據分類問題的解決和研究 成果對非均衡數據分類問題的解決仍然具有巨大的推動作用，最直接的使用方法 是將非均衡數據進行預處理，使之均衡化而后再用之前算法訓練分類器，即可得 到很好的分類效果。十幾年來，非均衡數據分類問題的步步深入，愈發(fā)激起研究 人員的研究熱情，吸引了越來越多優(yōu)秀人才的關注，在此過程中，國內外的學者 們提出了一個又一個性能卓越的分類算法。1.2國內外研究現(xiàn)狀1.2.1非負矩陣分解研究進展由于在確保非負性和稀疏性的情況下增強了數據的可解釋性，NMF已經成為

45、 多元數據分析的一種必要的工具，被廣泛應用于數學、優(yōu)化、神經計算、模式識 別和機器學習22】、數據挖掘I】、信號處理I、形象工程和計算機視覺VI、光譜數 據分析2習、生物信息學SI、化學計量學VI、地球物理學28】、財經29。更具體地說， 這些應用程序包括文本數據挖掘a】、數字水印、圖像去噪DI】、圖像恢復、圖像分 割DI、圖像融合、圖像分類I、圖像檢索、人臉識別I、面部表情識別SI、音頻 模式分離3們、音樂流派分類Ml、語音識別等。自從問題被提出以來已經產生了大量關于NMF的成果，研究者來自不同領域: 數學家、統(tǒng)計學家、計算機科學家、生物學家和神經學家等，都從不同角度探索 T NMF的相關問

46、題?？偟膩碚f，NMF理論是現(xiàn)今已經獲得巨大的進步但仍在進 展中的一項工作。具體來說：第一，NMF自身的性質已獲得很深入的探索，而嚴 格的統(tǒng)計支撐，像那些傳統(tǒng)的分解方法PCA或LDA 一樣，并沒有完全地發(fā)展， 從某種程度上說這也是它的難題；第二，像文獻國中提到的如加性約束的一些問 題已經被解決，而很多其他問題還有待解決。總結過去十幾年，NMF算法的各種修改、擴展和推廣已經形成了一個很全面 的系統(tǒng)，本文做出歸納總結見圖1.1?？偟膩碚f，現(xiàn)有的NMF算法可以被劃分為 四類，它們都遵循統(tǒng)一的標準。第一，基本NMF(BNMF),即NMF的原始模型， 它只規(guī)定了非負約束；第二，約束NMF(CNMF),它增

47、加了諸如正則化之類的加性 約束項；第三，結構化NMF(SNMF),它修改了標準分解公式；第四，廣義 NMF(GNMF),它廣義地突破了傳統(tǒng)的數據類型和分解模式，使模型等級變得更加 寬泛。圖1.1 NMF模型及算法分類示意圖具體來說，首先，基本NMF為其它所有NMF模型建立了一個基礎的分析框 架?；綨MF的研究主要集中在優(yōu)化工具和計算方法方面以及大規(guī)模數據處理和 在線處理。約束NMF分為四個子類：第一，稀疏NMF(SPNMF)增加了稀疏約束； 第二，正交NMF(ONMF)增加了正交約束；第三,判別NMF(DNMF)增加了判別 約束；第四，復合NMF(MNMF)，保留了局部拓撲性質。事實證明這些

48、形態(tài)約束 在本質上也是必要的，從后面的理論和實驗分析都可以看出來。結構化NMF分為 三個子類：第一，加權NMF(WNMF),依據它們的相對重要性對不同的元素添加 不同的權值；第二，卷積NMF(CVNMF),考慮了時頻域分解；第三，三系數 NMF(NMTF),顧名思義，將數據矩陣分解為三個因子矩陣。此外，廣義NMF也 可以分為四個子類：第一，半監(jiān)督NMF(Semi-NMF),非負約束僅僅限制特定的因 子矩陣；第二，非負張量分解(NTF),將矩陣數據的維數拓展到更高維的張量；第 三，非負矩陣集分解(NMSF),將數據集從矩陣拓展到矩陣集；第四，熱核 NMF(KNMF),創(chuàng)建了 NMF的非線性模型。

49、從以上總結分類來看，我們可以從另一個角度來歸納現(xiàn)今NMF算法的研究, 主要集中在這幾方面：第一，約束條件的選擇，諸如正交性、稀疏性、光滑性或 使用數據的先驗知識等；第二，算法求解方法，很多學者分別使用了乘法更新法、 投影梯度法、最小二乘法、秩1殘差法等方法，來求解不同模型下的NMF問題； 第三，數據形式，如CP張量、TUCKER張量等；第四，應用研究，前文已多次 歸納出應用方向，這里不再贅述。1.2.2非均衡數據分類研究進展在現(xiàn)實領域中，非均衡學習問題代表有著廣泛應用的具有高度重要性的循環(huán) 問題，需要持續(xù)不斷的開拓發(fā)展。這種需求和增長的關注度也反映在最近幾個專 業(yè)研討會或會議的特殊問題研討會上

50、，包括美國人工智能發(fā)展協(xié)會關于非均衡數 據集的學習研討會(AAAr00)t39,機器學習國際會議關于非均衡數據集的學習研討 會(ICMmB),美國計算機協(xié)會關于知識發(fā)現(xiàn)和數據挖掘的特殊興趣小組(ACM SIGKDD Explorations04)叫等。非均衡數據分類的根本問題是數據的非均衡性會嚴重降低大多數標準學習算 法的性能。大多數標準算法假設或預計的是平衡的類分布或平等的誤分類代價。 因此，當面對復雜的非均衡數據集，這些算法無法正確地表示數據的分布特點， 最終會產生混淆不同類別的不好的結果。數據的不均衡分布主要有兩方面的體現(xiàn): 一方面表現(xiàn)為樣本密度不均衡，另一方面為樣本數目、類別不均衡?，F(xiàn)

51、有的研究 方法主要集中在后者，即考慮樣本數目差異大的情況。由于多類數據的分類可以 轉化為二分類，因此現(xiàn)有的非均衡數據研究方法主要針對二分類問題。二分類非 均衡數據集，即為一個數據集中某一類的樣本數遠大于另一類的樣本數，其中樣 本數多的類一般稱為多數類(負類)，樣本數少的類稱為少數類(正類)。非均衡數據 集分類問題的研究重點也就集中在如何提高少數類的分類性能上。目前，對于樣本數目非均衡的數據分類研究主要集中在數據層、算法層和兩 種層面結合起來的綜合方法。在數據層面，主要是通過采樣，重構數據集，改變 數據的不平衡分布，使不平衡性降低；在算法層面，主要是提出新的分類思想， 通過引入不同的權重值，諸如

52、代價敏感學習、集成學習等方法改進傳統(tǒng)分類算法； 綜合層面，則是將二者結合起來提高分類準確率。下面進行詳盡的歸納總結。首先，數據層面抽樣技術的使用。通常，在非均衡學習應用中采取包括某些 機械措施的抽樣方法都是為了提供一個平衡的分布情況。研究表明，對于一些基 本的分類器，一個均衡的數據集能比不均衡的數據集更容易提高它的總體分類性 能4244。文獻中的結果都證實了抽樣方法對非均衡學習的必要性。最簡單的抽樣技術是隨機過采樣和欠采樣。顧名思義，隨機欠采樣就是隨機 去掉多數類樣本集中的一些樣本，隨機過采樣是隨機復制少數類樣本集中的樣本 并添加到原數據集中，以此方式來降低數據集的不平衡性。但是，隨機欠采樣去

53、 樣本時容易丟失掉多數類中的有用信息，隨機過采樣容易造成分類器的過度擬合。 因此產生了合成采樣戲46、自適應合成采樣印、基于數據清洗技術的采樣48、采 樣和迭代結合等方法，都是在前二者之上的衍生。其中，合成少數類過取樣算 法(SMOTE),對少數類樣本進行擴充，根據一定的規(guī)則隨機制造生成新的少數類 樣本，并將這些新合成的少數類樣本合并到原來的數據集，產生新的訓練集。這 種方法已成為該領域的一個標準算法。其次，在算法層面上。雖然抽樣技術的應用確實有助于提高分類精度，但這 并不意味著分類器不能直接學習非均衡數據。相反地，研究表明由特定的非均衡 數據集誘導的分類器可以比得上由同樣的經過抽樣的均衡數據

54、集誘導的分類器 t5051o算法層面是指針對現(xiàn)有的分類算法，對不同類別的樣本設置不同的權值、 改變概率密度、調整分類邊界等措施解決。常用的改進算法包括：支持向量機、 聚類、神經網絡、決策樹等。支持向量機(Support Vector Machine, SVM)以統(tǒng)計學習理論為基礎，采用結構 風險最小化準則設計學習機器，較好地解決了非線性、高維數、局部極小點等問 題。一些學者對支持向量機進行適當改進以更好地處理不平衡數據分類。比如， 將分類邊界向多數類進行適當的偏移，以使更多的少數類樣本不會被誤判；或者 對正類和負類賦予不同的代價，作為支持向量機的懲罰因子。楊揚和李善平皿將 不平衡數據按照“最重

55、要”、“較重要”和“不重要”三個層次重新組織，提出了 基于實例重要性的支持向量機IISVM； Batuwita和Palade53提出了模糊支持向量 機；Hwangt54提出了一種基于拉格朗日支持向量機的加權方法來解決不平衡分類 問題。但由于支持向量機在學習過程中的被動性，不能有效地選擇學習樣本，使 得當支持向量機用于訓練規(guī)模較大的分類時，支持向量較多，其訓練速度和分類 速度較慢。另一個最常用的算法是代價敏感學習。它通過為小類設置更高的誤分類代價 來解決類別非均衡問題，即將各類不同的錯分代價用到分類決策中，盡可能降低 誤分類的總體代價而不是盡可能降低誤分類的錯誤率。改變現(xiàn)有分類算法使其變 得代價

56、敏感是非常困難的工作，有時效果并不明顯。通常的方法是不改變原有的 算法，通過增加一個過程使原來的分類算法變得代價敏感。常用方法有如下幾種： （1）調整樣本分布。根據錯誤分類的代價按一定比例變換訓練集中類別的頻率，其 缺點是改變了樣本的分布情況，有時會影響算法的性能。（2）元代價方法。通過“元 學習”過程，根據最小期望代價修改訓練樣本的類標記，并用修改過的訓練集重 新學習新的模型。（3）代價敏感決策。首先在訓練集中多次抽樣，生成多個模型， 再根據模型，得到測試樣本屬于每個類別的概率，然后計算測試樣本的所有錯誤 分類代價，并根據最小代價得到類標記。周志華等探討了類別非均衡性對代價敏感學習的影響【5

57、5-56,對通用代價敏感 學習方法的共性機理進行了分析，指出其解決多類問題失效的原因，并提出了一 種多類代價敏感學習方法Rescalenew,該方法能有效地進行多類代價敏感學習。 Xia等人列基于數據空間擴張技術，將代價敏感學習問題轉化為一個標準的0/1損 失分類問題，并提出了一個新的加權機制。Masnadi-Shirazi等人御提出了代價敏 感提升算法。由于支持向量機的良好分類性能，許多學者對基于支持向量機的代 價敏感學習問題也展開了研究工作。最后，在綜合層面上。單一的研究方法對非均衡數據分類性能的提升有限， 因此許多學者致力于結合不同的方法來解決類別非均衡問題，如集成學習。集成 學習是將多

58、個分類器組合來解決同一個分類問題以提升性能。其中，基于代價敏 感Boosting的集成方法尤為常見，它們的通用策略是增加高代價樣本的權重。 SMOTEBoost方法是一種基于上采樣的提升方法，它將SMOTE和Boosting相 結合。該方法不是通過更新每類樣本的權值來改變訓練數據的分布，而是通過使 用SMOTE算法添加新的少數類樣本。但該方法由于增加了過多的樣本，使得訓練 時間增大，同時可能導致過學習現(xiàn)象。1.3論文內容及章節(jié)安排本文首先從非負矩陣分解基本問題入手，對現(xiàn)有的NMF算法進行了總結和比 較，介紹了不同的目標函數構造方式、求解方法、約束條件和衍生算法。同時， 由于本文主要關注的是保持

59、數據結構信息的NMF算法，所以重點研究了樣本密度 分布不均勻、鄰域類標分布不均勻的情況，更加深入地挖掘樣本數據的結構信息， 提出了改進算法。此外，考慮到在某種程度上樣本密度不均衡是非均衡數據的一 種形式，因此先研究了現(xiàn)有的非均衡數據分類方法，然后提出了面向數目不均衡 數據的非負矩陣分解算法。根據上述研究內容，本文章節(jié)安排如下：第一章緒論，闡述了非負矩陣分解和非均衡數據分類的研究背景和現(xiàn)實意義, 總結歸納了它們的國內外研究進展和現(xiàn)狀，最后給出論文的主要內容和章節(jié)安排。第二章研究了非負矩陣分解及非均衡數據分類的基礎理論。首先給出了 NMF 基本算法及其數學模型、求解方法，建立了 NMF問題的基本框

60、架。然后介紹了經 典的NMF衍生算法，重點分析了各種算法的加性約束項。此外，總結了現(xiàn)有的數 目不均衡數據的分類難點，并重點介紹了常用的抽樣處理方法。第三章研究了基于數據結構信息的非負矩陣分解算法。針對基于圖信息的非 負矩陣分解僅用歐式距離來衡量樣本鄰域結構的局限性，首先將鄰域樣本相似度 引入NMF,提出一種基于鄰域樣本相似度的非負矩陣分解算法；其次進一步挖掘 鄰域信息，引入鄰域類標相似度，并且考慮了基向量的正交性，提出一種基于鄰 域相似度的非負矩陣分解算法。并在標準數據庫和雷達輻射源數據庫上驗證了兩 種算法的有效性。第四章研究了面向非均衡數據分類的非負矩陣分解算法。首先針對常見的非 均衡數據問