汪峰坤，張婷婷

安徽機電職業(yè)技術(shù)學(xué)院信息工程系，安徽蕪湖，241000

?

一種改進的高效用頻繁集挖掘算法

汪峰坤，張婷婷

安徽機電職業(yè)技術(shù)學(xué)院信息工程系，安徽蕪湖，241000

摘要：運用(k-1)階頻繁集與1階頻繁集中較少項數(shù)的頻繁集組合生成k階頻繁候選項、使用最大效用值系數(shù)、各階頻繁項集最大數(shù)目限制三種方法，對高效用頻繁集數(shù)據(jù)挖掘經(jīng)典算法Two-Phase進行了改進，研究了在低維數(shù)據(jù)集上不同數(shù)據(jù)量、高維數(shù)據(jù)集上不同數(shù)據(jù)量和不同維數(shù)數(shù)據(jù)集改進算法了運行時間。結(jié)果表明：改進方法的算法在高數(shù)據(jù)量和高維數(shù)據(jù)集中提高了算法運行效率，減少了運行時間。實驗表明，在高維和百萬數(shù)據(jù)級的數(shù)據(jù)集上，執(zhí)行時間相對于Two-Phase算法至少節(jié)約了50%。

關(guān)鍵詞：數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;頻繁項集;高效用項集

在經(jīng)典的關(guān)聯(lián)規(guī)則生成算法中，對事務(wù)數(shù)據(jù)庫中所有的項集的重要性假定是同等的，僅僅是根據(jù)項集在事務(wù)集中出現(xiàn)的次數(shù)來判斷項之間的關(guān)聯(lián)情況。在實際的一些數(shù)據(jù)挖掘應(yīng)用中，既要考慮項集出現(xiàn)的次數(shù)，又要考慮項集的重要性。例如，在職工體檢中，不同的檢測項的重要性是不一樣的。

針對此類問題，B.Barber等提出了基于“效用”的挖掘概念[1]。項的“效用”值是用戶設(shè)定的用于反應(yīng)項的權(quán)重、收益、消費等內(nèi)容的整數(shù)值。如果某項集的效用值不小于用戶設(shè)定的閾值，則此項集被稱為高效用頻繁項集(HUI)。

基于效用的關(guān)聯(lián)規(guī)則挖掘算法最基本的是枚舉方法，其時空性能差，一般只用于驗證其他算法的正確性。Ying Liu等提出了Two-Phase算法[2]，此算法對效用值的計算公式進行了修改，使新定義的效用值滿足“事務(wù)權(quán)重向下閉屬性”性質(zhì)。Erwin A等提出了CTU-Mine算法[3]，通過一次掃描事務(wù)集，在內(nèi)存中生成表示所有事務(wù)的樹狀結(jié)構(gòu)，減少了事務(wù)集的讀取次數(shù)。以上算法會生成非常多的頻繁項目集和關(guān)聯(lián)規(guī)則，算法的執(zhí)行時間較長，也不利于決策者對求解的關(guān)聯(lián)規(guī)則進行分析[4]。

本文針對Two-Phase算法進行改進，提出了用于生成精簡頻繁項集的近似算法CAMine算法。CAMine算法的改進主要體現(xiàn)在以下幾方面：優(yōu)化k階頻繁候選集的生成、使用最大效用值系數(shù)、使用各階頻繁項集限數(shù)等優(yōu)化策略。經(jīng)過實驗仿真，本算法的運算效率大大提高。

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

定義1設(shè)事務(wù)數(shù)據(jù)庫DB={T1,T2,…,Tn}，其中Ti(i∈[1,n])為DB中的一條事務(wù)。項目集合I={I1,I2,…,Im}，其中Ii(i∈[1,m])為項集中的一個項目。|DB|為事務(wù)數(shù)據(jù)庫中事務(wù)個數(shù)。|I|為項目集中項目個數(shù)。

定義2本地事務(wù)效用值(LocalTransactionUtilityValue)，數(shù)值型數(shù)據(jù)，是客觀數(shù)據(jù)，反映某事務(wù)中項出現(xiàn)的次數(shù)，記為o(ip,Tq)，如表1中，o(E,T4)的值為15。

表1　事務(wù)數(shù)據(jù)庫

