基于頻繁項(xiàng)集分類統(tǒng)計(jì)的增量式關(guān)聯(lián)規(guī)則應(yīng)用

基于頻繁項(xiàng)集分類統(tǒng)計(jì)的增量式關(guān)聯(lián)規(guī)則應(yīng)用*

劉 紹 清

(福州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系，福州 350002)

摘要：針對(duì)商業(yè)交易數(shù)據(jù)構(gòu)成項(xiàng)目繁多、動(dòng)態(tài)數(shù)據(jù)增加量大、歷史數(shù)據(jù)量更大的特點(diǎn)，根據(jù)頻繁項(xiàng)集的商業(yè)特征，分為新生、成熟、老化、過期4種類型并分類統(tǒng)計(jì)；提出了基于分類統(tǒng)計(jì)增量地挖掘新增業(yè)務(wù)數(shù)據(jù)中關(guān)聯(lián)規(guī)則的算法，算法只需兩次掃描新增數(shù)據(jù)庫，無需掃描歷史數(shù)據(jù)庫，算法將發(fā)現(xiàn)的規(guī)則按照其反應(yīng)的商業(yè)特征分為4種類型：新生規(guī)則、成熟規(guī)則、老化規(guī)則、過期規(guī)則，在提升規(guī)則內(nèi)容識(shí)別效率的同時(shí)，強(qiáng)化規(guī)則特點(diǎn)的識(shí)別能力。

關(guān)鍵詞：頻繁項(xiàng)集分類;統(tǒng)計(jì)信息;增量式更新;關(guān)聯(lián)規(guī)則分類

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

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

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

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

中圖分類號(hào)：TP3文獻(xiàn)標(biāo)志碼：A

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

1FUP算法簡介

1.1算法基本思想

(1) 掃描新事務(wù)數(shù)據(jù)集(d)生成頻繁項(xiàng)目集L(d)；

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

情況A：在D中是頻繁項(xiàng)集，在d中是頻繁項(xiàng)集；

情況B：在D中是非頻繁項(xiàng)集，在d中是頻繁項(xiàng)集；

情況C：在D中是頻繁項(xiàng)集，在d中不是頻繁項(xiàng)集；

情況D：在D中是非頻繁項(xiàng)集，在d中是非頻繁項(xiàng)集。

① 對(duì)于情況A，放入當(dāng)前事務(wù)數(shù)據(jù)庫(d+D)的頻繁項(xiàng)目集L(d+D)中

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

(1)

③ 對(duì)于情況D，則不需要處理。

1.2FUP算法不足

在處理情況B和情況C的時(shí)候，F(xiàn)UP會(huì)存在以下兩個(gè)不足：

不足1：對(duì)于情況B需要掃描歷史交易數(shù)據(jù)集D，掃描需要耗費(fèi)大量的資源；

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

2HS_IAR算法思路

2.1策略1——對(duì)發(fā)現(xiàn)的規(guī)則分類對(duì)待

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

定義1：一個(gè)項(xiàng)集X，在D中是非頻繁項(xiàng)集，在d中是頻繁項(xiàng)集，則稱X為新生頻繁項(xiàng)集；

定義2：D中一個(gè)成熟頻繁項(xiàng)集X，在d中是非頻繁項(xiàng)集，則稱X為老化頻繁項(xiàng)集；

交易行為的變遷，導(dǎo)致交易規(guī)則性質(zhì)發(fā)生變化，具體有：

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

可見，情況A是一種成熟交易模式的表現(xiàn)，相關(guān)項(xiàng)集可歸入成熟頻繁項(xiàng)集中重點(diǎn)關(guān)注；情況B預(yù)示著一種新的交易模式可能出現(xiàn)，相關(guān)項(xiàng)集可歸入新生頻繁項(xiàng)集中，繼續(xù)跟蹤；情況C是一個(gè)規(guī)則老化的開始，相關(guān)項(xiàng)集歸入老化頻繁項(xiàng)集中，繼續(xù)跟蹤；情況D不會(huì)出現(xiàn)規(guī)則，無需處理。

2.2策略2——?jiǎng)h除事務(wù)中非頻繁數(shù)據(jù)項(xiàng)，減少候選項(xiàng)集

