基于頻繁項集分類統計的增量式關聯規則應用

基于頻繁項集分類統計的增量式關聯規則應用*

劉 紹 清

(福州職業技術學院 計算機系，福州 350002)

摘要：針對商業交易數據構成項目繁多、動態數據增加量大、歷史數據量更大的特點，根據頻繁項集的商業特征，分為新生、成熟、老化、過期4種類型并分類統計；提出了基于分類統計增量地挖掘新增業務數據中關聯規則的算法，算法只需兩次掃描新增數據庫，無需掃描歷史數據庫，算法將發現的規則按照其反應的商業特征分為4種類型：新生規則、成熟規則、老化規則、過期規則，在提升規則內容識別效率的同時，強化規則特點的識別能力。

關鍵詞：頻繁項集分類;統計信息;增量式更新;關聯規則分類

doi:10.16055/j.issn.1672-058X.2015.0012.009

收稿日期：2015-06-08；修回日期：2010-06-15.

基金項目：*福建省教育廳A類項目“數據挖掘批量建模技術”(JA12401).

作者簡介：劉紹清(1974-)，男，福建福州人，副教授，碩士，從事數據挖掘應用研究.E-mail：1132655585@qq.com.

中圖分類號：TP3文獻標志碼：A

商業活動是一個不斷進行的過程，活動的行為模式隨時間推移而變化，體現在數據上就是：商業活動每天會產生大量的數據，積累下來就是海量的數據；從新數據中也可能存在新規律需要發掘；這些新發現的規律在隨著新數據的加入將逐漸失效，也可能持續有效。增量式關聯規則在有效地發現商業活動中交易行為的動態規律方面有其特殊的優勢，因此，很多學者對增量式關聯則進行了研究，提出了FUP[1]、IUA[2]、FUFLA[3]、FIUA[4]以及很多改進算法與應用[5-9]，但是這些算法在提升規律發現效率的同時，沒有考慮到隨著新數據的增加，一些已經發現的商業規律可能會逐漸失去價值，而一些原先不成熟的規律會逐漸成熟，也就無法識別這些規律是處于新發現的，還是處于逐步失效的規律，還是逐步成熟的規律。鑒于此，針對商業交易數據的動態特征，提出一種基于數據頻繁項集歷史統計信息的增量式關聯規則算法(HS_IAR)，只需對本期新增數據集掃描兩次，而無需對歷史數據集進行掃描，就能夠找出所有大于事先給定的最小支持度的關聯規則，并辨別關聯規則所處的生命周期階段，將其分為4種類型：新生規則、成熟規則、老化規則、過期規則，在提升規則內容識別效率的同時，強化規則特點的識別能力。

1FUP算法簡介

1.1算法基本思想

(1) 掃描新事務數據集(d)生成頻繁項目集L(d)；

(2) 獲得d中所有的頻繁項集之后，將其和D的頻繁項集合并，合并過程中，對任意項集可能存在4種情況：

情況A：在D中是頻繁項集，在d中是頻繁項集；

情況B：在D中是非頻繁項集，在d中是頻繁項集；

情況C：在D中是頻繁項集，在d中不是頻繁項集；

情況D：在D中是非頻繁項集，在d中是非頻繁項集。

① 對于情況A，放入當前事務數據庫(d+D)的頻繁項目集L(d+D)中

② 對于情況B和情況C，需要判斷頻繁項集xD∪d在合并后的數據集(D∪d)中是否還是頻繁，大多數算法往往采用公式：

(1)

③ 對于情況D，則不需要處理。

1.2FUP算法不足

在處理情況B和情況C的時候，FUP會存在以下兩個不足：

不足1：對于情況B需要掃描歷史交易數據集D，掃描需要耗費大量的資源；

不足2：對于情況B和C，由于D中的數據記錄數一般會遠遠大于d中的記錄數，導致公式(1)中項集xd的支持數count(xd)在合并后的數據集中作用太小，甚至小到可以被忽略的地步，導致d中的新情況(新規則出現，老規則過期)都被歷史數據否定了，這種否定現象要持續相當長一段時間，直到count(xD)積累了足夠大為止，這將導致算法發現新關聯規則能力大幅度滯后，最終影響算法的應用。

2HS_IAR算法思路

2.1策略1——對發現的規則分類對待

結合著4種情況體現出來的商業業務特點,HS_IAR將發現規則根據其所處生命周期位置分成四類：新生規則、成熟規則、老化規則、過期規則。類似地，頻繁項集也分為新生頻繁項集、成熟頻繁項集、老化頻繁項集、過期頻繁項集，收集四類頻繁項集的相關的統計信息，在后續新增交易數據集合并的時候，只要根據這些歷史統計信息以及每一類的特征，而不需要掃描歷史交易數據庫D，也不需要反復掃描新增交易數據庫d，就能有效地處理情況A到情況D。

定義1：一個項集X，在D中是非頻繁項集，在d中是頻繁項集，則稱X為新生頻繁項集；

定義2：D中一個成熟頻繁項集X，在d中是非頻繁項集，則稱X為老化頻繁項集；

交易行為的變遷，導致交易規則性質發生變化，具體有：

