關聯規(guī)則Ａｐｒｉｏｒｉ算法實際應用解析

摘要：數據挖掘能為決策者提供許多重要的、極有價值的信息或知識，從而產生不可估量的效益。文章通過實例論述了Apriori算法進行數據挖掘應用的價值。

關鍵詞：數據挖掘；關聯規(guī)則；Apriori算法

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)23-862-03

The Discourse and Application about Association and Apriori Arithmetic

XU Lei

(Liaoning University International Business and Economics，Dalian 116052，China)

Abstract: Data Mining can provide many valuable information and knowledge for decision maker， thereby producing the enormous benefit. This paper introduced the great value of Apriori Arithmetic on Data Mining.

Key words: Data Mining; Association; Apriori Arithmetic

數據挖掘技術是人們長期對數據庫技術進行研究和開發(fā)的結果。起初各種商業(yè)數據是存儲在計算機的數據庫中的，然后發(fā)展到可對數據庫進行查詢和訪問，進而發(fā)展到對數據庫的即時遍歷。數據挖掘使數據庫技術進入了一個更高級的階段，它不僅能對過去的數據進行查詢和遍歷，并且能夠找出過去數據之間的潛在聯系，從而促進信息的傳遞。

1 數據挖掘

數據挖掘（Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。

2 數據挖掘的功能

數據挖掘通過預測未來趨勢及行為，做出前攝的、基于知識的決策。數據挖掘的目標是從數據庫中發(fā)現隱含的、有意義的知識，主要有以下五類功能。

1)自動預測趨勢和行為：數據挖掘自動在大型數據庫中尋找預測性信息，以往需要進行大量手工分析的問題如今可以迅速直接由數據本身得出結論。

2)關聯分析：數據關聯是數據庫中存在的一類重要的可被發(fā)現的知識。若兩個或多個變量的取值之間存在某種規(guī)律性，就稱為關聯。

3)聚類：數據庫中的記錄可被化分為一系列有意義的子集，即聚類。聚類增強了人們對客觀現實的認識，是概念描述和偏差分析的先決條件。

4)概念描述：概念描述就是對某類對象的內涵進行描述，并概括這類對象的有關特征。概念描述分為特征性描述和區(qū)別性描述，前者描述某類對象的共同特征，后者描述不同類對象之間的區(qū)別。

5)偏差檢測：數據庫中的數據常有一些異常記錄，從數據庫中檢測這些偏差很有意義。偏差檢測的基本方法是，尋找觀測結果與參照值之間有意義的差別。

3 關聯規(guī)則

設I={i1， i2，…，im}是二進制文字的集合，其中的元素稱為項(item)。記D為交易(transaction)T的集合，這里交易T是項的集合，并且T?哿I 。對應每一個交易有唯一的標識，如交易號，記作TID。設X是一個I中項的集合，如果X?哿T，那么稱交易T包含X。

一個關聯規(guī)則是形如X?圯Y的蘊涵式，這里X?奐I， Y?奐I，并且X∩Y=Φ。規(guī)則XTY在交易數據庫D中的支持度(support)是交易集中包含X和Y的交易數與所有交易數之比，記為support(X?圯Y)，即

support(X?圯Y)=|{T:X∪Y?哿T，T∈D}|/|D|

規(guī)則X?圯Y在交易集中的可信度（confidence）是指包含X和Y的交易數與包含X的交易數之比，記為confidence(X?圯Y)，即

confidence(X?圯Y)=|{T: X∪Y?哿T，T∈D}|/|{T:X?哿T，T∈D}|

給定一個交易集D，挖掘關聯規(guī)則問題就是產生支持度和可信度分別大于用戶給定的最小支持度(minsupp)和最小可信度(minconf)的關聯規(guī)則。

4 Apriori算法應用

Apriori算法是一種最有影響的挖掘布爾關聯規(guī)則頻繁項集的算法。算法的名字基于這樣的事實：算法使用頻繁項集性質的先驗知識，正如我們將看到的。Apriori使用一種稱作逐層搜索的迭代方法，k-項集用于探索(k+1)-項集。首先，找出頻繁1-項集的集合。該集合記作L1。L1用于找頻繁2-項集的集合L2，而L2用于找L3，如此下去，直到不能找到頻繁k-項集。找每個Lk：需要一次數據庫掃描。

將Apriori性質用于算法，我們必須使用兩步過程：連接和剪枝。

1)連接步：為找Lk，通過Lk-1，與自己連接產生候選k-項集的集合。該候選項集的集合記作Ck。

設l1和l2是Lk-1中的項集。記號li[j]表示li的第j項(例如，li[k-2]表示li的倒數第3項)。為方便計，假定事務或項集中的項按字典次序排序。執(zhí)行連接Lk-1 Lk-1，其中Lk-1的元素是可連接的，如果它們前(k-2)個項相同。即是，Lk-1的元素和l1和l2是可連接的，如果(l1[1]= l2[1])∧(l1[2]= l2[2]) ∧…∧(l1[k-2]= l2[k-2]) ∧(l1[k-1]= l2[k-1])。條件(l1[k-1]= l2[k-1])是簡單地保證不產生重復。連接l1和l2產生的結果項集是l1[1]l1[2]… l1[k-1] l2[k-1]。

