宋 威，吉紅蕾，李晉宏

(北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京 100144)

一種高效用項(xiàng)集并行挖掘算法*

宋 威，吉紅蕾，李晉宏

(北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京 100144)

由于能反映用戶的偏好，可以彌補(bǔ)傳統(tǒng)頻繁項(xiàng)集挖掘僅由支持度來(lái)衡量項(xiàng)集重要性的不足，高效用項(xiàng)集正在成為當(dāng)前數(shù)據(jù)挖掘研究的熱點(diǎn)。為使高效用項(xiàng)集挖掘更好地適應(yīng)數(shù)據(jù)規(guī)模不斷增大的實(shí)際需求，提出了一種高效用項(xiàng)集的并行挖掘算法PHUI-Mine。提出了記錄挖掘高效用項(xiàng)集信息的DHUI-樹(shù)結(jié)構(gòu)，描述了DHUI-樹(shù)的構(gòu)造方法，論證了DHUI-樹(shù)的動(dòng)態(tài)剪枝策略。在此基礎(chǔ)上，給出了高效用項(xiàng)集挖掘的并行算法描述。實(shí)驗(yàn)結(jié)果表明，PHUI-Mine算法具有較高的挖掘效率及較低的存儲(chǔ)開(kāi)銷(xiāo)。

數(shù)據(jù)挖掘；高效用項(xiàng)集；并行算法；動(dòng)態(tài)高效用項(xiàng)集樹(shù)

1 引言

傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘假設(shè)用戶只對(duì)頻繁發(fā)生的項(xiàng)集感興趣，平等地對(duì)待每一事務(wù)和項(xiàng)目，不管各個(gè)事務(wù)、項(xiàng)目在效用上有多大差異[1, 2]。但是，事實(shí)上，項(xiàng)目之間的確存在著效用的差異，如商家顯然不會(huì)同等對(duì)待一件珠寶首飾和一塊面包。因此，基于支持度的頻繁集挖掘已很難滿足用戶獲取不完全依賴于頻率的重要項(xiàng)集的需求。為解決這一問(wèn)題，高效用項(xiàng)集挖掘[3, 4]應(yīng)運(yùn)而生，并正在成為頻繁模式挖掘的熱點(diǎn)問(wèn)題之一。

2004年，Yao H等[3]最先提出了高效用項(xiàng)集問(wèn)題及MEU算法。MEU算法使用啟發(fā)式策略來(lái)判斷項(xiàng)集是否為候選高效用項(xiàng)集，但在使用這種啟發(fā)策略所得到的候選項(xiàng)集中，高效用項(xiàng)集所占的比例較小，造成了巨大的存儲(chǔ)與計(jì)算開(kāi)銷(xiāo)。

2005年，Liu Y等[4]提出了挖掘高效用項(xiàng)集的Two-Phase算法。該算法引入了高事務(wù)加權(quán)效用項(xiàng)集的概念，并論證了高事務(wù)加權(quán)效用項(xiàng)集不僅是高效用項(xiàng)集的超集，而且滿足頻繁項(xiàng)集挖掘中的反單調(diào)性[1]。這樣，Two-Phase算法將高效用項(xiàng)集挖掘分為兩個(gè)階段：先利用反單調(diào)性挖掘全體高事務(wù)加權(quán)效用項(xiàng)集；再通過(guò)掃描數(shù)據(jù)庫(kù)來(lái)計(jì)算高事務(wù)加權(quán)效用項(xiàng)集的真實(shí)效用值，進(jìn)而得到全體高效用項(xiàng)集。2008年，Li Y-C等[5]提出了兩種高效用項(xiàng)集挖掘算法FUM和DCG+，通過(guò)引入新的剪枝策略來(lái)減少高事務(wù)加權(quán)效用項(xiàng)集的數(shù)量。但是，與Two-Phase一樣，這些方法依然使用逐層產(chǎn)生候選項(xiàng)集再驗(yàn)證的策略，需要反復(fù)掃描數(shù)據(jù)庫(kù)。

