一種基于最大Lyapunov指數奇異分解的并行挖掘算法

文政穎，李運娣

(河南工程學院 計算機學院,河南 鄭州 451191)

一種基于最大Lyapunov指數奇異分解的并行挖掘算法

文政穎，李運娣

(河南工程學院 計算機學院,河南 鄭州 451191)

針對當前大數據挖掘并行計算采用多元線性回歸分析方法導致的計算開銷過大、挖掘準確度不高等問題，提出了一種基于最大Lyapunov指數奇異分解的大數據挖掘并行計算方法.該方法對大數據信息流進行高維相空間重構和QR分解，計算大數據流模型的最大Lyapunove指數譜，基于微積分極值理論構建大數據的Lyapunove指數譜的網格分布矩陣，采用奇異值分解方法對參與運算的大數據特征向量矩陣行分解，將大規(guī)模的數據挖掘計算問題變?yōu)橐幌盗行∫?guī)模的并行計算問題，實現(xiàn)了大數據挖掘中并行算法的改進.測試結果表明，采用該方法進行大數據挖掘的計算時間較短、內存開銷較小、準確度高.

大數據；挖掘；最大Lyapunove指數；奇異值分解；并行算法

數據挖掘是通過提取數據信息流中的有用特征來估計數據中的關鍵信息參量，以實現(xiàn)數據采集和參量估計.大數據挖掘中的并行算法是在分布式云計算環(huán)境下進行數據的并行調度和網格化多線程處理的[1]，為了提高大數據的挖掘效率，需要進行數據挖掘的并行算法優(yōu)化，研究大數據挖掘并行算法在數據庫構建、云計算信息處理等領域也具有較高的應用價值.

傳統(tǒng)方法中對大數據挖掘的并行處理主要有基于數據特征量的LU分解方法、QR分解方法與基于數據并行調度的塊匹配方法等[2-5].隨著大數據信息處理技術研究的不斷深入，對大數據挖掘的并行計算受到了相關學者的重視，取得了一定的研究成果.文獻[6]采用海量散亂點云快速壓縮方法進行海量云大數據的并行計算，對數據信息流進行互信息特征的提取，對提取的互信息特征采用支持向量機進行誤差修正，以提高數據并行計算的能力，但該算法應用于矩陣秩虧損大數據挖掘中收斂性不好，對求解大規(guī)模數據挖掘問題不適用.文獻[7]采用多元線性回歸分析方法進行大數據并行計算,實現(xiàn)數據擬合、參數估計和系統(tǒng)辨識，該方法在進行高維數據計算中容易導致計算開銷過大、挖掘準確度不高等問題[8].針對上述問題，課題組提出了一種基于最大Lyapunov指數奇異分解的大數據挖掘并行計算方法,計算大數據流模型的相空間重構軌跡和最大Lyapunove指數譜，構建大數據的Lyapunove指數譜的網格分布矩陣，采用奇異值分解方法對參與運算的大數據特征向量矩陣行分解，將大規(guī)模的數據挖掘計算問題變?yōu)橐幌盗行∫?guī)模的并行計算問題，最后進行仿真測試，得出了有效性結論.

1 大數據信息流高維相空間的重構和特征提取

1.1 大數據信息流高維相空間的重構

(1)

式中:m為海量大數據序列中的特征信息關聯(lián)維數；τ為相空間中的嵌入時間延遲.在重構數據映射的m維相空間內，構建對大數據挖掘的稀疏矩陣L，進行奇異值分解L=U×S×C，U和C是高階特征系矩陣，

C=(c1,c2,…,cn).

(2)

將映射u→uλ代入泛函性平衡解中，在有限域的線性子空間中存在廣義逆正解，S為L的奇異值，且

S=diag(σ1,σ2,…,σn),σ1≥σ2≥…≥σn≥0.

(3)

對任意一個正交矩陣，在線性子空間中得到高維相空間中大數據信息流并行計算的軌跡的歐式距離滿足

‖xj-xi‖≤ε，

(4)

式中：ε是足夠小的正數，由此可確定xj，從而組成一個大數據并行挖掘特征挖掘的鄰域矩陣：

Bxi=(δxi(j1),δxi(j2),…,δxi(jNb))T.

(5)

通過上述相空間的重構，在高維相空間中進行最大Lyapunove指數譜特征的提取，構建了高維特征矩陣，采用特征壓縮方法將高維矩陣轉換為低維矩陣，降低了運算的復雜度.

