閆東明　陳占芳　姜曉明

摘 要：數(shù)據(jù)挖掘是一項(xiàng)熱門技術(shù)，該技術(shù)融合了數(shù)據(jù)庫、統(tǒng)計(jì)學(xué)等領(lǐng)域知識(shí)，關(guān)聯(lián)規(guī)則的挖掘則能找出商品銷售中商品之間的聯(lián)系。本文針對Apriori算法，及其改進(jìn)算法FP-Growth進(jìn)行了研究，對比了Apriori算法與FP-Growth算法的效率，得出FP-Growth算法由于只需要對數(shù)據(jù)進(jìn)行一次掃描即可生成相應(yīng)的數(shù)據(jù)集，使其生成數(shù)據(jù)集的整體效率要高于Apriori算法。

關(guān)鍵詞：Apriori算法；數(shù)據(jù)挖掘；FP-Growth算法；關(guān)聯(lián)規(guī)則；游戲銷售

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：Data mining is a hot technology which comprises database，artificial intelligence，statistics，etc.The mining association rules can find out the relations among the selling commodities.This paper studies Apriori algorithm and its improved algorithm，F(xiàn)P-Growth，and compares the efficiency of them，where it is found that corresponding data set can be generated after only one data scanning based on FP-Growth algorithm，leading to higher overall efficiency of the generated data set than that of Apriori algorithm.

Keywords：Apriori algorithm；data mining；FP-Growth algorithm；association rules；game sale

1 引言（Introduction）

關(guān)聯(lián)規(guī)則是近年來數(shù)據(jù)挖掘領(lǐng)域中最熱門的問題之一，它已經(jīng)被證明對于市場與零售業(yè)，以及其他不同領(lǐng)域都有很重要的作用。關(guān)聯(lián)規(guī)則問題涉及了諸多技術(shù)知識(shí)，如數(shù)據(jù)庫、人工智能和統(tǒng)計(jì)學(xué)等，該問題的研究目的是統(tǒng)計(jì)龐雜的數(shù)據(jù)并提取出有效信息進(jìn)行分析，得到同一事件出現(xiàn)在不同項(xiàng)的相關(guān)性，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的主要對象是交易型數(shù)據(jù)庫。

Apriori算法是一種經(jīng)典的挖掘關(guān)聯(lián)規(guī)則的算法，該算法根據(jù)用戶給出的最小支持度閾值找到交易型數(shù)據(jù)庫中所有頻繁項(xiàng)集，再通過計(jì)算找出符合最小置信度的強(qiáng)關(guān)聯(lián)規(guī)則，從而挖掘出有用的知識(shí)。Apriori算法的核心思想有兩點(diǎn)：（1）非頻繁項(xiàng)的超集是非頻繁項(xiàng)集；（2）頻繁項(xiàng)的子集是頻繁項(xiàng)集。該算法利用了一個(gè)層次順序搜索的循環(huán)方法來完成頻繁項(xiàng)集的挖掘計(jì)算。但是，多次掃描數(shù)據(jù)庫和產(chǎn)生數(shù)量巨大的候選集是Apriori算法的兩個(gè)無法避免的性能瓶頸[1]。很多基于Apriori算法的方法被提出，目的都是為了提搞掃描數(shù)據(jù)庫的效率或是減少候選集的產(chǎn)生，其中AprioriTid算法對Apriori算法的循環(huán)掃描方式做出了改進(jìn)[2]，AprioriTid算法僅在計(jì)算第一個(gè)頻繁項(xiàng)集時(shí)掃描一次數(shù)據(jù)庫，然后使用候選集Ck-1來計(jì)算項(xiàng)集的支持度并得到頻繁k-項(xiàng)集，從而使掃描候選項(xiàng)集的次數(shù)隨著頻繁項(xiàng)集階數(shù)的增加而逐步減少，提高了掃描數(shù)據(jù)的效率。在掃描的初始階段，由于候選項(xiàng)集數(shù)量遠(yuǎn)大于數(shù)據(jù)項(xiàng)數(shù)量，這將導(dǎo)致候選事務(wù)的數(shù)據(jù)量可能遠(yuǎn)大于原始事務(wù)的數(shù)據(jù)量，所以此時(shí)AprioriTid算法的效率要低于Apriori算法[3-5]，而后隨著候選項(xiàng)集的減少，AprioriTid只需要掃描比原始數(shù)據(jù)庫小得多的候選事務(wù)數(shù)據(jù)庫，使運(yùn)算效率得以大幅提升。

