數(shù)據(jù)維數(shù)約簡及分類算法研究

1、分類號 密 級ij DC單位代碼 10154_遼寧工業(yè)大學碩士學位論文數(shù)據(jù)維數(shù)約簡及分類算法研究專 業(yè):通信與信息系統(tǒng)研究生：周勇指導教師：蔡希彪副教授二。一六年三月獨創(chuàng)性聲明本人聲明所呈交的論文是我個人在導師指導下進行的研究工作及取得的研 究成果。盡我所知，除了文中特別加以標注和致謝的地方外，論文中，不包含 其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得遼寧工業(yè)大學或其他教 育機構(gòu)的學位或證書而使用過的材料。與我一同工作的同志對本研究所作的任 何貢獻均已在論文中作了明確的說明并表示了謝意。研究生簽名:關(guān)于論文使用授權(quán)的說明本人完全了解遼寧工業(yè)大學有關(guān)保留、使用學位論文的規(guī)定，即：學校有 權(quán)

2、保留送交的復印權(quán)，允許論文被查閱和借閱；學?？梢怨颊撐牡娜炕虿?分內(nèi)容，可以采用影印、縮印或其他復制手段保存論文。（保密的論文在解密后應遵守此規(guī)定）Master ThesisData Dimensionality Reduction and ClassificationAlgorithmsSpeciality: Communication and Information SystemsCandidate: ZHOU YongSupervisor: Associate Professor CAI Xi-biaoLiaoning University of TechnologyJinzhou,

3、 121001, ChinaMarch 2016摘要隨著信息技術(shù)的發(fā)展，涌現(xiàn)出海量數(shù)據(jù)，推動了機器學習理論不斷地向前發(fā)展。樣 本數(shù)據(jù)維數(shù)越高，數(shù)據(jù)存儲越困難，同時數(shù)據(jù)的計算量也越大；此外，數(shù)據(jù)中還存在著 噪聲或者冗余特征。因此，如何降低高維數(shù)據(jù)的維數(shù)，避免“維數(shù)災難”問題，提高數(shù) 據(jù)的分類精度，已經(jīng)成為機器學習領(lǐng)域關(guān)注的一個熱點問題。非負矩陣分解作為一種矩陣分解算法，約束待分解矩陣中和因式分解獲得的矩陣中 所有的元素為非負。這種非負性約束具有明確的物理意義，使得非負矩陣分解作為一種 維數(shù)約簡算法得到了廣泛關(guān)注。同時，半監(jiān)督學習(semi-supervised learning)由于能夠 同時利

4、用少量的已知標記樣本和大量未標記樣本數(shù)據(jù)進行有效的學習，大大克服了有監(jiān) 督學習算法中樣本數(shù)量不足問題，提高了分類的精度，因而半監(jiān)督學習方法在圖像分類、 文本分類及郵件分類等問題中得到了普遍的運用。論文集成基于非負矩陣分解的維數(shù)約簡算法和基于半監(jiān)督學習的分類算法，首先提 出了一種基于非負矩陣分解與一致性學習的半監(jiān)督學習算法。然后，在非負矩陣分解過 程中引入類別信息，提出了一種基于約束非負矩陣分解與一致性學習的半監(jiān)督分類算 法。該算法在降維過程中引入少量巳知標簽類別信息作為約束條件，增強數(shù)據(jù)降維后的 特征表示能力。最后，引入類別之間的依賴性，提出了一種基于構(gòu)建類別圖的維數(shù)約減 的半監(jiān)督學習算法。該

5、算法分別在樣本與樣本之間、類與類之間創(chuàng)建圖，構(gòu)建基于圖的 正則化框架，再通過求解Sylvester方程得到未標記樣本的標簽。在公開數(shù)據(jù)集上的實驗 結(jié)果表明，論文算法在充分利用少量已知標簽的同時用于數(shù)據(jù)的維數(shù)約簡，不僅能有效 地降低了數(shù)據(jù)的維度，還能夠有效地提高分類器的泛化能力。關(guān)鍵詞：機器學習；維數(shù)災難；維數(shù)約簡；半監(jiān)督學習；Sylvester方程AbstractWith the development of information technology, huge amounts of data have constantly sprung up, which pushes forward

6、the theory of machine learning. The higher dimension of example data causes the more difficulty of data storage, the larger calculation of data, and in addition, the more occurance of the characteristics of noise or redundancy in the example data. Therefore, how to reduce the dimensionality of high-

7、dimensional data, avoid the curse of dimensionaIity, problem and improve the classification accuracy of data has become a hot issue in the field of machine learning.Non-negative matrix factorization (NMF) is a matrix decomposition algorithm. The algorithm constraints all elements to be nonnegative i

8、n the matrixs, which include the ones underdecomposed and obtained by factorization. The non-negative constraint of NMF has explicit physical significance and makes it widely concerned as a dimension reduction algorithm. At the same time, semi-supervised learning can combine limited labeled examples

9、 data and plenty of unlabeled ones for effectively learning, which overcomes the shortage of labeled examples in supervised learning algorithm and thus improves the accuracy of the classification. Therefore, it is widely used in image classification, text classification and e-mail classification.Fir

10、stly, in view of NMF and semi-supervised learning, the thesis proposes a semi-supervised learning algorithm based on non-negative matrix factorization and consistency of learning. Secondly, a novel semi-supervised learning approach based on constrained nonnegative matrix factorization and learning w

11、ith consistency is proposed by introducing class information in the process of non-negative matrix factorization, which introducing limited labeled examples classification information as constraints in the process of dimensionality reduction, enhanced data dimensionality reduction feature representa

12、tion capability. Finally, it be introduced the dependencies between classes, and it is proposed about semi-supervised learning algorithm based on the class graph of dimensionality reduction. The algorithm respectively between the examples and examples and between classes and classes create graphs to

13、 construct a graph regularize! based on frame, and then it is obtained unlabel samples of labels by solving the Sylvester equation. Experimental results on public data datasets show that the proposed algorithm are both make use of limited labeled examples data and about datasets dimension reduction,

