高維數(shù)據(jù)降維技術及研究進展

劉 靖，趙逢禹

(上海理工大學 光電信息與計算機工程學院，上海 200093)

隨著多媒體技術和計算機技術的高速發(fā)展，大規(guī)模的數(shù)據(jù)維度呈爆炸性增長。伴隨著數(shù)據(jù)維數(shù)的增長，使得目標函數(shù)優(yōu)化、參數(shù)估計、模型選擇變得越來越困難，這類問題已普遍地影響到諸多領域，如機器學習[1]、圖像處理[2]、模式識別[3]、文本分析[4]等，這種現(xiàn)象被稱為維度災難[5]。

維度災難帶來的問題主要表現(xiàn)在3個方面：(1)愈加增加的數(shù)據(jù)維數(shù)導致空間數(shù)據(jù)點分布更稀疏，使得空間的參數(shù)優(yōu)化越來越棘手；(2)維數(shù)的升高使得高維數(shù)據(jù)索引組織效果變差，數(shù)據(jù)節(jié)點的重疊性呈指數(shù)級遞增，導致數(shù)據(jù)檢索時，增加過多的訪問路徑，造成檢索效率低下；(3)高維數(shù)據(jù)處理對計算機的運算與存儲能力要求較高，目前計算機的運算與存儲能力仍不能完全滿足其運算與存儲要求。

上述問題給高維數(shù)據(jù)處理中的數(shù)據(jù)分析帶來了重大挑戰(zhàn)，同時維數(shù)的膨脹也給模式識別帶來了較大的困難。為降低、消除維度災難的影響，研究者提出了一系列的解決方法。為了準確把握降維技術的發(fā)展方向，本文研究了自2010年以來降維技術相關的大量國內外文獻，結果表明，近年來越來越多的研究者開始致力于降維技術的研究并取得了可觀的成果。

1 降維技術

降維技術旨在將高維數(shù)據(jù)映射到更低維的數(shù)據(jù)空間上以尋求數(shù)據(jù)緊湊表示，這種技術有利于對數(shù)據(jù)做進一步處理。例如在基于內容的圖像檢索中，將提取的高維圖像特征向量數(shù)據(jù)通過降維處理降低到一定的維度，則可以使用相關的索引機制組織數(shù)據(jù)以進行更高效的檢索。降維技術可用如下數(shù)學方式表達，設

(1)

其中，X為D維空間RD的一個數(shù)據(jù)集。通過降維技術找到一定的映射F：X→Y，使得

(2)

其中，Y為一個新的維度為d的數(shù)據(jù)集，且d

傳統(tǒng)降維技術通常在處理較低維度的數(shù)據(jù)集時非常有效，而對較高維度的數(shù)據(jù)集則很難得出有意義的分析[6]。近年來，人們對降維技術的理論研究和技術應用等各個方面都取得了長足的進步，新的降維技術被不斷提出，不同的技術各有所長，適用于不同的降維場景。

1.1 常見降維技術

目前研究者已陸續(xù)提出了多種降維技術，如線性判別分析法[7]、主成分分析法[8]、多維尺度分析法[9]、等。本文依據(jù)映射形式的分類，將現(xiàn)有的降維技術分為線性降維和非線性降維，圖1列出了典型的線性降維技術和非線性降維技術。

圖1 降維技術分類

1.2 線性降維技術

線性降維技術是出現(xiàn)最早的降維技術，特點是易于實現(xiàn)、快速簡單、不存在局部極值與相對有效性，因此得到了廣泛應用，下面介紹幾種典型的線性降維技術。

1.2.1 主成分分析

主成分分析(Principal Components Analysis，PCA)[8]是一種坐標變化技術，通過將數(shù)據(jù)集映射到一組新變量(主成分)上，并設置數(shù)據(jù)方差的閾值以舍棄方差較少的主成分，新得到的維度(主成分)為原維度的線性組合，并盡可能反映數(shù)據(jù)原有的信息，以達到降維目的。缺點是在降維過程中，需要人工選取主成分個數(shù)，如果選取不當將導致信息丟失。

