唐雯煒，李志敏

(浙江中醫(yī)藥大學(xué)信息技術(shù)中心，浙江 杭州 310053)

1 引言

信息化進(jìn)程腳步的加快，使得數(shù)據(jù)庫技術(shù)也取得突飛猛進(jìn)的發(fā)展，同時(shí)信息系統(tǒng)的存儲壓力和計(jì)算壓力也隨之增加。面對數(shù)據(jù)庫中的海量數(shù)據(jù)，從中獲取部分有價(jià)值的信息難度較大，且當(dāng)前的信息提取方法步驟較為繁瑣。因此，如何在數(shù)量巨大的數(shù)據(jù)中快速找到數(shù)據(jù)點(diǎn)所在的位置、挖掘其隱含的信息已經(jīng)成為了日后重點(diǎn)研究方向。

針對數(shù)據(jù)點(diǎn)位置的挖掘問題，相關(guān)領(lǐng)域研究學(xué)家們也對此展開了深入研究。文獻(xiàn)[1]利用人工智能裁決機(jī)制對網(wǎng)絡(luò)的挖掘?qū)挾?、網(wǎng)絡(luò)環(huán)境以及節(jié)點(diǎn)存儲大小等多方面因素進(jìn)行綜合考慮，確定這些因素對挖掘效果產(chǎn)生的影響程度，以此獲得數(shù)據(jù)挖掘的難易程度。然后，通過所得結(jié)果采取強(qiáng)化措施來提高算法的挖掘效率，但是挖掘精度有待提高；文獻(xiàn)[2]利用智能網(wǎng)絡(luò)系統(tǒng)對低匹配度的數(shù)據(jù)進(jìn)行了研究。首先，對數(shù)據(jù)進(jìn)行預(yù)處理，使其轉(zhuǎn)換為便于挖掘的規(guī)約形式，在一定程度上確保算法具有更高的挖掘效率；然后，對算法的挖掘規(guī)則利用神經(jīng)網(wǎng)絡(luò)模型進(jìn)行更新，同時(shí)剔除掉其中包含的冗余連接節(jié)點(diǎn)；最后，通過I/O輸出完成挖掘的數(shù)據(jù)。該方法對低匹配度的數(shù)據(jù)具有較為理想的效果，但并不適合處理高維或多模態(tài)數(shù)據(jù)。

為解決以上傳統(tǒng)方法的缺陷，提出基于并行FP-Growth算法的數(shù)據(jù)點(diǎn)位置智能挖掘算法。結(jié)合并行FP-Growth算法與MAP/Reduce并行編程模型，形成新的FPPM算法。該算法通過計(jì)算與之對應(yīng)的局部頻繁項(xiàng)目集，整合在一起得到全局頻繁項(xiàng)目集，并計(jì)算每個(gè)項(xiàng)目集屬性，利用增量分類的方法找出最佳屬性，同時(shí)統(tǒng)計(jì)每個(gè)屬性出現(xiàn)的次數(shù)，利用構(gòu)建的決策分支樹實(shí)現(xiàn)對數(shù)據(jù)點(diǎn)位置地準(zhǔn)確挖掘。在仿真中，本文方法較傳統(tǒng)方法相比在CPU占用率、挖掘時(shí)延、信息熵方面均取得了理想的結(jié)果，并且具有理想的可擴(kuò)展性。

2 FPPM算法優(yōu)化建立

2.1 并行FP-Growth算法

利用并行FP-Growth算法實(shí)現(xiàn)數(shù)據(jù)挖掘主要是通過頻繁模式增長的方式來實(shí)現(xiàn)的。首先，算法掃描待識別的事務(wù)數(shù)據(jù)集D，得到一個(gè)緊湊且包含事務(wù)集中所有頻繁模式信息的頻繁模式樹[3]，完成數(shù)據(jù)點(diǎn)的位置挖掘。

頻繁模式樹的建立過程主要通過以下四個(gè)步驟完成：

1)對處理器的每個(gè)處理過程都分配與之個(gè)數(shù)相等的事務(wù)集；

2)每個(gè)處理過程計(jì)算局部頻繁項(xiàng)集的計(jì)數(shù)；

3)將所有局部頻繁項(xiàng)集的計(jì)數(shù)[6]整合在一起，得到全局頻繁1-項(xiàng)集；

4)根據(jù)全局頻繁1-項(xiàng)集對所有處理過程進(jìn)行掃描，并將全局頻繁1-項(xiàng)集中的節(jié)點(diǎn)與局部頻繁項(xiàng)集中的節(jié)點(diǎn)連接在一起，形成頻繁模式樹。