定理1：一個(gè)頻繁項(xiàng)集的所有非空子集一定是頻繁項(xiàng)集，若一個(gè)項(xiàng)集是非頻繁項(xiàng)集，則該項(xiàng)集的超集也一定是非頻繁項(xiàng)集。

2.3策略3——限制候選項(xiàng)集最大項(xiàng)數(shù)，減少候選項(xiàng)集

3算法步驟

處理過程：

(2) 根據(jù)推論1方法，計(jì)算Max_k，在第二次掃描d時(shí)，只處理2-項(xiàng)集到Max_k-項(xiàng)集；

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

(6) 根據(jù)新合并后頻繁集，重新生成分類關(guān)聯(lián)規(guī)則集。

4算法實(shí)際應(yīng)用及效果分析

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

4.1運(yùn)行效率分析

兩個(gè)模型每天分析耗費(fèi)時(shí)間如圖1、圖2所示，隨著歷史數(shù)據(jù)的逐步增加，從圖1可以看出HS_IRA每天建模時(shí)間基本穩(wěn)定，而FUP則是逐步增加；從圖2可知，兩種算法和新增數(shù)據(jù)量都有一定關(guān)系，HS_IRA耗時(shí)和新增數(shù)據(jù)量的關(guān)系比較穩(wěn)定，而FUP因?yàn)樵L問歷史數(shù)據(jù)庫不確定導(dǎo)致二者關(guān)系不是那么穩(wěn)定。

圖1　歷史數(shù)據(jù)量與時(shí)間

圖2　新增數(shù)據(jù)量與時(shí)間

4.2規(guī)則發(fā)現(xiàn)能力

表1是對(duì)比了一個(gè)規(guī)則(巴布豆童裝(巴布豆童鞋)發(fā)現(xiàn)的過程，從表1看出，兩種算法都能發(fā)現(xiàn)規(guī)則，但是HS_IAR比FUP早了13 d發(fā)現(xiàn)，在發(fā)現(xiàn)規(guī)則的及時(shí)性上更有優(yōu)勢(shì)。

表1　規(guī)則發(fā)現(xiàn)能力對(duì)比表

5總結(jié)

針對(duì)商業(yè)交易中商品項(xiàng)數(shù)多、歷史數(shù)據(jù)量遠(yuǎn)大于新增交易數(shù)據(jù)量的特點(diǎn)，提出了基于頻繁項(xiàng)集分類統(tǒng)計(jì)信息的增量關(guān)聯(lián)規(guī)則算法，采取3種策略來減少數(shù)據(jù)庫掃描次數(shù)和候選項(xiàng)集數(shù)量，對(duì)挖掘的關(guān)聯(lián)規(guī)則按其體現(xiàn)商業(yè)活動(dòng)特點(diǎn)分成四類區(qū)別對(duì)待，算法具有較高的規(guī)則內(nèi)容識(shí)別效率，較強(qiáng)的規(guī)則特點(diǎn)識(shí)別能力。

參考文獻(xiàn)：

[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] 馮玉才，馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報(bào)，1998(4)：301-306

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

[4] 朱玉全，孫志揮，季小俊.基于頻繁模式樹的關(guān)聯(lián)規(guī)則增量式更新算法[J]計(jì)算機(jī)學(xué)報(bào)，2003(1):91-96

[5] 李松生，趙燕偉，顧熙仁，等.改進(jìn)的FUP算法在五金產(chǎn)品質(zhì)量分析系統(tǒng)中的應(yīng)用[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2012(9):251-254

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

[7] 杜煥強(qiáng)，俞立峰.一種高效的關(guān)聯(lián)規(guī)則連續(xù)增量更新改進(jìn)算法[J].哈爾濱師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2015(5):49-52

[8] 鄭亞軍，胡學(xué)鋼.基于PFP的關(guān)聯(lián)規(guī)則增量更新算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2015(4):500-503，551

[9] 陳麗芳.基于Apriori算法的購物籃分析[J].重慶工商大學(xué)學(xué)報(bào)：自然科學(xué)版，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，F(xiàn)uzhou Institute of Technology，F(xiàn)uzhou 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