基于支持矩陣的頻繁集增量更新算法改進(jìn)研究*

紀(jì)懷猛，陸林花，黃風(fēng)華

(陽(yáng)光學(xué)院)

?

基于支持矩陣的頻繁集增量更新算法改進(jìn)研究*

紀(jì)懷猛，陸林花，黃風(fēng)華

(陽(yáng)光學(xué)院)

針對(duì)FUP算法在頻繁集增量更新時(shí)，剪枝效率低下以及候選集驗(yàn)證速度慢的缺陷，提出了基于支持矩陣的頻繁集增量更新的高效挖掘算法—SMFUP算法.該算法不僅采用支持矩陣進(jìn)行整體剪枝來(lái)提高剪枝效率，而且進(jìn)一步結(jié)合頻繁2項(xiàng)集矩陣加快候選頻繁集的驗(yàn)證速度，從而使算法的增量更新效率大大提高.最后通過(guò)實(shí)驗(yàn)證明了算法改進(jìn)的有效性.

頻繁集；關(guān)聯(lián)規(guī)則；FUP；支持矩陣；增量更新

0 引言

近年來(lái)，電子商務(wù)的興起促進(jìn)了對(duì)個(gè)性化推薦系統(tǒng)研究.其中，在海量數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則[1]是個(gè)性化推薦系統(tǒng)中一個(gè)非常重要的研究課題.

關(guān)聯(lián)規(guī)則挖掘最經(jīng)典的算法Apriori算法[2]算法自提出后，眾多學(xué)者已對(duì)算法的挖掘效率進(jìn)行了多方面的研究和改進(jìn)，如：采用FP-tree壓縮存放數(shù)據(jù)庫(kù)的主要信息的FP-growth算法[3]，基于壓縮矩陣的方法[4]、基于2項(xiàng)集支持矩陣的算法F2AM[5]等，但是這些算法都是針對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)不變的情況.但是在電子商務(wù)應(yīng)用中，數(shù)據(jù)庫(kù)中的數(shù)據(jù)是隨時(shí)間不斷變化的，因此如何設(shè)計(jì)高效的挖掘算法來(lái)管理、維護(hù)和更新規(guī)則庫(kù)中的關(guān)聯(lián)規(guī)則成為個(gè)性化推薦研究中必須解決的首要問(wèn)題.

針對(duì)關(guān)聯(lián)規(guī)則的增量更新問(wèn)題，目前也有眾多的研究，最具代表性的是Cheung 等提出的如FUP[6],FUP2[7], 馮玉才等提出的 IUA 和 PIUA[8]，但這些算法都需要多次掃描數(shù)據(jù)庫(kù)，為提高更新速度，牛小飛提出了基于支持矩陣的UBM算法[9]，但是該算法只考慮原數(shù)據(jù)庫(kù)中的頻繁項(xiàng)目，而對(duì)新項(xiàng)目不夠敏感；黃德才提出的PFUP[10]算法，該算法的不足之處在 于需要保存原數(shù)據(jù)庫(kù)中每個(gè)頻繁集對(duì)應(yīng)的向量，這樣浪費(fèi)了巨大的內(nèi)存空間.而且不管是何種算法，采用的都是將原數(shù)據(jù)庫(kù)和新數(shù)據(jù)庫(kù)截然分開(kāi)的處理方式.

該文提出的基于支持矩陣的頻繁集增量快速挖掘算法(Fast Updating Algorithm based on Support Matrix, SMFUP)，特別適合最小支持度和最小置信度都保持不變的情況下，數(shù)據(jù)庫(kù)D被添加增量數(shù)據(jù)d時(shí)關(guān)聯(lián)規(guī)則更新的情況.SMFUP算法將原數(shù)據(jù)庫(kù)和新數(shù)據(jù)庫(kù)既看成整體，通過(guò)支持矩陣進(jìn)行整體剪枝大幅減少了候選頻繁項(xiàng)集的產(chǎn)生；又適當(dāng)區(qū)分，利用支持矩陣與頻繁2項(xiàng)集向量來(lái)提高候選集驗(yàn)證的效率.實(shí)驗(yàn)證明，該算法的改進(jìn)是行之有效的.

1 基本概念

設(shè)I={i1,i2,…,im}是m個(gè)不同項(xiàng)目的集合，每個(gè)事務(wù)T是項(xiàng)的集合，使得T?I，D是數(shù)據(jù)庫(kù)事務(wù)的集合.

