基于分布式全局頻繁項集挖掘算法的研究

摘要：隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)庫技術(shù)的不斷更新，社會各個領(lǐng)域的數(shù)據(jù)信息增長趨勢飛快，如何能夠從海量數(shù)據(jù)中提取到具有實際應用價值的信息是目前數(shù)據(jù)挖掘領(lǐng)域中的重點研究問題。本文提出了一種分布式的全局頻繁項集挖掘算法（BFM-MGFIS），與傳統(tǒng)的全局頻繁模式挖掘算法（FDM）相比能夠有效提高算法的計算效率。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；算法研究

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1007-9599 （2012） 24-0156-02

1 數(shù)據(jù)挖掘的基本過程

1.1 問題定義。對業(yè)務問題進行詳細分析，歸類數(shù)據(jù)挖掘的問題，了解其應用具體范圍，掌握用戶需要實現(xiàn)的最終目標，發(fā)現(xiàn)某種有利用價值的知識。

1.2 數(shù)據(jù)準備。在進行數(shù)據(jù)挖掘之前完成必要的準備工作，包括數(shù)據(jù)選擇、預處理、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)分割和數(shù)據(jù)壓縮等等。

1.3 數(shù)據(jù)挖掘。數(shù)據(jù)挖掘是整個數(shù)據(jù)挖掘過程的核心，也是發(fā)掘知識的關(guān)鍵點。數(shù)據(jù)挖掘主要是利用相關(guān)算法從已經(jīng)完成預處理的數(shù)據(jù)中發(fā)現(xiàn)內(nèi)在模式，要將數(shù)據(jù)挖掘類型、數(shù)據(jù)挖掘方法、數(shù)據(jù)挖掘效率等問題綜合考慮，再選擇適當?shù)乃惴◤臄?shù)據(jù)中發(fā)掘用戶需要的知識，最終通過特定的方式將其表達出來。

1.4 模式評估。經(jīng)過數(shù)據(jù)挖掘得到的內(nèi)在模式不能夠?qū)?shù)據(jù)的真是含義正確反映出來，并不存在具體的實際利用價值，因此，需要對經(jīng)過數(shù)據(jù)挖掘的模式重新進行評估，將結(jié)果轉(zhuǎn)換成為用戶能夠理解的方式進行表達，或者通過可視化界面顯示出來。

數(shù)據(jù)挖掘過程是一個反復循環(huán)的過程，其中包含了多種反饋回路，如果某一個步驟不能夠到底預定的目標，則需要立刻返回到上一個步驟進行調(diào)整之后重新執(zhí)行，因此，數(shù)據(jù)挖掘過程屬于一種螺旋式的上升過程。

2 分布式關(guān)聯(lián)規(guī)則挖掘

2.1 無主站點的通信模式。當每個站點從本地數(shù)據(jù)庫得到局部數(shù)據(jù)模型之后，再將每個候選集數(shù)據(jù)分別映射到已經(jīng)確認的站點中進行計算，每個站點都得到了全局性規(guī)則部分內(nèi)容之后完成合并工作，使得最終獲取到的數(shù)據(jù)是完整的全局性規(guī)則。每個站點之間都是相互平行的，并不存在主站點。

分組計數(shù)技術(shù)是當處于無主站點的通信模式時經(jīng)常使用到的關(guān)鍵技術(shù)，分組計數(shù)技術(shù)是將待計算的項目集按照一定規(guī)律的映射函數(shù)發(fā)送到與其相對應的站點中進行計數(shù)，同時，將在站點完成計算的項目集支持數(shù)的技術(shù)進行收集，以此減少網(wǎng)絡通信的消耗。

2.2 有主站點的通信模式。當局部站點從本地數(shù)據(jù)庫中得到局部數(shù)據(jù)模型之后，將獲得的數(shù)據(jù)挖掘結(jié)果一起發(fā)送到全局站點中進行計算，將每個項目的全局支持合計數(shù)進行詳細統(tǒng)計，最終得到具體的全局頻繁項目集，這種通信模式成為有主站點的通信模式。

有主站點的通信模式的數(shù)據(jù)挖掘算法設計相對簡單，而且比較容易實現(xiàn)。但是，全局站點在整個關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的過程中占據(jù)著核心地位，需要較強的安全性和速度性。無主站點的通信模式如果需要優(yōu)化網(wǎng)絡通信，可以采用分組映射的方法。目前，大多數(shù)分布式關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法采用的都是無主站點的通信模式。

3 分布式全局頻繁項集挖掘算法

3.1 算法思想。本文選擇了相對簡單和容易實現(xiàn)的全局剪枝策略：對于某個候選集 來說，如果 不屬于全局頻繁候選集，則 的子樹及其左兄弟的對應分支也不應該屬于全局頻繁項。如圖1所示，由全局子集枚舉數(shù)的剪枝策略可以看出還是有很多策略能夠隨意選擇的，包括相等性剪枝策略、深度優(yōu)先最大兼職策略等等。

圖1 全局剪枝策略示意圖

3.2 算法實例。如表1所示，將三個站點分別設為 、 和 ，這三個站點的交易數(shù)據(jù)庫分別對應為 、 和 ，而且每個站點交易數(shù)據(jù)庫都用來表示一個交易事物的集合（ ），。首先，算法根據(jù)FP-tree（頻繁模式樹）的具體構(gòu)造和各個站點的數(shù)據(jù)建立起具有標記的域，分別為FP-tree1、FP-tree2和FP-tree3。

每個站點進行并行求解得到局部最大頻繁項 ，當每個站點完成⊕運算得到一個簡約候選最大頻繁項集 之后，再對最大頻繁項集 中每項子集枚舉數(shù)進行構(gòu)建，根據(jù)映射關(guān)系計算得出每個節(jié)點的支持合計數(shù)。根據(jù)BF_DMFI（快速挖掘最大頻繁項集算法）計算每個節(jié)點的 ，完成⊕運算后獲得 ，本文以求 的全局頻繁項集為具體實例，當每個站點都得到了最大頻繁項集之后構(gòu)建其枚舉數(shù)，再根據(jù)映射關(guān)系分配到對應的站點進行計算，如圖2所示：

圖2 子集枚舉數(shù)示意圖

（下轉(zhuǎn)第161頁）