近年來(lái)，學(xué)者們提出了各種新的高效用項(xiàng)集挖掘算法，如：基于投影的方法[6, 7]、基于數(shù)據(jù)庫(kù)垂直表示的方法[8]、基于效用列表的方法[9]、模式增長(zhǎng)的方法[10, 11]等，這些方法有效地減少了掃描數(shù)據(jù)庫(kù)的次數(shù)、高事務(wù)加權(quán)效用項(xiàng)集的數(shù)量，提高了挖掘效率。但是，現(xiàn)有的絕大多數(shù)高效用項(xiàng)集挖掘算法都是串行的，隨著真實(shí)世界數(shù)據(jù)規(guī)模越來(lái)越龐大，各種挖掘任務(wù)對(duì)處理的響應(yīng)效率要求越來(lái)越高，提出并行的高效用項(xiàng)集挖掘算法已勢(shì)在必行。

本文引入動(dòng)態(tài)高效用項(xiàng)集樹(shù)DHUI-樹(shù)(Dynamic High Utility Itemset Tree)結(jié)構(gòu)來(lái)記錄高效用項(xiàng)集挖掘的信息，進(jìn)而給出了新的高效用項(xiàng)集剪枝策略。在此基礎(chǔ)上，提出了一種基于動(dòng)態(tài)裁剪樹(shù)型結(jié)構(gòu)的高效用項(xiàng)集并行挖掘算法PHUI-Mine(Parallel High Utility Itemset Mine)。實(shí)驗(yàn)結(jié)果表明，該算法挖掘效率較高、存儲(chǔ)開(kāi)銷(xiāo)較小。

2 問(wèn)題描述

設(shè)I={i1,i2,…,im}為項(xiàng)目集合，其中每個(gè)項(xiàng)目ip∈I(1≤p≤m)都有唯一的利潤(rùn)值p(ip)。項(xiàng)目的集合稱為項(xiàng)集，含有k個(gè)項(xiàng)目的項(xiàng)集稱作k-項(xiàng)集。為簡(jiǎn)單起見(jiàn)，把項(xiàng)集{i1,i2,…,ik}記為i1i2…ik。D={T1,T2,…,Tn}為事務(wù)數(shù)據(jù)庫(kù)，每一事務(wù)Td∈D都是I的一個(gè)子集，有唯一的標(biāo)識(shí)TID。事務(wù)Td中的每個(gè)項(xiàng)目ip都有一個(gè)數(shù)量q(ip,Td)，表示項(xiàng)目ip在事務(wù)Td中出現(xiàn)的次數(shù)。項(xiàng)目ip在事務(wù)Td中的效用定義為：u(ip,Td)=p(ip)×q(ip,Td)。

項(xiàng)集X在事務(wù)Td中的效用定義為：

(1)

項(xiàng)集X在數(shù)據(jù)庫(kù)D中的效用定義為：

(2)

給定項(xiàng)集X及用戶指定的最小效用閾值min_util，若u(X)≥min_util，則稱X為高效用項(xiàng)集；否則，稱X為低效用項(xiàng)集。給定事務(wù)數(shù)據(jù)庫(kù)D和最小效用閾值min_util，挖掘高效用項(xiàng)集也就是發(fā)現(xiàn)所有效用值不低于min_util的項(xiàng)集。

由于高效用項(xiàng)集的挖掘不再滿足頻繁項(xiàng)集挖掘中通常使用的Apriori性質(zhì)，為提高挖掘效率，Liu Y等[4]提出了事務(wù)加權(quán)向下閉合的策略，利用反單調(diào)性來(lái)挖掘高效用項(xiàng)集的超集，再通過(guò)一遍掃描數(shù)據(jù)庫(kù)得到所有高效用項(xiàng)集。

事務(wù)Td的事務(wù)效用定義為：TU(Td)=u(Td,Td)。項(xiàng)集X的事務(wù)加權(quán)效用定義為：

(3)

若TWU(X)≥min_util，則稱X為高事務(wù)加權(quán)效用項(xiàng)集；否則，稱X為低事務(wù)加權(quán)效用項(xiàng)集。

