唐雯煒，李志敏

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

1 引言

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

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

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

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

2.1 并行FP-Growth算法

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

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

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

2)每個處理過程計算局部頻繁項集的計數(shù)；

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

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

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

2.2 FP-tree建立

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

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

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

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

2.3 Map/Reduce并行編程模型

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

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

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

2.4 FPPM算法框架

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

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

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

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

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

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

3.1 選取候選屬性子集

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

Dt=[Xt，Yt]

(1)

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

(2)

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

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

(3)

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

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

(4)

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

3.2 數(shù)據(jù)點位置挖掘計算

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

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

(5)

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

4 仿真研究

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

4.1 CPU占用率測試

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

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

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

4.2 挖掘時延測試

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

圖3 三種方法挖掘時延對比

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

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

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

圖4 挖掘信息熵對比

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

4.4 可擴展性測試

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

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

(6)

式中，t1*DB表示1個節(jié)點在D中所花費的計算時間；tm*m*D表示當節(jié)點數(shù)量為m時，在規(guī)模大小為m*D的項目集上運行所花費的時間。

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

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

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

5 結(jié)論

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