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

?？诐?，李興建，王 樂

（1.南陽理工學(xué)院 軟件學(xué)院，河南 南陽473000；2.南陽理工學(xué)院 圖書館，河南 南陽473000；3.大連理工大學(xué) 創(chuàng)新實(shí)驗(yàn)學(xué)院，遼寧 大連116624）

0 引 言

頻繁模式的挖掘僅僅考慮項(xiàng)集在多少個事務(wù)項(xiàng)集中出現(xiàn)，而沒有考慮項(xiàng)在一個事務(wù)中對應(yīng)的數(shù)量和項(xiàng)的權(quán)重值，如在一個購物單中，同一個商品的購買的數(shù)量和商品的價(jià)格或利潤；但這些信息對于商務(wù)數(shù)據(jù)分析等應(yīng)用卻很重要。針對該問題，提出了高效用項(xiàng)集的挖掘，并且也成為近來一個新的研究方向[1－9]，其研究的焦點(diǎn)主要是提高算法的時(shí)間和空間效率。

目前，高效用項(xiàng)集的挖掘算法主要采用兩階段方法[1－5，7，10，11]和項(xiàng)集枚舉[8，9]辦法。本文主要對基于兩階段方法的算法進(jìn)行了研究；兩階段方法是指算法通過兩個階段來完成高效用項(xiàng)集的挖掘:候選項(xiàng)集挖掘和從候選項(xiàng)集中識別高效用項(xiàng)集。算法 CTU－Mine[11]針對 Two－Phase算法中的問題進(jìn)行了改進(jìn)，該算法采用樹結(jié)構(gòu)的方式挖掘高效用項(xiàng)集，但是只在稠密數(shù)據(jù)集上的該算法的性能才優(yōu)于Two－Phase算法。算法IHUP[3]只需要兩次數(shù)據(jù)集掃描，并采用模式增長方式產(chǎn)生候選項(xiàng)集，候選項(xiàng)集的個數(shù)相對已有算法有了很大降低，算法的性能得到了較大的提高。算法 UP－Growth[1，4]針對IHUP算法提出了改進(jìn)策略來降低候選項(xiàng)集個數(shù)。采用兩階段方式的算法主要問題就是產(chǎn)生候選項(xiàng)集過多，因此這會影響算法挖掘的時(shí)空效率。

針對此問題，本文從兩方面對算法UP－Growth進(jìn)行改進(jìn)，降低候選項(xiàng)集效用的估計(jì)值，從而減少候選項(xiàng)集的個數(shù)。實(shí)驗(yàn)部分采用稀疏和稠密數(shù)據(jù)集進(jìn)行了算法性能測試，實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)后算法的時(shí)間效率得到了較大的提高。

1 問題描述和相關(guān)定義

設(shè)數(shù)據(jù)集D＝｛t1，t2，t3，… ，tn｝共包含m個不同項(xiàng)，即I＝｛i1，i2，…，im｝，并且包含n個事務(wù)，其中tj（j＝1，2，3，…，n）表示D中第j個事務(wù)項(xiàng)集 （j被稱為事務(wù)項(xiàng)集的ID），事務(wù)項(xiàng)集tj可以表示為｛（x1:c1），（x2:c2），…，（xv:cv）｝，其中xk∈I（k＝1，2，...，v），ck是項(xiàng)xk在事務(wù)tj中的數(shù)量，記為q（xk，tj），ck也被稱為項(xiàng)xk的內(nèi)部效用值，如表1中每個事務(wù) （第二列）中的數(shù)值；項(xiàng)集I中每一項(xiàng)ir（1≤r≤m）的權(quán)重值記為p（ir），該權(quán)重值也被稱為項(xiàng)ir的外部效用值，如表2所示。｜D｜表示數(shù)據(jù)集的大小。

表1 帶效用數(shù)據(jù)的數(shù)據(jù)集實(shí)例

表2 利潤表實(shí)例

定義1 項(xiàng)x在事務(wù)t中的效用值，記為u（x，t），其定義如下

例如，在表中，u（b，T1）＝10＊3＝30。

定義2 項(xiàng)集X在事務(wù)t中的效用值，記為u（X，t），其定義如下