1.2.2 線性判別分析

線性判別分析(Linear Discriminant Analysis，LDA)[6]也稱為Fisher判別分析，是一種有監(jiān)督降維方法。LDA通過找尋數(shù)據(jù)集中的投影矩陣，可以將高維數(shù)據(jù)投影到低維空間中，并使數(shù)據(jù)集在低維空間中同類數(shù)據(jù)區(qū)別最小化，異類數(shù)據(jù)區(qū)別最大化。目前該方法主要應用于高維數(shù)據(jù)的分類工作，由于降維過程中不能靈活的調整分解矩陣的大小，在分類中心有重疊時會得到較差的分類效果。

1.3 非線性降維技術

線性降維技術通常不能在真實數(shù)據(jù)集的降維過程中較好地保持數(shù)據(jù)集的非線性特性，因此研究者提出了非線性降維技術。非線性降維技術通常情況下是基于線性降維技術進行非線性的擴展或采用神經(jīng)網(wǎng)絡等方法來進行優(yōu)化降維，下面介紹幾種典型的非線性降維技術。

1.3.1 多維尺度分析

多維尺度分析(Multi-Dimensional Scaling，MDS)[6]分為度量MDS和非度量MDS。度量MDS確保降維后低維數(shù)據(jù)點之間的距離與原數(shù)據(jù)點之間的相對距離盡量保持一致，以盡可能保留數(shù)據(jù)對象間的相似性，其降維過程中距離函數(shù)的選擇具有靈活性。非度量MDS旨在確保降維前后數(shù)據(jù)對象間順序關系一致性，而非數(shù)據(jù)對象間的相對距離。

1.3.2 局部線性嵌入

局部線性嵌入(Local Linear Embedding，LLE)[10]是一種突破傳統(tǒng)降維方式的非線性降維模式，很多后續(xù)的流形學習和降維技術都與LLE有著緊密的聯(lián)系。LLE的主要思想是將數(shù)據(jù)集視作是由大量相互鄰接的局部線性塊連接形成，這種局部線性塊可以較好的描述原數(shù)據(jù)集的特征屬性，從而實現(xiàn)降維。LLE的提出進一步地擴展了研究者關于降維的認識，并提出了一系列的LLE變體。如拉普拉斯特征映射(Laplacian Eigenmaps)[11]的主要思想是先將數(shù)據(jù)集中的數(shù)據(jù)點與其最近鄰居連接構建一個鄰居圖，并對圖的每條邊賦予相應的權值，接著尋求數(shù)據(jù)集的嵌入坐標表示，保證嵌入坐標的平方距離最小，從而得到最優(yōu)的低維表示向量。

1.4 近年推出的降維技術

隨著降維技術的不斷研究與應用，降維技術的理論框架已逐步形成。現(xiàn)有的降維技術已取得了可觀的研究成果，近幾年對于降維技術的研究，主要集中于原有算法的改進和延伸方面。

1.4.1 自適應線性數(shù)據(jù)降維技術

YN.Jeng等[12]基于元學習(Meta-learning)提出一種自適應線性數(shù)據(jù)降維算法。該算法針對數(shù)據(jù)的類型和特點，引入元學習和選擇統(tǒng)計的方法作為數(shù)據(jù)集的構造和分類規(guī)則，以達到降維過程中的分類錯誤率。該算法的優(yōu)點是適用于多種數(shù)據(jù)類型，且降維分類過程是是自適應的，缺點則是在處理含有較多異常值的數(shù)據(jù)集時性能較差。

1.4.2 基于統(tǒng)計相關的數(shù)據(jù)降維技術

