流式數(shù)據(jù)的動(dòng)態(tài)正交降維算法

陳新元，謝晟祎，陳慶強(qiáng)，劉 羽

(1.福州墨爾本理工職業(yè)學(xué)院信息工程系，福建 福州 350108；2.福建農(nóng)業(yè)職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)實(shí)訓(xùn)中心，福建 福州 350181；3.福建工程學(xué)院信息科學(xué)與工程學(xué)院，福建 福州 350118；4.福州墨爾本理工職業(yè)學(xué)院現(xiàn)代教育技術(shù)中心，福建 福州 350108)

0 引言

近年來(lái)，各行各業(yè)持續(xù)發(fā)展，與信息技術(shù)的融合逐漸加強(qiáng)，相關(guān)數(shù)據(jù)規(guī)模不斷提升，維數(shù)增加，稀疏性增強(qiáng)，處理數(shù)據(jù)的難度和計(jì)算量不斷提高，導(dǎo)致“維數(shù)災(zāi)難”[1]。數(shù)據(jù)降維作為重要的表示技術(shù)，可去除無(wú)關(guān)信息、提升數(shù)據(jù)質(zhì)量并降低數(shù)據(jù)存儲(chǔ)和計(jì)算代價(jià)[2]，是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、計(jì)算機(jī)視覺(jué)等方向不可或缺的工具，在工程、商業(yè)等領(lǐng)域也有著廣泛應(yīng)用[3]。

主流降維方法可分為特征選擇和特征變換[4]，前者根據(jù)先驗(yàn)信息和人工經(jīng)驗(yàn)從屬性集中提取特征子集，主要關(guān)注泛化能力和計(jì)算開銷；后者評(píng)價(jià)體系類似，但強(qiáng)調(diào)特征的變換和映射，可分為線性方法和非線性方法。線性方法如非負(fù)矩陣分解(NMF)[5]、主成分分析法(PCA)[6-7]、線性判斷分析(LDA)[8]等，多忽略數(shù)據(jù)的流形結(jié)構(gòu)；非線性算法如核方法(KPCA)[9]、多維縮放方法(MDS)[10]、ISOMAP[11-12]、SNE[13]、t-SNE[14]、隨機(jī)投影(ROP)[15-16]等，計(jì)算開銷較大，但能更好地保持流形結(jié)構(gòu)；上述方法多在傳統(tǒng)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。

降維的難點(diǎn)之一在于選取維度；而行業(yè)數(shù)據(jù)流往往具有維數(shù)規(guī)模較大、持續(xù)動(dòng)態(tài)增長(zhǎng)、初期核心特征不明等特點(diǎn)，近年來(lái)許多研究使用增量模型等方法處理實(shí)時(shí)數(shù)據(jù)流[17]。

鑒于目前尚無(wú)完善的流式數(shù)據(jù)處理方案，本文提出動(dòng)態(tài)正交降維算法(dynamic orthogonal analysis for dimension reduction，DOADR)通過(guò)優(yōu)化的正交分解實(shí)現(xiàn)快速線性降維，使用低開銷的自適應(yīng)閾值函數(shù)動(dòng)態(tài)調(diào)整維度規(guī)模映射空間，最后針對(duì)流式數(shù)據(jù)的特點(diǎn)優(yōu)化自適應(yīng)閾值，提出增量DOADR算法(incremental DOADR，IDOADR)。真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，如計(jì)算開銷、重構(gòu)誤差，分類準(zhǔn)確率等指標(biāo)得分驗(yàn)證了算法的可行性。

1 相關(guān)工作