14、 and not only can effectively reduce the dimension of the data, but also can improve the classifier generalization ability.Key words: machine learning; the curse of dimensionality; dimensionality reduction; semi-supervised learning; Sylvester equation目錄 TOC o 1-5 h z HYPERLINK l bookmark14 o Current

15、 Document 摘要IAbstractII HYPERLINK l bookmark20 o Current Document 1緒論1 HYPERLINK l bookmark23 o Current Document 1.1研究背景與意義1 HYPERLINK l bookmark26 o Current Document 1.2國內(nèi)夕卜研究現(xiàn)狀31.2.1維數(shù)約簡研究現(xiàn)狀31.2.2數(shù)據(jù)分類研究現(xiàn)狀6 HYPERLINK l bookmark36 o Current Document 1.3論文的主要工作和結(jié)構(gòu)安排81.3.1論文的主要工作81.3.2論文的組織結(jié)構(gòu)8 HYPERLI

16、NK l bookmark44 o Current Document 2維數(shù)約簡與半監(jiān)督學習概況10 HYPERLINK l bookmark47 o Current Document 2.1維數(shù)約簡10 HYPERLINK l bookmark64 o Current Document 2.2半監(jiān)督學習的基本知識162.2.1半監(jiān)督學習基本思想及其未標記數(shù)據(jù)的作用162.2.2半監(jiān)督學習假設(shè)17 HYPERLINK l bookmark69 o Current Document 2.3基于圖的半監(jiān)督學習182.3.1基于圖的半監(jiān)督學習框架182.3.2基于圖的半監(jiān)督分類算法192.3.3基于

17、圖的半監(jiān)督學習算法20 HYPERLINK l bookmark81 o Current Document 2.4本章小結(jié)22 HYPERLINK l bookmark84 o Current Document 3基于非負矩陣分解和一致性學習的半監(jiān)督分類算法23 HYPERLINK l bookmark87 o Current Document 3.1非負矩陣分解233.1.1非負矩陣分解原理233.1.2非負矩陣分解算法收斂性證明25 HYPERLINK l bookmark90 o Current Document 3.2基于NMF和一致，性學習半監(jiān)督分類算法27 HYPERLINK l

18、bookmark104 o Current Document 3.3實驗結(jié)果與分析293.3.1 評價指標293.3.2數(shù)據(jù)集與參數(shù)選擇293.3.3分類結(jié)果及分析30 HYPERLINK l bookmark107 o Current Document 3.4本章小結(jié)32 HYPERLINK l bookmark116 o Current Document 4基于約束非負矩陣分解和一致性學習的半監(jiān)督分類算法33 HYPERLINK l bookmark119 o Current Document 4.1約束非負矩陣分解334.1.1約束非負矩陣分解原理334.1.2約束非負矩陣分解算法收斂性

19、證明35 HYPERLINK l bookmark125 o Current Document 4.2基于CNMF和一致性學習的半監(jiān)督分類算法38 HYPERLINK l bookmark140 o Current Document 4.3實驗結(jié)果與分析414.3.1數(shù)據(jù)集與參數(shù)選擇414.3.2分類結(jié)果及分析42 HYPERLINK l bookmark143 o Current Document 4.5本章小結(jié)44 HYPERLINK l bookmark146 o Current Document 5基于構(gòu)建類別圖的維數(shù)約簡半監(jiān)督學習45 HYPERLINK l bookmark149

20、o Current Document 5.1基于類別圖的結(jié)構(gòu)框架45 HYPERLINK l bookmark160 o Current Document 5.2基于構(gòu)建類別圖的維數(shù)約簡半監(jiān)督學習48 HYPERLINK l bookmark167 o Current Document 5.3實驗結(jié)果及分析495.3.1評價指標4953.2 數(shù)據(jù)集與參數(shù)選擇495.3.3分類結(jié)果及分析49 HYPERLINK l bookmark170 o Current Document 5.4本章小結(jié)50 HYPERLINK l bookmark173 o Current Document 6總結(jié)與展望5

21、1 HYPERLINK l bookmark176 o Current Document 6.1總結(jié)51 HYPERLINK l bookmark182 o Current Document 6.2展望51 HYPERLINK l bookmark188 o Current Document 參考文獻53 HYPERLINK l bookmark194 o Current Document 攻讀碩士期間發(fā)表學術(shù)論文情況56 HYPERLINK l bookmark197 o Current Document 致謝571緒論在豐富多彩的復雜世界中，人們正在以超乎想象的能力，不斷的改變著我們的世界

22、。 如今，各行各業(yè)都積累了大量的數(shù)據(jù)，數(shù)據(jù)作為信息交流、傳送的主要載體，填充著整 個空間，換句話說，我們的生活被大量的數(shù)據(jù)所籠罩著。一般情況下，這些數(shù)據(jù)具有高 維性和復雜性等特點，使其較難發(fā)現(xiàn)其隱藏的本質(zhì)特性。所以，從汪洋復雜的高維數(shù)據(jù) 中獲得符合現(xiàn)實運用所需的有用信息顯得迫為重要?！熬S數(shù)約簡”簡單來說就是數(shù)據(jù)的降維，將數(shù)據(jù)中的冗余信息刪除，充分提取出人 們所關(guān)心的數(shù)據(jù)信息。從某種意義來說，維數(shù)約簡是“機器學習” 1的一個重要的研究 范疇，它也屬于“人工智能”的探究的重點領(lǐng)域。在本節(jié)中，針對維數(shù)約簡問題所面臨的挑戰(zhàn)性，主要從數(shù)據(jù)處理和實際運用兩個方 面來進行闡述；其次，在高維數(shù)據(jù)處理的層次上介