定理1[4]若項(xiàng)集X不是高事務(wù)加權(quán)效用項(xiàng)集，則X的任何超集都不是高事務(wù)加權(quán)效用項(xiàng)集。

給定項(xiàng)集X，稱g(X)={t∈D|?i∈X,i∈t}為X的支持集。定義X的支持度計(jì)數(shù)為count(X)=|g(X)|。支持度計(jì)數(shù)將在3.3節(jié)中用于對(duì)樹(shù)型結(jié)構(gòu)進(jìn)行剪枝。

例1 表1是一個(gè)示例數(shù)據(jù)庫(kù)，其中每個(gè)項(xiàng)目的利潤(rùn)值如表2所示。項(xiàng)目E在事務(wù)T2中的效用為：u(E,T2)=2×1=2，項(xiàng)集BE在事務(wù)T2中的效用為：u(BE,T2)=u(B,T2) +u(E,T2)=10+2=12。T2的事務(wù)效用為T(mén)U(T2)=u(ABDE,T2)=25，項(xiàng)集BE的事務(wù)加權(quán)效用TWU(BE)=TU(T2)+TU(T4)+TU(T5)=74，而項(xiàng)集BE在示例數(shù)據(jù)庫(kù)中的效用為u(BE)=u(BE,T2)+u(BE,T4)+u(BE,T5)=12+14+20=46。給定min_util=35，由于TWU(BE)>min_util且u(BE)>min_util，故BE既是一個(gè)高事務(wù)加權(quán)效用項(xiàng)集，也是一個(gè)高效用項(xiàng)集。由于BE被T2、T4和T5三條事務(wù)所包含，故其支持度計(jì)數(shù)count(BE)=3。

Table 1 Example database

Table 2 Profit table

3 DHUI-樹(shù)結(jié)構(gòu)

3.1 DHUI-樹(shù)的元素

為實(shí)現(xiàn)并行挖掘高效用項(xiàng)集，我們?cè)诿總€(gè)站點(diǎn)保存一棵樹(shù)型結(jié)構(gòu)。

定義1(動(dòng)態(tài)高效用項(xiàng)集樹(shù)(DHUI-樹(shù)))T是一種按如下方式定義的樹(shù)結(jié)構(gòu)：

(1)它包含一個(gè)標(biāo)記為null的根節(jié)點(diǎn)，記作T.root；一個(gè)項(xiàng)目前綴子樹(shù)的集合，記作T.tree；一個(gè)高事務(wù)加權(quán)效用項(xiàng)目頭表，記作T.header。

(2)項(xiàng)目前綴子樹(shù)T.tree中的每個(gè)節(jié)點(diǎn)至少包含六個(gè)域：item、count、util、node-link、children以及parent。其中：item表示節(jié)點(diǎn)代表的項(xiàng)目；count表示包含從根節(jié)點(diǎn)到本節(jié)點(diǎn)的路徑上所有項(xiàng)目的事務(wù)數(shù)目；util表示從根節(jié)點(diǎn)到本節(jié)點(diǎn)的路徑上項(xiàng)目item的事務(wù)加權(quán)效用；node-link指向樹(shù)中下一個(gè)與本節(jié)點(diǎn)具有相同item的節(jié)點(diǎn)；children代表本節(jié)點(diǎn)所有的孩子節(jié)點(diǎn)；parent指向本節(jié)點(diǎn)的父節(jié)點(diǎn)。

(3)高事務(wù)加權(quán)效用項(xiàng)目頭表T.header中的每行至少存儲(chǔ)四個(gè)域：item、No、TWU、node-link。其中：item表示該行對(duì)應(yīng)的項(xiàng)目；No表示包含項(xiàng)目item的事務(wù)數(shù)目的變化，初始值為item的支持度計(jì)數(shù)，即count(item)；TWU代表item的事務(wù)加權(quán)效用，即TWU(item)；node-link指向樹(shù)中第一個(gè)表示項(xiàng)目item的節(jié)點(diǎn)。