定義3外部效用(ExternalUtility)是使用者主觀賦予項的一個實數(shù)值，以反映此項的語義特征，記為s(ip)，可用來表示項的重要性、成本、收益、價值等。例如，由表2可得E的外部效用：s(E)=10。

表2　外部效用表

定義4事務(wù)Tq中項ip的效用值表示某項在某條事務(wù)中給用戶帶來的效用值，記為：u(ip,Tq)。計算公式為：u(ip,Tq)=o(ip,Tq)*s(ip)，例如：u(E,T4)=o(E,T4)*s(E)=15*10=150。

定義8高效用頻繁候選集和高效用頻繁項集：如果項集滿足u′(Ik)≥MinUtilNum，則項集Ik是高效用頻繁候選集。如果項集滿足u(Ik)≥MinUtilNum，則項集Ik是高效用頻繁集。

性質(zhì)1高效用頻繁項集的向下閉包性質(zhì)：設(shè)Ik是k-項集，Ik-1為(k-1)項集，其中Ik-1?Ik。如果Ik是高效用頻繁項集，則Ik-1也是高效用頻繁項集。

本算法新增定義如下：

定義9各階頻繁項集最大數(shù)目MAXFI：整數(shù)值，指每一階頻繁項集的最大數(shù)目。

定義10項集X的最大效用值系數(shù)MUC：整數(shù)值，指任何項集X的最大效用值的限定系數(shù)，即u(X)=MAX(u(X),MUC×MinUtilNum)。

定義11最小效用閾值比例MinUtil：百分比值，表示最小效用閾值占數(shù)據(jù)集事務(wù)個數(shù)的比例，即MinUtilNum=MinUtil×|DB|。

2改進算法

2.1算法的基本數(shù)據(jù)結(jié)構(gòu)

項目結(jié)點Ii包括項目名稱、本地事務(wù)效用值o和項目效用值u。

項目集I={I1,I2,…,Im}的數(shù)據(jù)結(jié)構(gòu)包括表示組成項目集I的所有項目的列表集合、項目效用值u、期望效用值up、本項集的支持?jǐn)?shù)SupNum。

K-階項集Ik的數(shù)據(jù)結(jié)構(gòu)：用來表示所有的k-階的頻繁項和頻繁候選項，主要的數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，鏈表的每個結(jié)點是一個k階的項目集I。

各階頻繁項集數(shù)組指針結(jié)構(gòu)(Pointer)：數(shù)組下標(biāo)對應(yīng)階數(shù)，數(shù)組的元素是指針，指向各階頻繁項集。

2.2CAMine算法流程

當(dāng)前主流的高效用頻繁集計算算法有如下缺點[5-7]：(1)合適的MinUtilNum值確定困難。(2)由于高效用值u不滿足反單調(diào)性，當(dāng)前算法優(yōu)化的主要策略是“定義更加寬松的效用期望效用值up”，利用up的向下閉包性質(zhì)減少候選集數(shù)目。但是維數(shù)較多時，up值與相應(yīng)的u值相差很大，生成高效用候選集時，容易造成組合爆炸情況的產(chǎn)生。(3)維數(shù)較多時，u值增加非?？?，經(jīng)常出現(xiàn)超過整數(shù)范圍的錯誤。(4)在實際使用中，更期望在合理的時間內(nèi)得到適量的高效用頻繁集，用于決策支持。而當(dāng)前的主流算法是生成所有的高效用頻繁集，在數(shù)據(jù)量較大或維數(shù)較多時，算法運行時間過長。

本算法的改進方法主要有：(1)生成k階頻繁候選集時，比較(k-1)階頻繁候選集的長度與一階頻繁候選集長度，利用長度低的候選集與(k-1)階頻繁候選集組合生成階頻繁候選集。當(dāng)候選集長度越長，階數(shù)越多時，此優(yōu)化方法效果越明顯。(2)定義項集X的最大效用值系數(shù)MUC，當(dāng)頻繁集的效用值遠大于最小效用閾值MinUtilNum時，為了防止計算溢出，將頻繁集的效用值設(shè)為MUC×MinUtilNum。這樣，既保證了計算不會溢出，又表示頻繁集的效用。(3)本算法引入了各階頻繁項集最大數(shù)目MAXFI，通過對各階頻繁項集按效用值u降序排序，只保留前MAXFI項，避免了由于最小效用閾值MinUtilNum過小造成的各階頻繁項集組合爆炸問題。