1.2 最大Lyapunove指數譜特征的提取

通過提取大數據信息流的最大Lyapunove指數譜，實現(xiàn)大數據挖掘的并行處理[9].計算在相空間內的數據序列映射向量{δxi+1(jk)=xjk+1-xi+1|k1,…,Nb}，重構數據映射的m維相空間，采集一維數據矢量Xn，又得一個鄰域矩陣：

(6)

當ε足夠小，當相空間嵌入維數m增加到m+1時，有

(7)

(8)

(9)

(10)

在大數據挖掘過程中，數據信息流的最大Lyapunove指數譜通過自適應泛函通向局部收斂，有

(11)

對全部Q0，大數據信息流的Lyapunove指數譜特征收斂于

(12)

2 數據挖掘并行算法的改進

2.1 大數據挖掘并行處理中的矩陣分解

在進行了上述最大Lyapunove指數譜特征提取的基礎上，進行大數據挖掘并行計算，提出了一種基于最大Lyapunov指數奇異分解的大數據挖掘并行計算方法，待挖掘的大數據信息流為

(xi1,xi2,…,xi,m-1,yi),i=1,2,…,n.

(13)

對大數據挖掘的并行計算問題就是求向量β的一致性估計的最小二乘問題，為了使‖Y-Xβ‖達到最小，對于有因變量自變量的n組觀測大數據(xi1,xi2,…,xi,m-1,yi)求解

(14)

采用奇異值分解方法對參與運算的大數據特征向量矩陣行分解，進行大數據挖掘的并行計算.

2.2 大數據挖掘并行計算的優(yōu)化

采用最大Lyapunove指數譜特征矩陣的奇異值分解方法，設A∈Rn×m且秩為r的非零矩陣，n和m都是正整數，考慮第i次迭代，輸入為雙端塊雅克比向量Y(i)和奇異矩陣X(i)，矩陣維數分別為N(i)×1和N(i)×m.在大數據信息流的特征分解過程中，矩陣X(i)被分解為p(i)個大小為Nij×m的子矩陣Xij，將矩陣X進行奇異值分解，X=UΣVT，求大數據信息流Lyapunove指數譜的子矩陣最小二乘解.這里,Nij≥m，對于大數據挖掘的重構特征矩陣A，存在n階正交矩陣U和m階正交矩陣V，對第j個奇異值分解矩陣Xij進行非零特征值分解：

Xij=UijΣijVijT.

(15)

β*=V(k)1Σ(k)1-1U(k)1TY(k)，

(16)

式中：V(k)，Σ(k)1，U(k)1為X(k)進行奇異值矩陣分解運算所得.限于篇幅，并行算法偽代碼省略.

采用奇異值分解方法進行數據挖掘的特征分解和并行處理，對參與運算的大數據特征向量矩陣行分解，子矩陣之間是完全獨立的.對p(i)個子矩陣，奇異值分解運行能在數據挖掘過程中并行處理，從而加快了運算速度，降低了大數據挖掘并行運算的開銷，提高了計算效率.

3 實驗與分析

為了測試本算法在實現(xiàn)大數據挖掘并行運算中的性能，進行數據挖掘并行運算對比仿真實驗，實驗平臺采用的CPU是四核八線程的，軟件采用Matlab7仿真平臺，使用大型網絡數據庫OpenMP2.0和MPICHNT1.2.5中的數據為測試樣本數據集，分別取其中的6組數據樣本進行大數據挖掘并行運算仿真分析，圖1給出了其中一組數據的時域波形.

圖1 大數據信息流時域波形Fig.1 Time domain waveform of large data information flow

對圖1所示的大數據信息流進行特征提取和挖掘分析，計算大數據流模型的最大Lyapunove指數譜，得到Lyapunove指數譜，如圖2所示.圖2中，4條譜線中收斂值最大的譜即最大Lyapunove指數譜.

以計算得到的Lyapunove指數為特征參量，構建大數據的Lyapunove指數譜的網格分布矩陣，采用奇異值分解進行并行運算，實現(xiàn)大數據挖掘.為了對比性能，采用并行算法和傳統(tǒng)的串行算法進行數據挖掘的時間開銷對比，結果如圖3所示.

圖2 大數據信息流的Lyapunove譜特征提取Fig.2 Lyapunove spectrum feature extraction of large data stream

