第5章基于數(shù)據(jù)倉庫的決策支持系統(tǒng)4解析課件

第5章基于數(shù)據(jù)倉庫的決策支持系統(tǒng)

(4)15.5數(shù)據(jù)挖掘的決策支持5.5.3關聯(lián)規(guī)則的挖掘及其應用基本原理Apriori算法3.實例關聯(lián)規(guī)則（AssociationRule）挖掘是發(fā)現(xiàn)大量數(shù)據(jù)庫中項集之間的關聯(lián)關系。從大量商業(yè)事務中發(fā)現(xiàn)有趣的關聯(lián)關系，可以幫助許多商業(yè)決策的制定，如分類設計、交叉購物等。Agrawal等人于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關聯(lián)規(guī)則問題。

1．關聯(lián)規(guī)則的挖掘原理

關聯(lián)規(guī)則是發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品（項）之間的聯(lián)系，這些規(guī)則找出顧客購買行為模式。例1：在購買鐵錘的顧客當中，有70％的人同時購買了鐵釘。

例2：年齡在40歲以上，工作在A區(qū)的投保人當中，有45％的人曾經(jīng)向保險公司索賠過?？梢钥闯鰜?，A區(qū)可能污染比較嚴重，環(huán)境比較差，索賠率也相對比較高。（1）

基本原理設I={i1,i2,…,im}是項（Item）的集合。記D為事務（Transaction）的集合，事務T是項的集合，并且T

I。設A是I中一個項集，如果A

T，稱事務T包含A。定義1：關聯(lián)規(guī)則是形如A

B的蘊涵式，這里A

I，B

I，并且A

B=

。定義2：規(guī)則的支持度。規(guī)則A

B在數(shù)據(jù)庫D中具有支持度S，表示S是D中事務同時包含AB的百分比，它是概率P(AB)，即：

其中|D|表示事務數(shù)據(jù)庫D的個數(shù)，表示A、B兩個項集同時發(fā)生的事務個數(shù)。定義3：規(guī)則的可信度規(guī)則A

B具有可信度C，表示C是包含A項集的同時也包含B項集，相對于包含A項集的百分比，這是條件概率P(B|A)，即：

其中表示數(shù)據(jù)庫中包含項集A的事務個數(shù)。定義4：閾值。在事務數(shù)據(jù)庫中找出有用的關聯(lián)規(guī)則，需要由用戶確定兩個閾值：最小支持度（min_sup）和最小可信度（min_conf）。定義5：項的集合稱為項集（Itemset），包含k個項的項集稱之為k-項集。如果項集滿足最小支持度，則它稱之為頻繁項集（FrequentItemset）。定義6：關聯(lián)規(guī)則。同時滿足最小支持度（min_sup）和最小可信度（min_conf）的規(guī)則稱之為關聯(lián)規(guī)則，即成立時，規(guī)則稱之為關聯(lián)規(guī)則，也可以稱為強關聯(lián)規(guī)則。（2）關聯(lián)規(guī)則挖掘過程關聯(lián)規(guī)則的挖掘一般分為兩個過程：

1）找出所有的頻繁項集：找出支持度大于最小支持度的項集，即頻繁項集。

2）由頻繁項集產(chǎn)生關聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小可信度。（3）關聯(lián)規(guī)則的興趣度例子：討論不購買商品與購買商品的關系。設，交易集D，經(jīng)過對D的分析，得到表格:

買咖啡不買咖啡合計買牛奶20525不買牛奶70575合計9010100設定minsupp=0.2,minconf=0.6,得到如下的關聯(lián)規(guī)則：

買牛奶→買咖啡s=0.2c=0.8即80％的人買了牛奶就會買咖啡。同時得到結論：90％的人肯定會買咖啡。關聯(lián)規(guī)則：

買咖啡→不買牛奶s=0.7c=0.78支持度和可信度分別為0.7和0.78，更具有商業(yè)銷售的指導意義。定義7：興趣度：

公式反映了項集A與項集B的相關程度。若即表示項集A出現(xiàn)和項集B是相互獨立的。若表示A出現(xiàn)和B出現(xiàn)是負相關的。若表示A出現(xiàn)和B出現(xiàn)是正相關的。意味著A的出現(xiàn)蘊含B的出現(xiàn)。一條規(guī)則的興趣度越大于1說明我們對這條規(guī)則越感興趣（即其實際利用價值越大）；一條規(guī)則的興趣度越小于1說明我們對這條規(guī)則的反面規(guī)則越感興趣（即其反面規(guī)則的實際利用價值越大）；興趣度I不小于0。所有可能的關聯(lián)規(guī)則

RulesSCI1買牛奶→買咖啡0.20.80.892買咖啡→買牛奶0.20.220.893買牛奶→不買咖啡0.050.224不買咖啡→買牛奶0.050.525不買牛奶→買咖啡0.70.931.0376買咖啡→不買牛奶0.70.781.0377不買牛奶→不買咖啡0.050.0670.678不買咖啡→不買牛奶0.050.20.87討論I1﹑I2﹑I3﹑I6共4條規(guī)則：由于I1、I2<1，在實際中它的價值不大；I3、I6>1，規(guī)則才有價值。興趣度也稱為作用度（Lift）,表示關聯(lián)規(guī)則A→B的“提升”。如果作用度（興趣度）不大于1，則此關聯(lián)規(guī)則就沒有意義了。

