吳 春 瓊

(廈門大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 福建 廈門 361005; 陽光學(xué)院 商學(xué)院, 福州 350015)

隨著大規(guī)模數(shù)據(jù)信息時代的到來, 海量的數(shù)據(jù)都保存在網(wǎng)絡(luò)和云存儲中, 導(dǎo)致網(wǎng)絡(luò)和云存儲中的大規(guī)模數(shù)據(jù)數(shù)量與規(guī)模急劇增加, 因此在使用和調(diào)度大規(guī)模數(shù)據(jù)時, 必須對數(shù)據(jù)庫與云存儲系統(tǒng)中的大規(guī)模數(shù)據(jù)進行處理, 如特征提取和特征趨勢推理等. 面向數(shù)據(jù)的特征趨勢推理已成為目前該領(lǐng)域的關(guān)注熱點. 文獻[1]提出了一種隨機變分推理算法, 但該算法未能在推理數(shù)據(jù)特征趨勢前聚類大規(guī)模數(shù)據(jù), 導(dǎo)致推理結(jié)果的誤差較大； 文獻[2]提出了一種并行化Top-kSkyline查詢算法, 但該算法計算過程較復(fù)雜, 且效率較低； 文獻[3]提出了一種基于直覺模糊Petri網(wǎng)的模糊推理算法, 但該算法未能推理數(shù)據(jù)的特征趨勢, 不適用于處理推理的問題. 針對上述算法存在的問題, 本文提出一種新的面向大規(guī)模數(shù)據(jù)的特征趨勢推理算法, 首先對大規(guī)模數(shù)據(jù)進行聚類, 獲取最佳聚類結(jié)果后提取聚類結(jié)果的動態(tài)特征, 然后采用基于特征趨勢規(guī)則的推理算法, 實現(xiàn)大規(guī)模數(shù)據(jù)的特征趨勢推理.

1 算法設(shè)計

1.1 面向大規(guī)模數(shù)據(jù)聚類優(yōu)化算法

本文使用Hash函數(shù)抽取樣本體現(xiàn)數(shù)據(jù)的分布狀況, 采用Pam算法和并行K-means聚類算法聚類樣本數(shù)據(jù), 將實際樣本點設(shè)為新聚類中心, 防止受噪聲點與孤立點的干擾, 以此提升聚類效果和速度[4], 獲取最佳大規(guī)模數(shù)據(jù)聚類結(jié)果.

1.1.1 基于Hash函數(shù)的樣本抽樣 抽樣Hash函數(shù)時, 必須計算大規(guī)模數(shù)據(jù)抽樣樣本的內(nèi)存[5]. 將置信度取值為1-β, 由中心極限定理可知, 在正態(tài)整體里, 隨機抽取m個樣本, 大規(guī)模數(shù)據(jù)樣本均值與正態(tài)分布相符[6]； 在偏態(tài)整體里抽樣, 若m接近無窮大, 則大規(guī)模數(shù)據(jù)抽樣分布與正態(tài)分布a～N(η,λ2)相符, 其中：η表示樣本均值;λ2表示樣本方差. 因此置信度是1-β的置信區(qū)間為

其中：a表示二元變量；β表示置信因子；Y表示置信匹配度. 假設(shè)抽樣誤差為γ, 則置信區(qū)間為[(1-γ)η,(1+γ)η]. 綜合上述方法獲取的大規(guī)模數(shù)據(jù)抽樣樣本數(shù)目m為

(1)

近似分布估計大規(guī)模數(shù)據(jù)各維變量時, 能建立如下Hash函數(shù)：

T(x1,x2,…,xm)=B(x1),B(x2),…,B(xm),

(2)

其中:B(x)表示分布函數(shù);T(x)表示Hash函數(shù);x表示分配目標. 設(shè)該Hash函數(shù)的值域為[0,1], 假設(shè)需要提取m個大規(guī)模數(shù)據(jù)的樣本數(shù)據(jù), 則把次區(qū)間m等分： 0=i1

ik-1

則將該目標分配至第k個桶內(nèi).

基于Hash函數(shù)的樣本抽樣算法流程如下：

步驟1) 設(shè)定大規(guī)模數(shù)據(jù)抽樣樣本內(nèi)存m；

步驟2) 計算每列分布函數(shù)B(x)；

