夏 英，劉曉鳳

(重慶郵電大學(xué)計算機科學(xué)與技術(shù)學(xué)院，重慶 400065)

0 引言

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域中的一個重要研究內(nèi)容，在電信業(yè)務(wù)、零售業(yè)交易、環(huán)境監(jiān)測、工業(yè)生產(chǎn)、互聯(lián)網(wǎng)服務(wù)等領(lǐng)域中應(yīng)用廣泛。隨著高速數(shù)據(jù)獲取、網(wǎng)絡(luò)通信、數(shù)據(jù)管理等技術(shù)的高速發(fā)展，時效性高、動態(tài)變化的數(shù)據(jù)不斷聚集，隱藏在其中的關(guān)聯(lián)規(guī)則也必然會發(fā)生變化，及時高效的關(guān)聯(lián)規(guī)則更新對于趨勢分析、指揮調(diào)度、輔助決策、信息推薦等具有重要的應(yīng)用價值。

近年來，已有許多學(xué)者開展了增量式關(guān)聯(lián)規(guī)則挖掘的研究，提出了相應(yīng)的更新算法［1-5］。比如，基于樹結(jié)構(gòu)的關(guān)聯(lián)規(guī)則更新算法［1-3］，由于算法在發(fā)現(xiàn)頻繁項集過程中，不需要產(chǎn)生候選項集，因此在挖掘長頻繁項集時，具有較高的效率。張根香等［4］提出了基于免疫優(yōu)化的遺傳算法(immune optimization based genetic algorithm，IOGA)，引入遺傳算法解決大規(guī)模數(shù)據(jù)集的關(guān)聯(lián)規(guī)則增量更新問題。夏英等［5］提出了基于滑動窗口的關(guān)聯(lián)規(guī)則增量式更新算法(incremental updating algorithm based on slidingwindow，SWIUA)，該算法基于滑動窗口進行數(shù)據(jù)更新，挖掘出用戶感興趣的近期的關(guān)聯(lián)規(guī)則。以上算法雖然一定程度上提高了關(guān)聯(lián)規(guī)則更新算法的效率，但是大多沒有考慮關(guān)聯(lián)規(guī)則更新時機的問題，直接將其用于實時環(huán)境中的模式更新，容易造成不必要的模式更新，同時頻繁進行關(guān)聯(lián)規(guī)則更新耗費的系統(tǒng)資源較大。針對實時應(yīng)用中頻繁更新的數(shù)據(jù)集，丁虎［6］提出基于抽樣技術(shù)的算法(sampling algorithm，SA)，該算法考慮了關(guān)聯(lián)規(guī)則更新時機，適合于頻繁更新數(shù)據(jù)時模式更新的情況。但該算法在判定更新時機時需要對新增數(shù)據(jù)集進行多次掃描，在關(guān)聯(lián)規(guī)則更新時僅利用原頻繁項集對候選項集進行修剪，這不利于處理大數(shù)據(jù)集和長頻繁項集。

針對頻繁更新的數(shù)據(jù)集，本文在SA算法的基礎(chǔ)上，綜合考慮關(guān)聯(lián)規(guī)則更新時機判定和關(guān)聯(lián)規(guī)則增量更新問題，提出了與時機判定相結(jié)合的關(guān)聯(lián)規(guī)則增量更新算法。

1 相關(guān)定義與性質(zhì)

定義1 關(guān)聯(lián)規(guī)則差異度描述了2個數(shù)據(jù)集中關(guān)聯(lián)規(guī)則差異的大小，主要表現(xiàn)在數(shù)據(jù)集中頻繁項集的差異上，其計算方法［6］為

(1)式中:Lk(D)表示數(shù)據(jù)集D中的頻繁k項集;Lk(S)表示數(shù)據(jù)集 S 中的頻繁 k－項集，k=1，2，…，n。

關(guān)聯(lián)規(guī)則差異度的取值為［0，1］，0表示2個數(shù)據(jù)集的關(guān)聯(lián)規(guī)則完全相同;1表示2個數(shù)據(jù)集的關(guān)聯(lián)規(guī)則完全不同。計算關(guān)聯(lián)規(guī)則差異度可以用于判定關(guān)聯(lián)規(guī)則的更新時機，如當關(guān)聯(lián)規(guī)則差異度大于閾值ˉd時進行關(guān)聯(lián)規(guī)則更新，ˉd的取值為［0，1］，通常由領(lǐng)域?qū)＜一蛴脩羲ā?/p>

定義2 頻繁項集的集合 L={L1，L2，…，Ln}，其中，Ln是頻繁n項集，則Ln含有的非空子集個數(shù)之和是(2n－2)×mn，其中mn是Ln中頻繁項集的個數(shù)，對含有非空子集個數(shù)之和最多的頻繁項集記為LKmax，此時LKmax中頻繁項集的長度是Kmax。

