劉張榕

(福建林業(yè)職業(yè)技術學院 信息工程系，福建 南平 353000)

0 引言

數(shù)據(jù)庫種類可以按照有效性，分為靜態(tài)數(shù)據(jù)庫、動態(tài)數(shù)據(jù)庫和實時數(shù)據(jù)庫3種，在檢索數(shù)據(jù)庫中的數(shù)據(jù)時，大多是從靜態(tài)數(shù)據(jù)庫中挖掘數(shù)據(jù)。但數(shù)據(jù)庫的實時性，又使數(shù)據(jù)庫處于一種動態(tài)變化中，不斷在數(shù)據(jù)庫中積累新的數(shù)據(jù)，此時，采用挖掘方法挖掘到的靜態(tài)數(shù)據(jù)庫數(shù)據(jù)，則會因為數(shù)據(jù)庫數(shù)據(jù)的更新，出現(xiàn)知識失效問題[1-2]。所以，需要研究動態(tài)數(shù)據(jù)庫數(shù)據(jù)挖掘方法。

目前，國內(nèi)外對動態(tài)數(shù)據(jù)庫挖掘也有許多研究，文獻[3]提出了多域分布式數(shù)據(jù)庫的電能質量擾動事件記錄關聯(lián)規(guī)則挖掘，采用移動時間窗技術實現(xiàn)擾動數(shù)據(jù)預處理，然后在考慮數(shù)據(jù)庫更新的情況下，提出一種分布式協(xié)同算法，該算法通過交換各數(shù)據(jù)庫間的局部頻繁項目集，實現(xiàn)擾動數(shù)據(jù)關聯(lián)模式分布式挖掘。文獻[4]設計了基于聚類優(yōu)化的大型網(wǎng)絡數(shù)據(jù)庫挖掘系統(tǒng)，該搭建數(shù)據(jù)采集所需的傳感器節(jié)點結構，選擇CC3200作為主控芯片，在原有的電路中引入射頻通信電路，實現(xiàn)數(shù)據(jù)的無線傳輸。在此基礎上，對數(shù)據(jù)庫中數(shù)據(jù)進行預處理，利用優(yōu)化后的聚類算法和軟件程序實現(xiàn)數(shù)據(jù)挖掘，至此系統(tǒng)設計完成。

針對上述存在問題，本文提出基于大數(shù)據(jù)集的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘研究。

1 研究基于大數(shù)據(jù)集的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法

在動態(tài)數(shù)據(jù)庫中，會存在歷史數(shù)據(jù)和新增數(shù)據(jù)兩種，因此，此次研究動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，將選擇靜態(tài)挖掘與動態(tài)挖掘相結合的方式，先挖掘動態(tài)數(shù)據(jù)庫中的歷史數(shù)據(jù)，再挖掘動態(tài)數(shù)據(jù)庫中的更新數(shù)據(jù)。

1.1 動態(tài)數(shù)據(jù)庫數(shù)據(jù)存儲

在大數(shù)據(jù)背景下，采用大數(shù)據(jù)集中的分布式計算，分布式存儲動態(tài)數(shù)據(jù)庫中的歷史數(shù)據(jù)，需要將動態(tài)數(shù)據(jù)庫中的原始大數(shù)據(jù)分割成多個子數(shù)據(jù)集，大量的小文件則需要合并為一個子數(shù)據(jù)集，從而提高數(shù)據(jù)存儲效率。此時，需要采用并行化技術統(tǒng)計方式，優(yōu)化每一個子數(shù)據(jù)集中的數(shù)據(jù)量，并將數(shù)據(jù)的空間與時間復雜度記為O，單節(jié)點中分片數(shù)據(jù)量記為D，則數(shù)據(jù)的分布式存儲過程，如圖1所示。

圖1 數(shù)據(jù)分布式存儲過程

