基于粒度理論的高維數據流并行計算方法

路 晶，胡順仿

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

1 引言

隨著計算機網絡、數據庫、通信等技術的高速發展，導致了信息數量的爆炸性增長，許多領域出現了高速產生、動態變化的流式數據[1]，如銷售業務中的交易數據流、金融市場的交易數據流、環境監測的實時數據流都以高維屬性發揮各自的作用，研究人員稱這種類型的數據為高維數據流[2，3]。由于高維數據流的應用逐漸廣泛，如何在具備關聯性的高維數據流之間進行并行計算成為了目前研究的熱點[4]。

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

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

2 基于粒度理論的高維數據流并行計算方法

2.1 基于動態粒度的數據流挖掘模型

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

圖1 基于動態粒度的數據流挖掘模型

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

形成新數據后，再次遍歷檢索全部數據，會耗費過多的資源與時間[11]，這是由于數據流中數據量產生速度過快且數據量巨大，這并不符合數據流挖掘對速度和實用性的需求。為了高效率修正挖掘結果，利用增量式修正方法處理新加入的數據[12]。

2.2 基于LPP和PCA的數據噪聲抑制

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

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

1)用以下公式計算每個采樣點xi的k(k

(1)

2)依據LPP算法確認權重，與數據集X相應的對稱稀疏權值矩陣為Sm×m，其通過xi到xj的權值Sij=e-‖xi-xj‖2/t計算得出。

4)基于數據X*進行PCA線性變換，用線性正交變換矩陣W描述Y的線性組合，即重構結果X′

(2)

式中，ui表示矩陣U的列；yi表示矩陣Y的行，特征數據與特征值λi相對應。基于特征數據的加權組合重構獲得原信號，進而通過式(2)獲取隨機噪聲的抑制結果。

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

圖2 基于LPP+PCA的數據去噪處理流程圖

2.3 高維數據流相關性并行計算方法

2.3.1 皮爾遜積差系數及其數學特性

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

(3)

(4)

兩組n維變化數據的關聯性可由上述式(5)獲得

(5)

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

2.3.2 高維數據流并行計算的實現

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

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

(6)

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

3 實驗分析

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

表1 四種類別數據情況

3.1 挖掘性能分析

為測試數據流挖掘對內存消耗的影響，對電信記錄、金融證券、天文觀測、醫療數據四種類別數據進行測試，測試三種方法對四種類別數據流進行挖掘的內存消耗，實驗結果由表2表示。

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

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

3.2 數據去噪分析

為完善高維數據流的計算，還需進行數據去噪實驗，測試三種方法對不同類型數據進行去噪時去除的噪聲點數，實驗結果由表3表示。

表3 不同方法數據去噪能力

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

3.3 并行計算分析

通過對比不同滑動窗口長度下，三種方法的并行計算精度，分析不同方法的高維數據流并行計算能力。實驗結果由圖3表示。

圖3 不同滑動窗口長度計算精度

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

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

表4 不同方法并行計算時間

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

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

圖4 三種方法并行計算時間差

圖5 三種方法并行計算時間差

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

4 結論

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