全局頻繁1-項(xiàng)集與局部頻繁模式樹在連接的過程中，形成了一種連接網(wǎng)絡(luò)，這個(gè)網(wǎng)絡(luò)就是FP-tree，同時(shí)也是實(shí)現(xiàn)數(shù)據(jù)點(diǎn)位置挖掘的有力保障。

2.2 FP-tree建立

FP-tree中，通常以“null”作為樹的根節(jié)點(diǎn)。隨機(jī)選取一個(gè)節(jié)點(diǎn)a，在從根節(jié)點(diǎn)延伸出的路徑中，將不包含a所在的部分路徑稱之為a的前綴路徑，a則是該條路徑的后綴項(xiàng)。前綴路徑不斷延伸，始終都有a的存在，當(dāng)這些路徑在某個(gè)節(jié)點(diǎn)相交時(shí)，即可得到a的條件模式基。由條件模式基可以構(gòu)建條件模式樹[7]，在條件模式樹下再進(jìn)行數(shù)據(jù)點(diǎn)位置的挖掘，可以快速得到頻繁模式下的數(shù)據(jù)。

將事務(wù)數(shù)據(jù)集定義為D、最小支持度設(shè)置為2，通過表1的事務(wù)集建立如圖1所示的FP-tree。

表1 事務(wù)數(shù)據(jù)集D

圖1 構(gòu)建的FP-tree

2.3 Map/Reduce并行編程模型

Map/Reduce在處理數(shù)量巨大的挖掘工作時(shí)，會分配給每一個(gè)主節(jié)點(diǎn)以及其下一層的各個(gè)分節(jié)點(diǎn)來共同完成工作，最后將各個(gè)分節(jié)點(diǎn)的數(shù)據(jù)整合在一起，即為最終的挖掘結(jié)果。換句話說，Map/Reduce的主要工作是分配任務(wù)與匯總結(jié)果。將分配任務(wù)與匯總結(jié)果用函數(shù)表示為：Map和Reduce。這兩個(gè)函數(shù)的主要任務(wù)就是處理輸入鍵值對。

在Map函數(shù)中，數(shù)據(jù)的格式發(fā)生改變，以分片的形式存在，而Mapper存在于每一個(gè)分片上。首先，在Map函數(shù)中輸入鍵值對為的數(shù)值，計(jì)算后得到結(jié)果為[]的數(shù)值，根據(jù)鍵值[8]的不同對其進(jìn)行排列，相同的則劃分在>元組內(nèi)；最后，將劃分結(jié)果傳送至Reducer模塊中。

在Reducer這個(gè)階段中，Reducer將從不同Mapper傳送來的元組整合在一起，利用reducer函數(shù)處理>，以此獲得新的鍵值對，并將reducer函數(shù)輸出結(jié)果引入到HDFS中。

2.4 FPPM算法框架

將并行FP-Growth算法與Map/Reduce并行編程模型整合在一起，得到FPPM算法。

FPPM算法實(shí)現(xiàn)過程為：

1)對D中1-項(xiàng)集的支持?jǐn)?shù)進(jìn)行具體數(shù)值的計(jì)算：初始化一個(gè)統(tǒng)計(jì)頻繁項(xiàng)目集的Map/Reduce job，將輸出結(jié)果存儲在分布式緩存模塊中；

3)篩選候選全局頻繁項(xiàng)目集，并對其進(jìn)行統(tǒng)計(jì)運(yùn)算：重新初始化一個(gè)Map/Reduce job，將步驟2)中存儲在分布式文件內(nèi)的元組進(jìn)行支持度的計(jì)算，最終得到最小支持度下的頻繁項(xiàng)目集，在全局頻繁項(xiàng)集中進(jìn)行匯總。

步驟2)和步驟3)所得計(jì)算結(jié)果即為數(shù)據(jù)點(diǎn)位置的全局頻繁項(xiàng)目集。

3 數(shù)據(jù)點(diǎn)位置智能挖掘

3.1 選取候選屬性子集

將t定義為時(shí)間。隨機(jī)選定一個(gè)時(shí)刻t，將D中的全部數(shù)據(jù)傳輸至reducer函數(shù)中，傳輸過程如式(1)所示

Dt=[Xt，Yt]

(1)

式中，X、Y分別表示數(shù)據(jù)集中數(shù)據(jù)的屬性[10]。設(shè)定一段時(shí)長為T的時(shí)間段，選取其中某個(gè)時(shí)刻并將其標(biāo)記為t=1，2，…，T，將這個(gè)時(shí)間段以內(nèi)的數(shù)據(jù)標(biāo)記為DT，算法如下

(2)

