基于粒度理論的高維數(shù)據(jù)流并行計(jì)算方法

路 晶，胡順仿

(1. 中國民用航空飛行學(xué)院，四川 廣漢 618307；2. 云南民族大學(xué)，云南 昆明 650000)

1 引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)庫、通信等技術(shù)的高速發(fā)展，導(dǎo)致了信息數(shù)量的爆炸性增長，許多領(lǐng)域出現(xiàn)了高速產(chǎn)生、動態(tài)變化的流式數(shù)據(jù)[1]，如銷售業(yè)務(wù)中的交易數(shù)據(jù)流、金融市場的交易數(shù)據(jù)流、環(huán)境監(jiān)測的實(shí)時數(shù)據(jù)流都以高維屬性發(fā)揮各自的作用，研究人員稱這種類型的數(shù)據(jù)為高維數(shù)據(jù)流[2，3]。由于高維數(shù)據(jù)流的應(yīng)用逐漸廣泛，如何在具備關(guān)聯(lián)性的高維數(shù)據(jù)流之間進(jìn)行并行計(jì)算成為了目前研究的熱點(diǎn)[4]。

許多相關(guān)學(xué)者對此進(jìn)行了大量研究，目前，常用的數(shù)據(jù)流計(jì)算處理方法主要有基于GPU并行處理的大規(guī)模連續(xù)潮流批量計(jì)算方法和基于分治法求解對稱三對角矩陣特征問題的MPI/Cilk混合并行方法，雖然都獲得了一定的研究成果，但是上述方法主要面向傳統(tǒng)類型的靜態(tài)數(shù)據(jù)，數(shù)據(jù)只能勻速到達(dá)且到達(dá)次序不獨(dú)立，還要受系統(tǒng)控制，當(dāng)數(shù)據(jù)流數(shù)量以及類別增多時，存在計(jì)算精度低和計(jì)算效率慢的問題。在此背景下，研究效率更高的高維數(shù)據(jù)流并行計(jì)算方法顯得尤為重要[5-7]。

因此，提出基于粒度理論的高維數(shù)據(jù)流并行計(jì)算方法，該方法主要包括四個部分，一是挖掘高維數(shù)據(jù)流，利用粒度理論可逐漸降低數(shù)據(jù)流環(huán)境的復(fù)雜性，可對數(shù)據(jù)進(jìn)行更有效的分析處理。二是利用基于局部保持投影(LPP)原理和主成分分析(PCA)原理對數(shù)據(jù)噪聲進(jìn)行壓制，使數(shù)據(jù)流可以進(jìn)一步處理。三是利用皮爾遜積差系數(shù)及其數(shù)學(xué)特性中的皮爾遜積差相關(guān)系數(shù)使數(shù)據(jù)流之間進(jìn)行關(guān)聯(lián)。最后在數(shù)據(jù)流十字轉(zhuǎn)門模型的基礎(chǔ)上，定義適合高維數(shù)據(jù)流分析的滑動數(shù)據(jù)流窗口模式，使高維數(shù)據(jù)流能進(jìn)行有效的并行計(jì)算。

2 基于粒度理論的高維數(shù)據(jù)流并行計(jì)算方法

2.1 基于動態(tài)粒度的數(shù)據(jù)流挖掘模型

基于動態(tài)粒度的數(shù)據(jù)流挖掘模型是結(jié)合粒度理論和數(shù)據(jù)流的特性組成的模型，如圖1所示。第一部分是圖中虛線框內(nèi)部分表示在線挖掘數(shù)據(jù)流，第二部分是對在線部分的挖掘結(jié)果進(jìn)行分析與更新維護(hù)，又稱為離線分析[8]。

圖1 基于動態(tài)粒度的數(shù)據(jù)流挖掘模型

原始數(shù)據(jù)流由DS(data Stream)描述[9]，涵蓋數(shù)據(jù)預(yù)處理，數(shù)據(jù)粒度塑造、詳細(xì)挖掘任務(wù)的行動(如分類、聚類、關(guān)聯(lián)規(guī)則等)，整體稱為數(shù)據(jù)挖掘過程，用Data Minging描述涵蓋保存、修正以及檢索在線結(jié)果，即修正、保存與檢索中間結(jié)果集稱為在線挖掘結(jié)果，用On-line Result指代[10]。持續(xù)解析和修訂在線挖掘結(jié)果稱為離線分析，用Off-line Analysis表示。修正、保存與檢索最后結(jié)果集稱為最終挖掘結(jié)果，用Final result描述。

