改進(jìn)的頻繁和高效用項(xiàng)集挖掘算法

張健, 劉韶濤

(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 福建 廈門(mén) 361021)

改進(jìn)的頻繁和高效用項(xiàng)集挖掘算法

張健, 劉韶濤

(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 福建 廈門(mén) 361021)

提出一種基于局部效用質(zhì)量值的上界剪枝新方法，引入偽投影技術(shù)避免真實(shí)地構(gòu)造物理投影，基于二者提出改進(jìn)的FHIMA-P算法.在提出的FHIMA-P算法中引入事務(wù)合并和投影事務(wù)合并技術(shù)，提出最終的FHIMA-MP算法，并在mushroom和accident數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).結(jié)果表明：FHIMA-P算法的運(yùn)行時(shí)間相比FHIMA-ALL算法縮短，而FHIMA-MP算法則較前兩者效率有非常大的提高；在不同參數(shù)下，mushroom和accident數(shù)據(jù)集中大量可合并事務(wù)(投影事務(wù))數(shù)目也很好地證明了事務(wù)(投影事務(wù))合并的有效性.

頻繁項(xiàng)集； 高效用項(xiàng)集； 偽投影； 事務(wù)合并

關(guān)聯(lián)規(guī)則最初是挖掘頻繁項(xiàng)集[1-4]，項(xiàng)集的支持度大于等于最小支持度時(shí)，這個(gè)項(xiàng)集是頻繁的.高效用項(xiàng)集挖掘[5-9]是頻繁項(xiàng)集挖掘的擴(kuò)展，項(xiàng)集的效用值大于等于最小效用值時(shí)，這個(gè)項(xiàng)集是高效用的.高效用項(xiàng)集挖掘中，每個(gè)項(xiàng)在事務(wù)中可以出現(xiàn)多次，并且可以有不同的權(quán)重，因此，高效用項(xiàng)集挖掘更加復(fù)雜.現(xiàn)有算法多將支持度和效用值單獨(dú)考慮，很少將這兩種衡量標(biāo)準(zhǔn)同時(shí)考慮.李慧等[10]首次將支持度和相對(duì)效用值線性加權(quán)，定義為質(zhì)量值，提出挖掘數(shù)據(jù)庫(kù)中高質(zhì)量項(xiàng)集的FHIMA算法.FHIMA算法使用PrefixSpan算法[11]的思想，遞歸地構(gòu)造前綴的投影數(shù)據(jù)庫(kù)挖掘頻繁和高效用項(xiàng)集.然而，如果是物理地復(fù)制得到投影數(shù)據(jù)庫(kù)，開(kāi)銷(xiāo)很大.因此，本文引入偽投影技術(shù)進(jìn)行優(yōu)化,提出一種本地效用質(zhì)量值上界剪枝的方法，在 FHIMA算法基礎(chǔ)上，引入事務(wù)合并和投影事務(wù)合并技術(shù)，提出FHIMA-MP算法.

1 頻繁高效用項(xiàng)集挖掘算法FHIMA

FHIMA算法是基于前綴投影的模式增長(zhǎng)算法，它把支持度σ(X)和相對(duì)效用值線性加權(quán)λΦ(X)后的變量定義為質(zhì)量，在給定參數(shù)下，挖掘所有高質(zhì)量項(xiàng)集.FHIMA算法有以下3個(gè)執(zhí)行步驟.1) 刪去數(shù)據(jù)庫(kù)中非頻繁高效用項(xiàng)集的項(xiàng)(不滿足最小支持度和事務(wù)效用權(quán)重估計(jì)的1-項(xiàng)集)，得到頻繁高效用1-項(xiàng)集，數(shù)目為n.2) 將數(shù)據(jù)庫(kù)中各條事物按?(1-項(xiàng)集事務(wù)效用權(quán)重遞增的順序)排序，排序后按照?順序?qū)⑺阉骺臻g劃分為n個(gè)具有不同前綴的投影數(shù)據(jù)庫(kù).3) 在這n個(gè)投影數(shù)據(jù)庫(kù)中,遞歸構(gòu)造子投影數(shù)據(jù)庫(kù)進(jìn)行挖掘，挖掘中進(jìn)行算法搜索空間剪枝.