設(shè)A是一個(gè)項(xiàng)集，事務(wù)T包含A，當(dāng)且僅當(dāng)A?T.A在D中的支持?jǐn)?shù)記為sup(A)，即sup(A)=|A|/|D|，表示D中包含A的事務(wù)數(shù).如果sup(A)大于等于用戶(hù)給定的最小支持度minsup，則稱(chēng)A為頻繁項(xiàng)集.如果A為頻繁項(xiàng)集，并且包含k個(gè)項(xiàng)目，則A稱(chēng)為頻繁k項(xiàng)集.

定義1 每個(gè)項(xiàng)Ij的向量定義為：

Dj=(d1j,d2j,…,dnj)T

項(xiàng)Ij的支持度計(jì)數(shù)為：

定義2 設(shè)事務(wù)數(shù)據(jù)庫(kù)D中含有m個(gè)數(shù)據(jù)項(xiàng)，n個(gè)事務(wù).令f:D→DM， DM=f (D)=(D1,D2,…,Dm)=(dij)m×n，其中：

其中，i=1,2,…,m;j=1,2,…,n.表示在事務(wù)數(shù)據(jù)庫(kù)D中，如果第i個(gè)項(xiàng)出現(xiàn)在第j個(gè)事務(wù)中，則將矩陣DM第j行第i列的值為1，否則為0.

定義3 2項(xiàng)集{Ii,Ij}的向量定義為：

其中，“∧”是“邏輯與”運(yùn)算符.

定義4 頻繁2項(xiàng)集矩陣DM2定義如下：

DM2=(dm1,dm2,…,dmp)

其中，dmi為順序生成的第i個(gè)頻繁2項(xiàng)集對(duì)應(yīng)的列向量.

定義5 頻繁2項(xiàng)集支持矩陣M定義如下：

其中， w為頻繁2項(xiàng)集{Ii,Ij}在DM2中對(duì)應(yīng)列向量的編號(hào).

2 基于支持矩陣的頻繁集增量更新2.1 基于支持矩陣的頻繁項(xiàng)集增量更新原理

2.2 SMFUP算法

算法假設(shè)源數(shù)據(jù)庫(kù)D以矩陣形式存放.

輸入 新增數(shù)據(jù)庫(kù)d，最小支持度s

輸出 滿(mǎn)足最小支持度的所有D∪d的頻繁項(xiàng)集

{由定義3計(jì)算Dij和dij;

if(Dij中1的個(gè)數(shù)+dij中1的個(gè)數(shù)≥s×

(|D|+|d|))

{DM2=(DM2,Dij);dM2=(dM2,dij);

Mij=w;w=w+1;

}

}

Step3 由頻繁k項(xiàng)集增量挖掘頻繁k+1項(xiàng)集.

k =2; //記Lk={Ik1,…,Ikmk}，Inew為Iki與Ikj連接后的項(xiàng)集

if(Iki與Ikj是可連接的) // 將Iki與ikj連接后的項(xiàng)集記為Inew

{if(Mij=0)

continue;

利用支持矩陣M、d以及dM2，計(jì)算出Inew在d中的支持?jǐn)?shù)count1;

在D的頻繁k+1項(xiàng)集中查找Inew;

if(Inew是D的頻繁k+1項(xiàng)集)

if( count1+Inew在D中的支持?jǐn)?shù)≥s×

(|D|+|d|))

Else

If(count1≥s×|d|

{利用支持矩陣M、D以及DM2，計(jì)算出Inew在D中的支持?jǐn)?shù)count2;

If(count1+count2≥s×(|D|+|d|))

}

}

}

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

采用C++語(yǔ)言編寫(xiě)程序，采用安裝了Windows XP SP3操作系統(tǒng)Pentium(R) Dual-Core CPU T4200主頻2.00 GHz 2 GB內(nèi)存的筆記本電腦為實(shí)驗(yàn)平臺(tái)對(duì)SMFUP算法的性能進(jìn)行了實(shí)驗(yàn)分析.實(shí)驗(yàn)采用的數(shù)據(jù)庫(kù)為http://fimi.ua.ac.be/data中提供的Mushroom數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)共有8 124條記錄，119個(gè)屬性；采用的增量數(shù)據(jù)分別為數(shù)據(jù)庫(kù)的前200、400、600、800和1000條.將SMFUP算法與經(jīng)典FUP算法的執(zhí)行時(shí)間進(jìn)行比較，兩種算法的對(duì)比情況如圖1所示.

圖1 兩種算法執(zhí)行時(shí)間對(duì)比

