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

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

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 24-0156-02

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

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

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

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

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

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

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

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

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

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

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

3 分布式全局頻繁項(xiàng)集挖掘算法

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

圖1 全局剪枝策略示意圖

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

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

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

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