圖3 運算時間開銷對比Fig.3 Operation time overhead contrast

Tab.1 Memory consumption M

分析圖3可知，采用并行算法進行大數據挖掘的時間開銷較小.表1給出了不同算法進行數據挖掘的內存開銷.分析表1可知，隨著數據規(guī)模的增加，內存開銷加大，傳統(tǒng)方法內存開銷的增長幅度較大，嚴重占用了計算的內存，而本算法的內存開銷遠小于傳統(tǒng)方法，受大數據運算規(guī)模的影響較小，特別適合用于海量數據的挖掘.因此，采用本算法進行并行運算，降低了內存開銷，提高了運算性能.

4 結語

為了提高大數據挖掘的效率和準確性，本研究提出了一種基于最大Lyapunov指數奇異分解的大數據挖掘并行計算方法.該方法對大數據信息流進行高維相空間的重構和QR分解，計算大數據流模型的最大Lyapunove指數譜，基于微積分極值理論構建了大數據Lyapunove指數譜的網格分布矩陣，采用奇異值分解方法對參與運算的大數據特征向量矩陣行分解，將大規(guī)模的數據挖掘問題變?yōu)橐幌盗行∫?guī)模的并行計算問題，實現(xiàn)了大數據挖掘中并行算法的改進.實驗證明，采用本算法進行大數據挖掘并行運算處理的計算開銷和內存開銷都較小，運算效率得到了提高.

[1] 邢淑凝,劉方愛,趙曉暉.基于聚類劃分的高效用模式并行挖掘算法[J].計算機應用,2016,36(8):2202-2206.

[2] ZIHAYAT M,AN A.Mining top-k high utility patterns over data streams[J].Information Sciences,2014(285):138-161.

[3] YUN U,RYANG H,RYU K H.High utility itemset mining with techniques for reducing overestimated utilities and pruning candidates[J].Expert Systems with Applications,2014,41(8):3861-3878.

[4] SONG W,LIU Y,LI J.Mining high utility itemsets by dynamically pruning the tree structure[J].Applied Intelligence,2014,40(1):29-43.

[5] HIE B E,HSIAO H F,TSENG V S.Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments[J].Knowledge and Information Systems,2013,37(2):363-387.

[6] 方芳,程效軍.海量散亂點云快速壓縮算法[J].武漢大學學報(信息科學版),2013,38(11):1353-1357.

[7] LEE D,PARK S H,MOON S.Utility-based association rule mining:a marketing solution for cross-selling[J].Expert Systems with Applications,2013,40(7):2715-2725.

[8] 閆昭,劉磊.基于數據依賴關系的程序自動并行化方法[J].吉林大學學報(理學版),2010,48(1):94-98.

[9] 楊景明,侯宇浩,孫浩,等.采用數量級閾值與二維信息排序策略的NSGA-II-DE算法[J].控制與決策,2016,31(9):1577-1584.

[10]張景祥,王士同,鄧趙紅,等.融合異構特征的子空間遷移學習算法[J].自動化學報,2014,40(2):236-246.

A parallel mining algorithm based on maximal Lyapunov exponent singular decomposition

WEN Zhengying，LI Yundi

(CollegeofComputer，HenanUniversityofEngineering，Zhengzhou451191，China)

In view of the current data mining parallel computing method of regression analysis leads to excessive computational overhead by using multivariate linear, mining accuracy is not high, in order to improve the efficiency and accuracy of data mining, a large number of maximum Lyapunov Exponent Based on singular decomposition according to the parallel computing method of mining. For phase space reconstruction and QR decomposition of large data flow, the maximum Lyapunov index calculation of large data flow model of the spectrum, constructing the grid distribution matrix data Lyapunov exponent spectrum calculus based on extreme value theory, using singular value decomposition method for participating in the operation of large numbers according to the eigenvector matrix decomposition, large-scale data mining the calculation problem into a series of small scale parallel computing problem, improved algorithm in data mining. Experimental results show that the proposed method is used for large data mining, the computation time is relatively short, the memory cost is small, and the accuracy of data mining has been greatly improved.

big data; mining; maximum Lyapunov exponent; singular value decomposition; parallel algorithm

2016-10-12

河南省高等學校重點科研項目(16A520004)

文政穎(1979-)，女，河南南召人，副教授，主要研究方向為圖像處理與計算機應用.

TP312

A

1674-330X(2017)01-0067-04