關(guān)聯(lián)規(guī)則挖掘在游戲視頻銷售中的研究與應(yīng)用

1、 關(guān)聯(lián)規(guī)則挖掘在游戲視頻銷售中的研究與應(yīng)用 閆東明陳占芳姜曉明摘 要：數(shù)據(jù)挖掘是一項熱門技術(shù)，該技術(shù)融合了數(shù)據(jù)庫、統(tǒng)計學(xué)等領(lǐng)域知識，關(guān)聯(lián)規(guī)則的挖掘則能找出商品銷售中商品之間的聯(lián)系。本文針對Apriori算法，及其改進算法FP-Growth進行了研究，對比了Apriori算法與FP-Growth算法的效率，得出FP-Growth算法由于只需要對數(shù)據(jù)進行一次掃描即可生成相應(yīng)的數(shù)據(jù)集，使其生成數(shù)據(jù)集的整體效率要高于Apriori算法。Key：Apriori算法；數(shù)據(jù)挖掘；FP-Growth算法；關(guān)聯(lián)規(guī)則；游戲銷售：TP391 ：AAbstract：Data mining is a hot techn

2、ology 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 correspondi

3、ng 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 sale1 引言（Introduction）關(guān)聯(lián)規(guī)則是近年來數(shù)據(jù)挖掘領(lǐng)域中

4、最熱門的問題之一，它已經(jīng)被證明對于市場與零售業(yè)，以及其他不同領(lǐng)域都有很重要的作用。關(guān)聯(lián)規(guī)則問題涉及了諸多技術(shù)知識，如數(shù)據(jù)庫、人工智能和統(tǒng)計學(xué)等，該問題的研究目的是統(tǒng)計龐雜的數(shù)據(jù)并提取出有效信息進行分析，得到同一事件出現(xiàn)在不同項的相關(guān)性，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的主要對象是交易型數(shù)據(jù)庫。Apriori算法是一種經(jīng)典的挖掘關(guān)聯(lián)規(guī)則的算法，該算法根據(jù)用戶給出的最小支持度閾值找到交易型數(shù)據(jù)庫中所有頻繁項集，再通過計算找出符合最小置信度的強關(guān)聯(lián)規(guī)則，從而挖掘出有用的知識。Apriori算法的核心思想有兩點：（1）非頻繁項的超集是非頻繁項集；（2）頻繁項的子集是頻繁項集。該算法利用了一個層次順序搜索的循環(huán)方法來完成頻

5、繁項集的挖掘計算。但是，多次掃描數(shù)據(jù)庫和產(chǎn)生數(shù)量巨大的候選集是Apriori算法的兩個無法避免的性能瓶頸1。很多基于Apriori算法的方法被提出，目的都是為了提搞掃描數(shù)據(jù)庫的效率或是減少候選集的產(chǎn)生，其中AprioriTid算法對Apriori算法的循環(huán)掃描方式做出了改進2，AprioriTid算法僅在計算第一個頻繁項集時掃描一次數(shù)據(jù)庫，然后使用候選集Ck-1來計算項集的支持度并得到頻繁k-項集，從而使掃描候選項集的次數(shù)隨著頻繁項集階數(shù)的增加而逐步減少，提高了掃描數(shù)據(jù)的效率。在掃描的初始階段，由于候選項集數(shù)量遠大于數(shù)據(jù)項數(shù)量，這將導(dǎo)致候選事務(wù)的數(shù)據(jù)量可能遠大于原始事務(wù)的數(shù)據(jù)量，所以此時Apr

6、ioriTid算法的效率要低于Apriori算法3-5，而后隨著候選項集的減少，AprioriTid只需要掃描比原始數(shù)據(jù)庫小得多的候選事務(wù)數(shù)據(jù)庫，使運算效率得以大幅提升。2 理論基礎(chǔ)（Theoretical basis）關(guān)聯(lián)規(guī)則挖掘的問題被定義為：為一個或多個的n項組，項目是其中的一個字段，一般指一次交易中的一個物品6；為一組被稱為交易數(shù)據(jù)庫的事務(wù)集，而每個事務(wù)t都是I的非空子集，即每一個交易都與一個唯一的標識符對應(yīng)。每一條事務(wù)中僅包含該事務(wù)涉及的項目，并不包含項目中的具體信息；：表示規(guī)則（Rule），其中并且，項和分別是規(guī)則的前提和結(jié)論，或被稱為左手邊與右手邊；：表示項和的支持度，支持度的計