為提高數(shù)據(jù)分析能力，需要從高維數(shù)據(jù)中分辨出關(guān)鍵特征，即φ:d→k(k

線性算法往往需要計(jì)算矩陣特征值，進(jìn)行多次迭代，因此內(nèi)在維數(shù)的判斷對(duì)計(jì)算開銷和降維結(jié)果影響較大；非線性算法則關(guān)注低維流形結(jié)構(gòu)到高維特征空間中的嵌入，如KPCA將數(shù)據(jù)轉(zhuǎn)換到高維空間，實(shí)現(xiàn)線性可分，再映射到低維空間提取主成分。難點(diǎn)在于核函數(shù)的選擇。趙孝禮等結(jié)合KPCA和局部判別分析，兼顧全局特征信息和局部判別信息[21]。MDS是一種全局降維算法，計(jì)算原始數(shù)據(jù)集中任意兩點(diǎn)間的歐式距離，通過(guò)局部結(jié)構(gòu)構(gòu)建全局結(jié)構(gòu)[10]。ISOMAP可視為其改進(jìn)版本，對(duì)于鄰域外的樣本，使用測(cè)地距離替換歐式距離以保留流形結(jié)構(gòu)[11]。SNE和t-SNE引入了條件概率以判斷相似度，算法對(duì)于局部最優(yōu)陷阱有一定的規(guī)避能力[13-14]。ROP通過(guò)隨機(jī)生成的矩陣將原始數(shù)據(jù)從d維映射至k維(k

關(guān)于降維的性能度量指標(biāo)，Antoniadis A等將降維與非參數(shù)判別結(jié)合，通過(guò)分類性能進(jìn)行驗(yàn)證[24]；Laohakiat S等將降維融入聚類框架，最后驗(yàn)證方案的聚類性能和整體時(shí)間開銷[25]。本文使用降維后的分類準(zhǔn)確率驗(yàn)證算法性能。

在流式數(shù)據(jù)的降維研究上，F(xiàn)eng J等提出實(shí)時(shí)PCA算法，通過(guò)批量子空間計(jì)算降低數(shù)據(jù)加載的時(shí)間開銷，提升算法在稀疏數(shù)據(jù)上的魯棒性[26]；Malik Z K等使用基于流形的增量LE算法處理廣義特征值問(wèn)題，但沒(méi)有考慮計(jì)算復(fù)雜度[27]；Souilem N等基于優(yōu)化的核希爾伯特空間模型算法提出一種在線識(shí)別非線性系統(tǒng)的方案[28]；Lois B等針對(duì)子空間穩(wěn)定的監(jiān)控?cái)?shù)據(jù)流，在稀疏矩陣上通過(guò)優(yōu)化最初子空間提高了PCA算法的魯棒性[29]；Pehlevan C等將行業(yè)數(shù)據(jù)規(guī)則與MDS結(jié)合進(jìn)行權(quán)重學(xué)習(xí)，對(duì)成本函數(shù)進(jìn)行改進(jìn)，提高了神經(jīng)網(wǎng)絡(luò)的分類表現(xiàn)，但算法的時(shí)間開銷較高[30]；Han L等提出了多線性主成分分析算法，并證明其在處理最大化散布張量矩陣時(shí)總是收斂至穩(wěn)定值[31]；單燕等提出了基于PCA的數(shù)據(jù)流降維算法，使用滑動(dòng)窗口和概要結(jié)構(gòu)適應(yīng)流，在Storm平臺(tái)上實(shí)現(xiàn)并行計(jì)算[32]；吳楓等在KPCA的基礎(chǔ)上提出了增量核主成分分析方法，同時(shí)結(jié)合神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)分類框架[33]；Zhu T等通過(guò)正交成分提取，以較低的計(jì)算成本實(shí)現(xiàn)流式數(shù)據(jù)的低維表示[34]。本文在此基礎(chǔ)上進(jìn)行優(yōu)化設(shè)計(jì)。

2 DOADR

傳統(tǒng)的正交成分分析將線性降維轉(zhuǎn)化為矩陣分解，設(shè)原數(shù)據(jù)集表示為X={x1, …,xN}∈d×k，使用VY近似X，V是規(guī)模為d×k的基底矩陣，Y為k×n系數(shù)矩陣；V決定了特征子空間S的表示。V的學(xué)習(xí)需要考慮k值和各基底的表示。

定義向量x相對(duì)于向量系v1, …,vk的線性獨(dú)立性表示為‖r(k)‖2，如式1所示：

(1)

(2)

其中，N可以是常量或變量，用于對(duì)閾值進(jìn)行修正。若數(shù)據(jù)集已知，N可以用極值或區(qū)域極值代替；反之考慮動(dòng)態(tài)變化。