2 理論基礎(chǔ)（Theoretical basis）

關(guān)聯(lián)規(guī)則挖掘的問題被定義為：

為一個(gè)或多個(gè)的n項(xiàng)組，項(xiàng)目是其中的一個(gè)字段，一般指一次交易中的一個(gè)物品[6]；

為一組被稱為交易數(shù)據(jù)庫的事務(wù)集，而每個(gè)事務(wù)t都是I的非空子集，即每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符對應(yīng)。每一條事務(wù)中僅包含該事務(wù)涉及的項(xiàng)目，并不包含項(xiàng)目中的具體信息；

：表示規(guī)則（Rule），其中并且，項(xiàng)和分別是規(guī)則的前提和結(jié)論，或被稱為左手邊與右手邊；

：表示項(xiàng)和的支持度，支持度的計(jì)算公式如公式（1）所示：

：被稱為規(guī)則的置信度，置信度的計(jì)算公式如公式（2）所示：

：表示用戶自定義的一個(gè)衡量支持度的閾值，同時(shí)也表示該項(xiàng)目集在統(tǒng)計(jì)意義上的最低閥值，用支持度來衡量規(guī)則是非常重要的，因?yàn)榉浅５偷闹С侄戎粫?huì)偶然發(fā)生，低支持度的規(guī)則從商業(yè)的角度出發(fā)看起來也是沒有意義的，因?yàn)橥茝V客戶購買非常低可能性同時(shí)出售的商品可能是無利可圖的，基于上述原因，支持度常被用來消除無意義的規(guī)則；

頻繁項(xiàng)集：對于一個(gè)項(xiàng)目集，如果，則稱為頻繁項(xiàng)集。

強(qiáng)關(guān)聯(lián)規(guī)則：如果的置信度和支持度不小于用戶自定義的和，則稱是一個(gè)強(qiáng)關(guān)聯(lián)規(guī)則，否則為弱關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則的挖掘是在事務(wù)數(shù)據(jù)庫中，找到滿足用戶定義的最小支持度和最小置信度要求的關(guān)聯(lián)規(guī)則，其過程主要有兩個(gè)階段：

（1）第一個(gè)階段必須先從所有數(shù)據(jù)集合中找出所有的頻繁項(xiàng)集。

在事務(wù)數(shù)據(jù)庫D的所有數(shù)據(jù)中找出滿足條件的全部頻繁項(xiàng)的集合，也就是找出所有的的項(xiàng)集X。

（2）第二個(gè)階段是在這些頻繁項(xiàng)中產(chǎn)生關(guān)聯(lián)規(guī)則

利用頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則，針對每一頻繁項(xiàng)集X，如果，Y非空，且，則X與Y構(gòu)成了關(guān)聯(lián)規(guī)則，滿足用戶給定的最小支持度和最小置信度。

關(guān)聯(lián)規(guī)則的第一個(gè)階段是從原始的數(shù)據(jù)集合中開始的，需要找出所有頻繁項(xiàng)集，這一步驟是關(guān)聯(lián)規(guī)則挖掘的一個(gè)重點(diǎn)問題，也是能夠衡量關(guān)聯(lián)規(guī)則算法優(yōu)良的指標(biāo)。頻繁項(xiàng)集的是指某一個(gè)項(xiàng)出現(xiàn)的頻率相對于所有記錄而言，必須到達(dá)某一水平。第二個(gè)問題相對容易一些，目前所有的關(guān)聯(lián)規(guī)則算法都是針對第一個(gè)問題提出的[7]。

3 Apriori算法與AprioriTid算法的研究（Research on Apriori algorithm and AprioriTid algorithm）