Apriori算法是一種常用的關(guān)聯(lián)規(guī)則挖掘算法，通常包括連接和剪枝2個步驟，具有“頻繁項集的所有非空子集都必須也是頻繁的”這一Apriori性質(zhì)［7］。在關(guān)聯(lián)規(guī)則增量更新時，根據(jù)定義2計算LKmax，找出其中在更新數(shù)據(jù)集中仍然頻繁的項集，根據(jù)Apriori性質(zhì)，則其對應(yīng)長度的所有子集也是頻繁的，由于這部分子集不需要掃描數(shù)據(jù)集來判斷其頻繁性，將其從候選項集中刪除，完成對候選項集的修剪。

性質(zhì)1 如果項集X在原數(shù)據(jù)集和新增數(shù)據(jù)集中都是非頻繁的，則項集X在更新數(shù)據(jù)集中是非頻繁的，同時項集X的超集也是非頻繁的。

對于滿足上述條件的候選項集中的項集，根據(jù)性質(zhì)1，則該項集在更新數(shù)據(jù)集中也不可能是頻繁的，可直接從候選項集中刪除，從而修剪候選項集。

2 關(guān)聯(lián)規(guī)則增量更新算法

關(guān)聯(lián)規(guī)則增量更新算法包括更新時機判定和關(guān)聯(lián)規(guī)則增量更新2個階段。根據(jù)更新前后數(shù)據(jù)集的關(guān)聯(lián)規(guī)則差異度判定更新時機，如果所得的關(guān)聯(lián)規(guī)則差異度大于閾值ˉd，則進行關(guān)聯(lián)規(guī)則增量更新。

2.1 關(guān)聯(lián)規(guī)則更新時機判定方法

針對頻繁更新的數(shù)據(jù)集，以固定時間間隔的方式執(zhí)行關(guān)聯(lián)規(guī)則更新時機判定。在關(guān)聯(lián)規(guī)則時機判定階段，利用已經(jīng)得到的頻繁項集在累積新增數(shù)據(jù)集中的支持度計數(shù)，發(fā)現(xiàn)頻繁項集，計算關(guān)聯(lián)規(guī)則差異度，并以此確定關(guān)聯(lián)規(guī)則更新時機，減少對關(guān)聯(lián)規(guī)則更新后累積新增數(shù)據(jù)集的重復(fù)掃描，具體過程如下:首先，通過逐層搜索的迭代方法，產(chǎn)生候選項集，然后，掃描本次新增數(shù)據(jù)集和原始數(shù)據(jù)集，統(tǒng)計項集支持度計數(shù)，發(fā)現(xiàn)更新后數(shù)據(jù)集的頻繁項集，進而計算關(guān)聯(lián)規(guī)則差異度，最后，確定是否更新關(guān)聯(lián)規(guī)則。

根據(jù)以上分析，關(guān)聯(lián)規(guī)則更新時機判定方法描述如下。

算法1 關(guān)聯(lián)規(guī)則更新時機判定方法Updatemoment。

輸入:原數(shù)據(jù)集DB，DB的頻繁項集L={L1，L2，…，Ln}，關(guān)聯(lián)規(guī)則更新后累積新增數(shù)據(jù)集db'，本次新增數(shù)據(jù)集db，最小支持度min_sup，關(guān)聯(lián)規(guī)則差異度閾值 ˉd。

輸出:是否更新關(guān)聯(lián)規(guī)則的布爾值。