例如，在表中，u（｛bd｝，T1）＝u（b，T1）＋u（d，T1）＝30＋8＝38。

定義3 項(xiàng)集在一個數(shù)據(jù)集中的效用值:項(xiàng)集X在一個數(shù)據(jù)集Dut中的效用值，記為u（X），其定義如下

例如，在表中，u（｛bd｝）＝u（｛bd｝，T1）＋u（｛bd｝，T7）＝38＋46＝84。

定義4 一個事務(wù)t的效用值，記為tu（t），其定義如下

例如，在表中，tu（T3）＝u（d，T3）＋u（f，T3）＝24＋12＝36。

定義5 數(shù)據(jù)集總的效用值:一個數(shù)據(jù)集D的總效用值，記為Ttu（D），其定義如下

定義6 最小效用閾值η是用戶預(yù)定義的一個大于0小于1的值，在一個數(shù)據(jù)集Dut中，最小效用值min＿uti定義如下

定義7 在一個數(shù)據(jù)集中，一個項(xiàng)集的效用值不小于預(yù)定義的最小效用值，則該項(xiàng)集就成為一個高效用項(xiàng)集。

定義8 項(xiàng)集的事務(wù)權(quán)重效用值 （transaction－weightedutilization，twu）:在一個數(shù)據(jù)集Dut中，一個項(xiàng)集X的事務(wù)權(quán)重效用值，記twu（X）為，定義如下

其是包含該項(xiàng)集的所有事務(wù)效用值的和，例如，twu（｛bd｝）＝tu（T1）＋tu（T7）＝50＋54＝104。

定義9 高效用項(xiàng)集的候選項(xiàng)集與非候選項(xiàng)集:一個項(xiàng)集／項(xiàng)X的twu值不小于預(yù)定義的最小效用值，則該項(xiàng)集／項(xiàng)就是一個候選項(xiàng)集／項(xiàng)，否則就是非候選項(xiàng)集／項(xiàng)。

性質(zhì)項(xiàng)集的事務(wù)權(quán)重效用值滿足閉包屬性[12]:任一個候選項(xiàng)集的非空子集也是一個候選項(xiàng)集，任一個非候選項(xiàng)集的超集也是一個非候選項(xiàng)集。

2 算法設(shè)計(jì)

UP－Growth和IHUP[3]在計(jì)算項(xiàng)的twu值的時(shí)候，將低效用值的項(xiàng)和已經(jīng)被處理過的項(xiàng)對應(yīng)的效用值都計(jì)算到相關(guān)項(xiàng)集的twu值中，因此當(dāng)處理到頭表中一項(xiàng)的時(shí)候，可以重新計(jì)算該項(xiàng)的twu值，如果新計(jì)算的twu值小于預(yù)定義的最小效用值，則就不需要再繼續(xù)為該項(xiàng)創(chuàng)建子頭表和子樹。另外本文還利用項(xiàng)在事務(wù)中的最大效用值和最小效用值來降低項(xiàng)集被估計(jì)的效用值，從而可以將少候選項(xiàng)集、以及挖掘過程中創(chuàng)建樹的棵數(shù)。本文將以上策略應(yīng)用到UP－Growth中進(jìn)行算法改進(jìn)，將改進(jìn)后算法記為IUPGrowth；另外以上的策略可以應(yīng)用到所有采用模式增長方式的算法中來降低候選項(xiàng)集的個數(shù)。

IUP－Growth主要包括兩個過程:創(chuàng)建樹UP－Tree和從樹上挖掘高效用模式，其中從樹上挖掘高效用模式是一個遞歸的過程，在這個過程中需要遞歸的創(chuàng)建新的子樹、以及從新的子樹上再遞歸的執(zhí)行模式挖掘。

（1）創(chuàng)建樹 UP－Tree

這里創(chuàng)建UP－Tree的方法和算法UP－Tree中創(chuàng)建樹的方法相同，以表1和表2中數(shù)據(jù)為例說明UP－Tree的構(gòu)建，這里設(shè)定最小效用值為80。

