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

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

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

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

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

例2：年齡在40歲以上，工作在A區(qū)的投保人當(dāng)中，有45％的人曾經(jīng)向保險(xiǎn)公司索賠過。可以看出來，A區(qū)可能污染比較嚴(yán)重，環(huán)境比較差，索賠率也相對(duì)比較高。（1）

基本原理設(shè)I={i1,i2,…,im}是項(xiàng)（Item）的集合。記D為事務(wù)（Transaction）的集合，事務(wù)T是項(xiàng)的集合，并且T

I。設(shè)A是I中一個(gè)項(xiàng)集，如果A

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

B的蘊(yùn)涵式，這里A

I，B

I，并且A

B=

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

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

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

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

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

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

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

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

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

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

公式反映了項(xiàng)集A與項(xiàng)集B的相關(guān)程度。若即表示項(xiàng)集A出現(xiàn)和項(xiàng)集B是相互獨(dú)立的。若表示A出現(xiàn)和B出現(xiàn)是負(fù)相關(guān)的。若表示A出現(xiàn)和B出現(xiàn)是正相關(guān)的。意味著A的出現(xiàn)蘊(yùn)含B的出現(xiàn)。一條規(guī)則的興趣度越大于1說明我們對(duì)這條規(guī)則越感興趣（即其實(shí)際利用價(jià)值越大）；一條規(guī)則的興趣度越小于1說明我們對(duì)這條規(guī)則的反面規(guī)則越感興趣（即其反面規(guī)則的實(shí)際利用價(jià)值越大）；興趣度I不小于0。所有可能的關(guān)聯(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，在實(shí)際中它的價(jià)值不大；I3、I6>1，規(guī)則才有價(jià)值。興趣度也稱為作用度（Lift）,表示關(guān)聯(lián)規(guī)則A→B的“提升”。如果作用度（興趣度）不大于1，則此關(guān)聯(lián)規(guī)則就沒有意義了。

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

2.

Apriori算法Apriori是挖掘關(guān)聯(lián)規(guī)則的一個(gè)重要方法。算法分為兩個(gè)子問題：找到所有支持度大于最小支持度的項(xiàng)集（Itemset），這些項(xiàng)集稱為頻繁集（FrequentItemset）。使用第1步找到的頻繁集產(chǎn)生規(guī)則。Apriori使用一種稱作逐層搜索的迭代方法，“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ù)掃描。

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

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

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

如

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.實(shí)例事務(wù)ID事務(wù)的項(xiàng)目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C1)

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

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

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

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

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

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

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

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

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

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