2 FHIMA算法改進(jìn)

2.1局部效用剪枝和數(shù)據(jù)庫(kù)偽投影

FHIMA算法的剪枝是剪掉以該節(jié)點(diǎn)為根的整棵子樹(shù)，經(jīng)過(guò)分析，在這以前如果適當(dāng)減少這棵子樹(shù)上的節(jié)點(diǎn)，得到的剪枝上界將更緊湊，結(jié)果將更高效.

在高效用項(xiàng)集挖掘算法中，一般第一步用事務(wù)效用權(quán)重的閉包屬性[6]刪去不可能從中得到高效用項(xiàng)集的項(xiàng)目.借鑒這點(diǎn)，提出了局部效用剪枝的概念.文中除自定義符號(hào)外，所有符號(hào)和文獻(xiàn)[10]一致.

定義1局部效用lu(X,c)，其中，X是任意一個(gè)項(xiàng)集；項(xiàng)c∈EI(X).項(xiàng)集X∪c的局部效用定義為

).

性質(zhì)1X是任意一個(gè)項(xiàng)集，對(duì)于項(xiàng)c∈EI(X),如果項(xiàng)集C是項(xiàng)集X通過(guò)添加EI(X)中元素后得到的項(xiàng)集，則有l(wèi)u(X,c)≥u(C)成立.

證明 因?yàn)轫?xiàng)集C是通過(guò)添加項(xiàng)集X擴(kuò)展項(xiàng)集中元素后得到的項(xiàng)集，所以項(xiàng)集C的效用小于等于項(xiàng)集X的效用加上X的擴(kuò)展項(xiàng)集中全部元素效用之和，即

X是任意一個(gè)項(xiàng)集，對(duì)于項(xiàng)c∈EI(X)，如果lu(X,c)小于最小效用值，則所有項(xiàng)集X的擴(kuò)展項(xiàng)集中包含項(xiàng)c的都是低效用的，也就是項(xiàng)c這個(gè)節(jié)點(diǎn)可以從子樹(shù)中刪去.

得到基于局部效用剪枝的質(zhì)量值上界計(jì)算式為

利用這個(gè)上界，從投影數(shù)據(jù)庫(kù)中刪去不滿足條件的項(xiàng)目，可以進(jìn)一步縮減搜索空間.

定義2以項(xiàng)集a為前綴的投影事務(wù)定義為α-T={i|i∈T∧i∈EI(a)}.

定義3以項(xiàng)集a為前綴的投影數(shù)據(jù)庫(kù)定義為α-D={a-T|T∈D∧a-T≠Φ}.

在FHIMA算法中,如果物理地復(fù)制得到投影數(shù)據(jù)庫(kù)，則花費(fèi)在計(jì)算a-D上的時(shí)間是O(n×l)(n是投影數(shù)據(jù)庫(kù)的事務(wù)數(shù),l是事務(wù)平均長(zhǎng)度).為了避免物理地復(fù)制，運(yùn)用偽投影技術(shù).對(duì)數(shù)據(jù)庫(kù)中每一條事務(wù)添加一個(gè)偏移量指針指向它，在每條事務(wù)中查找擴(kuò)展項(xiàng)集中第一個(gè)項(xiàng)相對(duì)于整條事務(wù)的偏移量，從而得到投影事務(wù)，進(jìn)而得到整個(gè)數(shù)據(jù)庫(kù)的偽投影.采用偽投影將a-D的算法時(shí)間復(fù)雜度降為O(n).

2.2事務(wù)合并和投影事務(wù)合并技術(shù)

事務(wù)合并是將兩條或多條事務(wù)合并為一條事務(wù)，從而減少數(shù)據(jù)庫(kù)規(guī)模的一種策略.

定義4稱(chēng)兩條事務(wù)是可合并的，當(dāng)且僅當(dāng)它們按照規(guī)則排序后所含的項(xiàng)是完全相同時(shí)，而不管它們的內(nèi)部效用值或支持度是否相同.

投影數(shù)據(jù)庫(kù)比原來(lái)規(guī)模更小，因而,會(huì)有更多滿足可合并條件的事務(wù).

