一種基于不確定數(shù)據(jù)的頻繁模式分布式挖掘算法研究

李 峰

（湖南工程學院 計算機與通信學院，湘潭 411104）

0 引言

現(xiàn)實世界數(shù)據(jù)分為兩類：精確數(shù)據(jù)和不確定數(shù)據(jù).在精確數(shù)據(jù)中人們必須精確知道相互作用數(shù)據(jù)的質(zhì)量，而在不確定數(shù)據(jù)中，由于人們無法精確確定數(shù)據(jù)的質(zhì)量，數(shù)據(jù)質(zhì)量常常用概率來表示.

數(shù)據(jù)采掘就是從真實世界數(shù)據(jù)中提取知識.因為人類對現(xiàn)實世界認識的局限性，造成不確定數(shù)據(jù)在數(shù)據(jù)挖掘中普遍存在.人們越來越關注從不確定數(shù)據(jù)中挖掘頻繁模式.

頻繁模式（frequent pattern），是指頻繁地出現(xiàn)在數(shù)據(jù)集中的模式，譬如項集、子序列或子結構.在數(shù)據(jù)集中挖掘頻繁模式稱為頻繁模式挖掘.

1 相關工作

1.1 頻繁模式挖掘概述

一般頻繁模式挖掘算法都只是處理確定數(shù)據(jù).但是越來越多的人們關注從不確定數(shù)據(jù)中挖掘交易決策樹 .Chui［1］，韓［2］，Leung［3］都研究過不確定數(shù)據(jù)，并開發(fā)出相應算法，從不確定數(shù)據(jù)中挖掘知識在現(xiàn)實生活非常重要［4］.Chui提出 U-Apriori算法，該算法根據(jù)范式產(chǎn)生并檢測候選集.Leung提出挖掘不確定數(shù)據(jù)的樹型結構算法并在文獻［4］中提出改進過的UF-tree and UF-growth算法.因為不確定數(shù)據(jù)的復雜性，在單機上處理分析很單薄，這時采用分布式處理就會相對容易.本文提出一種基于交易決策樹的分布式處理策略，完善了Leung在文獻［3］中提出的在分布式環(huán)境中處理交易決策樹的算法——PUF-Tree，能快速挖掘出頻繁模式.文獻［1］Chui的U-Apriori算法是基于不確定數(shù)據(jù)的算法，但其需要多次遍歷搜索.隨后文獻［3］Leung提出了UF-growth算法，減少了對不確定數(shù)據(jù)的掃描次數(shù).UF-growth算法分為2步：UF Tree的建立和UF Tree的挖掘，但是在UF Tree中規(guī)定只有相同概率的節(jié)點才會被共享訪問，這樣降低了執(zhí)行效率 .為了解決這個問題，Aggarwal［5］提出了 UFP-Growth算法，算法中有相同概率的節(jié)點被分組，從而能快速挖掘頻繁模式.

Leung提出基于前綴上界的不確定數(shù)據(jù)頻繁模式挖掘樹結UFP-Tree，該樹具有和FP-Tree相同的壓縮結構.郝天鵬［6］提出基于同類項的最小支持度和并行計算的頻繁模式挖掘算法，對UFP-Tree提出兩種改進算法.

1.2 改進算法

本文改進了UFP-Tree算法，主要改進如下：

（1）改變了存在概率的表示.在交易數(shù)據(jù)t中的不確定項目x的存在概率表示為p(x∈t)∈(0,1).

（2）改進了期望支持度的表示，定義如下：

（3）改進了I(xt,tj)的表示，定義如下：

2 PUF-Tree的重建

在表1的不確定交易數(shù)據(jù)庫（DB）［7］中，a、b、c、d、e、f是交易事務，minsup＝0.9，m＝6；t1、t2、t3、t4是不確定數(shù)據(jù)庫中4個交易集.每個t都包含a、b、c、d、e、f中一個或幾個.重建PUF-Tree分為2步：首先，遍歷DB并計算出每一項的expSup.其次，遍歷t并插入樹中.

表1 不確定交易數(shù)據(jù)庫

下面公式計算出表1交易數(shù)據(jù)a的期望支持度.

這樣，我們可以計算出所有交易事物的expSup如表2所示.

表2 不確定交易數(shù)據(jù)庫

因為約定minsup＝0.9，所以表2中b、d不符合要求，刪去后就得到表3.

表3 修改后的不確定交易數(shù)據(jù)庫

3 分布式壓縮、并行重構PUF-Tree

3.1 分布式壓縮PUF-Tree