CAMine算法流程如下：

(1)第一遍掃描事務(wù)數(shù)據(jù)庫DB，統(tǒng)計每一項目結(jié)點的效用值u，生成一階頻繁候選集。

(3)第二遍掃描事務(wù)數(shù)據(jù)庫DB，計算二階高效用頻繁候選集每一個候選項的效用值u、期望效用值up和支持?jǐn)?shù)SupNum。

(4)掃描二階頻繁高效用候選集，去除期望效用值up小于最小效用閾值MinUtilNum的候選項。

(5)對于k階(k>2)高效用頻繁候選集，設(shè)(k-1)階高效用頻繁集長度為nk-1。如果nk-1>n1，則k階高效用頻繁候選集由(k-1)階高效用頻繁集與1階高效用頻繁候選集組合生成。否則，k階高效用頻繁候選集由(k-1)階高效用頻繁集與自身組合生成。

(6)掃描事務(wù)數(shù)據(jù)庫DB，計算k階高效用頻繁候選集每一個候選項的效用值u、期望效用值up和支持?jǐn)?shù)SupNum。

(7)k階高效用頻繁候選集按u值排序，掃描生成的k階高效用頻繁候選集，刪除up小于MinUtilNum的候選項。如果u值大于MUC×MinUtilNum，則u值取MUC×MinUtilNum，并且只保留前MAXFI項。

如果k階高效用頻繁候選集不為空，則轉(zhuǎn)向步驟(5)，計算下一階，否則轉(zhuǎn)向步驟8。

(8)遍歷所有階中的候選項，刪除u小于MinUtilNum的項，剩余的項就是高效用頻繁集。

3CAMine算法實驗與分析

3.1算法流程實驗

事務(wù)數(shù)據(jù)庫DB如上表1所示，外部效用表如上表2。CAMine算法的參數(shù)設(shè)置為：最小效用閾值MinUtilNum為30，各階頻繁項集最大數(shù)目MAXFI為100，項集X的最大效用值系數(shù)MUC為10。

一階高效用頻繁項為：[D,(u:48)]，[E,(u:600)]。

二階高效用頻繁項為：[D,(u:48)][E,(u:600)]：[A,D,(u:47)]，[A,E,(u:357)]，[B,E,(u:229)]，[C,D,(u:30)]，[C,E,(u:102)]，[D,E,(u:352)]，[E,F,(u:82)]。

三階高效用頻繁項為：[A,D,E,(u:248)]，[C,D,E,(u:110)]，[A,E,F,(u:84)]，[A,B,E,(u:78)]，[B,D,E,(u:31)]。

四階高效用頻繁項為：[A,B,D,E),(u:32)]。

從挖掘的結(jié)果可以看出，外部效用值E和D在高效用頻繁項集中出現(xiàn)的次數(shù)較多，符合外部效用值的含義。

3.2算法性能比較

本文主要比較算法CAMine和經(jīng)典的Two_Phase算法的時間性能。測試數(shù)據(jù)集由修改后的IBM數(shù)據(jù)生成器生成。

(1)比較低維數(shù)據(jù)集、不同數(shù)據(jù)量的算法性能。數(shù)據(jù)生成器生成的數(shù)據(jù)集的維數(shù)是10，內(nèi)部效用值為0～10，外部效用值為1～100，最小效用閾值比例MinUtil為30%。CAMine算法的MAXFI參數(shù)設(shè)置為500，MUC參數(shù)設(shè)置為100。數(shù)據(jù)量從1萬條升到50萬條。

圖1　低維數(shù)據(jù)運行時間和數(shù)據(jù)量關(guān)系

從圖1可見，當(dāng)數(shù)據(jù)維數(shù)較低時，兩種算法運行速度都比較快。數(shù)據(jù)量較少時(少于16萬)，兩種算法性能相差不多。在數(shù)據(jù)量較大時，CAMine算法要略優(yōu)于Two-Phase算法，當(dāng)數(shù)據(jù)量達到50萬條時，改進算法所用時間減少40%。

