關(guān)聯(lián)規(guī)則Ａｐｒｉｏｒｉ算法實(shí)際應(yīng)用解析

摘要：數(shù)據(jù)挖掘能為決策者提供許多重要的、極有價(jià)值的信息或知識(shí)，從而產(chǎn)生不可估量的效益。文章通過(guò)實(shí)例論述了Apriori算法進(jìn)行數(shù)據(jù)挖掘應(yīng)用的價(jià)值。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

數(shù)據(jù)挖掘技術(shù)是人們長(zhǎng)期對(duì)數(shù)據(jù)庫(kù)技術(shù)進(jìn)行研究和開(kāi)發(fā)的結(jié)果。起初各種商業(yè)數(shù)據(jù)是存儲(chǔ)在計(jì)算機(jī)的數(shù)據(jù)庫(kù)中的，然后發(fā)展到可對(duì)數(shù)據(jù)庫(kù)進(jìn)行查詢(xún)和訪問(wèn)，進(jìn)而發(fā)展到對(duì)數(shù)據(jù)庫(kù)的即時(shí)遍歷。數(shù)據(jù)挖掘使數(shù)據(jù)庫(kù)技術(shù)進(jìn)入了一個(gè)更高級(jí)的階段，它不僅能對(duì)過(guò)去的數(shù)據(jù)進(jìn)行查詢(xún)和遍歷，并且能夠找出過(guò)去數(shù)據(jù)之間的潛在聯(lián)系，從而促進(jìn)信息的傳遞。

1 數(shù)據(jù)挖掘

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

2 數(shù)據(jù)挖掘的功能

數(shù)據(jù)挖掘通過(guò)預(yù)測(cè)未來(lái)趨勢(shì)及行為，做出前攝的、基于知識(shí)的決策。數(shù)據(jù)挖掘的目標(biāo)是從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)隱含的、有意義的知識(shí)，主要有以下五類(lèi)功能。

1)自動(dòng)預(yù)測(cè)趨勢(shì)和行為：數(shù)據(jù)挖掘自動(dòng)在大型數(shù)據(jù)庫(kù)中尋找預(yù)測(cè)性信息，以往需要進(jìn)行大量手工分析的問(wèn)題如今可以迅速直接由數(shù)據(jù)本身得出結(jié)論。

2)關(guān)聯(lián)分析：數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫(kù)中存在的一類(lèi)重要的可被發(fā)現(xiàn)的知識(shí)。若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就稱(chēng)為關(guān)聯(lián)。

3)聚類(lèi)：數(shù)據(jù)庫(kù)中的記錄可被化分為一系列有意義的子集，即聚類(lèi)。聚類(lèi)增強(qiáng)了人們對(duì)客觀現(xiàn)實(shí)的認(rèn)識(shí)，是概念描述和偏差分析的先決條件。

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

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

3 關(guān)聯(lián)規(guī)則

設(shè)I={i1， i2，…，im}是二進(jìn)制文字的集合，其中的元素稱(chēng)為項(xiàng)(item)。記D為交易(transaction)T的集合，這里交易T是項(xiàng)的集合，并且T?哿I 。對(duì)應(yīng)每一個(gè)交易有唯一的標(biāo)識(shí)，如交易號(hào)，記作TID。設(shè)X是一個(gè)I中項(xiàng)的集合，如果X?哿T，那么稱(chēng)交易T包含X。

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

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

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

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

給定一個(gè)交易集D，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是產(chǎn)生支持度和可信度分別大于用戶(hù)給定的最小支持度(minsupp)和最小可信度(minconf)的關(guān)聯(lián)規(guī)則。

4 Apriori算法應(yīng)用

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

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

1)連接步：為找Lk，通過(guò)Lk-1，與自己連接產(chǎn)生候選k-項(xiàng)集的集合。該候選項(xiàng)集的集合記作Ck。

設(shè)l1和l2是Lk-1中的項(xiàng)集。記號(hào)li[j]表示li的第j項(xiàng)(例如，li[k-2]表示li的倒數(shù)第3項(xiàng))。為方便計(jì)，假定事務(wù)或項(xiàng)集中的項(xiàng)按字典次序排序。執(zhí)行連接Lk-1 Lk-1，其中Lk-1的元素是可連接的，如果它們前(k-2)個(gè)項(xiàng)相同。即是，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])是簡(jiǎn)單地保證不產(chǎn)生重復(fù)。連接l1和l2產(chǎn)生的結(jié)果項(xiàng)集是l1[1]l1[2]… l1[k-1] l2[k-1]。

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

對(duì)于一大中型生產(chǎn)企業(yè)財(cái)務(wù)結(jié)算管理系統(tǒng)，為了了解同月產(chǎn)品的價(jià)格變化情況，用Apriori算法分析同時(shí)上漲的產(chǎn)品類(lèi)別。見(jiàn)表1的事務(wù)數(shù)據(jù)庫(kù)。