形成新數(shù)據(jù)后，再次遍歷檢索全部數(shù)據(jù)，會耗費(fèi)過多的資源與時間[11]，這是由于數(shù)據(jù)流中數(shù)據(jù)量產(chǎn)生速度過快且數(shù)據(jù)量巨大，這并不符合數(shù)據(jù)流挖掘?qū)λ俣群蛯?shí)用性的需求。為了高效率修正挖掘結(jié)果，利用增量式修正方法處理新加入的數(shù)據(jù)[12]。

2.2 基于LPP和PCA的數(shù)據(jù)噪聲抑制

在數(shù)據(jù)流挖掘模型的基礎(chǔ)上，提出基于局部保持投影(LPP)+主成分分析(PCA)方法，LPP(利用LPP重構(gòu)特性，并非降維特性)對數(shù)據(jù)采樣點(diǎn)進(jìn)行重新構(gòu)建，獲取最佳重構(gòu)權(quán)值矩陣，逐漸減小噪聲隱患，實(shí)現(xiàn)涵蓋非線性的彎曲或傾斜同相軸數(shù)據(jù)去噪處理。

依據(jù)PCA特性，使用PCA分解后的隨機(jī)噪聲擁有不相關(guān)性，數(shù)據(jù)有效信號分解后擁有較好的相關(guān)性，所以PCA分解特征值較小，數(shù)據(jù)有效信號分解后特征值很大。由上述可知，為完成抑制隨機(jī)噪聲的需求，PCA可依據(jù)該特征從大量數(shù)據(jù)之中查詢同相軸，重新構(gòu)建特征向量，獲得主成分中最主要的部分，將小特征值的隨機(jī)噪聲數(shù)據(jù)刪除。設(shè)置數(shù)據(jù)流的個數(shù)是D，采樣點(diǎn)集合為X=[x1，x2，…xN]。數(shù)據(jù)流進(jìn)行LPP重構(gòu)和PCA特征值分解過程如下：

1)用以下公式計(jì)算每個采樣點(diǎn)xi的k(k

(1)

2)依據(jù)LPP算法確認(rèn)權(quán)重，與數(shù)據(jù)集X相應(yīng)的對稱稀疏權(quán)值矩陣為Sm×m，其通過xi到xj的權(quán)值Sij=e-‖xi-xj‖2/t計(jì)算得出。

4)基于數(shù)據(jù)X*進(jìn)行PCA線性變換，用線性正交變換矩陣W描述Y的線性組合，即重構(gòu)結(jié)果X′

(2)

式中，ui表示矩陣U的列；yi表示矩陣Y的行，特征數(shù)據(jù)與特征值λi相對應(yīng)。基于特征數(shù)據(jù)的加權(quán)組合重構(gòu)獲得原信號，進(jìn)而通過式(2)獲取隨機(jī)噪聲的抑制結(jié)果。

LPP向線性化處理變化是因k值過高，LPP原高維空間中的分布結(jié)構(gòu)特性難以保證是由于k值較低，因此，選取采樣點(diǎn)最鄰k值在LPP重構(gòu)流程中十分重要。把PCA的前K個最大特征值(根據(jù)特征值解析算出)固定在90%能量采集范圍內(nèi)，以確保有效信號盡可能完整。為不影響提取維度，LPP算法只在LPP+PCA算法重新構(gòu)造過程中使用。LPP+PCA方法去噪流程見圖2。

圖2 基于LPP+PCA的數(shù)據(jù)去噪處理流程圖

2.3 高維數(shù)據(jù)流相關(guān)性并行計(jì)算方法

2.3.1 皮爾遜積差系數(shù)及其數(shù)學(xué)特性

表達(dá)兩個隨機(jī)變量之間線性關(guān)系的強(qiáng)度和方向稱為相關(guān)系數(shù)(correlation，或稱關(guān)聯(lián)系數(shù))，其屬于概率論和統(tǒng)計(jì)學(xué)內(nèi)容。衡量數(shù)據(jù)的相關(guān)系數(shù)大部分要依據(jù)數(shù)據(jù)的特性，利用皮爾遜積差相關(guān)系數(shù)研究數(shù)據(jù)特性。統(tǒng)計(jì)意義上兩組數(shù)據(jù)的關(guān)聯(lián)性，若n維(n≥1)元素是xi，n維元素映射的數(shù)據(jù)函數(shù)是F(xi)、G(xi)

(3)

(4)