現(xiàn)實中由于交易數(shù)據(jù)量巨大，PUF-Tree的重構耗時巨大，所以采用分布式計算，大大減少時耗.可以在局域數(shù)據(jù)中獲取頻繁模式，然后整合它們以實現(xiàn)全局模式.為了克服現(xiàn)有的不足，修改了Leung的PUF-Tree，得出壓縮PUF-Tree壓縮算法.具體步驟如下：

第一步：分離數(shù)據(jù)庫同時部署到不同節(jié)點.

第二步：和中心服務機同步并行計算每一個節(jié)點中不同項目的expSup.

第三步：中心服務機編譯并計算不同節(jié)點的expSup，并行計算每一個節(jié)點不同項目的expSup，并部署到局域節(jié)點.

第四步：每一局域節(jié)點從中心機接收expSup，然后并行建立壓縮PUF-Tree，并傳回中心機.

第五步：中心機整合局域PUF-Tree，由此獲得全局PUF-Tree.

3.2 全局壓縮PUF-Tree，生成GPUF-Tree

在此構建GPUF-Tree的過程包括2個階段：第一階段是以中心機為基礎分布式構建LPUF-Treei；第二階段是合并分布式計算結果MPUFi，生成GPUF-Tree.算法如下：

上述算法提出一種獲取GPUF-Tree的模型，此模型通過獲取局域或全局節(jié)點來深層次挖掘多種信息，最后在分布式環(huán)境中挖掘出頻繁模式.

4 實驗分析

為了比較現(xiàn)有算法和本文算法，實驗采用Intel（R）Core（TM）i5-5200 CPU 3.00 GHz，內(nèi)存為 3 GB，Windows 10操作系統(tǒng).

采用合成數(shù)據(jù)庫，基礎數(shù)據(jù)庫來自癌癥基因組圖譜（TCGA）.癌癥基因組圖譜（TCGA）是國家癌癥研究所（NCI）和國家人類基因組研究所（NHGRI）之間的合作成果，已經(jīng)生成33種癌癥關鍵基因組變化的全面、多維地圖.在此基礎上采用不確定函數(shù)f（0，1）合成了基因組之間的相關作用強弱，從而得到不確定數(shù)據(jù).

4.1 在不同的支持度條件下的GPUF重建實驗

實驗中的2000交易數(shù)據(jù)被分為五個部分，分別部署到5個不同的節(jié)點，用5個不同的處理器并行處理.交易樹采用OpenMP重構.處理器間的同步由OpenMP實現(xiàn).表4表示在不同閾值下重構GPUF-Tree的執(zhí)行時間.圖1顯示GPUF-Tree的執(zhí)行時間隨著閾值的增加單調(diào)遞減.

表4 不同閾值下重構GPUF-Tree的執(zhí)行時間

圖1 GPUF-Tree的執(zhí)行時間隨著閾值的增加單調(diào)遞減

4.2 在不同的支持度條件下的GPUF重建實驗

下面是在順序和并行環(huán)境下GPUF-Tree的執(zhí)行情況表.表5顯示在順序執(zhí)行和并行執(zhí)行環(huán)境下分別構建GPUF-Tree所用時間.

表5 順序執(zhí)行和并行執(zhí)行環(huán)境下分別構建GPUF-Tree所用時間

從表5可知，計算時間隨交易時間的增加而增加.

在順序執(zhí)行模式中，時間以指數(shù)形式增加，而在并行執(zhí)行模式中，時間是逐漸緩慢增加的.耗時并不和計算的節(jié)點成正相關，而是與在中心機處理的節(jié)點數(shù)量成正相關.

由此可以得出順序執(zhí)行和并行執(zhí)行所用總時間，如表6所示.圖2顯示并行執(zhí)行環(huán)境下構建所用總時間優(yōu)于順序環(huán)境下構建所用總時間.

表6 順序執(zhí)行和并行執(zhí)行環(huán)境下構建所用總時間

圖2 順序執(zhí)行和并行執(zhí)行環(huán)境下構建所用總時間對比圖

5 結論

本文提出一種基于不確定交易數(shù)據(jù)的頻繁模式挖掘算法，該算法能在分布式并行環(huán)境中挖掘基于樹形結構的不確定數(shù)據(jù).通過快速在分布式環(huán)境中構建樹形結構，該算法給出了一種全局壓縮PUF-Tree方法，并討論了從局域或全局數(shù)據(jù)中獲取局域或全局頻繁模式，從而提供可靠的輔助決策信息.