需要注意，對(duì)于投影事務(wù)合并先要得到投影數(shù)據(jù)庫(kù)，得到投影數(shù)據(jù)庫(kù)時(shí)項(xiàng)的效用值是相加，但支持?jǐn)?shù)不是.應(yīng)該先和它前綴項(xiàng)集的支持?jǐn)?shù)比較，取較小的作為投影后相應(yīng)項(xiàng)的支持?jǐn)?shù).

事務(wù)合并和投影事務(wù)合并顯然會(huì)大大減少數(shù)據(jù)庫(kù)的掃描次數(shù)，但關(guān)鍵的問(wèn)題是如何高效地實(shí)現(xiàn)這兩種合并.最直接的做法就是將所有的事務(wù)進(jìn)行相互比較，看哪些是可以合并的，但這種操作算法的時(shí)間復(fù)雜度為O(n2).為了將時(shí)間復(fù)雜度降低到O(n),定義如下的偏序全排序.

定義7?T定義在全排序?的基礎(chǔ)上，假設(shè)有兩條事物ta={i1,i2,…,im}和tb={j1,j2,…,jk}.這個(gè)偏序全排序關(guān)系定義如下4種情況.

1) 如果這兩條事物可合并，且事物編號(hào)tb大于ta，則最終偏序關(guān)系為T(mén)b?TTa.

2) 如果kgt;m,對(duì)任意整數(shù)x，x滿足0≤xlt;m,都有im-x=jk-x，則最終偏序關(guān)系為T(mén)b?TTa.

3) 如果存在x是整數(shù)，x滿足0≤xlt;min(m,k)，此時(shí)，對(duì)所有整數(shù)y，y滿足xlt;ylt;min(m,k)且jk-x?im-x,im-y=jk-y，則最終偏序關(guān)系為T(mén)b?TTa.

4) 當(dāng)不滿足這3種關(guān)系時(shí)，則最終偏序關(guān)系為T(mén)b?TTa.

按照?T順序排序后，可以得到性質(zhì)2.根據(jù)性質(zhì)2，所有可合并的事務(wù)在數(shù)據(jù)庫(kù)(或投影數(shù)據(jù)庫(kù))中能通過(guò)比較相鄰事務(wù)得到，這樣就能在線性時(shí)間內(nèi)找到它們.

性質(zhì)2項(xiàng)集a的投影數(shù)據(jù)庫(kù)a-D按T排序后，滿足可相互合并的事務(wù)在排序后的投影數(shù)據(jù)庫(kù)中是連續(xù)出現(xiàn)的.

3 實(shí)驗(yàn)結(jié)果與分析

3.1實(shí)驗(yàn)設(shè)置

為了對(duì)比算法性能，將實(shí)現(xiàn)FHIMA算法挖掘全部頻繁高效用項(xiàng)集的算法命名為FHIMA-ALL，與加入偽投影和局部效用剪枝優(yōu)化后的FHIMA-P算法和在FHIMA-P算法中加入事務(wù)(投影事務(wù))合并后的FHIMA-MP算法進(jìn)行對(duì)比.實(shí)驗(yàn)平臺(tái)為Intel(R) Core(TM) i5-3470，主頻 3.20 GHz,內(nèi)存8 GB，Windows 7 旗艦版 64位 SP1，編程語(yǔ)言為Java，開(kāi)發(fā)環(huán)境Eclipse 4.4.0.數(shù)據(jù)集為fimi[http:∥fimi.ua.ac.be/]網(wǎng)站下載的mushroom和accident數(shù)據(jù)集.和文獻(xiàn)[6-8]中方法一樣，各數(shù)據(jù)集中各項(xiàng)的內(nèi)部效用值使用對(duì)數(shù)正態(tài)分布生成1到10之間的數(shù)，事務(wù)中各項(xiàng)的數(shù)量是隨機(jī)生成1到10之間的數(shù).

3.2不同參數(shù)設(shè)置的算法對(duì)比