Algorithm 1 DOADR

算法分析：

1)選擇元素的參與分量彼此正交，而‖r(k)‖2單調(diào)遞減，故該過(guò)程可視為矩陣的QR分解[36]。

3 IDOADR

針對(duì)行業(yè)數(shù)據(jù)快速更新且需要進(jìn)行實(shí)時(shí)處理的特點(diǎn)，提出增量改進(jìn)方案，基本原則與DOADR算法一致，但針對(duì)數(shù)據(jù)流，具體如Algorithm 2所示。

Algorithm2 IDOADR

IDOADR算法與DOADR算法相似，開始時(shí)S空間都為空，區(qū)別在于一旦出現(xiàn)1次閾值不滿足，DOADR算法即停止，而IDOADR算法一直持續(xù)到數(shù)據(jù)流終止。

算法分析：

1)算法主要優(yōu)勢(shì)在于對(duì)每個(gè)輸入都只處理1次，判定是否提取基底，獲取其低維表示，因此計(jì)算復(fù)雜度較低，仍為O(kNd)。

2)算法缺點(diǎn)在于使用貪婪策略學(xué)習(xí)特征空間，受到數(shù)據(jù)輸入順序影響較大。

4 實(shí)驗(yàn)與分析

4.1 人工數(shù)據(jù)集實(shí)驗(yàn)

隨機(jī)生成d0維的一組正交基，結(jié)合標(biāo)準(zhǔn)正態(tài)分布的系數(shù)生成基本數(shù)據(jù)集，加入一定比例的高斯噪聲后，使用6種閾值函數(shù)，比較其從d0降至d維的S空間的實(shí)際維數(shù)d和距離dis。實(shí)驗(yàn)數(shù)據(jù)集分別取d0=30,d=10；d0=100,d=10和d0=100,d=30，結(jié)果取10次平均值，如表1所示。

表1 DOADR算法上不同閾值函數(shù)的降維性能比較

結(jié)果表明：閾值函數(shù)越嚴(yán)格，k越?。籨0越大，d越大。f(x)=x在所有條件下的特征維數(shù)估計(jì)和dis值都較穩(wěn)定。

離群點(diǎn)很可能被先用于基底提取，因此實(shí)驗(yàn)嘗試在數(shù)據(jù)集中加入離群點(diǎn)并判斷其對(duì)最終特征空間S的影響。結(jié)果表明部分函數(shù)如f(x)=x受影響顯著；而f(x)=x2受的影響小得多。因此，若考慮離群點(diǎn)，可選擇寬松閾值函數(shù)；當(dāng)原始數(shù)據(jù)集的維數(shù)較大時(shí)，應(yīng)選擇嚴(yán)格閾值函數(shù)，同時(shí)對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，篩除離群點(diǎn)。

在相同條件下對(duì)IDOADR算法降維后的d和dis進(jìn)行比較，參數(shù)設(shè)置和方法相同，結(jié)果如表2所示。此時(shí)估計(jì)的維數(shù)普遍略大于DOADR。無(wú)論基底提取還是誤差計(jì)算，f(x)=x的表現(xiàn)都較好，因此作為后續(xù)實(shí)驗(yàn)的閾值函數(shù)。

表2 IDOADR算法上不同閾值函數(shù)的降維性能比較

4.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

算法特征比較如表3所示。

表3 主流算法特征比較

在6個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，其基本信息如表4所示，考慮PCA和ROP需要設(shè)定多個(gè)k值測(cè)其結(jié)果曲線，故將數(shù)據(jù)集劃分為訓(xùn)練樣本和測(cè)試樣本；DOADR使用10折交叉驗(yàn)證取平均結(jié)果；IDOADR使用流式數(shù)據(jù)輸入。

表4 數(shù)據(jù)集統(tǒng)計(jì)信息