Function Updatemoment(DB，L，db'，db，min_sup，ˉd)

處理步驟:

2.2 關(guān)聯(lián)規(guī)則增量更新算法

本文提出的關(guān)聯(lián)規(guī)則增量更新算法，根據(jù)上述提出的關(guān)聯(lián)規(guī)則時機判定方法，確定是否需要更新關(guān)聯(lián)規(guī)則，如果不需要就將原頻繁項集作為新頻繁項集直接返回;相反，則進行關(guān)聯(lián)規(guī)則的更新操作。

在關(guān)聯(lián)規(guī)則增量更新階段，首先對原數(shù)據(jù)集中頻繁項集L根據(jù)定義2，求出含有子集個數(shù)最多的LKmax，掃描新增數(shù)據(jù)集，找出LKmax中項集在更新數(shù)據(jù)集中仍然頻繁的項集組成L'Kmax，將L'Kmax的子集直接放入對應(yīng)長度的新頻繁項集 L1'，L2'，…，LK'max－1中。然后計算新頻繁i項集(1≤i≤Kmax－1)，通過逐層搜索迭代的方法產(chǎn)生候選項集，把候選項集分成3個互不相交的子集:①L'Kmax的i項子集;②Li－Li'中的項集，即項集在原數(shù)據(jù)集中是頻繁項集，但是它的Kmax項超集不在L'Kmax中;③原數(shù)據(jù)集中的非頻繁項集。對①中的項集，根據(jù)Apriori性質(zhì)，直接把項集加入新頻繁項集中，同時將其從候選項集中刪除。對②中的項集，掃描新增數(shù)據(jù)集，即可判斷項集在更新數(shù)據(jù)集中的頻繁性，同時將其也從候選項集中刪除。對③中的項集，由于其在原始數(shù)據(jù)集中是非頻繁的，基于性質(zhì)1進行修剪，將修剪之后的其余項集通過掃描更新數(shù)據(jù)集，即可判斷該項集是否是頻繁的。最后計算更新數(shù)據(jù)集中i項(iKmax)新頻繁集。

根據(jù)以上分析，本文的關(guān)聯(lián)規(guī)則增量更新算法描述如下。

算法2 關(guān)聯(lián)規(guī)則增量更新算法

輸入:原數(shù)據(jù)集DB，DB的頻繁項L={L1，L2，…，Ln}，關(guān)聯(lián)規(guī)則更新后累積新增數(shù)據(jù)集db'，本次新增數(shù)據(jù)集db，最小支持度min_sup，關(guān)聯(lián)規(guī)則差異度閾值 ˉd。

輸出:更新數(shù)據(jù)集 DB'=DB∪db'∪db的頻繁項集 L'。

處理步驟:

設(shè)原數(shù)據(jù)集事務(wù)數(shù)為N，新增數(shù)據(jù)集事務(wù)數(shù)為m，頻繁項集的最大長度為n，含有子集個數(shù)之和最大的頻繁項集的長度為k。在關(guān)聯(lián)規(guī)則更新時機判定階段，由于需要掃描原數(shù)據(jù)集一次，掃描新增數(shù)據(jù)集n次，確定關(guān)聯(lián)規(guī)則差異度，算法的時間復(fù)雜度為O(nm+N);在關(guān)聯(lián)規(guī)則增量更新階段，在最好的情況下，新頻繁i－項集(ik)可由Apriori性質(zhì)全部得到，為了得到更新后數(shù)據(jù)集的新頻繁項集，需要掃描原數(shù)據(jù)集(n－k+1)次，掃描新增數(shù)據(jù)集(n－k+1)次，此時算法的時間復(fù)雜度為O((n－k+1)(N+m));最壞的情況下，為了得到新頻繁項集，需要掃描原數(shù)據(jù)集n次，掃描新增數(shù)據(jù)集n次，此時算法的時間復(fù)雜度為O(n(N+m));因此，完成一次有效的關(guān)聯(lián)規(guī)則增量更新，其時間復(fù)雜度為O(nm+N+(2n－k+1)(N+m)/2)。對于長頻繁項集，k比較接近n，算法時間復(fù)雜度為O(nm+N+(n+1)(N+m)/2)。

從算法占有的存儲空間上來講，算法處理過程中，根據(jù)Apriori性質(zhì)，把頻繁項集的子集直接放入頻繁項集中，減少子集計數(shù)計算對存儲空間的需求，實現(xiàn)對候選項集的修剪，最終降低了算法對存儲空間的需求。

3 實驗結(jié)果及分析

為了驗證本文提出算法的有效性，實驗將本文所提出的算法和SA算法使用相同的數(shù)據(jù)集進行比較。實驗對算法的執(zhí)行時間和計算過程中需要存儲的候選項集數(shù)量2個指標進行評測。實驗使用的環(huán)境為Intel(R)CPU 2140@1.60GHz 2.00GB RAM，操作系統(tǒng)為Windows XP Professional，算法使用E-clipse平臺的 Java語言實現(xiàn)，數(shù)據(jù)庫選用MySQL5.0。數(shù)據(jù)集由 IBM QUEST［8］生成，采用的原數(shù)據(jù)集包含10 000條事務(wù)，每次新增的數(shù)據(jù)集包含1 000條事務(wù)。實驗中事務(wù)的平均長度是20，頻繁項集的數(shù)量為1 500，最大的潛在頻繁項集的平均長度為8。

實驗1:測試數(shù)據(jù)集相同，在不同的最小支持度條件下對比算法的執(zhí)行時間。設(shè)定關(guān)聯(lián)規(guī)則差異度閾值ˉd為2%，新增數(shù)據(jù)集的大小為4 000，結(jié)果如圖1所示。

圖1 不同最小支持度下算法的執(zhí)行時間Fig.1 Execution time under the different minimum support

由圖1可以看出，隨著最小支持度的增大，本文算法的執(zhí)行時間低于SA算法。原因主要有以下2點:①本文算法在關(guān)聯(lián)規(guī)則更新時機判定階段，利用了頻繁項集在累積新增數(shù)據(jù)集中的支持度計數(shù)，可以減少對累積新增數(shù)據(jù)集的掃描次數(shù);②在關(guān)聯(lián)規(guī)則增量更新階段，本文算法基于Apriori性質(zhì)直接得到頻繁的子集，采用增強的剪枝方法，對候選項集進行修剪，減少對候選項集計算的時間。隨著最小支持度的增大，2個算法執(zhí)行時間都逐漸降低，主要是由于最小支持度決定了產(chǎn)生頻繁項集的數(shù)量。

實驗2:測試數(shù)據(jù)集相同，在不同的最小支持度條件下對比算法的候選項集數(shù)量。設(shè)定關(guān)聯(lián)規(guī)則差異度閾值ˉd為2%，新增數(shù)據(jù)集的大小為4 000，結(jié)果如圖2所示。

通過圖2可以看出，本文算法的候選項集個數(shù)少于SA算法，這是因為本文算法在計算過程中利用Apriori性質(zhì)，采用增強的剪枝方法，有效的對候選項集進行了修剪，而SA算法在計算的過程中，只是簡單利用原頻繁項集對候選項集進行修剪。在不損失頻繁模式信息的情況下，如果候選項集的個數(shù)越少，則算法需要占用的存儲空間越少。因此，與SA算法相比，本文算法需要占用較少的存儲空間。

圖2 不同最小支持度下算法的候選項集數(shù)量Fig.2 Number of candidate itemsets under the different minimum support

4 結(jié)論

針對實時應(yīng)用中的模式增量更新問題，本文提出了與時機判定相結(jié)合的關(guān)聯(lián)規(guī)則增量更新算法，結(jié)合更新時機進行模式更新，同時采用增強的剪枝策略，從而實現(xiàn)關(guān)聯(lián)規(guī)則的高效更新。該算法不但可以滿足用戶的關(guān)聯(lián)規(guī)則增量更新要求，而且避免了關(guān)聯(lián)規(guī)則更新頻繁、更新時間長的這些缺點。目前，本文主要針對數(shù)據(jù)增加時的關(guān)聯(lián)規(guī)則增量更新算法研究，進一步工作還將考慮數(shù)據(jù)刪除或者最小支持度變化時的關(guān)聯(lián)規(guī)則更新算法。

［1］LIU Jian-ping，WANG Ying，YANG Fan-ding.Incremental Mining Algorithm Pre-FP in Association Rules Based on FP-tree［C］//Proceedings of Networking and DistributedComputing(ICNDC)，Hangzhou:IEEE Press，2010:199-203.

［2］易彤，徐寶文.一種基于FP樹的挖掘關(guān)聯(lián)規(guī)則的增量式更新算法［J］.計算機學(xué)報，2004，27(5):703-710.YI Tong，XU Baowen.A FP-Tree Based Incremental Updating Algorithm for Mining Association Rules［J］.Chinese Journal of Computers，2004，27(5):703-710.

［3］PRADEEPINI G，JYOTHI S.Tree-based Incremental Association Rule Mining without Candidate Itemset Generation［C］//Proceedings of Trendz in Information Sciences ＆ Computing(TISC)，Chennai:IEEE Press，2010:78-81.

［4］張根香，陳海山.大規(guī)模數(shù)據(jù)集的增量式關(guān)聯(lián)規(guī)則挖掘［J］.計算機工程與應(yīng)用，2009，45(29):120-124.ZHANG Genxiang，CHEN Haishan.Incremental Association Rules Mining for Large Dataset［J］.Computer Engineering and Applications，2009，45(29):120-124.

［5］夏英，劉婉蓉.基于滑動窗口的關(guān)聯(lián)規(guī)則增量式更新算法［J］.計算機應(yīng)用，2008，28(12):3224-3226.XIA Ying，LIU Wanrong.Incremental Updating Algorithm for Association Rule based on Sliding-window［J］.Journal of Computer Applications，2008，28(12):3224-3226.

［6］丁虎.基于數(shù)據(jù)倉庫的關(guān)聯(lián)規(guī)則抽樣算法研究［D］.哈爾濱:哈爾濱工程大學(xué)，2006.DING Hu.The Research of Association Rule Sampling Algorithm Based on Data Warehouse［D］.Harbin:Harbin Engineering University，2006.

［7］JIAWEI H，MICHELINE K.數(shù)據(jù)挖掘概念與技術(shù)［M］.第二版.范明，孟小峰，譯.北京:機械工業(yè)出版社，2007:148-151.JIAWEI H，MICHELINE K.Data Mining Concepts and Techniques［M］.2nd Edition.FAN Ming，MENG Xiaofeng，translation.BeiJing:Machinery Industry Press，2007:148-151.

［8］CHEUNG D，HAN J，NG V，et al.Maintenance of Discovered Association Rules in Large Databases:An Incremental Updating Technique［C］//Proceedings of the 12th International Conference on Data Engineering，New Orleans:ACM Press，1996:106-114.