3.2.1 支持度閾值 不同支持度下，mushroom和accident的運(yùn)行時(shí)間，如圖1所示.圖1中：t為時(shí)間；η為最小支持度.由圖1可知：支持度越小，算法挖掘的頻繁和高效用項(xiàng)集越多，2種算法運(yùn)行時(shí)間隨支持度的增加開(kāi)始變少,FHIMA-P算法比FHIMA-ALL算法運(yùn)行時(shí)間短，F(xiàn)HIMA-MP算法則比前2個(gè)算法的效率更高.原因在于，首先，在數(shù)據(jù)庫(kù)中，有許多滿足可合并的事務(wù)，F(xiàn)HIMA-MP算法將它們合并成一條事務(wù)，大大壓縮了事務(wù)數(shù)據(jù)庫(kù)；其次，由于算法挖掘都在構(gòu)造的投影數(shù)據(jù)庫(kù)中進(jìn)行，而投影數(shù)據(jù)庫(kù)因其規(guī)模更小滿足可合并要求的事務(wù)更多，所以，加入事務(wù)合并和投影事務(wù)合并技術(shù)大大提高了算法的運(yùn)行效率.

(a) mushroom數(shù)據(jù)集 (b) accident數(shù)據(jù)集圖1 不同支持度下mushroom和accident的運(yùn)行時(shí)間Fig.1 Running time in different support on mushroom and accident dataset

(a) mushroom數(shù)據(jù)集 (b) accident數(shù)據(jù)集圖2 不同支持度下mushroom和accident的事務(wù)(投影事務(wù))合并數(shù)Fig.2 Numbers of transactions (projected transactions) that can be merged in different support on mushroom and accident dataset

不同支持度下，mushroom和accident的事務(wù)(投影事務(wù))合并數(shù)，如圖2所示.圖2中：n為事務(wù)(投影事務(wù))合并數(shù)；η為最小支持度.由圖2可知：mushroom和accident數(shù)據(jù)集中，事務(wù)(投影事務(wù))合并數(shù)隨支持度的增加而減少，并且在指定支持度下，它們都存在百萬(wàn)級(jí)別的事務(wù)(投影事務(wù))合并數(shù).

3.2.2 相對(duì)效用值閾值 不同相對(duì)效用值下，mushroom和accident的運(yùn)行時(shí)間，如圖3所示.由圖3可知:當(dāng)最小相對(duì)支持度變大時(shí)，3種算法運(yùn)行時(shí)間也是逐漸變少，并且3種算法效率大小關(guān)系仍和支持度從小到大變化時(shí)一致，即FHIMA-P算法比FHIMA-ALL算法運(yùn)行時(shí)間更短，F(xiàn)HIMA-MP算法相比前兩個(gè)算法運(yùn)行效率有顯著的提高.

不同相對(duì)效用值下，mushroom和accident的事務(wù)(投影事務(wù))合并數(shù)，如圖4所示.由圖4可知：3種數(shù)據(jù)集中事務(wù)(投影事務(wù))合并數(shù)隨相對(duì)效用值的增加而減少，在最小效用值閾值下，同樣存在著百萬(wàn)級(jí)別的事務(wù)(投影)事務(wù)合并數(shù)，這是FHIMA-MP算法比FHIMA-P算法效率更高的原因.

(a) mushroom數(shù)據(jù)集 (b) accident數(shù)據(jù)集圖3 不同相對(duì)效用值下mushroom和accident的運(yùn)行時(shí)間Fig.3 Running time in different relative utility on mushroom and accident dataset

(a) mushroom數(shù)據(jù)集 (b) accident數(shù)據(jù)集圖4 不同相對(duì)效用值下mushroom和accident的事務(wù)(投影事務(wù))合并數(shù)Fig.4 Numbers of transactions (projected transactions) that can be merged in different relative utility on mushroom and accident dataset

3.2.3 加權(quán)系數(shù)閾值 加權(quán)系數(shù)λ代表相對(duì)效用值的重要程度.不同加權(quán)系數(shù)λ下,mushroom數(shù)據(jù)集上的運(yùn)行時(shí)間和(投影)事務(wù)合并數(shù)，如圖5所示.由圖5可知：3種算法運(yùn)行時(shí)間都在逐漸增加，且它們效率高低關(guān)系與支持度和相對(duì)效用的變化一致;當(dāng)λ變大時(shí)，mushroom中事務(wù)(投影事務(wù))合并數(shù)逐漸增加,當(dāng)λ增加到一定程度，3種算法效率和事務(wù)(投影事務(wù))合并數(shù)的增速都開(kāi)始變緩.這是因?yàn)榇藭r(shí)相對(duì)效用值起主導(dǎo)作用，再增加λ,對(duì)算法效率提升已經(jīng)不明顯了.