23、紹半監(jiān)督學習的重要性；最后，介紹 維數(shù)約簡、數(shù)據(jù)分類的那個研究現(xiàn)狀及與其它研究課題的關(guān)系。1.1研究背景與意義伴隨著科學信息技術(shù)水平的不斷提高，人們對數(shù)據(jù)的存儲與采集能力的快速提升， 使得獲取數(shù)據(jù)變得越來越容易，而數(shù)據(jù)處理的能力卻沒有得到較好地改善。在科學研究 的諸多領(lǐng)域中，如人臉識別、生物信息學、信息檢索、遙感圖像處理等都積累了大量的 數(shù)據(jù)。就普遍而言，這些數(shù)據(jù)具有“高維性”和“海量性”等特點，而且數(shù)據(jù)構(gòu)造變得 越來越復雜。如果直接對高維數(shù)據(jù)進行處理時會帶“維數(shù)災難”(Curse of Dimensionality) 問題；而且，如果樣本數(shù)小于數(shù)據(jù)的特征維數(shù)時，會導致模型估計的性能惡化，出現(xiàn)

24、 所謂的小樣本問題。因此，如何挖掘出高維海量的數(shù)據(jù)中背后蘊藏的符合實際需求有用 知識，探索高維數(shù)據(jù)中隱藏的數(shù)據(jù)結(jié)構(gòu)和內(nèi)在分布規(guī)律將成為模式識別囹、機器學習、 數(shù)據(jù)挖掘習、計算機視覺等6諸多研究領(lǐng)域的極大挑戰(zhàn)。計算機網(wǎng)絡對于檢測問題的入侵和蛋白質(zhì)關(guān)系的調(diào)控問題是高維數(shù)中的兩個典型 實例。就實際運用而言，這些數(shù)據(jù)需要大量的存儲空間，數(shù)據(jù)特征萬千復雜，并且維度 極其的高。就這樣的情景下，如果直接對數(shù)據(jù)進行的分析，較難達到預想的分類效果。 一方面，“雖然我們被信息淹沒，但是我們?nèi)狈χR”。人們比較關(guān)注的是在萬千復雜的 高維數(shù)據(jù)中存在的某種內(nèi)在分布規(guī)律和數(shù)據(jù)中所涵蓋關(guān)于描述事物的特征本質(zhì)問題。因 此，對

25、數(shù)據(jù)的預先處理給我們提出更高的要求，去除高維數(shù)據(jù)中的不相關(guān)信息和冗余信 息，從而進一步提取高維數(shù)據(jù)中所描述事物的特征本質(zhì)信息。另外，在計算機圖像處理中，通常將圖像進行按每一行(列)逐一拉伸成為一個向 量處理，且用圖像灰度值來表示圖像特征，最終用這些特征向量表示這些圖像7。不管 對其采用統(tǒng)計學方法進行統(tǒng)計推斷，還是估計其所對應的空間組成，都會使得計算變得非常復雜與此同時也會對存儲造成極大的困難和挑戰(zhàn)。如圖1.1所示和圖1.2所示。(a)初始圖像(b)三維俯視圖圖1.1初始灰度圖像及三維坐標表示Fig. 1.1 Original gray image and its three-(dimensio

26、nal coordinate representation圖1.2三維表示灰度圖側(cè)視圖Fig. 1.2 Three-dimensional representation side view在圖1.1中圖(a)為初始灰度圖像，圖(b)為原始圖像將轉(zhuǎn)換成三維坐標系下的 表示圖，其中，Z軸表示圖像的灰度值。圖(b)是三維的俯視圖，圖中每行(列)表 示一個維度，每點代表其一個灰度值。在圖1.2所示為視角為側(cè)面的灰度圖表示。由以 下圖可以看出，計算機要處理的圖像維數(shù)是非常高，如果預先對數(shù)據(jù)不進行處理，會對 計算機存儲和計算帶來嚴重的挑戰(zhàn)圓。維數(shù)約簡作為機器學習的重要課題，是處理高維數(shù)據(jù)的強有力的方式，它

27、的實際意 義是將原維數(shù)較高的數(shù)據(jù)映射到較低維的子空間中，獲得能夠盡可能描述原數(shù)據(jù)特征的 低維表示更加緊湊而有意義，從而尋找隱藏在高維數(shù)據(jù)中的本征低維結(jié)構(gòu)9。從幾何的 角度來講，維數(shù)約簡可以解釋為高維數(shù)據(jù)投影到低維流形結(jié)構(gòu)空間表示。這樣的低維度 投影不僅保持原數(shù)據(jù)的內(nèi)在隱藏結(jié)構(gòu)分布，而且保證了觀測原始空間相互靠攏的節(jié)點映 射到較低維度的空間表示也相互靠近。通過維數(shù)約簡方法可以有效的去除數(shù)據(jù)中隱藏的 冗余信息和不相關(guān)的信息從而有效的保留數(shù)據(jù)中的有用信息，為進一步的數(shù)據(jù)處理和分 析，如降噪、分類、插值和可視化等奠定良好的應用基礎(chǔ)。隨著互聯(lián)網(wǎng)技術(shù)的推進，涌現(xiàn)海量數(shù)據(jù)，致使機器學習有了迅速的發(fā)展。與傳統(tǒng)

28、的 監(jiān)督學習方法相比，機器學習要獲得更好的學習性能需要進行大量訓練和學習，而且一 般需要充足的標簽數(shù)據(jù)樣本。然而，在實際運用中，由于數(shù)據(jù)信息具有多樣性的特點， 使得獲取大量標記樣本數(shù)據(jù)變得相對比較困難，還可能需要耗費大量的人力、物力，且 需要很有經(jīng)驗、專業(yè)知識領(lǐng)域強的專家學者通過大量的工作和努力進行人工標注，使得 付出的代價過于“昂貴”。對于沒有利用少量寶貴的已標記樣本的傳統(tǒng)無監(jiān)督學習方法, 將會造成對“昂貴”數(shù)據(jù)的浪費，而且在一定程度上對算法的性能的提高也是一種限制。 與此同時，伴隨著科技技術(shù)的高速發(fā)展，獲取大量未標記數(shù)據(jù)已經(jīng)變得不是難事。試圖 僅僅通過使用沒有標記的數(shù)據(jù)來進行機器學習具有一

29、定的盲目性，使得結(jié)果在一定程度 上很難保證較高的學習性能；不光如此，對于少量的已標記樣本數(shù)據(jù)來說是一種對數(shù)據(jù) 資源的損失及浪費。因此，如何有效的結(jié)合已知標記數(shù)據(jù)和未知標記數(shù)據(jù)來挖掘數(shù)據(jù)所 隱含的數(shù)據(jù)信息進行機器學習是十分有意義的。如今，半監(jiān)督學習問題受到越來越多的研究者的關(guān)注和青睞，己發(fā)展成為機器學習 中的熱門研究領(lǐng)域。半監(jiān)督學習(semi-s叩ervised learning) 3】能夠在減少人工標注類別 信息為代價及增強學習性能的同時充分利用少量的已知標記樣本數(shù)據(jù)和大量的未標記 樣本數(shù)據(jù)進行有效的學習，彌補了傳統(tǒng)機器學習的不足。半監(jiān)督學習方法的這種優(yōu)越性 已經(jīng)在數(shù)字圖像處理、文本分類、醫(yī)學

30、數(shù)據(jù)處理和郵件分類等領(lǐng)域得到了普遍的運用。 在實際運用中，機器學習難以發(fā)現(xiàn)模型的真實變量，原因是高維數(shù)據(jù)中隱藏著大量的冗 余信息，因此，在半監(jiān)督學習前對高維數(shù)據(jù)進行有效的降維預處理過程顯得十分有必要 的。1.2國內(nèi)外研究現(xiàn)狀1.2.1維數(shù)約簡研究現(xiàn)狀科技技術(shù)地發(fā)展，使得高維數(shù)據(jù)遍布應用于各類場景中，如：文本分類、Web多媒 體以及文本數(shù)據(jù)挖掘等研究領(lǐng)域。這些高維數(shù)據(jù)帶來日常生活“維數(shù)福音”的與此同時 也對數(shù)據(jù)的處理帶來嚴峻的挑戰(zhàn)和代價。維數(shù)約簡作為機器智能領(lǐng)域處理高維數(shù)據(jù)的一 種主要方式，己被廣泛應用于解決信息處理等實際應用，有效的對高維數(shù)據(jù)進行維數(shù)約 簡，是提高數(shù)據(jù)分類處理、機器學習性能以及

31、解決類似問題顯得十分重要的。以往的高維數(shù)據(jù)處理是將原始的高維數(shù)據(jù)通過相應的轉(zhuǎn)換或者映射到低維數(shù)據(jù)空 間表示，按照其轉(zhuǎn)換或映射函數(shù)f(x)的不同可將其分為線性方法和非線性方法。線性降維方法最為經(jīng)典和常用的方法有主成分分析(Piincipal Component Analysis,PC A) Un 和 Fisher 線性判別(Linear Discriminant Analysis, LDA),其方法也是應用 最為廣泛的降維方法BL PCA利用初始數(shù)據(jù)和重構(gòu)后的數(shù)據(jù)之間的差的絕對值最小為 目的，通過向量空間的線性組合重建原始數(shù)據(jù)空間，已被普遍應用到機器學習、模式識 別等多個研究領(lǐng)域，并取得較好的效

32、果。但是一種無監(jiān)督的降維方法不適用于反映樣本 之間的差異。相對于PCA方法而言，LDA方法利用了類別信息，其降維方法是一種有 監(jiān)督的方法，它以聚內(nèi)散度最小化、聚間散度最大化為目的，最終能夠?qū)⒏黝悢?shù)據(jù)有效 的分開，在分類問題上比PCA更有效。但由于原始高維數(shù)據(jù)樣本的維度遠遠大于樣本 個數(shù)，則LDA會存在“奇異值”問題。為了有效地解決此類問題，研究者經(jīng)過共同的 努力提出了較多且合理的解決方案，如：正則線性判別分析(Regulaiized LDA, RLDA)、 PCA+LDA法和零空間法LDA等。另外，通過LDA得到的投影向量更傾向于被混淆在 原始數(shù)據(jù)特征空間中較為相近的標簽類別信息之中。因此，為

