非負(fù)矩陣分解及其在非均衡數(shù)據(jù)分類中的應(yīng)用

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

2、表示了謝意。學(xué)位論文若有不實之處，本人承擔(dān)一切法律責(zé)任。本人簽名：他親號 日 期：K山-以牛西安電子科技大學(xué)關(guān)于論文使用授權(quán)的說明本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究 生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬于西安電子科技大學(xué)。學(xué)校有權(quán) 保留送交論文的復(fù)印件，允許查閱、借閱論文；學(xué)?？梢怨颊撐牡娜炕虿糠?內(nèi)容，允許采用影印、縮印或其它復(fù)制手段保存論文。同時本人保證，獲得學(xué)位 后結(jié)合學(xué)位論文研充成果撰寫的文章，署名單位為西安電子科技大學(xué)。保密的學(xué)位論文在年解密后適用本授權(quán)書。本人簽名，他父導(dǎo)師簽名:日 期：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摘要摘要非負(fù)矩陣分解(NMF)是一

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

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

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

7、分解，非均衡數(shù)據(jù)分類，鄰域相似度，重采樣 論文類型：應(yīng)用基礎(chǔ)研究類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算法合成少數(shù)類樣本點示意圖18圖2.3 SMOTE算法效果圖18圖2.4分界線不明顯的SMOTE算法效果圖19圖2.5 Tomek links清理數(shù)據(jù)示意圖19圖3.1密度不均衡的數(shù)據(jù)分布示意圖22圖3.2 ORL數(shù)據(jù)庫的圖像樣本25圖3.3 ORL數(shù)據(jù)庫各算法性能比較26圖3.4 YALE數(shù)據(jù)庫的圖像樣本27圖3.5 YALE數(shù)據(jù)庫各算法性能比較27圖3.6數(shù)據(jù)1中1-6類樣本信號模糊函數(shù)切片特征28圖3.7雷達(dá)輻

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

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

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

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

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

25、ative Matrix Factorization結(jié)構(gòu)化非負(fù)矩陣分解GNMFGraph Regularized Nonnegative MatrixFactorization for Data Representation圖正則非負(fù)矩陣分解SPNMFSparsed Nonnegative Matrix Factorization稀疏非負(fù)矩陣分解ONMFOrthogonal Nonnegative Matrix Factorization正交非負(fù)矩陣分解DNMFDiscriminant Nonnegative Matrix Factorization判別非負(fù)矩陣分解MNMFNonnegativ

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

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

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

29、d Mutual Information歸一化互信息KNNk-Nearest Neighbor algorithmK最近鄰算法WNMFWeighted Nonnegative Matrix Factorization加權(quán)非負(fù)矩陣分解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國內(nèi)外研究現(xiàn)狀2

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

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

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

34、 Document 3.2基于鄰域樣本相似度的非負(fù)矩陣分解算法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實驗結(jié)果與分析24 HYPERLINK l bookmark126 o Current Document 3.3基于鄰域相似度的非負(fù)矩陣分解算法29 HYPER

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

36、陣分解37 HYPERLINK l bookmark147 o Current Document 4.1引言37 HYPERLINK l bookmark150 o Current Document 4.2加權(quán)非負(fù)矩陣分解算法37 HYPERLINK l bookmark153 o Current Document 4.2.1加權(quán)非負(fù)矩陣分解算法(WNMF)37 HYPERLINK l bookmark156 o Current Document 4.2.2實驗結(jié)果與分析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實驗結(jié)果與分析44 HYPERLINK l bookmark168 o Current Document 4.4本章小結(jié)46 HYPERLINK l bookmark171 o Current Document 第五章總結(jié)與展望47 HYPERLINK l bookmark174 o Current Document 5.1全文總結(jié)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課題研究背景及意義一個深深根植于科學(xué)和工程學(xué)研究者心目中的基本信念，是在明顯的混亂和 復(fù)雜中，一定有一些簡單、緊湊和典雅的東西扮演著最基本的角色。在信號處理、 數(shù)據(jù)分析、數(shù)據(jù)挖掘、模式識別和機器學(xué)習(xí)中也是這樣。近年來科學(xué)技術(shù)的飛速 發(fā)展使得原始數(shù)據(jù)的數(shù)量增多和可用性增強以爆炸的速度發(fā)生。隨著傳

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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