(a) 運(yùn)行時(shí)間 (b) 事務(wù)(投影事務(wù))合并數(shù)圖5 不同加權(quán)系數(shù)λ下mushroom數(shù)據(jù)集上的運(yùn)行時(shí)間和(投影)事務(wù)合并數(shù)Fig.5 Running time and numbers of transactions (projected transactions) that can be merged in different weighting coefficient λ on mushroom dataset

當(dāng)λ=0時(shí)，F(xiàn)HIMA-P和FHIMA-MP算法轉(zhuǎn)變?yōu)橥诰蝾l繁項(xiàng)集的算法.為了比較算法在λ=0時(shí)挖掘頻繁項(xiàng)集的效率，將FHIMA-P和FHIMA-MP算法分別與Apriori算法[1]和FpGrowth算法[2]進(jìn)行比較,結(jié)果如圖6,7所示.為了更直觀對(duì)比效果，將對(duì)比的4個(gè)算法拆分成2幅圖.

(a) FHIMA-MP和FpGrowth算法 (b) FHIMA-P和Apriori算法圖6 mushroom上不同支持度下運(yùn)行時(shí)間對(duì)比圖Fig.6 Comparation of running time in different support on mushroom dataset

(a) FHIMA-MP和FpGrowth算法 (b) FHIMA-P和Apriori算法圖7 Accident上不同支持度下運(yùn)行時(shí)間對(duì)比圖Fig.7 Comparation of running time in different support on accident dataset

4 結(jié)論

在FHIMA算法的基礎(chǔ)上，引入事務(wù)偽投影和局部效用剪枝，提出改進(jìn)的FHIMA-P算法.引入偽投影，避免了物理地復(fù)制構(gòu)造投影數(shù)據(jù)庫(kù)，另外，為了進(jìn)一步減少算法搜索空間，定義了一種基于局部效用的質(zhì)量值剪枝，從而提高算法效率，最終實(shí)驗(yàn)也證明了這種改進(jìn)的有效性.最后，觀察到數(shù)據(jù)庫(kù)中有很多事務(wù)是可以合并的，并且由于文中算法的特點(diǎn)，將這種合并擴(kuò)展到投影數(shù)據(jù)庫(kù)中.同時(shí)，為了快速找到滿足相互之間可合并條件的事務(wù)，定義了一種排序規(guī)則.實(shí)驗(yàn)結(jié)果證明:在FHIMA-P算法基礎(chǔ)上,加入事務(wù)(投影事務(wù))合并技術(shù)的FHIMA-MP算法相比于之前的FHIMA-P算法效率有非常顯著地提高,另外，在加權(quán)系數(shù)為0時(shí)，F(xiàn)HIMA-P算法明顯比Apriori算法高效，且FHIMA-P算法由于事務(wù)(投影事務(wù))合并仍然適用效率則遠(yuǎn)高于FHIMA-P算法和Apriori算法，它的效率只比FpGrowth算法稍低，從而進(jìn)一步證明了事務(wù)(投影事務(wù))合并的高效性.

接下來(lái)，有關(guān)頻繁高效用項(xiàng)集挖掘方法的研究，還可以從完全頻繁項(xiàng)集、基于約束條件的頻繁項(xiàng)集、最大頻繁項(xiàng)集、頻繁閉項(xiàng)集等類(lèi)型著手嘗試.在確定性數(shù)據(jù)中,每種類(lèi)型的頻繁項(xiàng)集都有其對(duì)應(yīng)的挖掘方法，還可以將頻繁高效用挖掘推廣到時(shí)間序列數(shù)據(jù)、不確定數(shù)據(jù)及其他類(lèi)型適合挖掘的數(shù)據(jù)上.

