摘要：頻繁模式是頻繁地出現(xiàn)在數(shù)據(jù)集中的模式（如項集、子序列或子結構）。如頻繁地同時出現(xiàn)在交易數(shù)據(jù)集中的商品的集合是頻繁項集，利用高效率的頻繁項集挖掘算法來發(fā)現(xiàn)頻繁項集，通過分析這些頻繁項集來預測商品的銷售情況。

關鍵詞：關聯(lián)規(guī)則；Apriori算法；頻繁項集；商品

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2013）04-0661-03

Based on the Improvement of Frequent Itemsets Mining Efficiency Algorithm in Market Analysis of Discuss

CHEN Wei

（Huainan Union University， Huainan 232038， China）

Abstract： Frequent pattern is frequently seen in the data concentration mode （such as itemsets， sequences or structures）.As frequently appear in both the transaction data concentrated merchandise collection is frequent itemset， Using of efficient algorithm for mining frequent itemsets to find frequent itemsets， through the analysis of the frequent itemsets to predict the commodity the sales situation.

Key words： association rule； Apriori algorithm； frequent itemsets； commodity

隨著大量數(shù)據(jù)不停地收集和存儲，從數(shù)據(jù)庫中挖掘頻繁模式引起各行各業(yè)人士的興趣。許多商務決策的制定，如交叉銷售、顧客購買習慣分析等，都可以從大量事務記錄中尋找一些有趣的相關聯(lián)系。如今的超級市場作為一種新的銷售形式，因為其商品價格低、品種多和商品直接面向顧客等優(yōu)勢得到了廣大顧客的青睞。但是，隨著超市規(guī)模的不斷增大，商品種類和交易量也日益龐大起來，自然所積累的商業(yè)數(shù)據(jù)也越來越多。在這種情況下，面臨如何以最少的資金組織最快的商品流動、如何根據(jù)顧客的需求對商品進行合理的布局和搭配、如何根據(jù)目前的銷售信息去預測未來的銷售情況等等一系列問題都是商家特別關心的。

1 頻繁項集挖掘方法概述

購物籃分析是頻繁項集挖掘的一個典型例子，它是根據(jù)購買者購買的商品來分析該顧客的購物習慣，比如典型的“啤酒和尿布”例子，超市經(jīng)過對購物信息的挖掘，改變貨物在貨架上的擺放位置，從而調高了銷售額。

除了購物籃分析以外，還有許多種頻繁模式、關聯(lián)規(guī)則和相關聯(lián)系。頻繁模式挖掘有多種方法：

1）根據(jù)所處理的值類型分為：布爾關聯(lián)規(guī)則和量化關聯(lián)規(guī)則。

2）根據(jù)涉及的數(shù)據(jù)維分為：單維關聯(lián)規(guī)則和多維關聯(lián)規(guī)則。

3）根據(jù)所涉及的抽象層分為：單層關聯(lián)規(guī)則和多層關聯(lián)規(guī)則。

目前已經(jīng)開發(fā)了許多有效的、可伸縮的頻繁項集挖掘算法，由它們可以導出關聯(lián)規(guī)則。這些算法分成三類：1）類Apriori算法，2）基于頻繁模式增長算法，如FP增長，3）使用垂直數(shù)據(jù)格式的算法。

關聯(lián)規(guī)則挖掘中最簡單形式的挖掘是單維、單層和布爾關聯(lián)規(guī)則，其中用一種稱為逐層搜索的迭代方法來找出所有的頻繁項集的Apriori算法是最著名、最有影響的關聯(lián)規(guī)則挖掘算法。它的建立也是基于頻繁項集性質的基礎。

2 提高頻繁項集挖掘效率算法

在尋找頻繁項集的Apriori算法中需要頻繁進行這樣兩個操作：判斷兩個k-項集中是否滿足前k-l項相同且最后一項不同，即連接步；判斷一個項集是否為另一個項集的子集，即剪枝步。假設事務數(shù)據(jù)庫中各記錄的項目均已排序，可以利用這一特點，從減少算法中這兩個操作的執(zhí)行次數(shù)的方法來達到優(yōu)化算法的目的。

1）減少連接步驟的執(zhí)行次數(shù)具體實現(xiàn)方法：

由于我們已經(jīng)設定各事務項目按字典排序，所以其中的任一個k-項集L，有L[l]

2）減少剪枝步驟的執(zhí)行次數(shù)具體實現(xiàn)方法：

對于一個k-項候選集的一個子集（k-1）-項集La和一個（k-l）-項頻繁集Lb，若La[i]< Lb[i]，則La與Lb后的所有（k-l）-項頻繁集都不會相同。所以只要La[i]< Lb[i]，就不需要再判斷La是否與Lb后的（k-1）-項集相同。則判定La不是頻繁項集。由頻繁項集的所有非空子集都必須是頻繁的Apriori算法性質，所以該k-項候選集不是頻繁項集，從而刪除它。該步操作中大大減少了判斷候選項集的任一子集是否是頻繁項集的執(zhí)行次數(shù)。

從Apriori算法中由k頻繁項集生成k+1頻繁項集時，要首先生成候選項目集Ck+1。在掃描數(shù)據(jù)庫時，要記錄下該函數(shù)生成的許多候選項目集的出現(xiàn)次數(shù)，但這些候選項目集并不都是要找的頻繁項集。假如數(shù)據(jù)庫中的事務數(shù)很大，k頻繁項集數(shù)就多，導致侯選項目集的元素個數(shù)也會很多。例如1000個頻繁1-項集，就生成1000*999/2=499500個候選2-項集。統(tǒng)計如此巨大數(shù)量的候選項目集的出現(xiàn)次數(shù)開銷非常大，這是整個算法性能好壞的關鍵。