用H(.)來表示并行FP-Growth算法的功能，通過運(yùn)用貪婪算法實(shí)現(xiàn)最優(yōu)FP-tree的構(gòu)建。算法中，H(.)的主要作用為計(jì)算數(shù)據(jù)點(diǎn)位置的信息增量[11]，并且按照由高到低的順序?qū)γ總€(gè)分支點(diǎn)的邊界輸入相應(yīng)的標(biāo)簽信息，然后選取分類的最佳屬性Xi。對于所選取的最佳屬性Xi，檢索i(i≤M)和j(j≤N)，其中，M表示屬性個(gè)數(shù)的最大值，N表示接收實(shí)例個(gè)數(shù)的最大值，也可以看作是xij的分支值。因此，從xi1到xij的分支值中選取滿足xij=arg maxH(xij)條件的功能屬性Xi。

為確保輸入結(jié)果是全局最優(yōu)解[12]，在以上計(jì)算過程中，就要使所有數(shù)據(jù)點(diǎn)的位置都在DT中，計(jì)算公式如式(3)所示

(3)

在任意時(shí)刻t下，將Xt定義為將要篩選的全部新數(shù)據(jù)集，在集合{Ytk}中整合數(shù)據(jù)點(diǎn)位置信息。{Ytk}中，k為在可能集合K中的任意一個(gè)可能集合序列號。

根據(jù)當(dāng)前所篩選的頻繁項(xiàng)目集，本文將FPPM算法按照最優(yōu)分類的原則計(jì)算，計(jì)算過程如式(4)所示

(4)

在時(shí)間t內(nèi)，數(shù)據(jù)點(diǎn)位置信息已經(jīng)全部匯總在DT內(nèi)，并在全局頻繁項(xiàng)目集中以良好的形式在集合TRGLOBAL中展現(xiàn)出來。在時(shí)間t+1內(nèi)，數(shù)據(jù)點(diǎn)位置信息更新到新的集合TRGLOBAL內(nèi)，通過式(3)和式(4)實(shí)現(xiàn)自我更新，更新時(shí)間隨著t和DT的上升而不斷延長。每更新一次，所有數(shù)據(jù)點(diǎn)位置信息都要重新載入DT的歷史數(shù)據(jù)。

3.2 數(shù)據(jù)點(diǎn)位置挖掘計(jì)算

在利用FPPM算法對數(shù)據(jù)點(diǎn)位置挖掘時(shí)，所采集到的數(shù)據(jù)量是非常巨大的，并且伴隨著新數(shù)據(jù)點(diǎn)位置信息的產(chǎn)生處理起來也是非常繁瑣的。因此，在處理此類數(shù)據(jù)時(shí)，本文利用增量分類的方法確保算法具有理想的挖掘效果。

增量分類的方法就是在所有候選屬性數(shù)據(jù)集中，找出可靠度最佳的數(shù)據(jù)集，將這些最佳數(shù)據(jù)集整合在一起，即可得到最佳候選屬性集。在利用增量分類方法提取數(shù)據(jù)點(diǎn)位置的過程中，只需要操作一次，無需重復(fù)操作，因此該方法也被稱為任意算法。通過統(tǒng)計(jì)每個(gè)屬性值出現(xiàn)的次數(shù)，來構(gòu)建決策分支樹。在計(jì)算過程中，Xi出現(xiàn)的頻率、與Xi的類Yk都通過(5)Hoffding計(jì)算得到

(5)

式中，R用來約束分類屬性，n表示同一數(shù)據(jù)集合中的個(gè)數(shù)，δ表示約束系數(shù)。在該算法中，通過兩組高值集合項(xiàng)推薦得到。對于任意時(shí)刻t下，Xi具有兩個(gè)最大集合值項(xiàng)檢測Xi，檢測結(jié)果分別為xin和xib，這兩個(gè)值均滿足條件xin=arg maxH(xij)和xib=arg maxH(xij)。通過上述的計(jì)算過程，即可完成對數(shù)據(jù)點(diǎn)位置的挖掘。

4 仿真研究

為驗(yàn)證本文提出的基于并行FP-Growth算法的數(shù)據(jù)點(diǎn)位置智能挖掘算法的有效性，與文獻(xiàn)[1]提出的基于人工智能裁決機(jī)制的數(shù)據(jù)點(diǎn)位置挖掘方法、文獻(xiàn)[2]提出的基于智能網(wǎng)絡(luò)系統(tǒng)的數(shù)據(jù)點(diǎn)位置挖掘方法進(jìn)行了對比仿真。仿真中所用到的數(shù)據(jù)均來自于IBM DataGen，其中包含了多達(dá)1000個(gè)種類的數(shù)據(jù)類型，所有數(shù)據(jù)的記錄長度均保持在10。

4.1 CPU占用率測試

為了驗(yàn)證三種方法在挖掘數(shù)據(jù)點(diǎn)位置過程中的CPU占用率，在上述實(shí)驗(yàn)環(huán)境中，依照實(shí)驗(yàn)設(shè)定的參數(shù)，展開對比仿真，仿真結(jié)果如圖2所示。