從圖1中可以看出，采用分割的方式將合并的小文件和分割的子數(shù)據(jù)集存儲至各個節(jié)點中，通過并行化統(tǒng)計，判斷各個節(jié)點數(shù)據(jù)的支持度，從而去除不滿足支持度的數(shù)據(jù)項，得到第一序列數(shù)據(jù)。完成數(shù)據(jù)分布式存儲。

1.2 數(shù)據(jù)分組

根據(jù)圖1得到的第一序列數(shù)據(jù)，需要進行數(shù)據(jù)修剪重排分組和計算量預估與均衡化分組。

(1)數(shù)據(jù)修剪重排分組。對于動態(tài)數(shù)據(jù)庫中的原始數(shù)據(jù)，按照圖1得到的第一序列數(shù)據(jù)，進行修剪排序，即刪除原始數(shù)據(jù)中不滿足支持度閾值的數(shù)據(jù)項，修剪后的數(shù)據(jù)依照支持度的降序排列，其數(shù)據(jù)修剪重排分組具體過程如圖2所示。

圖2 數(shù)據(jù)修剪重排分組過程

圖中，〈w,p,v,m,s,n〉表示數(shù)據(jù)集中的一條數(shù)據(jù)[5]。將〈w,p,v,m,s,n〉數(shù)據(jù)按照第一序列數(shù)據(jù)進行修剪重排分組后，得到的數(shù)據(jù)為〈p,w,n,s,v〉，再按照數(shù)據(jù)的后綴進行迭代分割，采用Key-Value的形式表達，則得到{v,〈p,w,n,s〉}，{s,〈p,w,n〉}，{n,〈p,w〉}，{w,〈p〉}。此時，得到的修剪重排分組后的數(shù)據(jù)需要再次存儲至圖1所示的節(jié)點中，進行計算量預估與均衡化分組處理。

(2)計算量預估與均衡化分組。計算圖2得到的數(shù)據(jù)，需要根據(jù)第一序列數(shù)據(jù)中，存在的以e為后綴的數(shù)據(jù)位置，計算量數(shù)據(jù)C(e)的估值,如式(1)。

C(e)=log(P(e,F))

(1)

式中，F(xiàn)表示第一序列數(shù)據(jù)；P表示以e為后綴的數(shù)據(jù)位置，與第一序列數(shù)據(jù)之間的關聯(lián)。此時，需要按照式(1)得到的關聯(lián)值，將第一序列數(shù)據(jù)按照估值的降序順序排列，其排列式如式(2)。

(2)

式中，Ti表示第i條原始數(shù)據(jù)；n表示包含e的數(shù)據(jù)總數(shù)目；P(e,Ti)表示第i條原始數(shù)據(jù)Ti中，所含有e的數(shù)據(jù)位置[6]。綜合式(1)、式(2)，即完成數(shù)據(jù)分組。此時，需要將計算量估值按照計算均衡化分配來進行分組歸類。對此，假設需要計算的數(shù)據(jù)節(jié)點數(shù)為N，依據(jù)計算節(jié)點數(shù)N建立分組記錄表gN，需要將每一計算節(jié)點都與分組數(shù)據(jù)相對應。則均衡化分組流程如下。

(1)將計算量數(shù)據(jù)C(e)的估值中的前N個節(jié)點數(shù)據(jù)保存至分組記錄表gN中；(2)計算gN的各個節(jié)點數(shù)據(jù)集之和，作為gN的計算估值；(3)確定計算量數(shù)據(jù)C(e)的估值中存在的多余節(jié)點數(shù)據(jù)數(shù)目；(4)將多余節(jié)點數(shù)據(jù)依次加入gN中，并計算估值最小列表；(5)更新gN對應的計算估值。綜合上述內(nèi)容，即完成數(shù)據(jù)分組處理。

1.3 更新動態(tài)數(shù)據(jù)庫新增數(shù)據(jù)