兩組n維變化數(shù)據(jù)的關(guān)聯(lián)性可由上述式(5)獲得

(5)

通過柯西-施瓦茨不等式可知，相關(guān)系數(shù)的絕對值低于1，實(shí)時比較過程中，即當(dāng)τ=0時，相關(guān)系數(shù)接近1或-1，因兩個變量的線性關(guān)系增高而發(fā)生，相關(guān)系數(shù)大于0是由一個變量增加而另一變量也增加的原因?qū)е?，相關(guān)系數(shù)小于0是由一個變量增加而另一變量減少的原因?qū)е拢嚓P(guān)系數(shù)為0因兩個變量獨(dú)立而發(fā)生，如果兩個變量不獨(dú)立，相關(guān)系數(shù)則不為0，這些判定都由柯西-施瓦茨不等式得到。解析單條數(shù)據(jù)流自身的屬相相關(guān)性和其變化周期性可在F=G的條件下完成。

2.3.2 高維數(shù)據(jù)流并行計(jì)算的實(shí)現(xiàn)

定義適應(yīng)高維數(shù)據(jù)流分析的滑動數(shù)據(jù)流窗口模式需依據(jù)數(shù)據(jù)流十字轉(zhuǎn)門模型，高維信號X到實(shí)數(shù)集上的一個映射X[1，2，…，N]→Rp是高維數(shù)據(jù)流a1，a2，…，ai，即向一個列向量中映射一條高維數(shù)據(jù)。差異時刻的數(shù)據(jù)流內(nèi)某一個屬于值X[j]的修正值用單個ai描述，一個修正元祖用ai=(j，Δi)描述，它的意義為xi[j]=Xi-1[j]+Δi，說明時刻t的p維修正向量滿足十字轉(zhuǎn)門模型。根據(jù)時間戳i的增高流入，僅可讀取1次向量Δi，涵蓋最近n項(xiàng)元素的序列ai-n-1…ai利用高維數(shù)據(jù)流的滑動窗口模式描述高維數(shù)據(jù)流X與Y之中典型相關(guān)性分析的根本線索：從X和Y中分別獲得組合變量U、組合變量V，通過式(6)得到高維數(shù)據(jù)流的并行計(jì)算結(jié)果

Un+1=Xp+nAn+1，Vn+1=Yq+nBn+1

(6)

式中，A、B代表線性變換，又叫空間特征向量。通過定義高維數(shù)據(jù)流的滑動數(shù)據(jù)流窗口模式，實(shí)現(xiàn)對高維數(shù)據(jù)流的并行計(jì)算。

3 實(shí)驗(yàn)分析

將本文研究的基于粒度理論的高維數(shù)據(jù)流并行計(jì)算方法應(yīng)用到某高維數(shù)據(jù)集中，對該數(shù)據(jù)集中的高維數(shù)據(jù)流進(jìn)行計(jì)算。該數(shù)據(jù)集中包含電信記錄、金融證券、天文觀測、醫(yī)療數(shù)據(jù)等共計(jì)40種類別的數(shù)據(jù)流，數(shù)據(jù)數(shù)量共計(jì)108個。其中電信記錄、金融證券、天文觀測、醫(yī)療數(shù)據(jù)四種類別數(shù)據(jù)的數(shù)據(jù)情況如表1所示。為證實(shí)本文方法的應(yīng)用效果，選取基于GPU并行處理的計(jì)算方法和分治法求解的MPI/Cilk混合并行方法為對比方法，從高維數(shù)據(jù)流挖掘、數(shù)據(jù)去噪以及并行計(jì)算的角度驗(yàn)證本文方法的應(yīng)用效果。

表1 四種類別數(shù)據(jù)情況

3.1 挖掘性能分析

為測試數(shù)據(jù)流挖掘?qū)?nèi)存消耗的影響，對電信記錄、金融證券、天文觀測、醫(yī)療數(shù)據(jù)四種類別數(shù)據(jù)進(jìn)行測試，測試三種方法對四種類別數(shù)據(jù)流進(jìn)行挖掘的內(nèi)存消耗，實(shí)驗(yàn)結(jié)果由表2表示。

表2 不同方法挖掘的內(nèi)存消耗(%)

根據(jù)表2可知，不同類別數(shù)據(jù)流下，三種方法的數(shù)據(jù)流挖掘?qū)?nèi)存消耗的影響不同，其中高維數(shù)據(jù)流規(guī)模越大，內(nèi)存消耗也隨之增加。但本文方法對不同類別數(shù)據(jù)流挖掘的內(nèi)存消耗始終小于兩種對比方法，說明本文方法在不同類別高維數(shù)據(jù)流挖掘時內(nèi)存消耗較小，高維數(shù)據(jù)流挖掘性能較好。