概括地說：可信度是對關聯(lián)規(guī)則地準確度的衡量。支持度是對關聯(lián)規(guī)則重要性的衡量。支持度說明了這條規(guī)則在所有事務中有多大的代表性。有些關聯(lián)規(guī)則可信度雖然很高，但支持度卻很低，說明該關聯(lián)規(guī)則實用的機會很小，因此也不重要。興趣度（作用度）描述了項集A對項集B的影響力的大小。興趣度（作用度）越大，說明項集B受項集A的影響越大。

2.

Apriori算法Apriori是挖掘關聯(lián)規(guī)則的一個重要方法。算法分為兩個子問題：找到所有支持度大于最小支持度的項集（Itemset），這些項集稱為頻繁集（FrequentItemset）。使用第1步找到的頻繁集產(chǎn)生規(guī)則。Apriori使用一種稱作逐層搜索的迭代方法，“K-項集”用于探索“K+1-項集”。首先，找出頻繁“1-項集”的集合。該集合記作L1。L1用于找頻繁“2-項集”的集合L2，而L2用于找L3，如此下去，直到不能找到“K-項集”。找每個LK需要一次數(shù)據(jù)庫掃描。

1）Apriori性質性質：頻繁項集的所有非空子集都必須也是頻繁的。如果項集B不滿足最小支持度閾值min-sup，則B不是頻繁的，即P（B）<min-sup。如果項A添加到B，則結果項集（即BA）不可能比B更頻繁出現(xiàn)。因此，BA也不是頻繁的，即P（BA）<min-sup。設K-項集LK，K+1項集LK+1，產(chǎn)生LK+1的候選集CK+1。有公式：

CK+1=LKLK={XY，其中X，YLK，|XY|=K+1}其中C1是1-項集的集合，取自所有事務中的單項元素。

2）“K-項集”產(chǎn)生“K+1-項集”

如

L1={{A}，{B}} C2={A}{B}={A，B}，且|AB|=2 L2={{A，B}，{A，C}} C3={A，B}{A，C}={A，B，C}，|ABC|=33.實例事務ID事務的項目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C1)

在算法的第一次迭代，每個項都是候選1-項集的集合C1的成員。算法掃描所有的事務，對每個項的出現(xiàn)次數(shù)計數(shù)。見圖中第1列。2)

假定最小事務支持計數(shù)為2（即min-sup=2/9=22%），可以確定頻繁1-項集的集合L1。它由具有最小支持度的候選1-項集組成。見圖中第2列。3)

為發(fā)現(xiàn)頻繁2-項集的集合L2，算法使用L1*L1來產(chǎn)生候選集C2。見圖中第3列。4)

掃描D中事務，計算C2中每個候選項集的支持度計數(shù)，如圖中的第4列。5)

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

候選3-項集的集合C3的產(chǎn)生，得到候選集：C3={{A，B，C}，{A，B，E}，{A，C，E}，{B，C，D}，{B，C，E}，{B，D，E}}按Apriori性質，頻繁項集的所有子集必須是頻繁的。由于{A，D}，{C，D}，{C，E}，{D，E}不是頻繁項集，故C3中后4個候選不可能是頻繁的，在C3中刪除它們。見圖第6列。掃描D中事務，對C3中的候選項集計算支持度計數(shù)，見圖第7列。7)

確定L3，它由具有最小支持度的C3中候選3－項集組成，見圖第8列。8）按公式產(chǎn)生候選4－項集的集合C4，產(chǎn)生結果{A,B,C,E},這個項集被剪去，因為它的子集｛B,C,E｝不是頻繁的。這樣L4=Ф。此算法終止。L3是最大的頻繁項集，即：｛A,B,C｝和｛A,B,E｝。具體產(chǎn)生過程用圖表示

候選集與頻繁項集的產(chǎn)生

項集支持度計數(shù)A,B 4 A,C 4 A,E 2 B,C 4 B,D 2 B,E 2 項集A,B，C A,B，E C3候選集L2頻繁2-項集計算支持度項集支持度計數(shù)

A,B,C 2 A,B,E 2 項集支持度計數(shù) A,B,C 2 A,B,E 2 C3候選集L3頻繁3-項集產(chǎn)生關聯(lián)規(guī)則根據(jù)前面提到的可信度的定義，關聯(lián)規(guī)則的產(chǎn)生如下：（1）對于每個頻繁項集L，產(chǎn)生L的所有非空子集；（2）對于L的每個非空子集S，如果則輸出規(guī)則“S→L－S”。注：L－S表示在項集L中除去S子集的項集。頻繁項集L={A，B，E}，可以由L產(chǎn)生哪些關聯(lián)規(guī)則？L的非空子集S有：{A,B},{A,E},{B,E},{A},{B},{E}?？傻玫疥P聯(lián)規(guī)則如下：A∧B→Econf=2/4=50%A∧E→Bconf=2/2=100%B∧E→Aconf=2/2==100%A