更新動態(tài)數(shù)據(jù)庫數(shù)據(jù)時，需要構建數(shù)據(jù)樹，并將數(shù)據(jù)樹分為多個子數(shù)據(jù)樹和總數(shù)據(jù)樹，更新匯聚在節(jié)點的第一序列數(shù)據(jù)，為此設定如下更新動態(tài)數(shù)據(jù)庫新增數(shù)據(jù)步驟。

1)更新動態(tài)數(shù)據(jù)庫新增數(shù)據(jù)特征。假設動態(tài)數(shù)據(jù)庫新增數(shù)據(jù)為d，其d中新增數(shù)據(jù)頻繁項集記錄為Qd，其頻次數(shù)據(jù)記錄為Qd={T1,T3},動態(tài)數(shù)據(jù)庫歷史數(shù)據(jù)為D，歷史數(shù)據(jù)頻繁項集記錄為QD，其頻次數(shù)據(jù)為QD={T1,T2}。將歷史數(shù)據(jù)和新增數(shù)據(jù)累加，記錄為QdD。此時更新動態(tài)數(shù)據(jù)庫中的歷史數(shù)據(jù)，會出現(xiàn)如下4種情形：(1)如T1∈Qd,T1∈QD，即T1在Qd和QD中，均屬于頻繁項集；(2)如T2?Qd,T2∈QD，即T2僅在QD中屬于頻繁項集；(3)如T3∈Qd,T3?QD，即T3僅在Qd中屬于頻繁項集；(4)如T4?Qd,T4?QD，即T4在Qd和QD中，均為非頻繁項集[7-8]。

2)按照步驟1，即可完成一組動態(tài)數(shù)據(jù)庫，歷史數(shù)據(jù)更新。當所有歷史數(shù)據(jù)完成更新時對數(shù)據(jù)進行統(tǒng)計，完成第一序列數(shù)據(jù)更新，并將其標記為FdD。

3)依據(jù)FdD來合并新舊數(shù)據(jù)樹。其合并步驟如下。

(1)輸入歷史數(shù)據(jù)樹和更新數(shù)據(jù)樹；(2)建立數(shù)據(jù)樹根節(jié)點；(3)從頭建立數(shù)據(jù)樹子節(jié)點；(4)遍歷數(shù)據(jù)樹節(jié)點；(5)從當前節(jié)點上溯至根節(jié)點路徑；(6)重新排列動態(tài)數(shù)據(jù)庫數(shù)據(jù)；(7)輸出更新后的動態(tài)數(shù)據(jù)庫數(shù)據(jù)。

綜合上述3步，即完成動態(tài)數(shù)據(jù)庫中新增數(shù)據(jù)的更新，此時，即可挖掘動態(tài)數(shù)據(jù)庫中的新增數(shù)據(jù)。

1.4 挖掘動態(tài)數(shù)據(jù)庫

1.4.1 挖掘動態(tài)數(shù)據(jù)庫歷史數(shù)據(jù)

基于多次分組后，節(jié)點得到了動態(tài)數(shù)據(jù)庫歷史分組數(shù)據(jù)，將其整理為〈key=word,value={g1,g2,…,gN}〉，將其作為數(shù)據(jù)挖掘的輸入數(shù)據(jù)，則動態(tài)數(shù)據(jù)庫的歷史數(shù)據(jù)挖掘過程如圖3所示。

圖3 動態(tài)數(shù)據(jù)庫的歷史數(shù)據(jù)挖掘過程

圖中，key表示動態(tài)數(shù)據(jù)庫新輸入數(shù)據(jù)的密鑰?；趫D3所示的動態(tài)數(shù)據(jù)庫的歷史數(shù)據(jù)挖掘過程，將各個節(jié)點數(shù)據(jù)分組，有序輸入數(shù)據(jù)。每當有新數(shù)據(jù)輸入時，都會發(fā)生改變，促進數(shù)據(jù)樹進一步挖掘，待數(shù)據(jù)輸出后會又重新計算其頻繁項集，清空數(shù)據(jù)樹，對動態(tài)數(shù)據(jù)庫的歷史數(shù)據(jù)進行重新挖掘。