定義2 在DHUI-樹(shù)T中，項(xiàng)集X的一個(gè)條件模式為CP(X)=(Y:num,util)，其中YX是從根節(jié)點(diǎn)T.root到項(xiàng)集X的一條分支，num是X在該分支上的支持度計(jì)數(shù)，util是該分支上項(xiàng)集X的事務(wù)加權(quán)效用。稱項(xiàng)集X的全部條件模式的集合為X的條件模式基，記作CPB(X)。由X的條件模式基構(gòu)建的動(dòng)態(tài)高效用項(xiàng)集樹(shù)稱為X的條件DHUI-樹(shù)，記作CT(X)。

3.2 DHUI-樹(shù)的構(gòu)造

DHUI-樹(shù)的構(gòu)造基于模式增長(zhǎng)[12]策略。具體而言：首先將高事務(wù)加權(quán)效用項(xiàng)目按照TWU由高到低的順序排列，構(gòu)成DHUI-樹(shù)的高事務(wù)加權(quán)效用項(xiàng)目頭表。接下來(lái)依次處理數(shù)據(jù)庫(kù)中的每條事務(wù)，刪去事務(wù)中的低事務(wù)加權(quán)效用項(xiàng)目，并將剩余項(xiàng)目按照TWU由高到低的順序排列，將事務(wù)中的項(xiàng)目依次插入DHUI-樹(shù)：若當(dāng)前節(jié)點(diǎn)n存在代表項(xiàng)目為待插入項(xiàng)目i的子節(jié)點(diǎn)m時(shí)，累加m.count和m.util；否則，創(chuàng)建節(jié)點(diǎn)n的孩子節(jié)點(diǎn)p，使得p.item=i，并記錄p.count和p.util，將樹(shù)中上一個(gè)代表項(xiàng)目i的節(jié)點(diǎn)與p連接起來(lái)。

Table 3 Re-organized example database

3.3 DHUI-樹(shù)的動(dòng)態(tài)剪枝

為快速挖掘高效用項(xiàng)集，利用DHUI-樹(shù)T的頭表T.header中No域的變化，對(duì)DHUI-樹(shù)進(jìn)行動(dòng)態(tài)剪枝，達(dá)到了邊構(gòu)造DHUI-樹(shù)邊挖掘高效用項(xiàng)集的效果。

具體而言，當(dāng)某個(gè)高事務(wù)加權(quán)效用項(xiàng)目item插入DHUI-樹(shù)T后，DHUI-樹(shù)T的頭表T.header中No(item)減1，若No(item)減為0，就可以對(duì)代表item的節(jié)點(diǎn)及其子節(jié)點(diǎn)剪枝，并開(kāi)始挖掘包含item的高效用項(xiàng)集。

定理2 給定DHUI-樹(shù)T及其中的項(xiàng)目i，N={n1,n2,…,nk}是T.tree中包含i的節(jié)點(diǎn)集合。在構(gòu)造(條件)DHUI-樹(shù)T的過(guò)程中，若頭表T.header中i對(duì)應(yīng)的No域的值減為0，則在T的后續(xù)構(gòu)造過(guò)程中，N中的節(jié)點(diǎn)不會(huì)發(fā)生變化，其后代節(jié)點(diǎn)所包含項(xiàng)目的條件模式不會(huì)發(fā)生變化。

證明 若T.header中i對(duì)應(yīng)的No域的值減為0，則說(shuō)明T.tree中包含i的節(jié)點(diǎn)均已構(gòu)造完畢，這些節(jié)點(diǎn)的集合就是N，在T的后續(xù)構(gòu)造過(guò)程中N中的節(jié)點(diǎn)不會(huì)再發(fā)生變化。

對(duì)?n∈N，分如下兩種情況討論：

(1)若n是葉子節(jié)點(diǎn)，則n沒(méi)有后代節(jié)點(diǎn)。

(2)若n不是葉子節(jié)點(diǎn)，由于n不會(huì)再發(fā)生變化，由DHUI-樹(shù)的構(gòu)造過(guò)程可知，不會(huì)再有項(xiàng)目作為n的后代添加到T中來(lái)，由定義2可知，它們的條件模式也不會(huì)發(fā)生變化。