Apriori算法是從TID項集格式的事務集中挖掘頻繁項集，這里的TID是事務標識符，而item是TID中購買的商品集，這種數(shù)據(jù)格式稱為水平數(shù)據(jù)格式。如果數(shù)據(jù)用項-TID集格式表示，其中item是項的名稱，TID_set是包含item的事務標識符的集合，這種格式稱為垂直數(shù)據(jù)格式。

所以在探討過程中準備使用垂直數(shù)據(jù)格式挖掘頻繁項集，這是對頻繁項集挖掘效率的進一步改進。然后再利用改進的方法重新對數(shù)據(jù)進行分析應用。

首先在求頻繁1項集的同時把數(shù)據(jù)轉化為垂直格式，即記錄下在數(shù)據(jù)庫中每個項集出現(xiàn)時的該條數(shù)據(jù)的TID號，那么項集的支持度計數(shù)就是項集的TID集的長度。從k=2開始，用Apriori算法通過取頻繁k項集的TID集的交計算對應的k+1項集的TID集，若該TID集的長度大于最小支持度計數(shù)，則該記錄為頻繁項集。重復該過程，k值增加1，直到不能再找到頻繁項集或候選項集[1-2]。

3 算法應用探討

實驗方案：

1）首先利用Visualfoxpro6.0中提供的導入向導功能將顧客信息和商品銷售信息的數(shù)據(jù)文件導入到Visualfoxpro6.0中，建立相應的數(shù)據(jù)庫文件；

2）針對現(xiàn)有數(shù)據(jù)進行數(shù)據(jù)預處理，包括二個步驟：數(shù)據(jù)清理和數(shù)據(jù)變換。

數(shù)據(jù)清理：消除一些冗余數(shù)據(jù)，消除噪聲數(shù)據(jù)，消除重復記錄。

數(shù)據(jù)變換：將數(shù)據(jù)轉換成適合于挖掘的形式。假設一段小數(shù)據(jù)量的交易如下：

其中表格中的數(shù)值代表顧客購買商品的數(shù)量。對數(shù)據(jù)進行預處理后其中1代表購買，0代表沒有購買：

3）用優(yōu)化的算法求解頻繁項集：根據(jù)超市的商品銷售量、顧客購買情況等信息，設定最小支持度，求解頻繁項目集。設酸奶為A、香腸B、面包C、啤酒D、果汁E：

①建立一個數(shù)據(jù)表，表中有1個字段，數(shù)據(jù)類型為字符型用于存放每種商品的表達值，該表中每條記錄代表一種表達值，記錄數(shù)就是表達值形式的數(shù)目。表中的記錄按升序排列。

②建立二個空數(shù)據(jù)表，分別用來存放1、2頻繁項集和它們的支持度計數(shù)。其中一個表中有2個字段，另一個表中有3個字段。

4）從已經(jīng)產(chǎn)生的頻繁項集中找出它們的子集，然后根據(jù)關聯(lián)規(guī)則的挖掘算法原理，設定最小置信度，由實驗得出關聯(lián)規(guī)則[3-6]。

從得出的規(guī)則中可以看出買酸奶的顧客就一定會同時購買面包，反之亦然；買酸奶的顧客一定會同時購買香腸，買面包一定會同時購買香腸，但反過來不一定等等購買信息。

4 總結

關聯(lián)規(guī)則的應用廣泛，而其中耗時最多的工作就是它的經(jīng)典算法 Apriori算法中的頻繁項集的求解，因此提高了頻繁項集的求解速度，自然也就加快了關聯(lián)規(guī)則的求解速度。在原算法的基礎上一步步改進其效率是本應用的一個主要亮點，并把這些改進的過程一一運用在具體的數(shù)據(jù)中是另一亮點。但在文章中由于數(shù)據(jù)量小，說明問題的力度不夠大，需要采集大容量數(shù)據(jù)。

近年來超市發(fā)展迅速，成為我國商品流通領域中非常重要的一種形式。超級市場的數(shù)據(jù)不僅十分龐大、復雜，而且包含著許多有用的信息，我們利用上述算法可以從這龐大的數(shù)據(jù)中發(fā)現(xiàn)一些潛在的、有用的、有價值的信息來應用于超市的經(jīng)營。利用提高挖掘效率的過程對顧客消費模式、商品銷售、營銷情況進行分析，可以幫助許多商務決策的制定。同樣利用該算法我們可以把它應用于銀行、股市等等其他行業(yè)，應用前景廣泛。

參考文獻：

[1] 陳文偉，黃金才.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].北京：人民郵電出版社，2004.

[2] 陳偉.數(shù)據(jù)挖掘技術在學生成績管理中的應用[D].合肥：安徽大學，2008.

[3] 戴智杰，袁衛(wèi)，謝邦昌.超市里的數(shù)據(jù)挖掘[J].中國統(tǒng)計，2008（5）：42-43.

[4] Agrawal R，Imielinski T，Swami A. Mining association rules between sets of items in large databases[C].Proceedings of the ACM SIGMOD Conference on Management of data（ACM SIGMOD’93），Washington.USA，1993：20-216.

[5] 洪晶，柳炳祥，程功勛.一種基于Apriori算法的彩票數(shù)字組合數(shù)據(jù)挖掘[J].福建電腦，2005（9）：92-92.

[6] 陳偉.關聯(lián)規(guī)則在學生CET4成績中的應用[J].信息化縱橫（原微型機與應用），2009，28（5）：10-12.