步驟3) 建立Hash函數(shù)；

步驟4) 將全部大規(guī)模數(shù)據(jù)目標分配至m個桶內(nèi)；

步驟5) 任意在各Hash桶內(nèi)提取固定比例的大規(guī)模數(shù)據(jù), 構(gòu)建成m個樣本數(shù)的大規(guī)模數(shù)據(jù)樣本數(shù)據(jù)集[7].

1.1.2 改進算法 改進算法步驟如下：

1) 計算大規(guī)模數(shù)據(jù)目標的均值和標準差[8]；

2) 設(shè)定大規(guī)模數(shù)據(jù)抽樣的樣本數(shù)目m；

3) 在數(shù)據(jù)集X中實行樣本抽樣；

4) 獲取的抽樣樣本使用Pam聚類算法實行聚類, 最后提取初始中心[9]；

5) 將穩(wěn)定的聚類中心設(shè)成全局初始聚類中心, 輸入數(shù)據(jù)組和有關(guān)參數(shù);

6) 使用并行K-means聚類算法再次聚類, 直至全部類簇穩(wěn)定或運行至最大迭代次數(shù)時停止[10].

大規(guī)模數(shù)據(jù)整體聚類流程如圖1所示.

圖1 聚類算法流程

通過上述過程獲取最佳大規(guī)模數(shù)據(jù)聚類結(jié)果后, 提取大規(guī)模數(shù)據(jù)聚類的動態(tài)特征, 在此基礎(chǔ)上采用基于特征趨勢規(guī)則的推理算法, 實現(xiàn)大規(guī)模數(shù)據(jù)特征趨勢的準確推理[11].

1.2 提取大規(guī)模數(shù)據(jù)聚類的動態(tài)特征

本文設(shè)計的提取大規(guī)模數(shù)據(jù)各方面特征如下：

1) 壓縮比數(shù)S為

2) 上升斜率均值L為

(3)

其中：Li表示斜率為正數(shù)的大規(guī)模數(shù)據(jù)段斜率；i=1,2,…,k,i和k表示計量參數(shù)；w表示極值點數(shù);

3) 下降斜率均值J為

(4)

其中,Ji表示斜率為負數(shù)的大規(guī)模數(shù)據(jù)段斜率；

4) 分析極值點數(shù)w, 如果分割點前后數(shù)據(jù)段斜率符合不同且為反向關(guān)系, 則該分割點是極值點;

5) 大規(guī)模數(shù)據(jù)流均值R為

(5)

6) 大規(guī)模數(shù)據(jù)流的均方差χ為

(6)

其中：R表示大規(guī)模數(shù)據(jù)流均值；G表示大規(guī)模數(shù)據(jù)流數(shù)據(jù)量.

1.3 基于特征趨勢規(guī)則的推理算法

1.3.1 大規(guī)模數(shù)據(jù)特征的趨勢規(guī)則推理模型 假設(shè)大規(guī)模數(shù)據(jù)聚類庫C中字段d是趨勢變化的軸,dmax和dmin描述d字段值的上下限,F表示d字段取值的間隔, 則將數(shù)據(jù)庫C根據(jù)d字段取值分為C={C1,C2,…,Cn}, 大規(guī)模數(shù)據(jù)聚類庫中相同特征種類Fj(j=1,2,…)在C1,C2,…,Cn內(nèi)的記錄數(shù)是{C1,C2,…,Cn}, 則{C1,C2,…,Cn}表示基于特征種類Fj的累計趨勢規(guī)則. 如果采用相同特征種類Fj在C1,C2,…,Cn中的字段數(shù)據(jù)項之和是{H1,H2,…,Hn}, 則{H1,H2,…,Hn}表示基于特征種類Fj的合計趨勢規(guī)則[12].

累計趨勢規(guī)則和合計趨勢規(guī)則的不同是前者計算記錄數(shù), 后者計算合計數(shù), 所以兩種算法基本相同, 本文通過累計趨勢規(guī)則方法設(shè)計趨勢規(guī)則算法.