(2)比較高維數(shù)據(jù)集、不同數(shù)據(jù)量的算法性能。數(shù)據(jù)生成器生成的數(shù)據(jù)集共有20維，內(nèi)部效用值為0～10，外部效用值為1～100，最小效用閾值比例MinUtil為30%，數(shù)據(jù)量從1萬條升到10萬條。

從圖2可見，對于高維數(shù)據(jù)集，CAMine算法明顯優(yōu)于Two-Phase算法，在數(shù)據(jù)量為50萬條時，改進算法運行時間僅為Two-Phase算法的1/10。

圖2　高維數(shù)據(jù)運行時間和數(shù)據(jù)量關(guān)系

(3)分析給定數(shù)據(jù)量時，不同維數(shù)對算法的性能影響。數(shù)據(jù)生成器生成的數(shù)據(jù)集為5萬條，內(nèi)部效用值為0～10，外部效用值為1～100，最小效用閾值比例MinUtil為30%，維數(shù)從10維增加到30維。

從圖3可見，Two-Phase算法對維數(shù)極其敏感，運行時間與維數(shù)接近指數(shù)關(guān)系。CAMine算法在維數(shù)較高時，算法運行時間仍然可以接受。

4結(jié)束語

Two-Phase算法求解出數(shù)據(jù)集中所有頻繁集，本算法是一種近似算法，可求解出每一階滿足最小效用閾值的給定頻繁項個數(shù)的

圖3 不同維數(shù)據(jù)算法的性能比較

頻繁集。因此，當(dāng)最小效用閾值較小或維數(shù)較高時，Two-Phase算法運算時間過長，出現(xiàn)組合爆炸情況，而本算法可在較短的時間內(nèi)完成。通過仿真，本算法性能相對于經(jīng)典的Two-Phase算法有了一定的提升。

參考文獻：

[1]Barber B,Hamilton H J.Extracting share frequent itemsets with infrequent subsets[J].Data Mining and Knowledge Discovery,2003,7(2):153-185

[2]Liu Y,Liao WK,Choudhary A.A Fast High Utility Itemsets Mining Algorithm[C]//New York USA:Proc of the 2005 Workshop on Utility-Based Data Mining,2005:90-99

[3]Erwin A,Gopalan R P,Achuthan N R.CTU-Mine:An Efficient High Utility Itemset Mining Algorithm Using the Pattern Growth Approach[C]//Washington DC USA:Proc.of the IEEE 7th International Conferences on Computer and Information Technology,2007:71-76

[4]?？诐?，李興建，王樂．高效用項集挖掘算法[J]．計算機工程與設(shè)計，2013，34(12)：4220-4225

[5]Agrawal R,Imielinski T,Swami A.Mining association rules between Sets of items in large databases[J].ACM SIGMOD Record,1993,22(2):207-216

[6]Agrawal R,Srikant R.Fast algorithms for mining association rules[C]//San Francisco CA USA:VLDB,94 Proceedings of the 20th International Conference on Very Large Data Bases,1994:487-499

[7]Lan G C,Hong T P,Tseng V S.Mining High Transaction-Weighted Utility Itemsets[C]//Washington DC USA:ICCEA '10 Proceedings of the 2010 Second International Conference on Computer Engineering and Applications,2010,1:314-318

[8]LAN Guo-cheng,Hong T P,Tseng V S.Efficiently mining high average-utility itemsets with an improved upper-bound strategy [J].International Journal of Information Technology & Decision Making,2012,11(5):1009-1030

(責(zé)任編輯：汪材印)

doi:10.3969/j.issn.1673-2006.2016.07.027

收稿日期：2016-02-25

基金項目：安徽省高校省級自然科學(xué)研究重點項目“基于移動客戶端的教職工健康體檢數(shù)據(jù)智能分析管理系統(tǒng)的研發(fā)”(KJ2014A038)。

作者簡介：汪峰坤(1978-)，安徽霍邱人，碩士，講師，主要研究方向：數(shù)據(jù)挖掘。

中圖分類號：TP301.6

文獻標(biāo)識碼：A

文章編號：1673-2006(2016)07-0103-04