A.Ramdas等[13]基于統(tǒng)計相關的方法，提出一種可應用最鄰近分類的算法，該算法中提出的內在距離是其他擴散距離的概念相似，是變量間相關統(tǒng)計方法的拓展。該算法已應用于真實數(shù)據(jù)集中，相比其他統(tǒng)計相關算法具有更好的穩(wěn)定性和分類效果。對于該算法中提出用于表示鄰里演變的連接程度的參數(shù)t，其選取和理論解釋不夠明確，仍需要進一步進行試驗驗證。

1.4.3 其它降維技術

除了上述討論的降維技術外，近年來還出現(xiàn)了多種降維技術。如線性降維方面的潛在語義索引(Latent Semantic Index，LSI)[14]、投影尋蹤(Projection Pursuit，PP)[15]、子分析(Factor Analysis，F(xiàn)A)[16]、獨立成分分析(Independent Components Analysis，ICA)[17]等方法。非線性降維方面則有核主成分分析(Kernel PCA，KPCA)[18]、等距映射(Isometric Mapping，Isomap)[19]、形[20]、局部線性協(xié)同(Locally Linear Coordination，LLC)[21]、Manifold Learning[22]等方法。

2 性能分析

本文對幾種典型高維數(shù)據(jù)降維技術的性能進行了分析整理，如表1所示。這些算法應用廣泛，主要集中在分類和聚類領域。由于各算法的應用領域不同，使得性能優(yōu)缺點差異較大，研究者需要根據(jù)實際情況進行適當?shù)倪x擇，并針對算法不足進行性能改進。

表1 典型降維技術性能

根據(jù)式(1)降維得到式(2)，T(n)為時間復雜度，S(n)為空間復雜度，i為迭代次數(shù)，k為Isomap近鄰點個數(shù)，w與m為Auto-encoder的權值和網(wǎng)絡大小。

3 未來研究方向

隨著科技的進步，出現(xiàn)了越來越多復雜的真實數(shù)據(jù)，呈現(xiàn)給研究者處理分析相關數(shù)據(jù)及問題的挑戰(zhàn)也愈加巨大?，F(xiàn)有降維技術的研究為快速有效地處理高維數(shù)據(jù)提供了一定的便利，已經(jīng)取得了較大的成果，但還有很多研究問題的處理效率有待提升。

3.1 流形學習降維

目前流形學習方法[22]難以在應用上進行推廣，原因在于該類方法并未建立高維流形數(shù)據(jù)與映射后低維數(shù)據(jù)之間的映射關系，使得無法獲得新輸入的高維數(shù)據(jù)與低維結果數(shù)據(jù)之間的映射表示。

3.2 超高維數(shù)據(jù)降維

目前降維技術在處理不同領域的較低維度數(shù)據(jù)(維度<50)時效率很好，但是在較高維度(維度>50)的處理效果仍有待提高。

3.3 自適應能力

目前降維技術對動態(tài)變化的數(shù)據(jù)集難以實現(xiàn)快速高效的降維，由于真實環(huán)境中數(shù)據(jù)的復雜性(非線性數(shù)據(jù))與受噪聲影響較大等原因，如何提高算法的魯棒性，降低噪聲和奇異值對數(shù)據(jù)的影響，提高降維算法的自適應性與降維結果的有效性是今后研究的重點。

4 結束語

本文圍繞降維技術將高維數(shù)據(jù)中的降維問題分為線性降維和非線性降維，進行分類描述，介紹了近年來降維技術的研究成果，為更好的推廣使用這些技術，對經(jīng)典降維技術進行了性能分析，指出其優(yōu)缺點。根據(jù)降維技術當前仍然存在的問題，展望了未來研究的方向。盡管降維技術原本是伴隨著多媒體數(shù)據(jù)處理和數(shù)據(jù)挖掘中數(shù)據(jù)預處理這一領域出現(xiàn)的，但降維技術獨特的理念給研究者在處理解決各類問題都提供了一個新的思路和方法，所以未來將產生更多的降維技術研究成果。