[1] AGRAWAL B R,SRIKANT R.Fast algorithm for mining association rules[C]∥Proc of International Conference on Very Large Data Bases.Santiago:VLDB,1994:487-499.DOI:10.1109/tencon.2003.1273266.

[2] HAN Jiawei,PEI Jian,YIN Yiwen.Mining frequent patterns without candidate generation[C]∥Proc of 2000 ACM-SIGMOD International Conference on Management of Data (SIGMOD′00).Dallas:Conference Publications,2000:1-12.DOI:10.1023/b:dami.0000005258.31418.83.

[3] DENG Zhihong,WANG Zhonghui,JIANG Jiajian.A new algorithm for fast mining frequent itemsets using N-lists[J].Sciece China Information Sciences,2012,55(9):2008-2030.DOI:10.1007/s11432-012-4638-z.

[4] DENG Zhihong,LYU Shenglong.Fast mining frequent itemsets using Nodesets[J].Expert Systems with Applications,2014,41(10):4505-4512.DOI:10.1016/j.eswa.2014.01.025.

[5] YAO Hong,HAMILTON H J,BUTZ C J.A foundational approach to mining itemset utilities from databases[C]∥Proceedings of the Fourth SIAM International Conference on Data Mining.Florida:DBLP,2004:482-486.

[6] LIU Ying,LIAO Weikeng,CHOUDHARY A.A two-phase algorithm for fast discovery of high utility itemsets[C]∥PAKDD′05 Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining.Hanoi:Springer Berlin Heidelberg,2005:689-695.DOI:10.1007/11430919_79.

[7] TSENG V S,WU C W,SHIE B E,etal.UP-Growth: An efficient algorithm for high utility itemset mining[C]∥Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington D C:ACM Press,2010:253-262.DOI:10.1145/1835804.1835839.

[8] LIU Mengchi,QU Junfeng.Mining high utility itemsets without candidate generation[C]∥ACM International Conference on Information and Knowledge Management.New York:ACM Press,2012:55-64.

[9] KRISHNAMOORTHY S.Pruning strategies for mining high utility itemsets[J].Expert Systems with Applications,2015,42(5):2371-2381.DOI:10.1016/j.eswa.2014.11.001.

[10] 李慧,劉貴全,瞿春燕.頻繁和高效用項(xiàng)集挖掘[J].計(jì)算機(jī)科學(xué),2015,42(5):82-87.DOI:10.11896/j.issn.1002-137X.2015.05.017.

[11] PEI Jian,HAN Jiawei,MORTAZAVI-ASL B,etal.PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]∥Proceedings of the 17th International Conference on Data Engineering.Washington D C:IEEE Press,2001:215-224.DOI:10.1109/icde.2001.914830.

(責(zé)任編輯： 黃曉楠英文審校： 吳逢鐵)

ImprovedMiningAlgorithmforFrequentandHighUtilityItemsets

ZHANG Jian， LIU Shaotao

(College of Computer Science and Technology, Huaqiao University, Xiamen 361021, China)

A new method that uses the upper bound of quality to prune the search space based on local utility quality is proposed, meanwhile, pseudo projection technique is introduced to avoid actually construct the physical projection, then based on these two points, an improved FHIMA-P algorithm is proposed. By adding the transaction merging and projected transaction merging technique in FHIMA-P algorithm, the final FHIMA-MP algorithm is proposed. An experiment is conducted on mushroom and accident dataset, the result shows that the running time of FHIMA-P algorithm is shorter than that of FHIMA-ALL algorithm, while the FHIMA-MP algorithm improves significantly compared with the previous two algorithms′ efficiency. Moreover, the huge number of transactions (projected transaction) that can be merged on mushroom and accident dataset in different papameters also prove the effectiveness of transaction (projected transaction) merging technique.

frequent itemsets； high utility itemsets； pseudo projection； transaction merging

10.11830/ISSN.1000-5013.201603067

TP 311

A

1000-5013(2017)06-0880-06

2016-03-24

劉韶濤(1969-)，男，副教授，主要從事軟件體系結(jié)構(gòu)與軟件復(fù)用的研究.E-mail:shaotaol@hqu.edu.cn.

福建省科技計(jì)劃重大項(xiàng)目(2011H6016)