33、了處理此類問題，Ta。等 人14從幾何均值的角度出發(fā)最優(yōu)化相異類之間的K-L散度(Kullback-Leibler divergences),提出了幾何均值散度分析(Geometric Mean Divergence Analysis, GMDA)。 經(jīng)過人們長期的努力出現(xiàn)了許多的線性降維方法，如：獨立成分分析、局部保持投影、 稀疏保持判別分析等，在此就不作逐一的介紹。線性降維方法是基于統(tǒng)計分布規(guī)律假設(shè)，且具有相對嚴謹?shù)睦碚撘罁?jù)；簡單實現(xiàn)、 易于執(zhí)行和分析，且能保持高維數(shù)據(jù)樣本在線性子空間上的幾何真實結(jié)構(gòu)、計算復雜度 低等優(yōu)點，因而得以被各個領(lǐng)域廣泛地運用。但在現(xiàn)實生活中數(shù)據(jù)并非是線性的，且數(shù)

34、 據(jù)通常情況下分布規(guī)律為非線性，以致于對處理復雜的非線性高維數(shù)據(jù)時現(xiàn)有的線性降 維方法得不到很好的運用，而且也無法揭示高維數(shù)據(jù)的內(nèi)在結(jié)構(gòu)。因此，對非線性降維 方法的研究顯得十分的迫切。近年來，在研究者的共同努力下非線性降維技術(shù)取得了長足進展，主要通過以下幾 個方面來實現(xiàn)：核技巧。將原始空間數(shù)據(jù)利用核函數(shù)轉(zhuǎn)換到一個空間，這空間是高維且線性 的空間，然后，在此特征空間上通過線性方法對其進行降維，最后，獲得所需的低維空 間表示。該技巧是對現(xiàn)有的線性降維方法的改進與補充，該方式巳經(jīng)成熟的運用于機器 學習和模式識別等相關(guān)領(lǐng)域中成。最為典型的算法包括Schdlkopf等16提出了核主分量 分析(Kerne

35、l Principal Component Analysis, KPCA)與核線性判別分析(Kernel LDA, KLDA)O還有核鄰域保持嵌入(Kernel NPE)、核半監(jiān)督判別分析(Kernel SDA)、核稀 疏保持判別分析(Kernel SPDA)以及核局部保持投影(Kernel LPP, KLPP)等叫都屬 于此類方法。實際上，核技巧或核方法是實現(xiàn)非線性和線性轉(zhuǎn)換的有效橋梁，是模式識 別嶄新研究階段的重要標記。但核化方法過度依賴于某些隱藏變換，不能直解地理解為 降維的概念I(lǐng)%而且如何選擇核參數(shù)至今沒有相對統(tǒng)一及可依據(jù)的理論印證。流形學習方法(Manifold Learning)1