□

根據(jù)定理2，在DHUI-樹(shù)T的構(gòu)造過(guò)程中，一旦T.header中某個(gè)項(xiàng)目i的支持度計(jì)數(shù)減為0，便可將與i對(duì)應(yīng)的節(jié)點(diǎn)及其后代進(jìn)行剪枝，并開(kāi)始挖掘含有i的高效用項(xiàng)集。

4 并行挖掘算法PHUI-Mine

并行挖掘算法PHUI-Mine分為兩個(gè)階段：第一階段是挖掘全局高事務(wù)加權(quán)效用項(xiàng)目；第二階段是分站點(diǎn)挖掘全體高效用項(xiàng)集。

4.1 計(jì)算全局高事務(wù)加權(quán)效用項(xiàng)目

算法1 計(jì)算全局高事務(wù)加權(quán)效用項(xiàng)目

輸入:數(shù)據(jù)庫(kù)D，最小效用閾值min_util。

輸出:全局高事務(wù)加權(quán)效用項(xiàng)目。

步驟2for每個(gè)站點(diǎn)Sido

步驟3for每個(gè)項(xiàng)目ido

步驟4 計(jì)算TWU(i)，并發(fā)送給其它n-1個(gè)站點(diǎn)；

步驟5endfor

步驟6 接收來(lái)自其它n-1個(gè)站點(diǎn)的項(xiàng)目事務(wù)加權(quán)效用；

步驟7 計(jì)算全局高事務(wù)加權(quán)效用項(xiàng)目；

步驟8endfor

4.2 并行挖掘高效用項(xiàng)集

假設(shè)經(jīng)算法1處理后，共得到n個(gè)全局高事務(wù)加權(quán)效用項(xiàng)目，則共需要n個(gè)站點(diǎn)并行挖掘高效用項(xiàng)集。記挖掘含項(xiàng)目i的高效用項(xiàng)集的站點(diǎn)為Si，記站點(diǎn)Si要處理的數(shù)據(jù)庫(kù)為Di。在并行挖掘高效用項(xiàng)集階段，由于每個(gè)站點(diǎn)執(zhí)行的算法是一致的，因此只給出一個(gè)站點(diǎn)的算法。

算法2 并行挖掘高效用項(xiàng)集

輸入:最小效用閾值min_util。

輸出:高效用項(xiàng)集。

步驟1forDi中的每條事務(wù)Trdo

步驟2 刪除低事務(wù)加權(quán)效用項(xiàng)目，按事務(wù)加權(quán)效用由高到低的順序排列高事務(wù)加權(quán)效用項(xiàng)目；

步驟3if項(xiàng)目i存在于Tr中then

步驟4 將Tr插入站點(diǎn)Si的DHUI-樹(shù)Ti；

步驟5 No(i)--；

步驟6ifNo(i)==0then

步驟7forDHUI-樹(shù)中的每個(gè)節(jié)點(diǎn)ndo

步驟8ifn.item==ithen

步驟9 計(jì)算CP(i)，構(gòu)建CT(i)；

步驟10 HTW-growth(i, CT(i));

步驟11 在Ti中對(duì)n及其后代節(jié)點(diǎn)剪枝；

步驟12endif

步驟13endfor

步驟14endif

步驟15endif

步驟16forTr中i之外的每個(gè)項(xiàng)目itemdo

步驟17 將Tr發(fā)送給站點(diǎn)Sitem；

步驟18endfor

步驟19endfor

步驟20for其它站點(diǎn)發(fā)來(lái)的每條事務(wù)Tkdo

步驟21 將Tk插入站點(diǎn)Si的DHUI-樹(shù)Ti；

步驟22 No(i)--；

步驟23ifNo(i)==0then

步驟24forDHUI-樹(shù)中的每個(gè)節(jié)點(diǎn)ndo

步驟25ifn.item==ithen

步驟26 計(jì)算CP(i)，構(gòu)建CT(i)；

步驟27 HTW-growth(i, CT(i));