定義4：X?I,Y?I，且X∩Y=?，蘊涵式X?Y稱為關聯規則。如果X∪Y與X滿足：二者都是成熟頻繁項集，意味著規則重復多次出現，而非偶然因素所致，為成熟關聯規則；如果二者有一個是過期頻繁項集，意味著規則有一段時期都不再，稱其為過期規則；如果二者都不是過期頻繁項集，但有一個老化頻繁項集，意味著規則之前有過一段時間沒有出現，但是近期又頻繁出現，這是失效的征兆，則為老化規則；如果上述3種情況都不滿足，則關聯規則為新生規則。

可見，情況A是一種成熟交易模式的表現，相關項集可歸入成熟頻繁項集中重點關注；情況B預示著一種新的交易模式可能出現，相關項集可歸入新生頻繁項集中，繼續跟蹤；情況C是一個規則老化的開始，相關項集歸入老化頻繁項集中，繼續跟蹤；情況D不會出現規則，無需處理。

2.2策略2——刪除事務中非頻繁數據項，減少候選項集

定理1：一個頻繁項集的所有非空子集一定是頻繁項集，若一個項集是非頻繁項集，則該項集的超集也一定是非頻繁項集。

2.3策略3——限制候選項集最大項數，減少候選項集

3算法步驟

處理過程：

(2) 根據推論1方法，計算Max_k，在第二次掃描d時，只處理2-項集到Max_k-項集；

(4) 從C中剔除所有非頻繁的項集，就得到了d中所有的頻繁項集Xd；

(6) 根據新合并后頻繁集，重新生成分類關聯規則集。

4算法實際應用及效果分析

用算法對一家大型百貨超市2012年11月和12月數據進行分析，超市有5家門店，大約10 900種商品，1 600小類，一天10 000筆以上21 d，最多13 663筆交易，5 000筆以下25 d，最少1 424筆交易，一筆交易2項以上產品的大約5%，最多的一筆78種商品,設定最小支持度為2%，最小置信度為60%，分別用matlab實現FUP算法和HS_IAR，效果如下：

4.1運行效率分析

兩個模型每天分析耗費時間如圖1、圖2所示，隨著歷史數據的逐步增加，從圖1可以看出HS_IRA每天建模時間基本穩定，而FUP則是逐步增加；從圖2可知，兩種算法和新增數據量都有一定關系，HS_IRA耗時和新增數據量的關系比較穩定，而FUP因為訪問歷史數據庫不確定導致二者關系不是那么穩定。

圖1　歷史數據量與時間

圖2　新增數據量與時間

4.2規則發現能力

表1是對比了一個規則(巴布豆童裝(巴布豆童鞋)發現的過程，從表1看出，兩種算法都能發現規則，但是HS_IAR比FUP早了13 d發現，在發現規則的及時性上更有優勢。

表1　規則發現能力對比表

5總結

針對商業交易中商品項數多、歷史數據量遠大于新增交易數據量的特點，提出了基于頻繁項集分類統計信息的增量關聯規則算法，采取3種策略來減少數據庫掃描次數和候選項集數量，對挖掘的關聯規則按其體現商業活動特點分成四類區別對待，算法具有較高的規則內容識別效率，較強的規則特點識別能力。

參考文獻：

[1] CHEUNG D W，HAN J，NG V T，et al.Maintenance of Discovered Association Rules in large Database：An Incremental Updating Technique[C]∥In：Proc of the 12th Int Conf on Data Engineering，New Orleans，Louisiana，1996：106-114

[2] 馮玉才，馮劍琳.關聯規則的增量式更新算法[J].軟件學報，1998(4)：301-306

[3] 朱玉全，孫志揮，趙傳申.快速更新頻繁項目集[J].計算機研究與發展，2003(1):94-99

[4] 朱玉全，孫志揮，季小俊.基于頻繁模式樹的關聯規則增量式更新算法[J]計算機學報，2003(1):91-96

[5] 李松生，趙燕偉，顧熙仁，等.改進的FUP算法在五金產品質量分析系統中的應用[J].吉林大學學報：工學版，2012(9):251-254

[6] 唐璐，江紅，上官秋子，等.一種改進的關聯規則的增量式更新算法[J].計算機應用與軟件，2012(4):246-248

[7] 杜煥強，俞立峰.一種高效的關聯規則連續增量更新改進算法[J].哈爾濱師范大學學報：自然科學版，2015(5):49-52

[8] 鄭亞軍，胡學鋼.基于PFP的關聯規則增量更新算法[J].合肥工業大學學報：自然科學版，2015(4):500-503，551

[9] 陳麗芳.基于Apriori算法的購物籃分析[J].重慶工商大學學報：自然科學版，2014(5):84-89

Application of Incremental Association RulesBased on Statistical Information of Classified Frequent Itemsets——Taking Supermarket as an Example

LIU Shao-qing

(Department of Computer，Fuzhou Institute of Technology，Fuzhou 350002，China)

Abstract：Business activities always generate large dataset and accumulate much larger dataset with many items in each transaction.According to the commercial character，frequent itemsets are classified into four classes：new，mature，aging，expired，and an incremental updating algorithm based on statistical information of classified frequent itemsets is put forward.The algorithm only scans newly increased transaction dataset twice without scanning original transaction dataset，and it can also classify all rules into four classes：new，mature，aging，expired with strong rule identification capability as well as higher rule identification efficiency.

Key words： classified frequent itemsets; statistical information; incremental updating; classified association rules