36、9o流形學習方法的最初是在2000年science 上所發(fā)表的文章中所提出的算法：等距映射(Isometrical Mapping, ISOMAP)和局部線 性嵌入(Locally Linear Embedding, LLE)方法吸引了研究者的眼球，通過流形學習方 法實現(xiàn)非線性維數(shù)約簡是處理高維數(shù)據(jù)問題的一個從前所未有的新視角，而且避免了局 部極小的優(yōu)化問題所帶來的困擾，該方法利用了嵌入在高維空間中低維流形上的數(shù)據(jù)集 隱藏的流形內(nèi)在結(jié)構(gòu)。典型的流形學習算法除了 ISOMAP和LLE外，還有拉普拉斯特 征映射(Laplacian Eigenmaps, LE)和 Local Tangent Spa

37、ce Alignment (LTSA)等。雖 然在某些人造數(shù)據(jù)集上流形學習方法呈現(xiàn)出顯著的性能，但研究表明，在實實在在的數(shù) 據(jù)集上流形學習無法獲得比傳統(tǒng)PCA更好的學習效果。另外，流形學習會帶來“外樣 本(out-of-sample)”問題啊，而解決此問題需要求助于特殊的處理技巧刖。為了解決 解決此類問題且提高流形學習在實際數(shù)據(jù)上的性能，2003年He等心提出了局部保持投 影算法，此方法宗旨是保留了數(shù)據(jù)的局部拓撲構(gòu)造，其本質(zhì)是LE的線性化版本。經(jīng)過 學者們的艱苦努力提出了一系列旨在保持數(shù)據(jù)局部結(jié)構(gòu)的算法，如：近鄰保持嵌入NPE(Neighborhood Preserving Embedding

38、)、局部線性嵌入特征分析、等距投影等。其他方法。局部混合線性的方法，該方法從局部表示整體，通過局部線性組 合表示來重新構(gòu)造全局數(shù)據(jù)的思緒為出發(fā)點。然而，怎樣通過局部線性模型來得到轉(zhuǎn)換 的低維空間中的基向量線性組合來表示整體的低維坐標系；其次，通過利用EM(Expectation Maximization)網(wǎng)算法對數(shù)據(jù)進行處理，則會使得其結(jié)果陷入局部極小值 得缺點；而且算法效率不高，對參數(shù)極其敏感。所以，此類算法的實用性較差，對其使 用較少。從方法上來講，維數(shù)約簡除了依據(jù)變換函數(shù)的形式分為線性和非線性外，還可根據(jù) 其準則的不同進行分類：按照已知少量類別標簽是否被充分考慮可劃分為無監(jiān)督維數(shù)約簡學習

39、方法2、 半監(jiān)督維數(shù)約簡學習方法和有監(jiān)督維數(shù)約簡學習方法26。無監(jiān)督降維方法就是在降維過程中沒有利用數(shù)據(jù)集的標號信息只利用數(shù)據(jù)自身進 行學習訓練；也就是說，其只關(guān)心未標記樣本的分布情況而不需人為的添加樣本，進而 得到一個分類器，用來估計出樣本的標簽；其主要提取的是數(shù)據(jù)的結(jié)構(gòu)信息。典型的無 監(jiān)督降維方法有 k-聚類(k-means)、主成分分析(Principal Component Analysis, PCA) 以及其他一些流形學習算法等，比如等距映射、局部線性嵌入(Locally Linear Embedding, LLE)等。無監(jiān)督方法沒有使用已知的標記數(shù)據(jù)和大量未標記數(shù)據(jù)，對其數(shù)據(jù)資源是

40、一 種浪費；而且對實驗結(jié)果的精確度不能保證，分類結(jié)果在很大程度上具有一定的盲目性 和不依賴性。有監(jiān)督降維方法不僅利用數(shù)據(jù)自身的特征而且利用了數(shù)據(jù)已知少量的類別信息，其 主要是對數(shù)據(jù)樣本判別信息的提取。其目標是在標簽數(shù)據(jù)中建立一個從樣本到標簽的映 射。通過標簽信息來反映對應數(shù)據(jù)集的特征關(guān)系，進而得到一個有效的分類器，用來分 類測試樣本。也可以建立標簽樣本集到實值(不一定是標簽)的映射，此稱之為回歸(regression) t27k有監(jiān)督監(jiān)降維方法包括線性判別分析(Linear Discriminent Analysis, LDA)、支持向量機(Support Vector Machine, SV

41、M)、局部保持判別投影(Locality Preserving Discriminant Projections, LPDP)等。半監(jiān)督學習降維方法不僅能利用數(shù)據(jù)自身而且充分考慮了已知對應的少量的類標信 息以確保獲得的低維空間表示有良好的判別性，又能利用大量無類別標簽數(shù)據(jù)來充分挖 掘數(shù)據(jù)的內(nèi)在結(jié)構(gòu)以達到在低維空間中保持原始高維數(shù)據(jù)潛在結(jié)構(gòu)的目的。半監(jiān)學習督 降維方法巳成為如今的研究焦點，其方法包括半監(jiān)督線性判別分析(Semi-supervised LDA, SSLDA) 口刃，SSDR (Semi-supervised Dimensionality Reduction)等。根據(jù)處理數(shù)據(jù)自身的特

