一種改進(jìn)的高效用頻繁集挖掘算法

汪峰坤，張婷婷

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

?

一種改進(jìn)的高效用頻繁集挖掘算法

汪峰坤，張婷婷

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

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

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

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

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

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

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

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

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

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

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

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

表2　外部效用表

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

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

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

本算法新增定義如下：

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

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

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

2改進(jìn)算法

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

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

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

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

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

2.2CAMine算法流程

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

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

CAMine算法流程如下：

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

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

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

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

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

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

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

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

3CAMine算法實(shí)驗(yàn)與分析

3.1算法流程實(shí)驗(yàn)

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

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

二階高效用頻繁項(xiàng)為：[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)]。

三階高效用頻繁項(xiàng)為：[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)]。

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

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

3.2算法性能比較

本文主要比較算法CAMine和經(jīng)典的Two_Phase算法的時(shí)間性能。測(cè)試數(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ù)運(yùn)行時(shí)間和數(shù)據(jù)量關(guān)系

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

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

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

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

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

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

4結(jié)束語

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

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

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

參考文獻(xiàn)：

[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]?？诐钆d建，王樂．高效用項(xiàng)集挖掘算法[J]．計(jì)算機(jī)工程與設(shè)計(jì)，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

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

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

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

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