[1] Rosten E,Drummond T.Machine learning for high-speed corner detection[M].Berlin:Computer Vision-ECCV,Springer Heidelberg,2006.

[2] Stommel M,Herzog O.SIFT-based object recognition with fast alphabet creation and reduced curse of dimensionality[C]. New Zealand: International Conference on Image and Vision Computing,2009.

[3] Qin H,Tang S.A solution to dimensionality curse of BP network in pattern recognition based on RS theory[C].Sanya:International Joint Conference on Computational Sciences and Optimization,2009.

[4] Gao M T,Wang Z O.A new algorithm for text clustering based on projection pursuit[C].Beijing:International Conference on Machine Learning and Cybernetics,IEEE,2007.

[5] Erchtold S,B?hm C,Kriegal H P.The pyramid-technique: towards breaking the curse of dimensionality[J].ACM SIGMOD Record,1998,27(2):142-153.

[6] Zhu X,Zhang S,Jin Z,et al.Missing value estimation for mixed-attribute data sets[J].IEEE Transactions on Knowledge & Data Engineering,2011,23(1):110-121.

[7] Alavi A H,Gandomi A H.A robust data mining approach for formulation of eotechnical engineering systems[J]. Engineering Computations,2011,28(3):242-274.

[8] 黃華盛,楊阿慶.基于PCA算法的人臉識別[J].電子科技,2015,28(8):98-101.

[9] Rachev B,Smrikarov A.Proceedings of the 9th international conference on computer systems and technologies and workshop for PhD students in computing[C].Russia:International Conference on Computer Systems and Technologies and Workshop for Phd Students in Computing,ACM,2008.

[10] Li B, Zhang Y. Supervised locally linear embedding projection (SLLEP) for machinery fault diagnosis[J].Mechanical Systems & Signal Processing,2011,25(8):3125-3134.

[11] Wang J.Geometric structure of high-dimensional data and dimensionality reduction[M].Berlin:Springer Heidelberg,2012.

[12] Jeng Y N,Lin S Y,Lee Z S. Smoothing of the multiple one-dimensional adaptive grid procedure[J].Aiaa Journal,2015, 38(38):2353-2355.

[13] Ramdas A, Reddi S J, Poczos B, et al. Adaptivity and computation-statistics tradeoffs for kernel and distance based high dimensional two sample testing[J]. Statistical Applications in Genetics & Molecular Biology,2015,12(6):1-12.

[14] Zheng W. Dimensionality reduction by combining category information and latent semantic index for text categorization[J].Journal of Information & Computational Science,2013, 10(8):2463-2469.

[15] Schimek M G.Projection pursuit regression[M].NewYork:John Wiley & Sons,Inc.,2012.

[16] Cady B, Sedgwick C E, Meissner W A,et al.Risk factor analysis in differentiated thyroid cancer[J].Cancer, 2015,43(43):810-820.

[17] Lacerda G,Spirtes P L,Ramsey J,et al. Discovering cyclic causal models by independent components analysis[C].Grace:Uncertainty in Artificial Intelligence,2012.

[18] Alzate C,Suykens J A K.Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2010,32(2):335-347.

[19] Zhang N,Tian X M.Nonlinear dynamic fault detection method based on isometric mapping[J].Journal of Shanghai Jiaotong University,2011,45(8):1202-1206.

[20] Zhang Z,Chow T W S,Zhao M. Trace ratio optimization-based semi-supervised nonlinear dimensionality reduction for marginal manifold visualization[J].IEEE Transactions on Knowledge & Data Engineering,2013,25(5):1148-1161.

[21] Hong Huang,Jianwei Li,Hailiang Feng. Subspaces versus submanifolds:a comparative study in small sample size problem[J].International Journal of Pattern Recognition & Artificial Intelligence,2011,23(3):463-490.

[22] Saini S,Rambli D R B A,Sulaiman S B,et al.Markerless multi-view human motion tracking using manifold model learning by charting[J].Procedia Engineering,2012(41):664-670.