由圖1可知，隨著增量數(shù)據(jù)庫(kù)d中記錄數(shù)目的增加，F(xiàn)UP算法在驗(yàn)證候選頻繁集時(shí)掃描的記錄數(shù)隨之增加，所以執(zhí)行時(shí)間增長(zhǎng)較快，而SMFUP算法在驗(yàn)證候選集是只需掃描各項(xiàng)目對(duì)應(yīng)的相應(yīng)列，并且采用了整體剪枝和頻繁2項(xiàng)集矩陣加快了掃描速度，因此增量數(shù)據(jù)庫(kù)中記錄數(shù)的增加對(duì)其影響較小，所以掃描時(shí)間增加沒(méi)有FUP明顯.實(shí)驗(yàn)過(guò)程中，注意到增量600條記錄時(shí)雖然新數(shù)據(jù)的加入使得頻繁項(xiàng)集數(shù)大幅減少，但是FUP算法執(zhí)行時(shí)間依然略有增加，但是SMFUP算法的執(zhí)行時(shí)間卻略有減少.實(shí)驗(yàn)結(jié)果表明，SMFUP算法執(zhí)行效率明顯優(yōu)于FUP算法，這也充分證明了算法改進(jìn)的有效性.

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

該文提出的SMFUP算法首先利用支持矩陣進(jìn)行整體剪枝，最大限度地減少了候選項(xiàng)集的產(chǎn)生并加快了剪枝速度；然后采用支持矩陣和頻繁2項(xiàng)集矩陣相結(jié)合的方式大大提高了算法驗(yàn)證候選頻繁集的速度；最后，通過(guò)實(shí)驗(yàn)證明了改進(jìn)算法的有效性.但是在電子商務(wù)的實(shí)際應(yīng)用中，事務(wù)數(shù)據(jù)庫(kù)D在記錄數(shù)量上不僅可能隨時(shí)間增加，有時(shí)還會(huì)因某種原因進(jìn)行刪除；而且最小支持度也可能會(huì)同時(shí)發(fā)生改變，因此設(shè)計(jì)能根據(jù)事務(wù)數(shù)據(jù)庫(kù)的增減以及支持度的變化對(duì)數(shù)據(jù)庫(kù)D進(jìn)行高效增量更新挖掘的算法是下一步的研究方向.

[1] Agrawal R, Imielinaki T, Swami A. Mining Association Rules Between Sets of Items in Large Databases[C].Proc. of ACM SIGMOD Conference on Management of Data. Washington D C, USA: ACM Press, 1993.

[2] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules[C].Proc. of VLDB’94. Santiago, Chile: [s. n.], 1994.

[3] Han Jiawei,Jian Pei,Yiwen Yin. Mining frequent patterns without candidate generation[J]. ACM SIGMOD Record, 2000(2) .

[4] Han Jiawei, Kamber M. 數(shù)據(jù)挖掘: 概念與技術(shù)[M]. 范 明, 孟小峰, 譯. 北京: 機(jī)械工業(yè)出版社, 2004.

[5] 紀(jì)懷猛.基于頻繁2項(xiàng)集支持矩陣的Apriori改進(jìn)算法[J].計(jì)算機(jī)工程, 2013,39(11):183-186.

[6] Cheung D W, Han Jiawei, Ng V, et al. Maintenance of discovered association rules in large database: an incremental updating technique[C]. Proceeding of 12th International Conference on Data Engineering, New Orleans, Louisiana, 1996: 106- 114.

[7] Cheung D, LEE S, Kao B.A general incremental technique for maintaining discovered association rules[C].Proceedings of the 5th International Conference on Database Systems for Advanced Applications, Melbourne, Australia, 1997.185- 194.

[8] 馮玉才, 馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報(bào), 1998, 9(4) : 301- 306.

[9] 牛小飛,劉浩,牛學(xué)東等.基于矩陣的關(guān)聯(lián)規(guī)則增量更新算法[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(21):169-171,206.

[10] 黃得才,張良燕,龔衛(wèi)華,等. 一種改進(jìn)的關(guān)聯(lián)規(guī)則增量式更新算法[J]. 計(jì)算機(jī)工程,2008,34(10):38-39,42.

(責(zé)任編輯：季春陽(yáng))

Improvement Research about Frequent Itemsets Incremental Updating Algorithm Based on Support Matrix

Ji Huaimeng, Lu Linhua, Huang Fenghua

(Yango College)

The efficiency is greatly reduced when the algorithm named FUP is used in incremental updating frequent sets. Because it’s low speed of candidate frequent set validation and pruning. The algorithm named SMFUP based on support matrix is put forward, using for efficiently mining incremental updating frequent item sets. The efficiency of the algorithm is greatly increased, because it is not only used to support matrix to speed up pruning; but also used 2- frequent item sets and support matrix to speed up candidate frequent set validation . Finally, the experiments show that the algorithm has a better performance than the FUP algorithm.

Frequent Itemsets; Association Rules; FUP; Support Matrix; Incremental Update

2016-01-09

*國(guó)家自然科學(xué)基金項(xiàng)目資助(41501451)

TP181

A

1000-5617(2016)02-0029-03