在第一遍數(shù)據(jù)集的掃描中，統(tǒng)計(jì)出每項(xiàng)的支持?jǐn)?shù) （sn）和事務(wù)權(quán)重效用值 （twu），然后只保留twu值不小于80的項(xiàng)，并且按支持?jǐn)?shù)從大到小排序，如圖1（a）所示，其中頭表中還記錄link（為了使圖清晰，圖中表示link的線沒畫）。

在第二遍數(shù)據(jù)集掃描中，主要任務(wù)就是將每個事務(wù)項(xiàng)集添加到一棵樹上，每個事務(wù)項(xiàng)集添加到樹上的步驟如下:①將事務(wù)項(xiàng)集中不在頭表中的項(xiàng)刪除；②事務(wù)項(xiàng)集中剩余項(xiàng)按頭表的順序排序；③將排好序的事務(wù)項(xiàng)集添加到樹上。

圖1 UP－Tree的構(gòu)造 （最小效用值為80）

例如表1中第一個事務(wù)，按以上步驟中的 （1）和 （2）中方法處理后得到事務(wù)項(xiàng)集為｛（b，10）（f，1）（d，1）｝；然后將事務(wù)項(xiàng)集添加到一棵樹上，如圖1（b）所示，其中每個節(jié)點(diǎn)上的第一個數(shù)值表示該節(jié)點(diǎn)的支持?jǐn)?shù)，第二個數(shù)值是節(jié)點(diǎn)及祖先節(jié)點(diǎn)效用值的和，如節(jié)點(diǎn) “b”上的 “30”是節(jié)點(diǎn) “b”的效用值，節(jié)點(diǎn) “f”上的 “32”是節(jié)點(diǎn) “b”和 “f”的效用值的和，節(jié)點(diǎn) “d”上的 “30”是節(jié)點(diǎn) “b”、“f”和 “d”的效用值的和。圖1（c）是添加前兩個事務(wù)項(xiàng)集后的結(jié)果；圖1（d）是添加表1中所有數(shù)據(jù)后的結(jié)果。

在數(shù)據(jù)集的第二遍掃描過程中，算法IUP－Growth還統(tǒng)計(jì)了各項(xiàng)在事務(wù)中的最大以及最小效用值，如表3所示，該表記為項(xiàng)最大 ＆最小效用值表 （minimum ＆maximum item utility table，MMUT）。表3中數(shù)據(jù)用來降低候選項(xiàng)集的twu值，從而可以減少候選項(xiàng)集的個數(shù)，即用來候選項(xiàng)集的剪枝，詳見頻繁模式挖掘過程。

表3 項(xiàng)最小與最大效用表 （MMUT）

（2）從樹上挖掘高效用模式

算法IUP－Growth從樹上挖掘高效用模式的算法首先是從頭表的最后一項(xiàng)開始處理，其中每項(xiàng)的處理步驟如下（假設(shè)當(dāng)前正在處理的UP－tree樹記為T，當(dāng)前正在處理的頭表為H，當(dāng)前正在處理的項(xiàng)為Y）:

步驟1 在頭表H中，Y.link中記錄了樹UP－tree上所有節(jié)點(diǎn)Y，設(shè)為k個節(jié)點(diǎn)N1，N2，…，Nk；

步驟2 計(jì)算k個節(jié)點(diǎn)上utility的和，記new＿twu＝；如果new＿twu小于最小效用值，則執(zhí)行步驟11；否則執(zhí)行下一步；

步驟3 將項(xiàng)Y添加到一個基項(xiàng)集base－itemset（初始值為空）；

步驟4 通過掃描樹T上包含節(jié)點(diǎn)Y到根節(jié)點(diǎn)的所有枝，為基項(xiàng)集｛Y｝創(chuàng)建一個子頭表subH，子頭表中包含所有對應(yīng)的候選及非候選項(xiàng)；

步驟5 計(jì)算基項(xiàng)集的最大效用值 （記為BIMU），即項(xiàng)集中各項(xiàng)最大效用值與項(xiàng)Y的支持?jǐn)?shù)的乘積的總和，如果BIMU小于預(yù)定義的最小效用值，則執(zhí)行步驟10。

步驟6 計(jì)算子頭表subH中所有項(xiàng)的最小效用值的和（記為MTU），其中每項(xiàng)的最小效用值等于項(xiàng)最大＆最小效用值表中最小效用值與該項(xiàng)在子頭表中支持?jǐn)?shù)的乘積；