1.3.2 面向大規(guī)模數(shù)據(jù)特征趨勢規(guī)則推理算法設(shè)計 面向大規(guī)模數(shù)據(jù)的特征趨勢規(guī)則推理必須設(shè)定大規(guī)模數(shù)據(jù)特征趨勢軸的初值、 終值和變化步長. 假設(shè)大規(guī)模數(shù)據(jù)特征趨勢軸的字段為d, 初值是dmin, 終值是dmax, 變化步長為F, 則根據(jù)特征趨勢軸的分類, 能將C劃分為n個字庫{C1,C2,…,Cn}, 假設(shè)B與C是等價關(guān)系,C共含有n個等價劃分, 能獲取下述矩陣,P1,j表示記錄數(shù).

矩陣的各列向量(P1,j,P2,j,…,Pn,j)(j=1,2,…,n)表示大規(guī)模數(shù)據(jù)特征趨勢規(guī)則, 若可獲取C上的全部等價關(guān)系, 便可獲取所有大規(guī)模數(shù)據(jù)特征趨勢規(guī)則[13].

面向大規(guī)模數(shù)據(jù)特征趨勢規(guī)則推理算法流程如下：

Fori=dminTodmaxorderFdry

Put intoCiinCWherei≤d≤i+F

Next

whole等價劃分B={B1,B2,…,Bn} dry

Fori=1 tondry

Forj=1 tondry

Choose count(*)intoR[i,j] inCj

WhereBi等價類

Next

Next

R[i,j] ? 結(jié)果庫

Next.

2 實 驗

本文實驗設(shè)推理目標為鋁電解槽電壓數(shù)據(jù), 其屬于平穩(wěn)大規(guī)模數(shù)據(jù)流, 有效推理鋁電解槽電壓的數(shù)據(jù)特征趨勢能對槽況惡化情形進行提前預(yù)警[14].

2.1 實驗設(shè)置

實驗依次使用本文算法(算法1)、 隨機變分推理算法(算法2)和并行化Top-kSkyline查詢算法(算法3)對相同數(shù)據(jù)流特征進行趨勢推理, 并用差異分割點閾值依次檢驗每個算法的性能指標：

1) 分割點點數(shù)設(shè)為?1；

2) 壓縮比S為

(7)

3) 擬合均方誤差UMs為

(8)

其中：l表示大規(guī)模數(shù)據(jù)段的長度, 也是電壓采樣點的點數(shù)；q表示該數(shù)據(jù)段的擬合參數(shù)值；si表示實際電壓；x1表示時間.

結(jié)合鋁電解狀況, 實驗將基準窗口長度設(shè)為len=Z/4, 其中Z表示電壓曲線波形周期, 該周期根據(jù)運行的工況設(shè)定, 初始值是110 min. 最長數(shù)據(jù)窗口長度是Zk,k是可變參數(shù), 通常取值為1.5～2, 初始值為1.5. 標準分割點閾值用φ描述.

2.2 實驗結(jié)果

擬合均方誤差主要用于判定算法推理結(jié)果的誤差均值, 可分析數(shù)據(jù)特征趨勢的變化水平, 實驗在具有差異性的分割點檢測閾值下, 對比上述3種算法的分割點點數(shù)、 壓縮比和擬合均方誤差, 對比結(jié)果列于表1. 由表1可見： 在相同閾值的前提下, 本文算法的最大分割點點數(shù)為212個, 分別比隨機變分推理算法和并行化Top-kSkyline查詢算法的最大分割點點數(shù)高3和7, 且本文算法的分割點點數(shù)始終大于其他兩種算法, 說明本文算法在推理大規(guī)模數(shù)據(jù)的特征趨勢時, 能全面分割大規(guī)模數(shù)據(jù)特征, 確保了大規(guī)模數(shù)據(jù)特征趨勢推理結(jié)果的準確度； 壓縮比數(shù)是數(shù)據(jù)流的數(shù)據(jù)量與分割總數(shù)間的比值, 表示實驗所用大規(guī)模數(shù)據(jù)與分割總數(shù)成正比, 壓縮比越小說明大規(guī)模數(shù)據(jù)特征分割的越全面, 本文算法、 并行化Top-kSkyline查詢算法以及隨機變分推理算法的最大壓縮比排序為39.33<41.51<42.31, 且本文算法的壓縮比始終小于另外兩種算法, 說明本文算法分割的大規(guī)模數(shù)據(jù)特征更全面, 同樣為大規(guī)模數(shù)據(jù)特征的準確推理提供了可靠依據(jù); 從擬合均方誤差方面分析, 本文算法的擬合均方誤差最大值為5.24, 隨機變分推理算法的擬合均方誤差最大值為11.02, 并行化Top-kSkyline查詢算法的擬合均方誤差最大值為11.34, 本文算法的擬合均方誤差最小, 說明本文算法平均誤差最小, 分割大規(guī)模數(shù)據(jù)特征的準確率最高[15].