數(shù)據(jù)庫(kù)中有11個(gè)事務(wù)，即|D|=11。Apriori假定事務(wù)中的項(xiàng)按字典次序放。

用Apriori算法尋找D中的頻繁項(xiàng)集：

1)在算法的第一次迭代，每個(gè)項(xiàng)都是候選1—項(xiàng)集的集合C1的成員。算法簡(jiǎn)單地掃描所有的事務(wù)，對(duì)每個(gè)項(xiàng)的出現(xiàn)次數(shù)計(jì)數(shù)。

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

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

4)下一步，掃描D中事務(wù)，計(jì)算C2中每個(gè)候選項(xiàng)集的支持計(jì)數(shù)，如圖5.1的第二行的中間表所示。

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

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

7)掃描D中事務(wù)，對(duì)候選計(jì)數(shù)。

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

9)算法使用L3?滎?茳 L3產(chǎn)生候選4—項(xiàng)集的集合C4。盡管連接產(chǎn)生結(jié)果{{A，B，C，E}，{A，B，C，F(xiàn)}}，這個(gè)項(xiàng)集被剪去，因?yàn)樗淖蛹瘂B，C，E}，{A，C，F(xiàn)}不是頻繁的。這樣，C4=φ，因此算法終止，找出了所有的頻繁項(xiàng)集。

1)連接

C3=L2?滎?茳 L2={{A，B}，{A，C}，{A，E}，{B，C}，{B，D}，{B，E}，{B，F(xiàn)}，{C，E}，{C，F(xiàn)}}?滎?茳 {{A，B}，{A，C}，{A，E}，{B，C}，{B，D}，{B，E}，{B，F(xiàn)}，{C，E}，{C，F(xiàn)}}={{A，B，C}，{A，B，E}，{A，B，D}，{A，B，F(xiàn)}，{A，C，E}，{A，C，F(xiàn)}，{B，C，D}，{B，C，E}，{B，C，F(xiàn)}，{B，D，E}，{B，D，F(xiàn)}，{B，E，F(xiàn)}，{C，E，F(xiàn)}}。

2)使用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的。

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

在進(jìn)行關(guān)聯(lián)分析時(shí)，需要輸入兩個(gè)參數(shù)：

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

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

在本例中，設(shè)規(guī)則“產(chǎn)品x價(jià)格變動(dòng)同時(shí)產(chǎn)品y價(jià)格變動(dòng)”的置信度為c，支持度為s，則

通過(guò)關(guān)聯(lián)分析可以得出一個(gè)關(guān)于產(chǎn)品價(jià)格變動(dòng)的規(guī)則，以及每條規(guī)則的置信度c和支持度為s（見(jiàn)表2）。如表2的第一行，產(chǎn)品A價(jià)格變動(dòng)同時(shí)產(chǎn)品B價(jià)格也變動(dòng)，其置信度0.57，支持度為0.36。

這樣，通過(guò)關(guān)聯(lián)分析，可以得到以下分析結(jié)果：

1)有36%的時(shí)候，產(chǎn)品A價(jià)格變動(dòng)同時(shí)產(chǎn)品B價(jià)格也變動(dòng)，其置信度0.57。

2)有36%的時(shí)候，產(chǎn)品B價(jià)格變動(dòng)同時(shí)產(chǎn)品A價(jià)格也變動(dòng)，其置信度0.50。

3)有45%的時(shí)候，產(chǎn)品A價(jià)格變動(dòng)同時(shí)產(chǎn)品C價(jià)格也變動(dòng)，其置信度0.71。

4)有45%的時(shí)候，產(chǎn)品A價(jià)格變動(dòng)同時(shí)產(chǎn)品C價(jià)格也變動(dòng)，其置信度0.71。

5)有45%的時(shí)候，產(chǎn)品B價(jià)格變動(dòng)同時(shí)產(chǎn)品C價(jià)格也變動(dòng)，其置信度0.63。

6)有45%的時(shí)候，產(chǎn)品C價(jià)格變動(dòng)同時(shí)產(chǎn)品B價(jià)格也變動(dòng)，其置信度0.63。

5 結(jié)論

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

參考文獻(xiàn)：

[1] 朱國(guó)昱.數(shù)據(jù)倉(cāng)庫(kù)與企業(yè)信息門(mén)戶(hù)[N].計(jì)算機(jī)世界，2000(8).

[2] 全國(guó)經(jīng)濟(jì)專(zhuān)業(yè)技術(shù)資格考試用書(shū)編寫(xiě)委員會(huì).商業(yè)經(jīng)濟(jì)專(zhuān)業(yè)知識(shí)與實(shí)物[M].北京:經(jīng)濟(jì)管理出版社，2002:225-254.