步驟28 在Ti中對(duì)n及其后代節(jié)點(diǎn)剪枝；

步驟29endif

步驟30endfor

步驟31endif

步驟32endfor

步驟33 計(jì)算包含項(xiàng)目i的高事務(wù)加權(quán)效用項(xiàng)集的實(shí)際效用；

步驟34 輸出包含項(xiàng)目i的高效用項(xiàng)集；

ProcedureHTW-growth(項(xiàng)集X, 條件DHUI-樹(shù)CT(X))

步驟1ifCT(X)只包含一個(gè)分支Bthen

步驟2forB的每個(gè)子集Ydo

步驟3 輸出Y∪X，TWU(Y∪X)與Y中所包含節(jié)點(diǎn)的最小TWU相等；

步驟4endfor

步驟5elsefor每個(gè)i∈CT(X).headerdo

步驟6 HTW-growth(X∪{i}, CT(X∪{i});

步驟7endfor

步驟8endif

5 性能評(píng)測(cè)

5.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

性能評(píng)測(cè)的硬件平臺(tái)是Intel雙核2.8GHzCPU，2GB內(nèi)存，操作系統(tǒng)是WindowsXP，編譯器是VisualStudio2010，通過(guò)多線程的方式來(lái)模擬并行算法中的多個(gè)站點(diǎn)。

大量文獻(xiàn)表明，高效用項(xiàng)集挖掘算法的研究重點(diǎn)主要集中在如何提高基于內(nèi)存的算法的挖掘效率，極少有高效用項(xiàng)集的并行挖掘算法[13, 14]。主要原因在于這些方法缺少適合于并行化的數(shù)據(jù)結(jié)構(gòu)，這也正是本文研究的出發(fā)點(diǎn)。因此，把本文提出的PHUI-Mine并行挖掘算法與兩種主流的串行高效用項(xiàng)集挖掘算法Two-Phase[4]和HUC-Prune[10]進(jìn)行了對(duì)比實(shí)驗(yàn)。在早期的頻繁模式并行挖掘的研究過(guò)程中，在缺少合適的并行對(duì)比算法的情況下，也曾使用過(guò)串行算法進(jìn)行性能比較[15, 16]。

實(shí)驗(yàn)所使用的數(shù)據(jù)集及其特性如表4所示，這些數(shù)據(jù)集可由FIMI資源庫(kù)下載(http://fimi.cs.helsinki.fi/)。

Table 4 Characteristics of datasets

由于這些數(shù)據(jù)均不包含項(xiàng)目的利潤(rùn)值及在不同事務(wù)中出現(xiàn)的次數(shù)，為適用于高效用項(xiàng)集挖掘，對(duì)數(shù)據(jù)做了如下處理：(1)為每條事務(wù)中的每個(gè)項(xiàng)目隨機(jī)產(chǎn)生一個(gè)1～5的整數(shù)作為出現(xiàn)次數(shù)；(2)為每個(gè)項(xiàng)目隨機(jī)產(chǎn)生一個(gè)1.0～10.0的實(shí)數(shù)作為利潤(rùn)值。與其它方法[4, 10]一樣，我們產(chǎn)生的利潤(rùn)值服從對(duì)數(shù)正態(tài)分布(Log Normal Distribution)。

5.2 運(yùn)行時(shí)間對(duì)比

我們首先比較了三種算法在三個(gè)數(shù)據(jù)集上的運(yùn)行效率，如圖3～圖5所示。

Figure 3 Comparison of execution time on T10D20k among three algorithms

Figure 4 Comparison of execution time on Mushroom among three algorithms

由圖3和圖4可以看出，在T10D20k和Mushroom兩個(gè)數(shù)據(jù)集上，算法PHUI-Mine和HUC-Prune的運(yùn)行時(shí)間均隨著最小效用閾值的降低而增加。在T10D20k數(shù)據(jù)集上，PHUI-Mine平均比HUC-Prune快59%，在Mushroom數(shù)據(jù)集上，PHUI-Mine平均比HUC-Prune快43%。Two-Phase算法在這兩個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間有一定的波動(dòng)性。在T10D20k數(shù)據(jù)集上，PHUI-Mine平均比Two-Phase快79%，在Mushroom數(shù)據(jù)集上，PHUI-Mine平均比Two-Phase快51%。

Figure 5 Comparison of execution time on BMS-POS among different algorithms

由圖5可以看出，當(dāng)最小效用閾值在68%～80%時(shí)，PHUI-Mine的運(yùn)行效率優(yōu)于Two-Phase和HUC-Prune。三種算法在BMS-POS數(shù)據(jù)集上運(yùn)行時(shí)間較為穩(wěn)定的原因在于，盡管BMS-POS數(shù)據(jù)集的記錄數(shù)較多，但其每條記錄都非常短，屬于極為稀疏的數(shù)據(jù)，因此算法的性能隨最小效用閾值變化的趨勢(shì)不明顯。

5.3 內(nèi)存消耗對(duì)比

我們還比較了三種算法在三個(gè)數(shù)據(jù)集上的內(nèi)存消耗，如圖6～圖8所示。

Figure 6 Comparison of memory usage on T10D20k

Figure 7 Comparison of memory usage on Mushroom

Figure 8 Comparison of memory usage on BMS-POS

由圖6～圖8可以看出，在三個(gè)數(shù)據(jù)集上，三種算法的內(nèi)存消耗基本都保持在較平穩(wěn)的數(shù)值上。PHUI-Mine和HUC-Prune消耗的內(nèi)存均遠(yuǎn)遠(yuǎn)少于Two-Phase，而PHUI-Mine消耗的內(nèi)存略少于HUC-Prune。

6 結(jié)束語(yǔ)

為提高高效用項(xiàng)集挖掘算法適應(yīng)大規(guī)模數(shù)據(jù)的能力，提出了一種高效用項(xiàng)集并行挖掘算法PHUI-Mine。算法通過(guò)引入DHUI-樹(shù)結(jié)構(gòu)，實(shí)現(xiàn)了在建樹(shù)的同時(shí)挖掘高效用項(xiàng)集，從而提高了算法的挖掘效率，降低了算法的存儲(chǔ)開(kāi)銷(xiāo)。

[1] Agrawal R, Srikant R.Fast algorithms for mining association rules [C]∥Proc of the 20th International Conference on Very Large Data Bases (VLDB’94), 1994:487-499.

[2] Zhang Su-qi, Liang Zhi-gang, Hu Li-juan, et al. Research and application of improved multidimensional association rule mining algorithms [J]. Computer Engineering &Science,2012,34(9):174-179. (in Chinese)

[3] Yao H,Hamilton H J, Butz C J. A foundational approach to mining itemset utilities from databases [C]∥Proc of the 4th SIAM International Conference on Data Mining (SDM’04), 2004:482-486.

[4] Liu Y,Liao W-K,Choudhary A N. A two-phase algorithm for fast discovery of high utility itemsets [C]∥Proc of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD’05), 2005:689-695.

[5] Li Y-C,Yeh J-S,Chang C-C. Isolated items discarding strategy for discovering high utility itemsets [J]. Data & Knowledge Engineering, 2008, 64(1):198-217.

[6] Lan G-C,Hong T-P,Tseng V S.A projection-based approach for discovering high average-utility itemsets [J]. Journal of Information Science and Engineering, 2012, 28(1):193-209.

[7] Liu J,Wang K, Fung B C M. Direct discovery of high utility itemsets without candidate generation [C]∥Proc of the 12th IEEE International Conference on Data Mining (ICDM’12),2012:984-989.

[8] Song W,Liu Y,Li J H.Vertical mining for high utility itemsets [C]∥Proc of the 2012 IEEE International Conference on Granular Computing (GrC’12), 2012:512-517.

[9] Liu M,Qu J-F.Mining high utility itemsets without candidate generation [C]∥Proc of the 21st ACM International Conference on Information and Knowledge Management (CIKM’12),2012:55-64.

[10] Ahmed C F,Tanbeer S K,Jeong B-S,et al. HUC-Prune:An efficient candidate pruning technique to mine high utility patterns [J]. Applied Intelligence, 2011, 34(2):181-198.

[11] Feng L,Wang L,Jin B.UT-Tree:Efficient mining of high utility itemsets from data streams [J]. Intelligent Data Analysis, 2013, 17(4):585-602.

[12] Han J,Pei J,Yin Y,et al.Mining frequent patterns without candidate generation:A frequent-pattern tree approach [J]. Data Mining and Knowledge Discovery, 2004, 8(1):53-87.

[13] Shie B-E,Hsiao H-F,Tseng V S.Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments [J]. Knowledge and Information Systems, 2013,37(2):363-387.

[14] Tseng V S,Shie B-E, Wu C-W, et al. Efficient algorithms for mining high utility itemsets from transactional databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(8):1772-1786.

[15] Cong S,Han J,Padua D A. Parallel mining of closed sequential patterns [C]∥ Proc of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’05), 2005:562-567.