42、點可分為：單視圖學習、多視圖學習DU。單視圖學習：數(shù)據(jù)從某個單一的視角觀測得到的，傳統(tǒng)的降維方法大多數(shù)都是在 單視圖的假設(shè)下進行處理的。多視圖學習：數(shù)據(jù)具有顯著的不僅僅只有一個視圖的特性，而且可以劃分為彼此 不相關(guān)的幾個單一視圖。最后，總結(jié)維數(shù)約簡方法分類如圖1.3所示。圖1.3維數(shù)約簡方法分類圖Fig. 1.3 Dimensionality reduction methods for classification1.2.2數(shù)據(jù)分類研究現(xiàn)狀在“信息爆炸”的今天，海量數(shù)據(jù)的獲取和使用變得越來越容易，與此同時，高維1緒論 遼寧工業(yè)大學碩士學位論文 數(shù)據(jù)的存儲和處理也就成了一個一直困擾我們的難題。數(shù)

43、據(jù)的搜集和分類信息成為人類 每天的必備工作，而隨著數(shù)據(jù)急劇擴張，手工分類已經(jīng)遠遠不能滿足我們的需求。因此， 如何快速準確的自動識別數(shù)據(jù)，選擇合適的方法對數(shù)據(jù)進行分類顯得十分的重要。分類 問題是機器學習中的基本問題，而圖像分類是分類問題中的一個子問題，已成為許多研 究領(lǐng)域的熱門話題。數(shù)據(jù)分類相關(guān)過程如圖1.4所示。圖1.4數(shù)據(jù)分類過程基本結(jié)構(gòu)Fig. 1.4 The basic framework of data classification process數(shù)據(jù)分類的過程主要有：分類器的訓練過程和數(shù)據(jù)的分類過程SI。分類器訓練過程 主要是根據(jù)訓練樣本集中數(shù)據(jù)樣本的本質(zhì)特征結(jié)構(gòu)和相關(guān)的巳知標簽信息

44、進行訓練學 習得到有效的分類器模型；而數(shù)據(jù)分類過程是利用的獲得的分類器模型對待分類的數(shù)據(jù) 進行預測并根據(jù)相關(guān)的決策函數(shù)輸出預測結(jié)果。而分類的目標就是通過少量已標記樣本 進行訓練學習出一個性能較佳的分類器，再利用訓練學習好的分類器對添加的樣本進行 標簽信息的預測。在給定X =X“X2,X,的樣本集合和類別信息集合 卜=少見，肩，分類就是根據(jù)樣本相應的已知類別信息V得到適合樣本X的每一個 樣本類別信息的過程。在傳統(tǒng)的分類學習問題一般是單標簽分類，也就是說單一樣本只能允許對應有一個 唯一標簽，諸如此類的分類問題在以往的兩類或多類的分類問題中較為最多。而在真實 應用中，單標簽己經(jīng)不能完整的描述數(shù)據(jù)樣本

45、的信息，因此，對多標簽分類學習的研究 具有相當重要的理論與應用價值，而且多標簽分類問題已經(jīng)成為了如今研究的焦點問 題。多標簽分類就是單一對象往往會對應于多重類別信息的情況。多標簽分類算法主要 包含兩種類型：問題轉(zhuǎn)換和算法適應。問題轉(zhuǎn)換方法是將學習目標變換成一個或多個相 互獨立的單個標記分類問題，此類方法沒有特定的算法約束；算法適應類型是將己有的 學習分類算法經(jīng)過改善為多重標簽學習問題，從而使得算法能夠?qū)Χ鄻撕灁?shù)據(jù)的問題進行處理。當前，針對多標簽學習問題上，研究者提出了許多經(jīng)典學習算法，其中應用比較廣 泛且最為基礎(chǔ)的學習分類算法有：Boosting算法33、支持向量機(Support Vecto

46、r Machines, SVM)啊、K 近鄰(K Nearest Neighbor, KNN)和樸素貝葉斯模型(Naive Bayes)四等。但依然存在許多問題有待于進一步解決。1.3論文的主要工作和結(jié)構(gòu)安排13.1論文的主要工作論文主要將維數(shù)約簡理論、半監(jiān)督學習、數(shù)據(jù)分類等理論結(jié)合并應用到了高維數(shù)據(jù) 分類中，進行了相關(guān)的研究，主要完成了以下工作：首先從實際運用出發(fā)闡述維數(shù)約簡的重要求，并介紹維數(shù)約簡的相關(guān)研究現(xiàn) 狀。研究了維數(shù)約簡的相關(guān)理論知識并介紹了維數(shù)約簡的經(jīng)典算法的比較；然后， 介紹半監(jiān)督學習的理論概述和相應的算法。首先介紹非負矩陣分解算法的相關(guān)知識，并對其算法推導、迭代規(guī)則、收斂 性

47、證明作相關(guān)方面的闡述，并提出一種基于非負矩陣分解與一致性學習的半監(jiān)督分類算 法，對其算法進行實驗驗證及分析。研究了類別約束(半監(jiān)督)的非負矩陣分解算法得相關(guān)理論知識，對其迭代 規(guī)則、收斂性進行證明。并提出一種基于約束非負矩陣分解與一致性學習的半監(jiān)督分類 算法，對其算法進行實驗驗證及分析。結(jié)合類別之間的依賴關(guān)系，對其基于約束非負矩陣分解與一致性學習的半監(jiān) 督分類算法進行改進，通過實驗驗證算法的可行性和有效性。13.2論文的組織結(jié)構(gòu)全文的章節(jié)安排及具體內(nèi)容如下：第一章，緒論。說明了維數(shù)約簡的重要性及分析了課題的研究背景及研究意義，以 此同時結(jié)合相關(guān)的機器學習領(lǐng)域闡述了維數(shù)約簡的相關(guān)研究現(xiàn)狀。第二章