7、算公式如公式（1）所示：被稱為規(guī)則的置信度，置信度的計算公式如公式（2）所示：表示用戶自定義的一個衡量支持度的閾值，同時也表示該項目集在統(tǒng)計意義上的最低閥值，用支持度來衡量規(guī)則是非常重要的，因為非常低的支持度只會偶然發(fā)生，低支持度的規(guī)則從商業(yè)的角度出發(fā)看起來也是沒有意義的，因為推廣客戶購買非常低可能性同時出售的商品可能是無利可圖的，基于上述原因，支持度常被用來消除無意義的規(guī)則；頻繁項集：對于一個項目集，如果，則稱為頻繁項集。強關(guān)聯(lián)規(guī)則：如果的置信度和支持度不小于用戶自定義的和，則稱是一個強關(guān)聯(lián)規(guī)則，否則為弱關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的挖掘是在事務(wù)數(shù)據(jù)庫中，找到滿足用戶定義的最小支持度和最小置信度要求的

8、關(guān)聯(lián)規(guī)則，其過程主要有兩個階段：（1）第一個階段必須先從所有數(shù)據(jù)集合中找出所有的頻繁項集。在事務(wù)數(shù)據(jù)庫D的所有數(shù)據(jù)中找出滿足條件的全部頻繁項的集合，也就是找出所有的的項集X。（2）第二個階段是在這些頻繁項中產(chǎn)生關(guān)聯(lián)規(guī)則利用頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則，針對每一頻繁項集X，如果，Y非空，且，則X與Y構(gòu)成了關(guān)聯(lián)規(guī)則，滿足用戶給定的最小支持度和最小置信度。關(guān)聯(lián)規(guī)則的第一個階段是從原始的數(shù)據(jù)集合中開始的，需要找出所有頻繁項集，這一步驟是關(guān)聯(lián)規(guī)則挖掘的一個重點問題，也是能夠衡量關(guān)聯(lián)規(guī)則算法優(yōu)良的指標。頻繁項集的是指某一個項出現(xiàn)的頻率相對于所有記錄而言，必須到達某一水平。第二個問題相對容易一些，目前所有的關(guān)聯(lián)規(guī)則

9、算法都是針對第一個問題提出的7。3 Apriori算法與AprioriTid算法的研究（Research on Apriori algorithm and AprioriTid algorithm）Apriori算法是一種基本的挖掘關(guān)聯(lián)規(guī)則算法，該算法的第一步為確定初始的一個大項集，記為L1。接下來的K步包含兩部分，第一部分，項集Lk-1做（k-1）次Apriori-gen循環(huán)以產(chǎn)生候選集Ck。第二部分，掃描數(shù)據(jù)并計算候選集Ck中每一項的支持度。如果存在候選K-集，其支持度不小于最小支持度，則判定為頻繁K-項集，Apriori-gen循環(huán)到不再產(chǎn)生候選集結(jié)束。Apriori算法輸入為銷售型數(shù)據(jù)

10、庫D，和最小支持度閾值，輸出的是計算過后的頻繁項集，該頻繁項集包含了所有滿足最小支持度的項。Apriori算法偽代碼實現(xiàn)：/找出頻繁1-項集，即通過單遍掃描確定每個項的支持度，得到頻繁1-項集的集合L1L1=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并計數(shù)Ct=subset（Ck，t）； /得到t的子集For each 候選子集c屬于Ctc.count+；/返回候選項集中，候選子集不小于最小支持度的的集合，即頻繁k-項集LkLk=

11、c屬于Ck|c.count=min_supReturn L=所有的頻繁項集；第一步：連接步Procedure apriori_gen（Lk-1：frequent（k-1）-items）For each 項集l1處于Lk-1For each 項集l2屬于Lk-1If（l11=l21）&（l12=l22）& （l1k-2=l2k-2）&（l1k-1thenc=l1連接l2/連接步：產(chǎn)生候選子集c，若頻繁k-1-項集Lk-1中已經(jīng)存在子集c則進行剪枝If has_infrequent_subset（c，Lk-1）thenDelete c； /剪枝步：刪除不符合條件的候選子集else add c to