[16] Wang Yong-heng,Yang Shu-qiang,Jia Yan.An efficient method for the parallel mining of frequent itemsets in very

large text databases [J]. Computer Engineering &Science,2007,29(9):110-113. (in Chinese)

附中文參考文獻(xiàn)：

[2] 張素琪，梁志剛，胡利娟,等.改進(jìn)的多維關(guān)聯(lián)規(guī)則算法研究及應(yīng)用[J].計(jì)算機(jī)工程與科學(xué),2012,34(9):174-179.

[16] 王永恒,楊樹(shù)強(qiáng),賈焰.海量文本數(shù)據(jù)庫(kù)中的高效并行頻繁項(xiàng)集挖掘方法[J].計(jì)算機(jī)工程與科學(xué),2007,29(9):110-113.

SONG Wei,born in 1980,PhD,associate professor,CCF member(E200019725S)，his research interest includes data mining.

吉紅蕾(1985-),女，河北深州人，碩士生，研究方向?yàn)閿?shù)據(jù)挖掘。E-mail:jihonglei1024@163.com

JI Hong-lei,born in 1985,MS candidate,her research interest includes data mining.

李晉宏(1965-),男，山西太原人，博士，教授，研究方向?yàn)閿?shù)據(jù)挖掘和智能系統(tǒng)。E-mail:ljh@ncut.edu.cn