圖2 三種方法CPU占用率對比

從圖2中可以看出，不論節(jié)點(diǎn)數(shù)量怎樣變化，本文方法較其它兩種方法相比，均展現(xiàn)出了明顯的優(yōu)勢，一直保持在較低的水平下，并且波動(dòng)幅度也較其它兩種方法相比要小。這是由于本文方法引入了增量分類方法，快速處理各類數(shù)據(jù)巨大且復(fù)雜的數(shù)據(jù)，實(shí)現(xiàn)高效挖掘，同時(shí)，使算法整體保持在平穩(wěn)的狀態(tài)下，避免出現(xiàn)較大的波動(dòng)。

4.2 挖掘時(shí)延測試

隨著節(jié)點(diǎn)數(shù)量的不斷增加，挖掘時(shí)延也發(fā)生了改變。本文方法與其它兩種方法相比，在挖掘時(shí)延方面的測試結(jié)果如圖3所示。

圖3 三種方法挖掘時(shí)延對比

從圖3中可以看出，雖然節(jié)點(diǎn)數(shù)量在不斷的增加，但是本文方法的挖掘時(shí)延一直比其它兩種方法要低，并且波動(dòng)的幅度也較其它兩種方法相比要緩一些。這是由于本文方法在挖掘數(shù)據(jù)點(diǎn)位置的過程中，將挖掘的帶寬、數(shù)據(jù)集的存儲大小以及多種因素綜合考慮在內(nèi)，在節(jié)點(diǎn)數(shù)量不斷增加的同時(shí)進(jìn)行快速的運(yùn)算，有效降低挖掘時(shí)延。

4.3 數(shù)據(jù)點(diǎn)位置信息熵

隨著挖掘得出節(jié)點(diǎn)位置數(shù)量不斷增加，為了驗(yàn)證其位置結(jié)果是否存在有效信息和數(shù)據(jù)，通過信息熵指標(biāo)判斷。信息熵能夠描述挖掘結(jié)果內(nèi)信息量的大小，設(shè)定大于0.5的位置信息為挖掘有效數(shù)據(jù)。圖4為分別運(yùn)用三種方法挖掘信息熵結(jié)果對比圖。

圖4 挖掘信息熵對比

從圖4中可以看出，三種方法挖掘結(jié)果均大于0.5，都符合要求，但是相對于文獻(xiàn)方法來說，本文方法的位置信息熵值更高、曲線更加平穩(wěn)，沒有出現(xiàn)較大的波動(dòng)。這是由于本文方法充分考慮到了數(shù)據(jù)點(diǎn)的屬性信息，只需要在計(jì)算過程中輸入與之對應(yīng)的標(biāo)簽信息即可，減少了計(jì)算步驟，因此可有效降低挖掘出現(xiàn)異常情況的概率。

4.4 可擴(kuò)展性測試

可擴(kuò)展性指的是當(dāng)節(jié)點(diǎn)數(shù)量按照一定的比例增加時(shí)，計(jì)算此時(shí)的算法性能?？蓴U(kuò)展性scaleup的計(jì)算公式如式(6)所示

scaleup(D，m)=t1*D/tm*m*D

(6)

式中，t1*DB表示1個(gè)節(jié)點(diǎn)在D中所花費(fèi)的計(jì)算時(shí)間；tm*m*D表示當(dāng)節(jié)點(diǎn)數(shù)量為m時(shí)，在規(guī)模大小為m*D的項(xiàng)目集上運(yùn)行所花費(fèi)的時(shí)間。

在評判過程中，當(dāng)scaleup的值在0.65以上，說明該算法具有優(yōu)秀的可擴(kuò)展性。圖5為本文方法在支持度大小分別為5%、10%、15%的情況下，所得的可擴(kuò)展性結(jié)果。

圖5 支持度不同的情況下本文方法可擴(kuò)展性

從圖5中可以看出，本文方法在支持度不同的情況下，所得scaleup的計(jì)算結(jié)果均在0.65以上，說明本文方法具有優(yōu)秀的可擴(kuò)展性。

5 結(jié)論

本文通過并行FP-Growth算法與Map/Reduce并行編程模型的結(jié)合，使得FP-tree在挖掘迭代的過程中具有更為理想的效率。通過設(shè)置仿真，在CPU占用率、挖掘時(shí)延、信息熵方面與傳統(tǒng)方法展開對比，驗(yàn)證了本文方法在挖掘時(shí)延較少的前提下實(shí)現(xiàn)了對數(shù)據(jù)點(diǎn)位置的高效率挖掘。最后在支持度不同的情況下對本文方法的可擴(kuò)展性完成了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明本文方法具有優(yōu)秀的可擴(kuò)展性。