1.4.2 挖掘動態(tài)數(shù)據(jù)庫增量數(shù)據(jù)

基于更新動態(tài)數(shù)據(jù)庫新增數(shù)據(jù)所分出的4種情形，需要采用不同的策略來挖掘動態(tài)數(shù)據(jù)庫中的新增數(shù)據(jù)，所以，此次設計的挖掘過程如圖4所示。

圖4 動態(tài)數(shù)據(jù)庫的增量更新數(shù)據(jù)挖掘流程

從圖4中可以看出，情形1中的項集，在動態(tài)數(shù)據(jù)庫的整體數(shù)據(jù)中，也屬于頻繁情況；情形2中的項集，需要計算其頻次，并將Qd和QD的項集頻次累加，即可確定數(shù)據(jù)的頻繁性；情形3需要重新計算各個節(jié)點的數(shù)據(jù)，獲取其在整體數(shù)據(jù)中的頻次信息；情形4中的數(shù)據(jù)在動態(tài)數(shù)據(jù)庫中并不頻繁，沒有數(shù)據(jù)可以挖掘。根據(jù)文中劃分的3種情形，完成動態(tài)數(shù)據(jù)庫中的新增數(shù)據(jù)挖掘后，將歷史數(shù)據(jù)和新增數(shù)據(jù)結合，即可得到動態(tài)數(shù)據(jù)庫中的關聯(lián)數(shù)據(jù)。

2 實驗論證分析

本次實驗將采用對比實驗的方式，以某系統(tǒng)的動態(tài)數(shù)據(jù)庫軟件作為此次實驗的研究對象，在計算機上驗證此次研究的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法。并將此次研究的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法記為實驗A組；兩組傳統(tǒng)的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法分別記為實驗B組和實驗C組。確定時間標準差計算式，改變基本窗口數(shù)量和支持度，對比3組方法的運行時間、內(nèi)存使用情況和節(jié)點任務分配度。

2.1 實驗準備

根據(jù)此次實驗，選擇了3組動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，設計的方法運行環(huán)境如表1所示。

表1 方法運行環(huán)境

為驗算此次研究的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，選擇了動態(tài)數(shù)據(jù)庫Mushroom數(shù)據(jù)源，設計實驗數(shù)據(jù)流來比較3組方法。此次實驗，將Mushroom數(shù)據(jù)源數(shù)據(jù)流的基本窗口數(shù)量設定為10，每個基本窗口中的事務數(shù)設定為200，則10個基本窗口的總數(shù)據(jù)數(shù)為2 000。在該數(shù)據(jù)流的基礎數(shù)據(jù)上，讓其隨著時間衰減，增加基本窗口。其中，w表示基本窗口數(shù)。根據(jù)Mushroom數(shù)據(jù)源數(shù)據(jù)流窗口數(shù)據(jù)增加情況，設置的時間衰減權重函數(shù)如式(3)。

w(d)=1-50%*(d-1)

(3)

式中，d表示時間衰減標識，即可以將首次讀入的基本窗口數(shù)據(jù)記為d=1，當窗口數(shù)增加時，其每一次增加的數(shù)據(jù)，增加值都為1。

依據(jù)上述內(nèi)容，確定了該方法的運行環(huán)境和實驗對象，選擇Test Director軟件測試工具，測試3組方法的運行時間、內(nèi)存占用情況和時間標準差，并形成XRD圖，對比3組動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，其實驗過程及結果如下。

2.2 實驗結果

2.2.1 第一組實驗