LI Jin-hong,born in 1965,PhD,professor,his research interests include data mining, and intelligent system.

A parallel algorithm for mining high utility itemsets

SONG Wei，JI Hong-lei，LI Jin-hong

(College of Computer,North China University of Technology,Beijing 100144,China)

Mining high utility itemsets is becoming a hot research topic in data mining owing to its ability to reflect users’preferences and make up for the shortcoming of measuring itemsets only by support degree.To meet the needs of larger data size,a parallel algorithm,called Parallel High Utility Itemset Mine (PHUI-Mine ),for mining high utility itemsets is proposed.Firstly,a tree structure,called DHUI-tree, is introduced to capture the information of high utility itemsets. Meanwhile, the DHUI-tree construction method is described,and the dynamic pruning strategy of DHUI-tree is discussed.Then, the parallel algorithm is presented. Experimental results show that PHUI-Mine algorithm is efficient and has low storage cost.

data mining;high utility itemset;parallel algorithm;DHUI-tree

1007-130X(2015)03-0422-07

2013-10-10;

2014-01-09基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61105045,51075423)；北京市屬市管高等學(xué)校人才強(qiáng)教計(jì)劃資助項(xiàng)目(PHR201108057)；北方工業(yè)大學(xué)科研人才提升計(jì)劃資助項(xiàng)目(CCXZ201303)

TP311

A

10.3969/j.issn.1007-130X.2015.03.002

宋威(1980-),男，遼寧撫順人，博士，副教授，CCF會(huì)員(E200019725S)，研究方向?yàn)閿?shù)據(jù)挖掘。E-mail:songwei@ncut.edu.cn

通信地址：100144 北京市北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院

Address:College of Computer,North China University of Technology,Beijing 100144,P.R.China