與時(shí)機(jī)判定相結(jié)合的關(guān)聯(lián)規(guī)則增量更新算法

夏 英，劉曉鳳

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入:原數(shù)據(jù)集DB，DB的頻繁項(xiàng)集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ī)則時(shí)機(jī)判定方法，確定是否需要更新關(guān)聯(lián)規(guī)則，如果不需要就將原頻繁項(xiàng)集作為新頻繁項(xiàng)集直接返回;相反，則進(jìn)行關(guān)聯(lián)規(guī)則的更新操作。

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

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

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

輸入:原數(shù)據(jù)集DB，DB的頻繁項(xiàng)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的頻繁項(xiàng)集 L'。

處理步驟:

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

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

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

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

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

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

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

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

通過(guò)圖2可以看出，本文算法的候選項(xiàng)集個(gè)數(shù)少于SA算法，這是因?yàn)楸疚乃惴ㄔ谟?jì)算過(guò)程中利用Apriori性質(zhì)，采用增強(qiáng)的剪枝方法，有效的對(duì)候選項(xiàng)集進(jìn)行了修剪，而SA算法在計(jì)算的過(guò)程中，只是簡(jiǎn)單利用原頻繁項(xiàng)集對(duì)候選項(xiàng)集進(jìn)行修剪。在不損失頻繁模式信息的情況下，如果候選項(xiàng)集的個(gè)數(shù)越少，則算法需要占用的存儲(chǔ)空間越少。因此，與SA算法相比，本文算法需要占用較少的存儲(chǔ)空間。

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

4 結(jié)論

針對(duì)實(shí)時(shí)應(yīng)用中的模式增量更新問(wèn)題，本文提出了與時(shí)機(jī)判定相結(jié)合的關(guān)聯(lián)規(guī)則增量更新算法，結(jié)合更新時(shí)機(jī)進(jìn)行模式更新，同時(shí)采用增強(qiáng)的剪枝策略，從而實(shí)現(xiàn)關(guān)聯(lián)規(guī)則的高效更新。該算法不但可以滿(mǎn)足用戶(hù)的關(guān)聯(lián)規(guī)則增量更新要求，而且避免了關(guān)聯(lián)規(guī)則更新頻繁、更新時(shí)間長(zhǎng)的這些缺點(diǎn)。目前，本文主要針對(duì)數(shù)據(jù)增加時(shí)的關(guān)聯(lián)規(guī)則增量更新算法研究，進(jìn)一步工作還將考慮數(shù)據(jù)刪除或者最小支持度變化時(shí)的關(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樹(shù)的挖掘關(guān)聯(lián)規(guī)則的增量式更新算法［J］.計(jì)算機(jī)學(xué)報(bào)，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］.計(jì)算機(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］夏英，劉婉蓉.基于滑動(dòng)窗口的關(guān)聯(lián)規(guī)則增量式更新算法［J］.計(jì)算機(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ù)倉(cāng)庫(kù)的關(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］.第二版.范明，孟小峰，譯.北京:機(jī)械工業(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.