李 峰

（湖南工程學(xué)院 計(jì)算機(jī)與通信學(xué)院，湘潭 411104）

0 引言

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

數(shù)據(jù)采掘就是從真實(shí)世界數(shù)據(jù)中提取知識(shí).因?yàn)槿祟悓?duì)現(xiàn)實(shí)世界認(rèn)識(shí)的局限性，造成不確定數(shù)據(jù)在數(shù)據(jù)挖掘中普遍存在.人們?cè)絹碓疥P(guān)注從不確定數(shù)據(jù)中挖掘頻繁模式.

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

1 相關(guān)工作

1.1 頻繁模式挖掘概述

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

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

1.2 改進(jìn)算法

本文改進(jìn)了UFP-Tree算法，主要改進(jìn)如下：

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

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

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

2 PUF-Tree的重建

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

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

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

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

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

因?yàn)榧s定minsup＝0.9，所以表2中b、d不符合要求，刪去后就得到表3.

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

3 分布式壓縮、并行重構(gòu)PUF-Tree

3.1 分布式壓縮PUF-Tree

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

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

第二步：和中心服務(wù)機(jī)同步并行計(jì)算每一個(gè)節(jié)點(diǎn)中不同項(xiàng)目的expSup.

第三步：中心服務(wù)機(jī)編譯并計(jì)算不同節(jié)點(diǎn)的expSup，并行計(jì)算每一個(gè)節(jié)點(diǎn)不同項(xiàng)目的expSup，并部署到局域節(jié)點(diǎn).

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

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

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

在此構(gòu)建GPUF-Tree的過程包括2個(gè)階段：第一階段是以中心機(jī)為基礎(chǔ)分布式構(gòu)建LPUF-Treei；第二階段是合并分布式計(jì)算結(jié)果MPUFi，生成GPUF-Tree.算法如下：

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

4 實(shí)驗(yàn)分析

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

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

4.1 在不同的支持度條件下的GPUF重建實(shí)驗(yàn)

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

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

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

4.2 在不同的支持度條件下的GPUF重建實(shí)驗(yàn)

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

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

從表5可知，計(jì)算時(shí)間隨交易時(shí)間的增加而增加.

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

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

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

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

5 結(jié)論

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