面向大規(guī)模數(shù)據(jù)的特征趨勢推理算法

吳 春 瓊

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

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

1 算法設(shè)計(jì)

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

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

1.1.1 基于Hash函數(shù)的樣本抽樣 抽樣Hash函數(shù)時(shí), 必須計(jì)算大規(guī)模數(shù)據(jù)抽樣樣本的內(nèi)存[5]. 將置信度取值為1-β, 由中心極限定理可知, 在正態(tài)整體里, 隨機(jī)抽取m個(gè)樣本, 大規(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)

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

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

(2)

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

ik-1

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

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

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

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

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

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

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

1.1.2 改進(jìn)算法 改進(jìn)算法步驟如下：

1) 計(jì)算大規(guī)模數(shù)據(jù)目標(biāo)的均值和標(biāo)準(zhǔn)差[8]；

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

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

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

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

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

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

圖1 聚類算法流程

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

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

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

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

2) 上升斜率均值L為

(3)

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

3) 下降斜率均值J為

(4)

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

4) 分析極值點(diǎn)數(shù)w, 如果分割點(diǎn)前后數(shù)據(jù)段斜率符合不同且為反向關(guān)系, 則該分割點(diǎn)是極值點(diǎ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的累計(jì)趨勢規(guī)則. 如果采用相同特征種類Fj在C1,C2,…,Cn中的字段數(shù)據(jù)項(xiàng)之和是{H1,H2,…,Hn}, 則{H1,H2,…,Hn}表示基于特征種類Fj的合計(jì)趨勢規(guī)則[12].

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

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

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

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

Fori=dminTodmaxorderFdry

Put intoCiinCWherei≤d≤i+F

Next

whole等價(jià)劃分B={B1,B2,…,Bn} dry

Fori=1 tondry

Forj=1 tondry

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

WhereBi等價(jià)類

Next

Next

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

Next.

2 實(shí) 驗(yàn)

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

2.1 實(shí)驗(yàn)設(shè)置

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

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

2) 壓縮比S為

(7)

3) 擬合均方誤差UMs為

(8)

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

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

2.2 實(shí)驗(yàn)結(jié)果

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

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

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

表2 隨機(jī)變分推理算法的推理準(zhǔn)確率(%)

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

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

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

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

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

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

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