高維數(shù)據(jù)降維算法綜述

高維瞄降維算法綜述景明利【摘要】分類介紹了目前具有代表性的數(shù)據(jù)降維方法，重點闡述了一種新的數(shù)據(jù)降維方法-壓縮感知，在此基礎(chǔ)上，分析了各種數(shù)據(jù)降維算法的優(yōu)缺點，并對數(shù)據(jù)降維研究中存在的問題進行了剖析.【期刊名稱】《西安文理學院學報(自然科學版)》【年(卷)，期】2014(017)004【總頁數(shù)】5頁(P48-52)【關(guān)鍵詞】數(shù)據(jù)降維;線性;非線性;局部;壓縮感知【作者】景明利【作者單位】西安財經(jīng)學院統(tǒng)計學院，西安710100【正文語種】中文【中圖分類】O241近年來，隨著信息技術(shù)的飛速發(fā)展，高維數(shù)據(jù)已經(jīng)廣泛產(chǎn)生于模式識別、醫(yī)學統(tǒng)計、計算機視覺、數(shù)字圖像處理等領(lǐng)域.高維數(shù)據(jù)給數(shù)據(jù)的傳輸與存儲帶來了新的挑戰(zhàn).如何從高維數(shù)據(jù)中有效的找出其特征信息，是信息科學與統(tǒng)計科學領(lǐng)域中的基本問題，也是高維數(shù)據(jù)分析面臨的主要挑戰(zhàn).應對這個挑戰(zhàn)的首要步驟是對高維數(shù)據(jù)進行有效地降維處理.所謂降維是指將高維空間中的數(shù)據(jù)通過線性或非線性映射投影到低維空間中，找出隱蔽在高維觀測數(shù)據(jù)中有意義的并且能揭示數(shù)據(jù)本質(zhì)的低維結(jié)構(gòu).通過此方法能夠減少高維數(shù)據(jù)的維數(shù)災難問題，促進高維數(shù)據(jù)的分類、壓縮和可視化.數(shù)據(jù)降維的數(shù)學本質(zhì)可表示為[1]：假設(shè)X={xi,i=1,...,N}是D維空間的一個樣本集合，Y={yi,i=1,...,N}是d維空間的一個數(shù)據(jù)集(dD),稱F:X-Y是一個降維映射，表示為y=F(x)，也稱y為x的低維表示.針對數(shù)據(jù)降維問題，傳統(tǒng)方法是假設(shè)數(shù)據(jù)具有低維的線性分布，代表性方法是主要成分分析(PCA)[2]和線性判別分析(LDA)[3].它們已經(jīng)形成了完備的理論體系，并且在應用中也表現(xiàn)出了良好的性態(tài).但由于現(xiàn)實數(shù)據(jù)的表示維數(shù)與本質(zhì)特征維數(shù)之間存在非線性關(guān)系，因此近幾年來由STRoweis和JBTenenbaum[4][5]提出來的流形學習方法，已經(jīng)逐漸成為數(shù)據(jù)特征提取方法的研究熱點問題.這類方法假設(shè)高維數(shù)據(jù)分布在一個本質(zhì)上低維的非線性流形上，在保持原始數(shù)據(jù)表示空間與低維流形上的不變量特征的基礎(chǔ)上來進行非線性降維.因此，流形學習算法也稱之為非線性降維方法，其中代表性算法包括基于譜分析的算法、等距特征映射算法(ISOMAP)[4]、局部線性嵌入算法(LLE)[5]、局部切空間排列(LTSA)[6]、核主成分分析(KPCA)[7]、Laplacian特征映射[8]、Hessian特征映射[9]等.后來，基于概率參數(shù)模型的算法也相繼出現(xiàn)，如Charting[10].然而，這些算法很難被應用于識別問題.但一些基于譜分析的算法由于具有特殊的分解特性能夠簡單的擴展為線性算法，通過解決優(yōu)化過程中的線性逼近來實現(xiàn).這些擴展化的方法使得流形思想更容易的應用到了實際中.流形化的學習從最初的非監(jiān)督學習擴展到了監(jiān)督學習和半監(jiān)督學習，流形學習已經(jīng)成為了機器學習相關(guān)領(lǐng)域的一個研究熱點.對現(xiàn)有主流降維方法，可以從不同的角度進行分類.比如，從算法執(zhí)行過程、從幾何結(jié)構(gòu)的保留角度、從待處理的數(shù)據(jù)特性等等.本文從待處理的數(shù)據(jù)特性出發(fā)對幾種典型的線性和非線性降維方法進行了詳細地闡述，著重分析討論了壓縮感知這種新的降維方法，分析并給出了各種算法的特性，最后指出了有待解決的問題.基于維數(shù)災難和小樣本問題的存在，許多基于統(tǒng)計或者幾何理論的數(shù)據(jù)降維方法被提出.從待處理的數(shù)據(jù)性質(zhì)考慮，將現(xiàn)有的降維方法分為線性和非線性兩大類.1.1線性降維算法1.1.1PCAPCA于20世紀初由Hotelling提出，通過對原始變量的相關(guān)矩陣或協(xié)方差矩陣結(jié)構(gòu)的研究，將多個原隨機變量轉(zhuǎn)換為少數(shù)幾個新的隨機變量（能夠反映原始變量絕大部分信息），從而達到降維目的.設(shè)圖像樣本為X={x1,...,xN},xiuRm,N為總樣本個數(shù).根據(jù)最優(yōu)重建準則，PCA目標函數(shù)為這里WeRmxm是變換陣，把樣本從高維空間變換到低維空間.（1）式通過特征值分解得其中：其中是所有樣本的均值，矩陣C是樣本的協(xié)方差矩陣.事實上，W是C較大特征值對應的特征向量.1.1.2LDALDA是根據(jù)著名的Fisher準則，對于二類（正類，負類）問題推廣到多類問題，希望找到的優(yōu)化方向是使得在低維空間中同類數(shù)據(jù)盡量靠近而非同類數(shù)據(jù)盡量分離，從而保留豐富的辨別信息，使投影后的數(shù)據(jù)具有最大的可分性.改進后的Fisher準則為：其中：[w1,w2,...,wd]是SB的前d個最大特征值對應的特征向量.也就是求SBwi=AiSWwi,i=1,./d的特征值問題來求出最優(yōu)的方向[w1,w2,...,wd],d<C-1.求出特征向量后，觀測數(shù)據(jù)在這些特征向量上的投影系數(shù)就是對觀測數(shù)據(jù)所提取的低維嵌入坐標.1.2非線性降維算法對非線性降維算法，從高維數(shù)據(jù)幾何結(jié)構(gòu)被保留至低維空間的角度對算法進行分類:1.2.1全局分析的流形算法ISOMAPISOMAP法主要思想是利用局部鄰域距離近似計算數(shù)據(jù)點間的流形測地距離，同時將高維數(shù)據(jù)間的測地距離進行推導，將低維嵌入坐標的求解轉(zhuǎn)化為矩陣的特征值問題.實現(xiàn)起來分為三步：第一步，對高維空間數(shù)據(jù)集上的每個數(shù)據(jù)點，判斷其k鄰近(距離數(shù)據(jù)點最近的前k個數(shù)據(jù))或8鄰近數(shù)據(jù)(數(shù)據(jù)點距離小于￡的所有數(shù)據(jù))，然后連接并構(gòu)成高維數(shù)據(jù)的帶權(quán)鄰域圖；第二步，計算鄰域圖中任意數(shù)據(jù)對間的最短路徑，將其作為近似測地線(所謂測地線就是一個曲面上，每一點處測地線曲率均為零的曲線)估計；第三步，利用多維尺度變換(MDS)算法對原數(shù)據(jù)集進行降維.KPCAKPCA算法是對線性PCA的推廣，使用了核方法即將核映射使用到數(shù)據(jù)處理方法中，其基本思想把輸入數(shù)據(jù)x經(jīng)過非線性映射①(x)映射到特征空間F上，在特征空間F上執(zhí)行線性PCA.該算法的性能依賴于核的選取，核矩陣的大小與數(shù)據(jù)集中樣本個數(shù)的平方成正比，但算法比較簡單，能夠處理非線性數(shù)據(jù).1.2.2局部分析的流形算法(1)LLELLE算法的主要思想是假設(shè)每個數(shù)據(jù)點與它鄰近點位于流形的一線性或近似線性區(qū)域中，將全局非線性轉(zhuǎn)換為局部線性.具體步驟分為三步：第一步，高維空間上建立原數(shù)據(jù)集的k鄰近或￡鄰近鄰域圖；第二步，計算數(shù)據(jù)的局部線性表示參數(shù)矩陣W，這可以通過求解下列約束優(yōu)化問題：使得，且Wij=0，如果Xi,Xj互為鄰域；第三步，將局部線性表示參數(shù)作為高維與低維數(shù)據(jù)的不變特征量，計算無約束優(yōu)化問題獲得降維結(jié)果Y(2)LTSALTSA算法主要思想是對每一個數(shù)據(jù)點構(gòu)建一個局部切空間，然后對這些切空間進行一個放射變換從而得到一個全局嵌入的坐標.其主要步驟為三步：第一步，提取局部信息.對于樣本點xi，選取k個鄰近點(包含xi本身)，并記為Xi的均值.計算協(xié)方差矩陣ieT)的d個最大的單位特征向量g1,...,gd，并記；第二步，構(gòu)造排列矩陣B.可根據(jù)此式構(gòu)造，這里Ii為鄰域索引；第三步，得到全部嵌入坐標.對B進行特征分解，選取對應于第2個到第d+1個最小的特征值構(gòu)造成向量矩陣[u2,...,ud+1],則最終的嵌入坐標為T=[u2,...,ud+1]T.除了這兩種算法，本類算法包括局部模型排列算法(ALM)[11]、局部線性坐標算法等.這些算法基本思想都是在局部分析后提取信息，在排列中使得這些信息在整體低維坐標中得到最大化保留.1.3新的降維方法——壓縮感知隨著人們對信息需求量的增加，基于數(shù)據(jù)稀疏性提出一種新的采樣理論——壓縮感知(CompressedSensing,CS)，使得高維數(shù)據(jù)的采樣與壓縮成功實現(xiàn).該理論指出：只要數(shù)據(jù)在某個正交變換域中或字典中是稀疏的，那么就可以用一個與變換基不相關(guān)的觀測矩陣將變換所得高維數(shù)據(jù)投影到一個低維空間上，然后通過求解一個優(yōu)化問題從這些少量的投影中以高概率重構(gòu)出原數(shù)據(jù)，可以證明這樣的投影包含了重構(gòu)數(shù)據(jù)的足夠信息.假設(shè)有一數(shù)據(jù)f(fuRN),長度為N，基向量為叫(i=12...,N),對數(shù)據(jù)進行變換：顯然f是數(shù)據(jù)在時域的表示，a是數(shù)據(jù)在W域的表示.若(5)式中的a只有K個是非零值㈠K)且經(jīng)排序后按指數(shù)級衰減并趨近于零，可認為數(shù)據(jù)是稀疏的.如何找到數(shù)據(jù)的最佳稀疏表示是CS理論和應用的基礎(chǔ)前提.Candes和Tao[12]研究表明，具有幕次速度衰減的數(shù)據(jù)，可利用壓縮感知理論恢復，并且重構(gòu)誤差滿足下式假設(shè)數(shù)據(jù)是可壓縮的(原始數(shù)據(jù)在某變換域中可快速衰減)，則CS過程［13］可分為兩步：數(shù)據(jù)的低速采樣問題:找一個與變換基不相關(guān)的MxN(MN)維測量矩陣對數(shù)據(jù)進行觀測，保證稀疏向量從N維降到M維時，重要信息不被破壞.數(shù)據(jù)的恢復問題:設(shè)計一個快速重構(gòu)算法，由M維的測量向量重構(gòu)原始數(shù)據(jù).壓縮感知理論以數(shù)據(jù)具有稀疏性為基礎(chǔ)，有效緩解了高速采樣實現(xiàn)的壓力，達到了壓縮的目的，為處理、傳輸、存儲節(jié)約了大量的成本，這種新的采樣理論的研究已經(jīng)受到了多方關(guān)注，并取得了豐碩的成果.然而壓縮感知理論目前面臨的挑戰(zhàn)為：電路中易于實現(xiàn)的采樣矩陣的構(gòu)造；魯棒性強、算法復雜度低的恢復算法；非稀疏數(shù)據(jù)的稀疏化表示問題.壓縮感知理論作為一種新的降維方法已經(jīng)應用到數(shù)據(jù)處理等多個研究領(lǐng)域中，與此同時壓縮感知理論與機器學習等領(lǐng)域的內(nèi)在聯(lián)系的研究工作已經(jīng)展開.雖然上述各種數(shù)據(jù)降維算法被廣泛應用于許多領(lǐng)域中，但是它們具有各自的優(yōu)缺點，為了更好的應用這些算法，下面對這些算法的優(yōu)缺點做一個簡單的總結(jié).PCA算法是一種無監(jiān)督的學習方法，算法簡單，具有線性誤差等優(yōu)點，但存在下述缺點：存儲空間大，計算復雜度高，該算法中用到了線性映射也影響最后的效果，協(xié)方差矩陣的大小與數(shù)據(jù)點的維數(shù)成正比，導致了計算高維數(shù)據(jù)的特征向量是不可行的；LDA算法是一種有監(jiān)督的學習方法，可以用于分類工作，但對于樣本維數(shù)大于樣本數(shù)的奇異值問題很敏感；ISOMAP算法雖具有拓撲不穩(wěn)定性，計算復雜性大，對噪聲敏感的局限性，但仍是一種優(yōu)秀的方法，在許多研究領(lǐng)域被廣泛采用，并取得了良好的效果；LLE算法具有以下優(yōu)點：每個點的近鄰權(quán)重在平移、旋轉(zhuǎn)、縮放下保持不變；有解析的整體解，不需要進行迭代，復雜度較小，容易計算，但要求流形必須是不閉合且局部線性，要求觀測的數(shù)據(jù)要稠密，對噪聲也比較敏感；Laplacian特征映射的基本思想比較簡單，計算起來也簡單，但也要求觀測數(shù)據(jù)采樣稠密，對噪聲敏感性很大；一般情況下，基于局部分析的算法在流形上的噪音數(shù)據(jù)較多，流形上的曲率較大，流形上的維數(shù)較高等情況下發(fā)揮不了優(yōu)點，導致算法應用的失敗；壓縮感知算法是一種基于數(shù)據(jù)稀疏的優(yōu)化計算恢復數(shù)據(jù)的過程，利用隨機采樣陣除去了冗余數(shù)據(jù)和無用的數(shù)據(jù)，緩解了高速采樣的壓力，減少了處理、存儲、傳輸成本，不失為一種優(yōu)秀的降維方法，但面臨在噪聲背景下，魯棒性恢復算法的構(gòu)想難題.本文對現(xiàn)有的分類方法進行了系統(tǒng)的分類，并對幾種典型的線性和非線性降維方法進行了詳細地闡述，著重分析討論了一種新的降維方法即壓縮感知，并指出了該算法的特性.目前降維算法仍在研究中，下列幾個方面的研究值得關(guān)注：(1)非線性數(shù)據(jù)降維方法中都需要確定數(shù)據(jù)鄰域尺寸和本質(zhì)維數(shù)兩個參數(shù)，如何確定更好的參數(shù)使得這些方法得到最大程度的改進.(2)前邊提出的方法大多為局部方法，受噪音影響大，因此如何減少噪聲的干擾、提高算法的魯棒性是未來的研究方向.(3)現(xiàn)在的方法對動態(tài)增加的觀測數(shù)據(jù)點不能快速的映射到低維空間中，因此學習改進增量算法具有一定的研究價值.(4)建立非凸的目標函數(shù)，不僅僅依賴于模型化數(shù)據(jù)流形的局部結(jié)構(gòu)的鄰域圖，得到優(yōu)化解.【相關(guān)文獻】吳曉婷，閆德勤.數(shù)據(jù)降維方法分析與研究[J].計算機應用研究，2009，26(8):2832-2835.HOTELLINGH.Analysisofacomplexofstatisticalvariablesintoprincipalcomponents[J].JournalofEducationalPsychology,1993,24:417-441.FISHERRA.Theuseofmultiplemeasurementsintaxonomicproblems.AnnalsofEugenics[J].Annalsofeugenics,1936,7:179-188.TENENBAUMJB,SILVAVD,LANGFORDJC.Aglobalgeometricframeworkfononlineardimensionalityreduction[J].Science,2000,5500(290):2319-2323.ROWEISST,SAULLK.Nonlineardimensionalityreductionbylocallylinearembedding[J].Science,2000,5500(290):2323-2326.ZHANG/.Principalmanifoldsandnonlineardimensionalityreductionviatangentspacealignment[J].SIAMJournalonScientificComputing,2004.26(1):313-338.SCHOLKOPFB.Nonlinearcomponentanalysisasakerneleigenvalueproblem[J].NeuralComputation,1998,10:1299-1319.BELKINM,NIYOGIP.Laplacianeigenmapsandspectraltechniquesforembeddingandc