淺談Apriori算法

摘要：Apriori算法是關聯規則的經典算法。它通過在項集中尋找頻繁項集，進而生成強關聯規則。該文對Apriori算法的基本概念、國內外研究現狀和應用領域做了闡述。

關鍵詞：Apriori算法；研究現狀；應用

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2011)04-0715-02

Simple Description about Apriori Algorithm

LV Ping-li1，2， DUAN Zi-ming3

(1.Computer Science and Technology College of Mining and Technology， Xuzhou 221008， China; 2.Xuhai College of China University of Mining and Technology， Xuzhou 221008， China; 3.Science College of China University of Mining and Technology， Xuzhou 221008， China)

Abstract: Apriori algorithm is a classical algorithm of association rule. It generates strong association rules through searching frequent itemsets. This paper describes the basic concept of Apriori algorithm and its research status home and abroad and its application field.

Key words: Apriori algorithm; research status; application

數據挖掘是從海量的數據中抽取出有價值的知識的數據處理過程。它是隨著數據庫和人工智能技術的發展而出現的全新信息技術，也是目前國際上數據庫和信息決策領域的一個熱點。按發現知識的種類，數據挖掘分為總結規則挖掘、特征規則挖掘、關聯規則挖掘、分類挖掘、聚類挖掘等。其中，關聯規則是數據挖掘領域的一個重要分支。

關聯規則是 Agrawal 等人在1993年提出的。它的定義如下：設I={I1，I2，…，Im}是m個項的集合，事務T是I的子集，事務集D是不同事務的集合。關聯規則是形如 X=>Y 的蘊涵式，其中X是I的子集，Y是I的子集，且X和Y沒有交集。關聯規則有2個基本概念：支持度和置信度。支持度描述了2個項X和Y同時在事務集D中出現的概率。計算公式為：Support(X->Y)=|{T：X∪Y ∈T，T∈D}|/|D|。置信度描述了在X出現的情況下，同時出現Y的概率，也就是條件概率P(Y|X)。計算公式為：Confidence(X->Y)=|{T：X∪Y∈T，T∈D}|/|{T：X∈T，T∈D}|。在實際業務的關聯規則處理中，用戶或本行業專家給出必須滿足的最小支持度和最小置信度，然后運用關聯規則算法從事務集D中找到滿足最小支持度和最小可信度的關聯規則。關聯規則的挖掘分2個步驟進行：1) 尋找頻繁集(頻繁集就是滿足最小支持度的項集的集合)；2) 根據頻繁集，產生可信度大于最小置信度的規則。

1 Apriori算法的思想

關聯規則通過算法運算得到。在眾多的關聯規則算法中，Apriori算法是最經典的。其他的關聯規則算法大多是在Apriori算法的基礎上提出的。1994年，Agrawal提出Apriori算法。該算法通過連接和剪枝2個階段完成關聯規則的挖掘。通過項集元素數目的逐步增長來發現頻繁集，然后以頻繁集為基礎去發現關聯規則。首先掃描事務數據庫得到含有1個項目的候選集C1。在C1中尋找大于或等于最小支持度的1-項目頻繁集L1（這里的字母L是字母Large的首字母。以前頻繁集也稱為大的項集，所以用字母L作為頻繁項集的縮寫）。找到L1之后，利用L1與自身做連接運算，生成候選集C2，然后在C2中找到包含2個項目且滿足最小支持度的頻繁集L2。依次類推，直到無法擴展元素數目為止。得到所有頻繁集（記作L）之后，再根據最小置信度挖掘出管理規則。Apriori算法用偽代碼描述如下：

階段1：生成頻繁項集。

輸入：事務數據庫D和最小支持度的值；

輸出：D中頻繁項目集L；

步驟：

階段2：根據頻繁集產生關聯規則。

輸入：頻繁項集L和最小置信度的值(記作mincof);

輸出：關聯規則;

對于L中的每一個頻繁項集l， 產生l的所有非空子集。

對于l中的每一個非空子集s， 如果l的支持度除以s的支持度得到的結果大于等于最小置信度，寫作Support(l)/support(s)≥minconf， 則輸出規則“S=>(l-S)”。

2 Apriori算法的特點和國內外研究現狀