表1 3種算法的數(shù)據(jù)分割點數(shù)、 壓縮比、 擬合均方誤差對比結(jié)果

基于上述實驗設(shè)置, 設(shè)定4個大規(guī)模數(shù)據(jù)流特征推理對象, 統(tǒng)計3種算法的大規(guī)模數(shù)據(jù)特征趨勢的推理準確率, 結(jié)果分別列于表2～表4. 由表2～表4可見, 隨機變分推理算法對大規(guī)模數(shù)據(jù)特征趨勢推理的準確率均值為61.95%, 本文算法對大規(guī)模數(shù)據(jù)特征趨勢推理的準確率均值為98.10%, 并行化Top-kSkyline查詢算法推理準確率均值為56.65%, 因此, 本文算法的推理準確率最高.

表2 隨機變分推理算法的推理準確率(%)

表3 本文算法的推理準確率(%)

表4 并行化Top-k Skyline查詢算法的推理準確率(%)

圖2 3種算法的推理速度增長率對比結(jié)果

實驗統(tǒng)計上述實驗過程中3種算法的推理效率, 獲取3種算法的推理速度增長率如圖2所示. 由圖2可見, 本文算法在大規(guī)模數(shù)據(jù)特征分割點閾值為1時, 推理大規(guī)模數(shù)據(jù)特征趨勢的速度便出現(xiàn)增長趨勢, 當大規(guī)模數(shù)據(jù)特征分割點閾值為10時, 本文算法的推理速度增長率高達50%； 隨機變分推理算法在分割點閾值為4時推理速度才出現(xiàn)增長趨勢, 當大規(guī)模數(shù)據(jù)特征分割點閾值為6～8時, 推理速度增長率達到頂峰, 速度增長率為30%, 當大規(guī)模數(shù)據(jù)特征分割點閾值大于8時速度增長率趨勢回落； 并行化Top-kSkyline查詢算法在分割點閾值為3時推理速度才出現(xiàn)增長趨勢, 當分割點閾值為8時, 推理速度增長率最高為30%. 因此, 相對于其他兩種算法, 本文算法的推理速度增長率最快, 是一種高效率的大規(guī)模數(shù)據(jù)特征趨勢推理算法.

上述實驗中3種算法的推理耗時對比結(jié)果列于表5. 由表5可見, 在不同分割點閾值下, 推理4個大規(guī)模數(shù)據(jù)的特征趨勢時, 本文算法的推理耗時最大均值為114.25 s； 隨機變分推理算法和并行化Top-kSkyline查詢算法的推理耗時最大均值分別為243.5 s和203.5 s. 因此, 相對于其他兩種算法, 本文算法的推理耗時最短, 效率最高.

表5 3種算法的推理耗時對比結(jié)果

綜上所述, 本文提出了一種新的面向大規(guī)模數(shù)據(jù)的特征趨勢推理算法, 使用Hash函數(shù)抽取樣本體現(xiàn)數(shù)據(jù)的分布狀況, 采用Pam算法和并行K-means聚類算法對大規(guī)模數(shù)據(jù)樣本實行聚類, 將實際樣本點設(shè)為新聚類中心, 防止受噪聲點與孤立點的干擾, 以此提升聚類效果和速度; 獲取最佳大規(guī)模數(shù)據(jù)聚類結(jié)果后提取大規(guī)模數(shù)據(jù)聚類的動態(tài)特征, 在此基礎(chǔ)上采用基于特征趨勢規(guī)則的推理算法, 實現(xiàn)大規(guī)模數(shù)據(jù)特征趨勢的準確推理. 實驗結(jié)果表明, 本文算法在推理大規(guī)模數(shù)據(jù)的特征趨勢時, 推理的準確率均值為98.10%, 表明本文算法具有較高的準確率； 本文算法的推理速度增長率為50%, 推理耗時最大均值為114.25 s, 遠低于隨機變分推理算法和并行化Top-kSkyline查詢算法的推理耗時, 說明本文算法的推理效率較高.