步驟7 如果new＿twu–mtu的差不小于最小效用值，則將當(dāng)前基項(xiàng)集添加到候選項(xiàng)集集合中；

步驟8 刪除子頭表中twu值小于最小效用值的項(xiàng)，剩余項(xiàng)按支持?jǐn)?shù)從大到小排序；

步驟9 如果子頭表不為空，則再次掃描樹T上包含節(jié)點(diǎn)Y到根節(jié)點(diǎn)的所有枝，為當(dāng)前基項(xiàng)集創(chuàng)建條件樹，然后按照處理頭表H的方法遞歸的處理子頭表subH；

步驟10 從基項(xiàng)集base－itemset中刪除項(xiàng)Y；

步驟11 按照處理頭表H中項(xiàng)Y的方法，處理頭表H中下一項(xiàng)。

算法IUP－Growth和算法 UP－Growth的主要區(qū)別:UP－Growth會將頭表中每一項(xiàng)添加到基項(xiàng)集base－itemset中，而每產(chǎn)生一個新的基項(xiàng)集都是一個候選項(xiàng)集，而算法IUP－Growth會在步驟2中重新計(jì)算項(xiàng)的twu值，而新計(jì)算的值不包含事務(wù)項(xiàng)集中刪除項(xiàng)的效用值和已經(jīng)被處理的項(xiàng)的效用值；同時(shí)算法IUP－Growth中步驟5－7，其包含2個判斷條件來減少候選項(xiàng)集的個數(shù)，從而提高算法的處理效率。

IUP－Growth從樹上挖掘候選項(xiàng)集的算法如圖2所示。IUP－Growth從樹上挖掘到候選項(xiàng)集后，最后再掃描一遍數(shù)據(jù)集來統(tǒng)計(jì)各個候選項(xiàng)集真實(shí)的效用值，當(dāng)真實(shí)的效用值不小于最小效用值，則該候選項(xiàng)集就是一個高效用項(xiàng)集。

圖2 挖掘候選項(xiàng)集算法

下面通過一個例子來說明IUP－Growth的挖掘過程，例如當(dāng)處理圖1（a）中的項(xiàng) “d”時(shí)，處理步驟如下:

步驟1 計(jì)算項(xiàng) “d”新的twu值，即new＿twu＝40＋54＋36＝130，因?yàn)閚ew＿twu值不小于80，則執(zhí)行下一步，否則就不需要繼續(xù)處理該項(xiàng)；

步驟2 將項(xiàng) “d”添加到基項(xiàng)集base－itemset中；

步驟3 計(jì)算項(xiàng)集base－itemset中所有項(xiàng)的最大效用值和，即BIMU＝24＊3＝72，因?yàn)锽IMU的值小于最小效用值，則該項(xiàng)集不是一個候選項(xiàng)集；

步驟4 因?yàn)閚ew＿twu值大于最小效用值，則通過掃描樹T（圖1（d））上包含節(jié)點(diǎn) “d”到根節(jié)點(diǎn)的所有枝，為當(dāng)前基項(xiàng)集創(chuàng)建子頭表，如圖3（a）所示 （因?yàn)椴襟E3中已經(jīng)判斷基項(xiàng)集不是一個候選項(xiàng)集，則這里的子頭表也不需要再保存twu值小于最小效用值的項(xiàng)）；

步驟5 因?yàn)樾陆ㄗ宇^表不為空，所以需要為當(dāng)前基項(xiàng)集創(chuàng)建條件樹，例如圖3（a）中的樹；

步驟6 遞歸的處理新的子頭表中的每一項(xiàng)，例如處理子頭表中的項(xiàng) “b”，得到項(xiàng)集｛db｝的子頭表和子樹，如圖3（b）所示；得到和項(xiàng) “d”相關(guān)的候選項(xiàng)集有｛db｝和｛dbf｝。

圖3 挖掘高效用項(xiàng)集的例子

