劉張榕
(福建林業(yè)職業(yè)技術(shù)學(xué)院 信息工程系,福建 南平 353000)
數(shù)據(jù)庫(kù)種類可以按照有效性,分為靜態(tài)數(shù)據(jù)庫(kù)、動(dòng)態(tài)數(shù)據(jù)庫(kù)和實(shí)時(shí)數(shù)據(jù)庫(kù)3種,在檢索數(shù)據(jù)庫(kù)中的數(shù)據(jù)時(shí),大多是從靜態(tài)數(shù)據(jù)庫(kù)中挖掘數(shù)據(jù)。但數(shù)據(jù)庫(kù)的實(shí)時(shí)性,又使數(shù)據(jù)庫(kù)處于一種動(dòng)態(tài)變化中,不斷在數(shù)據(jù)庫(kù)中積累新的數(shù)據(jù),此時(shí),采用挖掘方法挖掘到的靜態(tài)數(shù)據(jù)庫(kù)數(shù)據(jù),則會(huì)因?yàn)閿?shù)據(jù)庫(kù)數(shù)據(jù)的更新,出現(xiàn)知識(shí)失效問題[1-2]。所以,需要研究動(dòng)態(tài)數(shù)據(jù)庫(kù)數(shù)據(jù)挖掘方法。
目前,國(guó)內(nèi)外對(duì)動(dòng)態(tài)數(shù)據(jù)庫(kù)挖掘也有許多研究,文獻(xiàn)[3]提出了多域分布式數(shù)據(jù)庫(kù)的電能質(zhì)量擾動(dòng)事件記錄關(guān)聯(lián)規(guī)則挖掘,采用移動(dòng)時(shí)間窗技術(shù)實(shí)現(xiàn)擾動(dòng)數(shù)據(jù)預(yù)處理,然后在考慮數(shù)據(jù)庫(kù)更新的情況下,提出一種分布式協(xié)同算法,該算法通過交換各數(shù)據(jù)庫(kù)間的局部頻繁項(xiàng)目集,實(shí)現(xiàn)擾動(dòng)數(shù)據(jù)關(guān)聯(lián)模式分布式挖掘。文獻(xiàn)[4]設(shè)計(jì)了基于聚類優(yōu)化的大型網(wǎng)絡(luò)數(shù)據(jù)庫(kù)挖掘系統(tǒng),該搭建數(shù)據(jù)采集所需的傳感器節(jié)點(diǎn)結(jié)構(gòu),選擇CC3200作為主控芯片,在原有的電路中引入射頻通信電路,實(shí)現(xiàn)數(shù)據(jù)的無線傳輸。在此基礎(chǔ)上,對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)進(jìn)行預(yù)處理,利用優(yōu)化后的聚類算法和軟件程序?qū)崿F(xiàn)數(shù)據(jù)挖掘,至此系統(tǒng)設(shè)計(jì)完成。
針對(duì)上述存在問題,本文提出基于大數(shù)據(jù)集的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘研究。
在動(dòng)態(tài)數(shù)據(jù)庫(kù)中,會(huì)存在歷史數(shù)據(jù)和新增數(shù)據(jù)兩種,因此,此次研究動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,將選擇靜態(tài)挖掘與動(dòng)態(tài)挖掘相結(jié)合的方式,先挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)中的歷史數(shù)據(jù),再挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)中的更新數(shù)據(jù)。
在大數(shù)據(jù)背景下,采用大數(shù)據(jù)集中的分布式計(jì)算,分布式存儲(chǔ)動(dòng)態(tài)數(shù)據(jù)庫(kù)中的歷史數(shù)據(jù),需要將動(dòng)態(tài)數(shù)據(jù)庫(kù)中的原始大數(shù)據(jù)分割成多個(gè)子數(shù)據(jù)集,大量的小文件則需要合并為一個(gè)子數(shù)據(jù)集,從而提高數(shù)據(jù)存儲(chǔ)效率。此時(shí),需要采用并行化技術(shù)統(tǒng)計(jì)方式,優(yōu)化每一個(gè)子數(shù)據(jù)集中的數(shù)據(jù)量,并將數(shù)據(jù)的空間與時(shí)間復(fù)雜度記為O,單節(jié)點(diǎn)中分片數(shù)據(jù)量記為D,則數(shù)據(jù)的分布式存儲(chǔ)過程,如圖1所示。
圖1 數(shù)據(jù)分布式存儲(chǔ)過程
從圖1中可以看出,采用分割的方式將合并的小文件和分割的子數(shù)據(jù)集存儲(chǔ)至各個(gè)節(jié)點(diǎn)中,通過并行化統(tǒng)計(jì),判斷各個(gè)節(jié)點(diǎn)數(shù)據(jù)的支持度,從而去除不滿足支持度的數(shù)據(jù)項(xiàng),得到第一序列數(shù)據(jù)。完成數(shù)據(jù)分布式存儲(chǔ)。
根據(jù)圖1得到的第一序列數(shù)據(jù),需要進(jìn)行數(shù)據(jù)修剪重排分組和計(jì)算量預(yù)估與均衡化分組。
(1)數(shù)據(jù)修剪重排分組。對(duì)于動(dòng)態(tài)數(shù)據(jù)庫(kù)中的原始數(shù)據(jù),按照?qǐng)D1得到的第一序列數(shù)據(jù),進(jìn)行修剪排序,即刪除原始數(shù)據(jù)中不滿足支持度閾值的數(shù)據(jù)項(xiàng),修剪后的數(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ù)進(jìn)行修剪重排分組后,得到的數(shù)據(jù)為〈p,w,n,s,v〉,再按照數(shù)據(jù)的后綴進(jìn)行迭代分割,采用Key-Value的形式表達(dá),則得到{v,〈p,w,n,s〉},{s,〈p,w,n〉},{n,〈p,w〉},{w,〈p〉}。此時(shí),得到的修剪重排分組后的數(shù)據(jù)需要再次存儲(chǔ)至圖1所示的節(jié)點(diǎn)中,進(jìn)行計(jì)算量預(yù)估與均衡化分組處理。
(2)計(jì)算量預(yù)估與均衡化分組。計(jì)算圖2得到的數(shù)據(jù),需要根據(jù)第一序列數(shù)據(jù)中,存在的以e為后綴的數(shù)據(jù)位置,計(jì)算量數(shù)據(jù)C(e)的估值,如式(1)。
C(e)=log(P(e,F))
(1)
式中,F(xiàn)表示第一序列數(shù)據(jù);P表示以e為后綴的數(shù)據(jù)位置,與第一序列數(shù)據(jù)之間的關(guān)聯(lián)。此時(shí),需要按照式(1)得到的關(guān)聯(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ì)算量估值按照計(jì)算均衡化分配來進(jìn)行分組歸類。對(duì)此,假設(shè)需要計(jì)算的數(shù)據(jù)節(jié)點(diǎn)數(shù)為N,依據(jù)計(jì)算節(jié)點(diǎn)數(shù)N建立分組記錄表gN,需要將每一計(jì)算節(jié)點(diǎn)都與分組數(shù)據(jù)相對(duì)應(yīng)。則均衡化分組流程如下。
(1)將計(jì)算量數(shù)據(jù)C(e)的估值中的前N個(gè)節(jié)點(diǎn)數(shù)據(jù)保存至分組記錄表gN中;(2)計(jì)算gN的各個(gè)節(jié)點(diǎn)數(shù)據(jù)集之和,作為gN的計(jì)算估值;(3)確定計(jì)算量數(shù)據(jù)C(e)的估值中存在的多余節(jié)點(diǎn)數(shù)據(jù)數(shù)目;(4)將多余節(jié)點(diǎn)數(shù)據(jù)依次加入gN中,并計(jì)算估值最小列表;(5)更新gN對(duì)應(yīng)的計(jì)算估值。綜合上述內(nèi)容,即完成數(shù)據(jù)分組處理。
更新動(dòng)態(tài)數(shù)據(jù)庫(kù)數(shù)據(jù)時(shí),需要構(gòu)建數(shù)據(jù)樹,并將數(shù)據(jù)樹分為多個(gè)子數(shù)據(jù)樹和總數(shù)據(jù)樹,更新匯聚在節(jié)點(diǎn)的第一序列數(shù)據(jù),為此設(shè)定如下更新動(dòng)態(tài)數(shù)據(jù)庫(kù)新增數(shù)據(jù)步驟。
1)更新動(dòng)態(tài)數(shù)據(jù)庫(kù)新增數(shù)據(jù)特征。假設(shè)動(dòng)態(tài)數(shù)據(jù)庫(kù)新增數(shù)據(jù)為d,其d中新增數(shù)據(jù)頻繁項(xiàng)集記錄為Qd,其頻次數(shù)據(jù)記錄為Qd={T1,T3},動(dòng)態(tài)數(shù)據(jù)庫(kù)歷史數(shù)據(jù)為D,歷史數(shù)據(jù)頻繁項(xiàng)集記錄為QD,其頻次數(shù)據(jù)為QD={T1,T2}。將歷史數(shù)據(jù)和新增數(shù)據(jù)累加,記錄為QdD。此時(shí)更新動(dòng)態(tài)數(shù)據(jù)庫(kù)中的歷史數(shù)據(jù),會(huì)出現(xiàn)如下4種情形:(1)如T1∈Qd,T1∈QD,即T1在Qd和QD中,均屬于頻繁項(xiàng)集;(2)如T2?Qd,T2∈QD,即T2僅在QD中屬于頻繁項(xiàng)集;(3)如T3∈Qd,T3?QD,即T3僅在Qd中屬于頻繁項(xiàng)集;(4)如T4?Qd,T4?QD,即T4在Qd和QD中,均為非頻繁項(xiàng)集[7-8]。
2)按照步驟1,即可完成一組動(dòng)態(tài)數(shù)據(jù)庫(kù),歷史數(shù)據(jù)更新。當(dāng)所有歷史數(shù)據(jù)完成更新時(shí)對(duì)數(shù)據(jù)進(jìn)行統(tǒng)計(jì),完成第一序列數(shù)據(jù)更新,并將其標(biāo)記為FdD。
3)依據(jù)FdD來合并新舊數(shù)據(jù)樹。其合并步驟如下。
(1)輸入歷史數(shù)據(jù)樹和更新數(shù)據(jù)樹;(2)建立數(shù)據(jù)樹根節(jié)點(diǎn);(3)從頭建立數(shù)據(jù)樹子節(jié)點(diǎn);(4)遍歷數(shù)據(jù)樹節(jié)點(diǎn);(5)從當(dāng)前節(jié)點(diǎn)上溯至根節(jié)點(diǎn)路徑;(6)重新排列動(dòng)態(tài)數(shù)據(jù)庫(kù)數(shù)據(jù);(7)輸出更新后的動(dòng)態(tài)數(shù)據(jù)庫(kù)數(shù)據(jù)。
綜合上述3步,即完成動(dòng)態(tài)數(shù)據(jù)庫(kù)中新增數(shù)據(jù)的更新,此時(shí),即可挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)中的新增數(shù)據(jù)。
1.4.1 挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)歷史數(shù)據(jù)
基于多次分組后,節(jié)點(diǎn)得到了動(dòng)態(tài)數(shù)據(jù)庫(kù)歷史分組數(shù)據(jù),將其整理為〈key=word,value={g1,g2,…,gN}〉,將其作為數(shù)據(jù)挖掘的輸入數(shù)據(jù),則動(dòng)態(tài)數(shù)據(jù)庫(kù)的歷史數(shù)據(jù)挖掘過程如圖3所示。
圖3 動(dòng)態(tài)數(shù)據(jù)庫(kù)的歷史數(shù)據(jù)挖掘過程
圖中,key表示動(dòng)態(tài)數(shù)據(jù)庫(kù)新輸入數(shù)據(jù)的密鑰。基于圖3所示的動(dòng)態(tài)數(shù)據(jù)庫(kù)的歷史數(shù)據(jù)挖掘過程,將各個(gè)節(jié)點(diǎn)數(shù)據(jù)分組,有序輸入數(shù)據(jù)。每當(dāng)有新數(shù)據(jù)輸入時(shí),都會(huì)發(fā)生改變,促進(jìn)數(shù)據(jù)樹進(jìn)一步挖掘,待數(shù)據(jù)輸出后會(huì)又重新計(jì)算其頻繁項(xiàng)集,清空數(shù)據(jù)樹,對(duì)動(dòng)態(tài)數(shù)據(jù)庫(kù)的歷史數(shù)據(jù)進(jìn)行重新挖掘。
1.4.2 挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)增量數(shù)據(jù)
基于更新動(dòng)態(tài)數(shù)據(jù)庫(kù)新增數(shù)據(jù)所分出的4種情形,需要采用不同的策略來挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)中的新增數(shù)據(jù),所以,此次設(shè)計(jì)的挖掘過程如圖4所示。
圖4 動(dòng)態(tài)數(shù)據(jù)庫(kù)的增量更新數(shù)據(jù)挖掘流程
從圖4中可以看出,情形1中的項(xiàng)集,在動(dòng)態(tài)數(shù)據(jù)庫(kù)的整體數(shù)據(jù)中,也屬于頻繁情況;情形2中的項(xiàng)集,需要計(jì)算其頻次,并將Qd和QD的項(xiàng)集頻次累加,即可確定數(shù)據(jù)的頻繁性;情形3需要重新計(jì)算各個(gè)節(jié)點(diǎn)的數(shù)據(jù),獲取其在整體數(shù)據(jù)中的頻次信息;情形4中的數(shù)據(jù)在動(dòng)態(tài)數(shù)據(jù)庫(kù)中并不頻繁,沒有數(shù)據(jù)可以挖掘。根據(jù)文中劃分的3種情形,完成動(dòng)態(tài)數(shù)據(jù)庫(kù)中的新增數(shù)據(jù)挖掘后,將歷史數(shù)據(jù)和新增數(shù)據(jù)結(jié)合,即可得到動(dòng)態(tài)數(shù)據(jù)庫(kù)中的關(guān)聯(lián)數(shù)據(jù)。
本次實(shí)驗(yàn)將采用對(duì)比實(shí)驗(yàn)的方式,以某系統(tǒng)的動(dòng)態(tài)數(shù)據(jù)庫(kù)軟件作為此次實(shí)驗(yàn)的研究對(duì)象,在計(jì)算機(jī)上驗(yàn)證此次研究的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法。并將此次研究的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法記為實(shí)驗(yàn)A組;兩組傳統(tǒng)的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法分別記為實(shí)驗(yàn)B組和實(shí)驗(yàn)C組。確定時(shí)間標(biāo)準(zhǔn)差計(jì)算式,改變基本窗口數(shù)量和支持度,對(duì)比3組方法的運(yùn)行時(shí)間、內(nèi)存使用情況和節(jié)點(diǎn)任務(wù)分配度。
根據(jù)此次實(shí)驗(yàn),選擇了3組動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,設(shè)計(jì)的方法運(yùn)行環(huán)境如表1所示。
表1 方法運(yùn)行環(huán)境
為驗(yàn)算此次研究的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,選擇了動(dòng)態(tài)數(shù)據(jù)庫(kù)Mushroom數(shù)據(jù)源,設(shè)計(jì)實(shí)驗(yàn)數(shù)據(jù)流來比較3組方法。此次實(shí)驗(yàn),將Mushroom數(shù)據(jù)源數(shù)據(jù)流的基本窗口數(shù)量設(shè)定為10,每個(gè)基本窗口中的事務(wù)數(shù)設(shè)定為200,則10個(gè)基本窗口的總數(shù)據(jù)數(shù)為2 000。在該數(shù)據(jù)流的基礎(chǔ)數(shù)據(jù)上,讓其隨著時(shí)間衰減,增加基本窗口。其中,w表示基本窗口數(shù)。根據(jù)Mushroom數(shù)據(jù)源數(shù)據(jù)流窗口數(shù)據(jù)增加情況,設(shè)置的時(shí)間衰減權(quán)重函數(shù)如式(3)。
w(d)=1-50%*(d-1)
(3)
式中,d表示時(shí)間衰減標(biāo)識(shí),即可以將首次讀入的基本窗口數(shù)據(jù)記為d=1,當(dāng)窗口數(shù)增加時(shí),其每一次增加的數(shù)據(jù),增加值都為1。
依據(jù)上述內(nèi)容,確定了該方法的運(yùn)行環(huán)境和實(shí)驗(yàn)對(duì)象,選擇Test Director軟件測(cè)試工具,測(cè)試3組方法的運(yùn)行時(shí)間、內(nèi)存占用情況和時(shí)間標(biāo)準(zhǔn)差,并形成XRD圖,對(duì)比3組動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,其實(shí)驗(yàn)過程及結(jié)果如下。
2.2.1 第一組實(shí)驗(yàn)
基于此次實(shí)驗(yàn)設(shè)置的實(shí)驗(yàn)對(duì)象,將基本窗口數(shù)據(jù)的支持度設(shè)置為10%,每增加一個(gè)基本窗口,都會(huì)Mushroom數(shù)據(jù)源數(shù)據(jù)流窗口數(shù)據(jù)增加情況,增加數(shù)據(jù)。此時(shí),Mushroom數(shù)據(jù)源數(shù)據(jù)流窗口數(shù)據(jù)增加情況,改變基本窗口有效數(shù)據(jù)數(shù)目,測(cè)試3組方法運(yùn)行時(shí)間,其實(shí)驗(yàn)結(jié)果如圖5所示。
圖5 相同支持度下,不同窗口數(shù)據(jù)運(yùn)行時(shí)間比較圖
從圖5可以看出,在時(shí)間衰減權(quán)重函數(shù)作用下,實(shí)驗(yàn)C組的平均運(yùn)行時(shí)間高達(dá)3 900 s;實(shí)驗(yàn)B組其平均運(yùn)行時(shí)間依然達(dá)到了3 616.7 s;而實(shí)驗(yàn)A組在挖掘基本窗口中的數(shù)據(jù)時(shí),運(yùn)行時(shí)間波動(dòng)最小,僅需450 s。由此可見,在同一支持度,不同窗口數(shù)據(jù)下,挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)數(shù)據(jù),運(yùn)行時(shí)間波動(dòng)較小,方法運(yùn)行速度較快。
2.2.2 第二組實(shí)驗(yàn)
基于上述結(jié)果,進(jìn)行第二組實(shí)驗(yàn),改變基本窗口的支持度,并將其首次支持?jǐn)?shù)記為30%,對(duì)比3組方法,在挖掘窗口數(shù)據(jù)時(shí),對(duì)處理器內(nèi)存的使用情況。此后每隔10%,記錄一次方法對(duì)處理器內(nèi)存使用量。為保證實(shí)驗(yàn)的嚴(yán)謹(jǐn)性,將3組方法在首次支持度下,挖掘窗口數(shù)據(jù)對(duì)處理器內(nèi)存的使用情況比較2次,分別為讀入數(shù)據(jù)時(shí)給定的支持?jǐn)?shù)據(jù)和更新支持度后的支持?jǐn)?shù)據(jù)。其實(shí)驗(yàn)結(jié)果如圖6所示。
圖6 不同支持度下,方法內(nèi)存使用量對(duì)比
從圖6可以看出,不同支持度在挖掘數(shù)據(jù)過程中,處理器的內(nèi)存占用量都在不斷降低至固定值。實(shí)驗(yàn)B組所占用的內(nèi)存在逐漸恢復(fù)平穩(wěn)時(shí),出現(xiàn)大幅度下降現(xiàn)象;實(shí)驗(yàn)C組和實(shí)驗(yàn)A組所占用的內(nèi)存,都在同一支持度下逐漸走向平穩(wěn)。由此可見,此次研究的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,在支持度不同的條件下,內(nèi)存使用量偏低,在處理器存儲(chǔ)方面的開銷也較小。
2.2.3 第三組實(shí)驗(yàn)
基于第一組和第二組實(shí)驗(yàn)結(jié)果基礎(chǔ)上,進(jìn)行第三組實(shí)驗(yàn),通過任務(wù)執(zhí)行時(shí)間標(biāo)準(zhǔn)差,對(duì)比3組方法中的各個(gè)節(jié)點(diǎn)任務(wù)分配均度。為此假設(shè)3組方法的計(jì)算節(jié)點(diǎn)數(shù)量為N,第i個(gè)節(jié)點(diǎn)任務(wù)執(zhí)行時(shí)間為ti,則獲得節(jié)點(diǎn)任務(wù)執(zhí)行時(shí)間的標(biāo)準(zhǔn)差σ為式(4)。
(4)
圖7 不同支持度下,方法節(jié)點(diǎn)的時(shí)間標(biāo)準(zhǔn)差
從圖7可以看出,在不同支持度下,實(shí)驗(yàn)C組的時(shí)間標(biāo)準(zhǔn)差出現(xiàn)了下降趨勢(shì),而實(shí)驗(yàn)A組、B組的時(shí)間標(biāo)準(zhǔn)差都出現(xiàn)了一定的上升趨勢(shì)。由此可見,此次研究的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,受到支持度影響較小,可以均勻分配各個(gè)節(jié)點(diǎn)的計(jì)算量。
綜上所述,本文提出的基于大數(shù)據(jù)集的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,充分利用大數(shù)據(jù)時(shí)代下的大數(shù)據(jù)技術(shù),研究動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,優(yōu)化動(dòng)態(tài)數(shù)據(jù)庫(kù)中數(shù)據(jù)的挖掘效率。但是,此次研究的基于大數(shù)據(jù)集的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,未曾考慮大數(shù)據(jù)時(shí)代網(wǎng)絡(luò)數(shù)據(jù)的膨脹速度。因此在今后的研究中,還需深入研究基于大數(shù)據(jù)集的動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)挖掘方法,分析大數(shù)據(jù)時(shí)代網(wǎng)絡(luò)數(shù)據(jù)的膨脹速度,研究出可以挖掘不同數(shù)據(jù)交互、數(shù)據(jù)共享等動(dòng)態(tài)數(shù)據(jù)庫(kù)挖掘方法。