基于此次實驗設置的實驗對象，將基本窗口數(shù)據(jù)的支持度設置為10%，每增加一個基本窗口，都會Mushroom數(shù)據(jù)源數(shù)據(jù)流窗口數(shù)據(jù)增加情況，增加數(shù)據(jù)。此時，Mushroom數(shù)據(jù)源數(shù)據(jù)流窗口數(shù)據(jù)增加情況，改變基本窗口有效數(shù)據(jù)數(shù)目，測試3組方法運行時間，其實驗結果如圖5所示。

圖5 相同支持度下，不同窗口數(shù)據(jù)運行時間比較圖

從圖5可以看出，在時間衰減權重函數(shù)作用下，實驗C組的平均運行時間高達3 900 s；實驗B組其平均運行時間依然達到了3 616.7 s；而實驗A組在挖掘基本窗口中的數(shù)據(jù)時，運行時間波動最小，僅需450 s。由此可見，在同一支持度，不同窗口數(shù)據(jù)下，挖掘動態(tài)數(shù)據(jù)庫數(shù)據(jù)，運行時間波動較小，方法運行速度較快。

2.2.2 第二組實驗

基于上述結果，進行第二組實驗，改變基本窗口的支持度，并將其首次支持數(shù)記為30%，對比3組方法，在挖掘窗口數(shù)據(jù)時，對處理器內(nèi)存的使用情況。此后每隔10%，記錄一次方法對處理器內(nèi)存使用量。為保證實驗的嚴謹性，將3組方法在首次支持度下，挖掘窗口數(shù)據(jù)對處理器內(nèi)存的使用情況比較2次，分別為讀入數(shù)據(jù)時給定的支持數(shù)據(jù)和更新支持度后的支持數(shù)據(jù)。其實驗結果如圖6所示。

圖6 不同支持度下，方法內(nèi)存使用量對比

從圖6可以看出，不同支持度在挖掘數(shù)據(jù)過程中，處理器的內(nèi)存占用量都在不斷降低至固定值。實驗B組所占用的內(nèi)存在逐漸恢復平穩(wěn)時，出現(xiàn)大幅度下降現(xiàn)象；實驗C組和實驗A組所占用的內(nèi)存，都在同一支持度下逐漸走向平穩(wěn)。由此可見，此次研究的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，在支持度不同的條件下，內(nèi)存使用量偏低，在處理器存儲方面的開銷也較小。

2.2.3 第三組實驗

基于第一組和第二組實驗結果基礎上，進行第三組實驗，通過任務執(zhí)行時間標準差，對比3組方法中的各個節(jié)點任務分配均度。為此假設3組方法的計算節(jié)點數(shù)量為N，第i個節(jié)點任務執(zhí)行時間為ti，則獲得節(jié)點任務執(zhí)行時間的標準差σ為式(4)。

(4)

圖7 不同支持度下，方法節(jié)點的時間標準差

從圖7可以看出，在不同支持度下，實驗C組的時間標準差出現(xiàn)了下降趨勢，而實驗A組、B組的時間標準差都出現(xiàn)了一定的上升趨勢。由此可見，此次研究的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，受到支持度影響較小，可以均勻分配各個節(jié)點的計算量。

3 總結

綜上所述，本文提出的基于大數(shù)據(jù)集的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，充分利用大數(shù)據(jù)時代下的大數(shù)據(jù)技術，研究動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，優(yōu)化動態(tài)數(shù)據(jù)庫中數(shù)據(jù)的挖掘效率。但是，此次研究的基于大數(shù)據(jù)集的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，未曾考慮大數(shù)據(jù)時代網(wǎng)絡數(shù)據(jù)的膨脹速度。因此在今后的研究中，還需深入研究基于大數(shù)據(jù)集的動態(tài)數(shù)據(jù)庫關聯(lián)挖掘方法，分析大數(shù)據(jù)時代網(wǎng)絡數(shù)據(jù)的膨脹速度，研究出可以挖掘不同數(shù)據(jù)交互、數(shù)據(jù)共享等動態(tài)數(shù)據(jù)庫挖掘方法。