步驟7 處理完子頭表中的每一項(xiàng)，繼續(xù)處理圖1（a）中項(xiàng) “d”的下一項(xiàng) “c”，如圖3 （c）是項(xiàng)集 “c”的子頭表和條件樹；從新的子樹中可以得到新的候選項(xiàng)集｛ca｝；

步驟8 處理圖1（a）中頭表的下一項(xiàng) “f”，為項(xiàng)集｛f｝創(chuàng)建的子頭表和樹如圖3（d）所示；得到和項(xiàng) “f”相關(guān)的候選項(xiàng)集有｛fb｝；

步驟9 處理圖1（a）中頭表的下一項(xiàng) “b”，沒有新的子樹產(chǎn)生；得到新的候選項(xiàng)集有｛b｝；

步驟10 處理圖1（a）中頭表的下一項(xiàng) “a”，沒有新的子樹產(chǎn)生；得到新的候選項(xiàng)集有｛a｝。

3 實(shí) 驗(yàn)

實(shí)驗(yàn)平臺:Windows 7操作系統(tǒng)，4G內(nèi)存 （實(shí)際可用2.99G），Intel（R）Core（TM）i5－2300CPU ＠2.80GHz；Java堆空間設(shè)置為1.5G。將改進(jìn)后的算法IUP－Growth和UPGrowth挖掘的結(jié)果相同，都能將所有的高效用項(xiàng)集挖掘出來，因此這里僅進(jìn)行了算法時(shí)間性能對比，實(shí)驗(yàn)對比算法都是采用Java編程語言實(shí)現(xiàn)。測試數(shù)據(jù)3個:Chain－store[13]、mushroom[14]和 T10.I6.D100K，其中 T10.I6.D100K是一個用IBM數(shù)據(jù)生成器[15]合成的數(shù)據(jù)集。Chain－store是California一家鏈鎖超市產(chǎn)生的真實(shí)數(shù)據(jù)[13]；數(shù)據(jù)集mushroom和T10.I6.D100K中沒有提供數(shù)據(jù)的內(nèi)部效用值和外部效用值，本文采用文獻(xiàn)[3，10－12]中方法，事務(wù)項(xiàng)集中項(xiàng)的個數(shù)（內(nèi)部效用值）采用隨機(jī)的方法產(chǎn)生一個小于10大于0的整數(shù)；項(xiàng)的單位效用值 （外部效用值）也是隨機(jī)產(chǎn)生一個數(shù)值 （大于等于0.0100，小于等于10.0000）。

表5 數(shù)據(jù)集T10.I6.D100K的高效用項(xiàng)集和候選項(xiàng)集個數(shù)

表6 數(shù)據(jù)集chain－store的高效用項(xiàng)集和候選項(xiàng)集個數(shù)

表4～表6是3個數(shù)據(jù)集在不同的最小效用閾值下包含的高效用項(xiàng)集個數(shù)、以及兩個算法產(chǎn)生的候選項(xiàng)集個數(shù)，表中第二行是IUP－Growth算法在不同的閾值下產(chǎn)生的候選項(xiàng)集個數(shù)，第三行是UP－Growth算法在不同的閾值下產(chǎn)生的候選項(xiàng)集個數(shù)。從這3個表中很容易看出IUP－Growth算法產(chǎn)生的候選項(xiàng)集個數(shù)明顯低于算法UP－Growth，特別在真實(shí)數(shù)據(jù)集chain－store上更為明顯，因此這會導(dǎo)致算法IUP－Growth的時(shí)間和空間性能優(yōu)于算法UP－Growth，正如實(shí)驗(yàn)結(jié)果圖4～圖6所示，算法IUP－Growth的運(yùn)行時(shí)間明顯低于 UP－Growth，在真實(shí)數(shù)據(jù)集chain－store上，IUPGrowth算法性能優(yōu)勢更為明顯；另圖6中當(dāng)閾值取0.03%的時(shí)候，算法UP－Growth發(fā)生內(nèi)存溢出。

在圖5（a）的實(shí)驗(yàn)中，當(dāng)閾值從0.2%降低到0.1%的時(shí)候，數(shù)據(jù)集T10.I6.D100K中的高效用項(xiàng)集個數(shù)由131上升到524個，同時(shí)兩個算法產(chǎn)生的候選項(xiàng)集個數(shù)增加的也比較快，如表5所示，所以在這種情況下，算法的運(yùn)行時(shí)間也會相應(yīng)增加比較快。