48、，維數(shù)約簡與半監(jiān)督學習概況。介紹了維數(shù)約簡與半監(jiān)督學習的相關(guān)理論知 識和常見的算法分析，并給出相關(guān)圖的半監(jiān)督結(jié)構(gòu)框架。第三章，基于非負矩陣分解與一致性學習的半監(jiān)督分類算法。為了在分類中減少數(shù) 據(jù)中的冗余信息、提高分類準確率，提出了一種基于非負矩陣分解與一致性學習的半監(jiān) 督分類算法。第四章，基于約束非負矩陣分解與一致性學習的半監(jiān)督分類算法。為了它充分挖掘 了已知的少量樣本的標簽信息。標簽信息不僅作為約束條件用于數(shù)據(jù)的維數(shù)約簡，同時 也作為工具用于衡量圖上樣本標簽的光滑性。提出了基于約束非負矩陣分解與一致性學 習的半監(jiān)督分類算法。第五章，基于構(gòu)建類別圖的維數(shù)約簡半監(jiān)督學習算法。在以往的半監(jiān)督學習中

49、往往 只對樣本之間構(gòu)建圖，而未考慮類與類之間的相關(guān)性。所以，在訓練樣本和類別標簽上 分別構(gòu)建鄰近圖，對基于約束非負矩陣分解與一致性學習的半監(jiān)督分類算法進行改進， 提出基于構(gòu)建類別圖的維數(shù)約簡半監(jiān)督學習算法。第六章，總結(jié)和展望。對本文進行總結(jié)，并對未來的研究進行了下一步的展望。2維數(shù)約簡與半監(jiān)督學習概況在信息化時代，維數(shù)約簡是高維數(shù)據(jù)處理的有效手段，其在數(shù)據(jù)有效降低維度的同 時減少數(shù)據(jù)中的噪聲和冗余信息；是人工智能的研究核心之一，在科學研究領(lǐng)域中承擔 著十分重要的作用。而半監(jiān)督學習充分利用了少量的已知標記標簽和大量的未標注標簽 進行機器學習問題，提高了數(shù)據(jù)的分類效果。本章將具體介紹維數(shù)約簡相關(guān)理

50、論及常見 的維數(shù)約簡算法；詳細闡述半監(jiān)督學習相關(guān)知識和經(jīng)典半監(jiān)督學習算法。2.1維數(shù)約簡在實際運用中，高維數(shù)據(jù)的廣泛分布致使對數(shù)據(jù)維度約簡已變得頗為需要。維數(shù)約 簡是指將樣本從原始輸入空間通過某種變換或映射獲得原數(shù)據(jù)集有效子空間的低維表 示。維數(shù)約簡作為高維數(shù)據(jù)處理的一種有效方式，其對數(shù)據(jù)降維希望不損失數(shù)據(jù)的關(guān)鍵 特征信息，且同時保留原始數(shù)據(jù)的潛在的內(nèi)在結(jié)構(gòu)。維數(shù)約簡作為數(shù)據(jù)處理的預處理過 程，能夠有效的提高后續(xù)機器學習的性能和有效的提高分類效果。然而，也會造成一定 的信息損失。維數(shù)約簡方法在用于降維的同時不僅有效的減少數(shù)據(jù)中冗余信息、噪聲信 息及不相關(guān)的信息，而且能夠有效的解決高維數(shù)據(jù)所帶來

51、的維數(shù)災難性問題大大減低數(shù) 據(jù)處理的計算復雜度。在很多的實際情況下，將高維數(shù)據(jù)的維數(shù)的降到一個適當?shù)姆秶?而且在能盡可能的不破壞初始數(shù)據(jù)的結(jié)構(gòu)分布，進而有利于對數(shù)據(jù)的處理。因此，維數(shù) 約簡的一般處理過程描述如圖2.1所示。圖2.1維數(shù)約簡的基本過程Fig. 2.1 The basic process of dimensionality reduction維數(shù)約簡在實際運用帶來諸多的益處，首先，維數(shù)約簡能夠有效的減低數(shù)據(jù)維數(shù)， 降低了計算復雜度，提高了計算速度；其次，維數(shù)約簡能夠發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在隱藏結(jié)構(gòu)和 內(nèi)部的分布規(guī)律，達到可視化的目的；最后，維數(shù)約簡能去除數(shù)據(jù)間的冗余信息。經(jīng)過學者共同的實踐

52、努力，已有許多維數(shù)約簡方法得到了改善和完善，因此，下面 簡單介紹幾種應用較為廣泛的降維方法。首先介紹兩個典型的線性方法：(1)主成分分析(Principal Component Analysis, PCA)主成分分析由1933年被Hotellin于提出的，也被稱之為Hotelling變換，其主要思 想是以低維子空間來表示原始高維數(shù)據(jù)，將高維數(shù)據(jù)從原來的D維降到d維(Dd),提取主要特征(主元)、減少數(shù)據(jù)冗余；利用協(xié)方差矩陣的相關(guān)變量對數(shù)據(jù)進行有效的 壓縮、提取，是一種無監(jiān)督最經(jīng)典的維數(shù)約簡方法。其目標是尋找若干個彼此正交且能 夠保持數(shù)據(jù)盡可能分開的投影方向，通過線性變換函數(shù)f3)轉(zhuǎn)成另一組不相