Apriori算法通過多次掃描數據庫D來發現頻繁項集進而發現關聯規則。每得到一個頻繁集需要掃描數據庫一次。算法本身決定了它兩個比較嚴重的性能瓶頸：1)多次掃描數據庫帶來I/O負載大。2) 通過頻繁集的自身連接得到候選集，如果頻繁項集中項目個數多，生成候選集的時間和內存空間都是非常大的。這就引發了不少學者對Apriori算法進行改進。2000年，J. Han等提出了FP-tree算法。該算法對數據庫做第一遍掃描后，將頻繁項目集壓縮為一顆頻繁模式樹，即FP-tree。隨后對生成的頻繁樹分化成多個條件庫，對每一個條件庫逐一進行挖掘。該頻繁模式樹算法不使用候選集，只掃描數據庫2次，通過頻繁樹生成管理規則，大大減少了I/O操作的時間，且有效減少了內存空間的占用。此外，還有基于散列技術、事務壓縮、劃分、抽樣等方法。其中，基于散列技術是通過壓縮候選集Ck的項目數來減少內存空間的占有量；事務壓縮的核心思想基于一個事實：如果事務T不包含任何頻繁K項集，則它一定不包含任何k+1項集。因此對具備這種特點的事務T加上標記，在產生k+1以上項集的時候不掃描這種事務。該方法有效提高了掃描數據庫的時間。基于劃分的方法是：通過2次掃描數據庫，先將事務數據庫D劃分為n個不重疊的劃分，接著對每個劃分尋找頻繁集，它采用了將整體化為局部的方法，有效減少了I/O操作次數。

3 Apriori算法的應用

目前，數據挖掘已經在各行得到應用。比如，銀行使用數據挖掘技術將市場分類，進而去預測存款和貸款的趨勢，從而幫助相關人員更好地開展工作；數據挖掘在客戶關系管理（CRM）也有很廣泛的應用，它能夠協助相關人員了解客戶特征；比如，經典的“啤酒和尿布”故事，正是數據挖掘在零售業中成功應用的典型，它挖掘出了顧客的購買習慣，指導了商品的貨品擺放。

Apriori算法作為經典的關聯規則算法也已經在國內外的金融業、保險業、航空業等得到了廣泛應用。它對這些行業提高工作效率，增加效益起到了一定的指導意義。比如，銀行業通過應用Apriori算法對儲戶的個人屬性挖掘出關聯規則，挖掘出儲存金額大的用戶的特征，進而制定營銷策略。通過對信用卡用戶的屬性分析，挖掘高信用用戶的屬性特征，然后對這類用戶寄發新產品宣傳單。保險業通過應用Apriori算法，對客戶的特征，比如：婚姻狀況、學歷、收入、職業等屬性做關聯分析，讓得出的關聯規則來指導業務員推銷，大大提高了工作效率，為公司收益創造了價值。

隨著電子商務的快速發展，到網上購物的顧客越來越多。電子網站通過使用關聯規則算法，對顧客的購買習慣進行分析，向顧客推薦他可能感興趣的商品。這對提高銷售額是很有幫助的。比如china-pub網，作為國內很大的圖書銷售網站，它通過對顧客購買書籍的分析，設置捆綁銷售書籍，本來顧客的購買量是1本，但是捆綁銷售的推薦很有可能使得顧客的購買量提高到2本、3本，大大提高了銷售額。

目前，越來越多的企業重視企業信息化管理，重視對海量的數據應用數據挖掘技術。經驗表明，應用Apriori算法的企業比起沒有應用該算法的企業，效益增值明顯加快。

4 結束語

Apriori算法作為數據挖掘的經典算法，已經被越來越多的企業使用。它在給企業帶來經濟效益的同時，也讓人們意識到算法自身的不足。廣大數據挖掘愛好者對Apriori算法不斷進行改進，以提高挖掘效率。實踐表明改進后的算法能明顯提高效率。隨著信息化的推進，相信Apriori算法的應用領域將逐步擴大。

參考文獻：

[1] 紀希禹.數據挖掘技術應用實例[M].北京:機械工業出版社，2009.

[2] Han Jiawei，Kamber M.數據挖掘概念與技術[M].2版.范明，孟小峰，譯.北京:機械工業出版社，2006.

[3] Tang J，MaccLennan.數據挖掘原理與應用：SQL Server 2005數據庫[M].鄺祝芳，焦賢龍，高升.北京:清華大學出版社.

[4] 萬南洋.數據倉庫事實表的建模理論與方法[J].計算機工程，2002(11).

[5] 黃進.關聯規則挖掘的Apriori算法的改進[J].電子科技大學學報，2003，32(1).

[6] 何宏.關聯規則挖掘算法的研究與實現[D].湘潭:湘潭大學，2006.

[7] 孟凡榮.煤礦安全檢測監控數據知識發現方法[M].徐州:中國礦業大學出版社，2007.