圖4 數(shù)據(jù)集mushroom實(shí)驗(yàn)數(shù)據(jù)對比

圖5 數(shù)據(jù)集T10.I6.D100K實(shí)驗(yàn)數(shù)據(jù)對比

圖6 數(shù)據(jù)集chain－store實(shí)驗(yàn)數(shù)據(jù)對比

4 結(jié)束語

本文通過對兩階段法高效用項(xiàng)集挖掘算法的研究，為有效剪枝候選項(xiàng)集，提出了改進(jìn)策略:在不影響項(xiàng)集效用值的基礎(chǔ)上，降低候選項(xiàng)集的twu值，從而減少候選項(xiàng)集個數(shù)；另外通過項(xiàng)的最大和最小效用值來估計(jì)候選項(xiàng)集的效用值，這個策略也可以有效的減少候選項(xiàng)集的個數(shù)。實(shí)驗(yàn)采用了3個典型數(shù)據(jù)集，包括真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集；實(shí)驗(yàn)結(jié)果也表明了本文提出的策略在保證正確的挖掘結(jié)果的條件下，能有效地減少了候選項(xiàng)集的產(chǎn)生，從而算法的時(shí)間和空間性能得到了較大的提高，特別是在真實(shí)數(shù)據(jù)集上表現(xiàn)更為出色。

[1]Tseng V S，Shie B，Wu C，et al.Efficient algorithms for mining high utility itemsets from transactional databases[J].IEEE Transactions on Knowledge and Data Engineering，2012 （1）:1－10.

[2]Li H，Huang H，Chen Y，et al.Fast and memory efficient mining of high utility itemsets in data streams[C]／／Maui，HI，United States:Association for Computing Machinery，2008.

[3]Ahmed C F，Tanbeer S K，Jeong B S，et al.Efficient tree structures for high utility pattern mining in incremental databases[J].IEEE Transactions on Knowledge and Data Engineering，2009，21 （12）:1708－1721.

[4]Tseng V S，Wu C W，Shie B E，et al.UP－Growth:An efficient algorithm for high utility itemset mining[C]／／ Washington，DC，United States，2010.

[5]Lin C W，Hong T P，Lan G C，et al.Mining high utility itemsets based on the pre－large concept[M].Advances in Intelligent Systems and Applications，2013:243－250.

[6]Song W，Liu Y，Li J.Vertical mining for high utility itemsets[C]／／ Maui，HI，United States:Association for Computing Machinery，2012.

[7]Wu C W，Shie B，Tseng V S，et al.Mining top－K high utility itemsets[C]／／Washington，DC，United States，2012.

[8]Liu J，Wang K，F(xiàn)ung B.Direct discovery of high utility itemsets without candidate generation[C]／／ Maui，HI，United states:Association for Computing Machinery，2012.

[9]Liu M，Qu J.Mining high utility itemsets without candidate generation[C]／／ Maui，HI，United states:Association for Computing Machinery，2012.

[10]Li Y C，Yeh J S，Chang C C.Isolated items discarding strategy for discovering high utility itemsets[J].Data and Knowledge Engineering，2008，64 （1）:198－217.

[11]Erwin A，Gopalan R P，Achuthan N R.CTU－mine:An efficient high utility itemset mining algorithm using the pattern growth approach[C]／／IEEE Computer Society Washington，2007.

[12]Liu Y，Liao W K，Choudhary A.A two－phase algorithm for fast discovery of high utility itemsets[C]／／ Hanoi，Viet nam:2005.

[13]Pisharath J，Liu Y，Ozisikyilmaz B，et al.NU－MineBench version 2.0source code and datasets[EB／OL].http:／／cucis.ece.northwestern.edu／projects／DMS／MineBench.html，2012.

[14]Goethals B.Frequent itemset mining dataset repository[EB／OL].http:／／fimi.cs.helsinki.fi／data／.Frequent itemset mining dataset repository，2010.

[15]IBM data generator[EB／OL].http:／／www.almaden.ibm.com／software／quest／Resources／index.shtml，2012.