53、關(guān)的變量。 如圖2.1所示。Fig. 2.2 PC A method Geometric InterpretationPCA的目標函數(shù)為:NuPCA = arg max 一 yi=N=arg maxp心N=arg max Z 尸 xip ；=i IT tnX|2a心VI(2.1)=arg max 叭S,P)其中，,=*,且為總體離散矩陣：= 卜一尤)(改-x) o對 轉(zhuǎn)換矩陣作尺度約束PTP = Id ,其中L為dxd的單位矩陣。因此，PCA求解優(yōu)化問題 如下：aigmaxrr(PrSfP) s.t.PTP = Id(2.2)利用拉格朗日乘子法，構(gòu)造拉格朗日函數(shù)為：”(prp)_n(4(尹P_

54、/)(2.3)其中，人為實對稱矩陣，可以對角化為葉=UAIJT , U為正交矩陣，A為對角矩陣。對F 求偏導數(shù)并令其結(jié)果置零可得：SfP-PA = O= SrP = PUAUt = StPU =PUA(2.4)最終，問題轉(zhuǎn)化為求解前d個最大特征值對應的特征向量ppp?,P,所求特征 向量的集合就為變換矩陣P = P|，P2，P。所以，PCA降維的過程可以表示為：Xi-yi=PTxiOPCA算法的具體步驟如下：輸入：原數(shù)據(jù)樣本集知易,，叫如。，N為樣本的個數(shù)，。為原始特征維數(shù) 過程：建立相關(guān)矩陣(計算協(xié)方差矩陣)，根據(jù)K-L變換矩陣的特征值和特征向量。選取主分量。D建立優(yōu)化方程，求解主分量。第，

55、個主成分分量表示為其中j=i 七U = l,2,)為對應于特征值*得特征向量的分量，.為各個分量的標準化數(shù)值。 得到所需要的主分量值，即為新樣本集。輸出：新的樣本集3,力，一，為)如廠d為輸出的特征維數(shù)?？梢钥闯鲋鞒煞址治鐾ㄟ^對原始樣本集進行變換后，根據(jù)信息量大小對數(shù)據(jù)特征進 行排序，保留數(shù)據(jù)信息靠前的特征，去除較小的特征信息，從而減少對數(shù)據(jù)表示所需的 特征維數(shù)以及減少算法運算的復雜度，同時盡可能的減低數(shù)據(jù)恢復或從新線性組合時的 誤差。此算法不僅能提高算法的分類精度，而且能有效的去除數(shù)據(jù)中的不相關(guān)信息從而 改善數(shù)據(jù)的質(zhì)量。另外，PCA沒有利用到數(shù)據(jù)的類別信息，對分類結(jié)果具有盲目性和不 確定性，

56、因此從分類的角度考慮其不是最佳的投影選擇。(2)線性鑒別分析(Linear Discriminant Analysis, LDA)Fisher最早在1936年提出LDA算法印】，伴隨鑒別矢量對兩類或多類計算方法的提 出，LDA得以普遍的應用于許多場景。LDA充分考慮了類別間的依賴性，將原始數(shù)據(jù) 投影到維度較低的特征子空間中，從而使類別不同的數(shù)據(jù)距離盡量大，同類樣本盡量集 中。在這種情況下，LDA能提高分類器的分類精度。給定數(shù)據(jù)樣本集(沖q),1 = 1,2,其中x G Rd為訓練樣本，C.的標簽信息，k為類別個數(shù)。LDA的目的是尋找一個適合的投影矩陣PeRE(dvD), 使得在低維空間中樣本的

57、總類間距與樣本的總類內(nèi)距的比值最大。所以，定義類內(nèi)散度 矩陣S”和類間散度矩陣島如下：(2.6)kSb=Nr=其中，x=y 七為第，類樣本的均值，為全部樣本的均值，記， N 心 jni/.=柵1勺=尸, N,.=gd(%.)為.的勢，即/.中元素的個數(shù)，以此,=N,=N。在此，給出PCA和LDA算法之間的簡單對比圖，如圖2.3所示。圖2.3 PCA和LDA的比較Fig. 2.3 The comparison of PCA and LDA通常情況下，LDA的目標函數(shù)優(yōu)化有兩種：比值跡準則啊和跡比值準則39。比值跡準則如下： TOC o 1-5 h z max打(尸以寸尸廠尹&P)(2.7)住將上

58、述目標函數(shù)關(guān)于F求導并將其置零，令A = PSbP、B = PTSwP ,最終可得：SbP = SwPAB(2.8)又因為A和3均為實矩陣且為對稱矩陣，所以存在矩陣Q且可逆，使得：QtAQ = I, QtBQ=A(2.9) 其中A為對角矩陣。將/UQTQT和3 = QAQT帶入公式(2.8)中可得：ShP = SwP(Q-TQiy Q-tXQ(2o)=SbPQ = SwPQA所以，LDA的最終解P由矩陣和矩陣島中的前d個最大廣義特征值對應的特征 向量所組成的集合。跡比值準則如下：tr(PTS.P)P = arg max s.t.PTP = I(2.11)*(P0P)一般通過迭代方法進行求解此優(yōu)

59、化目標函數(shù)，求解過程計算量較大。此方法易于直 觀解釋，因此，此方法在某些領(lǐng)域中的應用優(yōu)于比值跡準則的實際效果。LDA充分利用了類別標簽信息同時用于維數(shù)約簡，不僅提高了算法的性能而且增 加了分類器的性能。因次，LDA被廣泛運用于計算機視覺、圖像檢索以及人臉識別等 領(lǐng)域中，但以此同時，LDA也存在著一些問題：如求解S,”是會出現(xiàn)奇異值問題(即小 樣本問題)、求解的投影特征向量個數(shù)受限制等。下面詳細介紹常見的幾種非線性維數(shù)約簡方法。(1)局部線性嵌入(Locally Linear Embedding, LLE)LLE算法由Sam T. Roweis和Lawrence K. Saul于2000年于提出

60、的，是一種無監(jiān) 督流形學習算法。該算法簡言之利用局部線性來表示全局非線性，從而使局部代表整體 的性質(zhì)特點，即處理后的低維數(shù)據(jù)能夠保持原有數(shù)據(jù)的拓撲結(jié)構(gòu)。在降維過程中，通過 尋找保持局部線性的重構(gòu)系數(shù)能夠在低維空間表示。LLE算法形象地表示如圖2.4所示。Step 1Step 2Step 3圖2.4 LLE算法示意圖Fig. 2.4 LLE algorithm schematicLLE算法主要步驟如下:選擇數(shù)據(jù)點兀的*鄰域；通過尋歐式距離找數(shù)據(jù)點吐的#個近鄰點，其k個數(shù)據(jù) 點組成的集合N（xJ = 氣叫，氣 , z?. =z1,z2,-，4） o根據(jù)相鄰數(shù)據(jù)之間的相互關(guān)系計算重構(gòu)相似矩陣WeRN