降維后使用KNN分類，記錄準(zhǔn)確率；使用平均相對(duì)重構(gòu)誤差E作為質(zhì)量指標(biāo)(式3)。分類準(zhǔn)確率和E的結(jié)果如圖1、圖2所示，橫軸為k值，縱軸分別為分類準(zhǔn)確率和E。PCA和ROP的降維結(jié)果以曲線表示，DOADR和IDOADR可以動(dòng)態(tài)調(diào)整k值，故圖中以點(diǎn)表示。

圖2 平均相對(duì)重構(gòu)誤差比較

圖1 分類準(zhǔn)確率比較

(3)

考慮到DOADR和IDOADR的主要目的是對(duì)大規(guī)模數(shù)據(jù)進(jìn)行快速降維和自適應(yīng)特征空間調(diào)整，其分類準(zhǔn)確率可以接受；在多數(shù)數(shù)據(jù)集上，其收斂的k值較小。

在4個(gè)數(shù)據(jù)集上，DOADR的重構(gòu)誤差小于對(duì)應(yīng)k值的PCA和ROP；IDOADR收斂略慢，k值略大，可能是因?yàn)槌霈F(xiàn)了無(wú)關(guān)或錯(cuò)誤基底，但影響不明顯，且整體重構(gòu)誤差低于DOADR。

4種算法的計(jì)算開銷如表5所示，PCA和ROP取k值∈[20%d0, 80%d0]的時(shí)間均值，DOADR的時(shí)間開銷明顯低于PCA和ROP，而IDOADR只需對(duì)數(shù)據(jù)作1次遍歷，不需要先遍歷數(shù)據(jù)集查找極值，相比DOADR又有明顯降低。當(dāng)k值不確定時(shí)，PCA和ROP需要根據(jù)先驗(yàn)信息，或多次迭代調(diào)整設(shè)置，才能取得較好的結(jié)果，因而DOADR和IDOADR的優(yōu)勢(shì)明顯。

表5 算法時(shí)間開銷

考慮到離群點(diǎn)的影響，實(shí)驗(yàn)選取孤立森林(IF，因數(shù)據(jù)集維數(shù)在其優(yōu)勢(shì)區(qū)間且行業(yè)數(shù)據(jù)離群點(diǎn)比例容易獲得)和PCA進(jìn)一步實(shí)現(xiàn)異常檢測(cè)，兩者Precision和AUC得分接近，維數(shù)較低時(shí)后者的時(shí)間開銷明顯低于IF，參數(shù)設(shè)置與結(jié)果略。

5 結(jié)語(yǔ)

降維算法是數(shù)據(jù)處理的支撐技術(shù)之一。信息時(shí)代的行業(yè)數(shù)據(jù)具有維度大、增長(zhǎng)快等特點(diǎn)，但目前流式數(shù)據(jù)的處理方案尚不完善，因此本文引入施密特正交以實(shí)現(xiàn)快速線性降維，通過(guò)線性獨(dú)立性的定義選取正交基底，針對(duì)先驗(yàn)信息缺少、維數(shù)k不明確的環(huán)境設(shè)計(jì)了動(dòng)態(tài)自適應(yīng)的閾值函數(shù)以動(dòng)態(tài)調(diào)整特征空間映射，最后根據(jù)流式數(shù)據(jù)的特點(diǎn)優(yōu)化閾值設(shè)置。實(shí)驗(yàn)在人工數(shù)據(jù)集上比較了不同自適應(yīng)函數(shù)的降維性能，將選擇結(jié)果應(yīng)用于真實(shí)數(shù)據(jù)集，通過(guò)分類準(zhǔn)確率、誤差和時(shí)間開銷等指標(biāo)驗(yàn)證了DOADR和IDOADR相比主流算法的優(yōu)勢(shì)。未來(lái)工作計(jì)劃包括：將異常檢測(cè)機(jī)制集成至降維框架，特別是實(shí)現(xiàn)IDOADR的實(shí)時(shí)離群檢測(cè)算法設(shè)計(jì)；結(jié)合生成式對(duì)抗網(wǎng)絡(luò)(GAN)模型進(jìn)行噪聲識(shí)別；算法的并行性能優(yōu)化以及在更大規(guī)模真實(shí)數(shù)據(jù)集上的驗(yàn)證。