12、 Ck；Return Ck；即通過將Lk-1與自身連接產(chǎn)生候選k-項集的集合Ck。第二步：剪枝步Procedure has_infrequent_subset（c：candidate k-itemset；Lk-1：frequent（k-1）-itemsets）For each （k-1）-subset s of cIf s不屬于Lk-1 thenReturn true；Return false；如代碼中描述的，Apriori算法的工作模式是先生產(chǎn)，再檢驗。如果數(shù)據(jù)集非常大，那么不斷掃描數(shù)據(jù)集就會造成運算效率較低這一問題。FP-Growth算法的思路是首先掃描兩次數(shù)據(jù)集，構(gòu)建出FP-Tree；然

13、后將數(shù)據(jù)集中的所有事務(wù)映射在FP-Tree上；最后通過FP-Tree找出其中的頻繁項集。FP-Growth算法的輸入輸出與Apriori算法一致，而構(gòu)建FP-Tree的過程為：1）第一次掃描數(shù)據(jù)庫，計算每個項的支持度并得到頻繁1-項集2）把項按支持度遞減排序3）第二次掃描數(shù)據(jù)庫，建立FP-Tree挖掘頻繁項集的過程：1）根據(jù)D和minsupp，調(diào)用FP-Tree；2）倘若FP-Tree是一條簡單路徑組合路徑上所有支持度大于minsupp的節(jié)點，得到頻繁項集else初始化最大頻繁集3）根據(jù)支持度從大到小排序，以每個1-頻繁項為后綴，調(diào)用挖掘算法挖掘最大頻繁項集4）輸出所有頻繁項集。根據(jù)以上兩個過

14、程，我們就可以完成FP-Growth的頻繁項集挖掘。FP-Growth算法可以避免產(chǎn)生大量的候選集，但由于該伏安法要遞歸生成條件數(shù)據(jù)庫和條件FP-Tree，所以內(nèi)存開銷較大，且只能用于挖掘單維的布爾型關(guān)聯(lián)規(guī)則。4 對比試驗（Contrast test）本實驗通過使用Weka軟件，對Apriori算法與FP-Growth算法進行比對，輸入數(shù)據(jù)為超市商品銷售數(shù)據(jù)，其格式如圖1所示。其橫坐標代表了每一次顧客的購買記錄，若購買了嬰幼兒必須品，則在該類別中以t為記錄，縱坐標表示了商品的種類。輸入最小支持度與置信度，當計算出最小支持度后，與項的概率相除即置信度，既可以找出相應(yīng)支持度與置信度的關(guān)聯(lián)規(guī)則，首先

15、應(yīng)用Apriori算法對書籍進行處理，當最小支持度設(shè)置為0.15，置信度設(shè)置為0.9時，得到的關(guān)聯(lián)規(guī)則如圖2所示。由圖可知當支持度為0.15，置信度為0.9時，購買餅干、冷凍食品、水果，則很有可能買面包和蛋糕，購買炊事用品、餅干和水果時、很有可能買了面包和蛋糕等。再利用FP-Growth算法，對同樣的數(shù)據(jù)進行挖掘計算，得到的結(jié)果如圖3所示。由圖3和圖4可以看出，F(xiàn)P-Growth算法效率要高于Apriori算法。5 結(jié)論（Conclusion）本文對Apriori算法及其改進的算法進行了研究，并將Apriori算法應(yīng)用于游戲銷售數(shù)據(jù)中，挖掘出銷售數(shù)據(jù)中的強關(guān)聯(lián)規(guī)則，并對相關(guān)規(guī)則作出描述，總結(jié)出

16、了一套視頻游戲的銷售規(guī)律。Reference（References）1 Tsai C F，Lin Y C，Chen C P.A new fast a-lgorithms for mining association rules in large databasesC.IEEE International Conference on Systems，Man and Cybernetics.IEEE，2002，7：6.2 Khabzaoui M，Dhaenens C，TalbiEG.Fast algorithms for mining association rulesJ.Journal of C

17、omputer 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-growthC.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 F