2)剪枝步：Ck是Lk的超集；即是，它的成員可以是也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數據庫，確定Ck中每個候選的計數，從而確定Lk(即根據定義，計數值不小于最小支持度計數的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質：任何非頻繁的(k-1)-項集都不可能是頻繁k-項集的子集。因此，如果一個候選k-項集的(k-1)-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。

對于一大中型生產企業(yè)財務結算管理系統(tǒng)，為了了解同月產品的價格變化情況，用Apriori算法分析同時上漲的產品類別。見表1的事務數據庫。

數據庫中有11個事務，即|D|=11。Apriori假定事務中的項按字典次序放。

用Apriori算法尋找D中的頻繁項集：

1)在算法的第一次迭代，每個項都是候選1—項集的集合C1的成員。算法簡單地掃描所有的事務，對每個項的出現次數計數。

2)假定最小事務支持計數為2(即min_sup=2/9=22％)。可以確定頻繁1—項集的集合L1。它由具有最小支持度的候選1-項集組成。

3)為發(fā)現頻繁2-項集的集合L2，算法使用L1?滎?茳 L1產生候選2-項集的集合C2。C2由CL12個2-項集組成。

4)下一步，掃描D中事務，計算C2中每個候選項集的支持計數，如圖5.1的第二行的中間表所示。

5)確定頻繁2-項集的集合L2，它由具有最小支持度的C2中的候選2—項集組成。

6)首先，令C3= L2?滎?茳 L2，根據Apriori性質，頻繁項集的所有子集必須是頻繁的，我們將不可能是頻繁的候選由C3刪除得到C3= L2 ?滎?茳 L2={{A，B，C}，{A，B，E}，{A，C，E}，{B，C，E}，{B，C，F}}。這樣，在此后掃描D確定L3時就不必再求它們的計數值。注意，Apriori算法使用逐層搜索技術，給定k-項集，我們只需要檢查它們的(k-1)-子集是否頻繁。

7)掃描D中事務，對候選計數。

8) 確定L3，它由具有最小支持度的C3中的候選3—項集組成。

9)算法使用L3?滎?茳 L3產生候選4—項集的集合C4。盡管連接產生結果{{A，B，C，E}，{A，B，C，F}}，這個項集被剪去，因為它的子集{B，C，E}，{A，C，F}不是頻繁的。這樣，C4=φ，因此算法終止，找出了所有的頻繁項集。

1)連接

C3=L2?滎?茳 L2={{A，B}，{A，C}，{A，E}，{B，C}，{B，D}，{B，E}，{B，F}，{C，E}，{C，F}}?滎?茳 {{A，B}，{A，C}，{A，E}，{B，C}，{B，D}，{B，E}，{B，F}，{C，E}，{C，F}}={{A，B，C}，{A，B，E}，{A，B，D}，{A，B，F}，{A，C，E}，{A，C，F}，{B，C，D}，{B，C，E}，{B，C，F}，{B，D，E}，{B，D，F}，{B，E，F}，{C，E，F}}。

2)使用Apriori性質剪枝：頻繁項集的所有子集必須是頻繁的。

3)這樣，剪枝后C3={{A，B，C}，{A，B，E}，{A，C，E}，{B，C，E}，{B，C，F}}。

在進行關聯分析時，需要輸入兩個參數：

a)最小置信度（Confidence），以過濾可能性過小的規(guī)則。本例中，設最小置信度為0.5。

b)最小支持度（Support），以表示這種規(guī)則發(fā)生的概率，即可信度。本例中，設最小支持度0.3。

在本例中，設規(guī)則“產品x價格變動同時產品y價格變動”的置信度為c，支持度為s，則

通過關聯分析可以得出一個關于產品價格變動的規(guī)則，以及每條規(guī)則的置信度c和支持度為s（見表2）。如表2的第一行，產品A價格變動同時產品B價格也變動，其置信度0.57，支持度為0.36。

這樣，通過關聯分析，可以得到以下分析結果：

1)有36%的時候，產品A價格變動同時產品B價格也變動，其置信度0.57。

2)有36%的時候，產品B價格變動同時產品A價格也變動，其置信度0.50。

3)有45%的時候，產品A價格變動同時產品C價格也變動，其置信度0.71。

4)有45%的時候，產品A價格變動同時產品C價格也變動，其置信度0.71。

5)有45%的時候，產品B價格變動同時產品C價格也變動，其置信度0.63。

6)有45%的時候，產品C價格變動同時產品B價格也變動，其置信度0.63。

5 結論

企業(yè)管理者可以根據分析結果適時在某一產品x價格變動時找到與其相關的產品y，如果產品x價格上漲，則加大產品y的生產與銷售。如果產品x價格下浮，則壓縮產品y的生產與銷售。企業(yè)決策者、管理者可免去許多以前用于討論、分析產品銷售情況的時間和精力，并有效的排除一些人為因素的干擾，在最短的時間內做出正確的分析和決定，從而產生不可估量的效益。

參考文獻：

[1] 朱國昱.數據倉庫與企業(yè)信息門戶[N].計算機世界，2000(8).

[2] 全國經濟專業(yè)技術資格考試用書編寫委員會.商業(yè)經濟專業(yè)知識與實物[M].北京:經濟管理出版社，2002:225-254.