Apriori算法是一種基本的挖掘關(guān)聯(lián)規(guī)則算法，該算法的第一步為確定初始的一個(gè)大項(xiàng)集，記為L1。接下來的K步包含兩部分，第一部分，項(xiàng)集Lk-1做（k-1）次Apriori-gen循環(huán)以產(chǎn)生候選集Ck。第二部分，掃描數(shù)據(jù)并計(jì)算候選集Ck中每一項(xiàng)的支持度。如果存在候選K-集，其支持度不小于最小支持度，則判定為頻繁K-項(xiàng)集，Apriori-gen循環(huán)到不再產(chǎn)生候選集結(jié)束。Apriori算法輸入為銷售型數(shù)據(jù)庫D，和最小支持度閾值，輸出的是計(jì)算過后的頻繁項(xiàng)集，該頻繁項(xiàng)集包含了所有滿足最小支持度的項(xiàng)。

Apriori算法偽代碼實(shí)現(xiàn)：

//找出頻繁1-項(xiàng)集，即通過單遍掃描確定每個(gè)項(xiàng)的支持度，得到頻繁1-項(xiàng)集的集合L1

L1=find_frequent_1-itemsets（D）；

For（k=2；Lk-1！=null；k++）

{

Ck=apriori_gen（Lk-1）； //產(chǎn)生候選集，并剪枝

For each 事務(wù)t 屬于 D //掃描D并計(jì)數(shù)

{

Ct=subset（Ck，t）； //得到t的子集

For each 候選子集c屬于Ct

c.count++；

}

//返回候選項(xiàng)集中，候選子集不小于最小支持度的的集合，即頻繁k-項(xiàng)集Lk

Lk={c屬于Ck|c.count>=min_sup}

}

Return L=所有的頻繁項(xiàng)集；

第一步：連接步

Procedure apriori_gen（Lk-1：frequent（k-1）-items）

For each 項(xiàng)集l1處于Lk-1

For each 項(xiàng)集l2屬于Lk-1

If（（l1[1]=l2[1]）&&（l1[2]=l2[2]）&&

……&& （l1[k-2]=l2[k-2]）&&（l1[k-1]

then

{

c=l1連接l2

//連接步：產(chǎn)生候選子集c，若頻繁k-1-項(xiàng)集Lk-1中已經(jīng)存在子集c則進(jìn)行剪枝

If has_infrequent_subset（c，Lk-1）then

Delete c； //剪枝步：刪除不符合條件的候選子集

else add c to Ck；

}

Return Ck；

即通過將Lk-1與自身連接產(chǎn)生候選k-項(xiàng)集的集合Ck。

第二步：剪枝步

Procedure has_infrequent_subset（c：candidate k-itemset；

Lk-1：frequent（k-1）-itemsets）

For each （k-1）-subset s of c

If s不屬于Lk-1 then

Return true；

Return false；

如代碼中描述的，Apriori算法的工作模式是先生產(chǎn)，再檢驗(yàn)。如果數(shù)據(jù)集非常大，那么不斷掃描數(shù)據(jù)集就會(huì)造成運(yùn)算效率較低這一問題。

FP-Growth算法的思路是首先掃描兩次數(shù)據(jù)集，構(gòu)建出FP-Tree；然后將數(shù)據(jù)集中的所有事務(wù)映射在FP-Tree上；最后通過FP-Tree找出其中的頻繁項(xiàng)集。FP-Growth算法的輸入輸出與Apriori算法一致，而構(gòu)建FP-Tree的過程為：

1）第一次掃描數(shù)據(jù)庫，計(jì)算每個(gè)項(xiàng)的支持度并得到頻繁1-項(xiàng)集

2）把項(xiàng)按支持度遞減排序

3）第二次掃描數(shù)據(jù)庫，建立FP-Tree

挖掘頻繁項(xiàng)集的過程：

1）根據(jù)D和minsupp，調(diào)用FP-Tree；

2）倘若FP-Tree是一條簡單路徑

組合路徑上所有支持度大于minsupp的節(jié)點(diǎn)，得到頻繁項(xiàng)集else初始化最大頻繁集

3）根據(jù)支持度從大到小排序，以每個(gè)1-頻繁項(xiàng)為后綴，調(diào)用挖掘算法挖掘最大頻繁項(xiàng)集