3.2 數(shù)據(jù)去噪分析

為完善高維數(shù)據(jù)流的計(jì)算，還需進(jìn)行數(shù)據(jù)去噪實(shí)驗(yàn)，測試三種方法對不同類型數(shù)據(jù)進(jìn)行去噪時去除的噪聲點(diǎn)數(shù)，實(shí)驗(yàn)結(jié)果由表3表示。

表3 不同方法數(shù)據(jù)去噪能力

根據(jù)表3可知，三種方法對不同類別高維數(shù)據(jù)流的刪除噪聲點(diǎn)數(shù)能力不同，本文方法刪除噪聲點(diǎn)數(shù)始終高于其它兩種算法，說明本文方法具有較強(qiáng)的數(shù)據(jù)去噪能力。

3.3 并行計(jì)算分析

通過對比不同滑動窗口長度下，三種方法的并行計(jì)算精度，分析不同方法的高維數(shù)據(jù)流并行計(jì)算能力。實(shí)驗(yàn)結(jié)果由圖3表示。

圖3 不同滑動窗口長度計(jì)算精度

分析圖3得知，隨著滑動窗口長度的增加，三種方法的并行計(jì)算精度均呈現(xiàn)上升趨勢，其中，GPU并行處理計(jì)算方法的最高并行計(jì)算精度只能達(dá)到0.881，分治法求解的MPI/Cilk混合并行方法的最高并行計(jì)算精度只能達(dá)到0.884，而本文方法的最高精度能達(dá)到0.887，始終高于另外兩種方法，因此本文方法具有較高的高維數(shù)據(jù)流并行計(jì)算精度。

為進(jìn)一步驗(yàn)證本文方法的并行計(jì)算能力，測試三種方法計(jì)算不同類別高維數(shù)據(jù)流所需時間，對比結(jié)果由表4表示。

表4 不同方法并行計(jì)算時間

根據(jù)表4可知，由于電信記錄、金融證券、天文觀測、醫(yī)療數(shù)據(jù)四種類別數(shù)據(jù)流的邊數(shù)和數(shù)據(jù)條數(shù)逐漸增加，所以三種方法的并行計(jì)算時間也隨之增加，但本文方法計(jì)算時間始終小于其它三種方法。說明本文方法可在極大程度上縮短高維數(shù)據(jù)流的并行計(jì)算時間，并行計(jì)算效率較高。

三種方法并行計(jì)算四種數(shù)據(jù)流類別時的時間差和加速比對比結(jié)果由圖4、圖5表示。

圖4 三種方法并行計(jì)算時間差

圖5 三種方法并行計(jì)算時間差

根據(jù)圖4、圖5可知，隨著高維數(shù)據(jù)流規(guī)模的增加，三種方法的并行計(jì)算時間差隨之升高，加速比逐漸減小，說明高維數(shù)據(jù)流規(guī)模的增加，高維數(shù)據(jù)流并行計(jì)算時間增加顯著，但本文方法的并行計(jì)算時間差始終比GPU并行處理計(jì)算方法、分治法求解的MPI/Cilk混合并行方法小，加速比降低情況也優(yōu)于兩種對比方法。實(shí)驗(yàn)結(jié)果表明本文方法的高維數(shù)據(jù)并行計(jì)算能力優(yōu)勢顯著。

4 結(jié)論

本文研究基于粒度理論的高維數(shù)據(jù)流并行計(jì)算方法，借助粒度理論對高維數(shù)據(jù)流的并行處理展開進(jìn)一步研究，粒度理論是數(shù)據(jù)并行處理的新理念和計(jì)算模式，它包含了所有關(guān)于粒度的方法研究，這種計(jì)算理論符合人類思維處理問題的方式。經(jīng)實(shí)驗(yàn)驗(yàn)證，該方法具備較高的高維數(shù)據(jù)流挖掘、去噪能力，并且擁有較好的并行計(jì)算效果。今后可在現(xiàn)有研究基礎(chǔ)上繼續(xù)加深研究，以期進(jìn)一步改進(jìn)高維數(shù)據(jù)流并行計(jì)算效果，未來工作包括對高維數(shù)據(jù)流挖掘、去噪的修改以及對并行計(jì)算的增進(jìn)。