4）輸出所有頻繁項(xiàng)集。

根據(jù)以上兩個(gè)過程，我們就可以完成FP-Growth的頻繁項(xiàng)集挖掘。FP-Growth算法可以避免產(chǎn)生大量的候選集，但由于該伏安法要遞歸生成條件數(shù)據(jù)庫和條件FP-Tree，所以內(nèi)存開銷較大，且只能用于挖掘單維的布爾型關(guān)聯(lián)規(guī)則。

4 對比試驗(yàn)（Contrast test）

本實(shí)驗(yàn)通過使用Weka軟件，對Apriori算法與FP-Growth算法進(jìn)行比對，輸入數(shù)據(jù)為超市商品銷售數(shù)據(jù)，其格式如圖1所示。

其橫坐標(biāo)代表了每一次顧客的購買記錄，若購買了嬰幼兒必須品，則在該類別中以t為記錄，縱坐標(biāo)表示了商品的種類。輸入最小支持度與置信度，當(dāng)計(jì)算出最小支持度后，與項(xiàng)的概率相除即置信度，既可以找出相應(yīng)支持度與置信度的關(guān)聯(lián)規(guī)則，首先應(yīng)用Apriori算法對書籍進(jìn)行處理，當(dāng)最小支持度設(shè)置為0.15，置信度設(shè)置為0.9時(shí)，得到的關(guān)聯(lián)規(guī)則如圖2所示。

由圖可知當(dāng)支持度為0.15，置信度為0.9時(shí)，購買餅干、冷凍食品、水果，則很有可能買面包和蛋糕，購買炊事用品、餅干和水果時(shí)、很有可能買了面包和蛋糕等。

再利用FP-Growth算法，對同樣的數(shù)據(jù)進(jìn)行挖掘計(jì)算，得到的結(jié)果如圖3所示。

由圖3和圖4可以看出，F(xiàn)P-Growth算法效率要高于Apriori算法。

5 結(jié)論（Conclusion）

本文對Apriori算法及其改進(jìn)的算法進(jìn)行了研究，并將Apriori算法應(yīng)用于游戲銷售數(shù)據(jù)中，挖掘出銷售數(shù)據(jù)中的強(qiáng)關(guān)聯(lián)規(guī)則，并對相關(guān)規(guī)則作出描述，總結(jié)出了一套視頻游戲的銷售規(guī)律。

參考文獻(xiàn)（References）

[1] Tsai C F，Lin Y C，Chen C P.A new fast a-lgorithms for mining association rules in large databases[C].IEEE International Conference on Systems，Man and Cybernetics.IEEE，2002，7：6.

[2] Khabzaoui M，Dhaenens C，TalbiEG.Fast algorithms for mining association rules[J].Journal of Computer Science & Technology，2008，15（6）：619-624.

[3] Yang L，Wang F，Wang T.Analysis of dishonorable behavior on railway online ticketing system based on k-means and FP-growth[C].IEEE International Conference on Information and Automation.IEEE，2017：1173-1177.

[4] Pamba R V，Sherly E，Mohan K.Automated Information Retrieval Model Using FP Growth Based Fuzzy Particle Swarm Optimization[J].International Journal of Information Technology & Computer Science，2017，9（1）：105-111.

[5] 林穎華，陳長鳳.基于關(guān)聯(lián)規(guī)則的企業(yè)財(cái)務(wù)風(fēng)險(xiǎn)評價(jià)研究[J].會(huì)計(jì)之友， 2017（1）：32-35.

[6] 高曉佳.Apriori算法優(yōu)化策略的研究[J].長春理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，32（4）：660-662.

[7] 劉玉鋒.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究與應(yīng)用[D].長春理工大學(xué)，2010.

作者簡介：

閆東明（1989-），男，碩士生.研究領(lǐng)域：數(shù)據(jù)庫與數(shù)據(jù)挖掘.

陳占芳（1980-），男，博士，副教授.研究領(lǐng)域：數(shù)據(jù)庫與數(shù)據(jù)挖掘.

姜曉明（1988-），男，碩士生.研究領(lǐng)域：數(shù)據(jù)庫與數(shù)據(jù)挖掘.