(精品)關聯規則Association20120313.ppt

《(精品)關聯規則Association20120313.ppt》由会员分享，可在线阅读，更多相关《(精品)關聯規則Association20120313.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Data Mining 方法論方法論:Association Rules 指導教授：指導教授：曾淑峰教授曾淑峰教授報告者報告者 ：游宗憲：游宗憲日日 期：期：2012/03/132012/03/13資管技術研究報告資管技術研究報告LOGO簡報大綱v關連式分析基本概念關連式分析基本概念vApriori 關規則演算法關規則演算法及案例說明及案例說明vFP-growth 演算法演算法及案例說明及案例說明v應用應用LOGO參考資料v曾淑峰曾淑峰SAS Enterprise Miner 應用應用手冊手冊vJiawei Han and Michelline Kamber(2006),“Data minin

2、g Concepts and Techniques,2nd ed”Morgan Kaufmann Publications.v某大旅行業務公司某大旅行業務公司2008、2009、2010 交資料交資料LOGO關連式分析基本概念關連式分析基本概念-1-1v關規則之定義關規則之定義:最早是由學者最早是由學者Agrawal,Imielinski及及Swami在在1993所提出，主要用於找尋資中所提出，主要用於找尋資中項目及屬性項目及屬性之間的關係，或某些之間的關係，或某些隱藏於資間隱藏於資間的的關關，用關規則分析出重要的資訊，因此常被用探勘同商品間銷售關，用關規則分析出重要的資訊，因此常被用探勘同商

3、品間銷售關係或顧客的消費習慣係或顧客的消費習慣v令令 I=i,i,.,im :items的集合的集合vD=T1,T2,.,Tk(D為所有交紀為所有交紀T的集合的集合),T I,T是是I的子集合的子集合v關規則的形式可以表示為關規則的形式可以表示為A=B;A I,B I 且且 AB=(空集合空集合)vSupport(A=B)=P(A B):交易中同時包含交易中同時包含A,B 聯集的百分比聯集的百分比 公式為公式為:包含包含A與與B的交易紀錄的交易紀錄/總交易次數總交易次數vConfidence(A=B)=P(B|A):交易中同時包含交易中同時包含A必定包含必定包含B之百分比之百分比 公式為公式為

4、:包含包含A與與B的交易紀錄的交易紀錄/包含包含A的交易紀錄的交易紀錄vitemset:一個一個items 之集合之集合vK-itemset:包括包括K個個items 的的itemsetLOGO關連式分析基本概念關連式分析基本概念-2-2v挖掘關聯規則中我們可以把它分成兩個次問題挖掘關聯規則中我們可以把它分成兩個次問題:一一.是從資料庫中找出所有滿足是從資料庫中找出所有滿足最小支持度最小支持度(Support)的的高頻項目集合高頻項目集合(large itemset)；二二.是從這些高頻項目集合中找出符合是從這些高頻項目集合中找出符合最小信賴度最小信賴度(Confidence)的關的關聯規則。

5、有項目限制的關規則探勘聯規則。有項目限制的關規則探勘v舉，假設在資庫中總共有舉，假設在資庫中總共有50,000 筆交記，其中有筆交記，其中有30,000 筆購買筆購買牛奶牛奶的交記，有的交記，有3,5000 筆購買筆購買麵包麵包的交記，的交記，且有且有20,000 筆同時購買筆同時購買牛奶和麵包牛奶和麵包的交記，則可以找出一個關的交記，則可以找出一個關規則：牛奶規則：牛奶=麵包麵包40%,66.7%。其支持和信心計算方法如下：其支持和信心計算方法如下：支持度支持度=P(牛奶牛奶 麵包麵包)=同時購買同時購買牛奶和麵包牛奶和麵包之百分比之百分比 =20000/50000=40%信心度信心度=P(

6、牛奶牛奶|麵包麵包)=同時購買同時購買牛奶和麵包牛奶和麵包之筆數之筆數/購買購買牛奶牛奶之筆之筆 數數=20000/30000=66.7%LOGO關連式分析基本概念關連式分析基本概念-3-3v有項目限制的關規則探勘（有項目限制的關規則探勘（Mining association rule with item constraint）根據使用者所指定的項目，找出與此項目相關的）根據使用者所指定的項目，找出與此項目相關的關規則關規則 C=AB就是一種符合限制的結果，且就是一種符合限制的結果，且AB=C 也是一種符合限制的結也是一種符合限制的結果果v發掘交內發掘交內(intra-transaction)

7、的關規則的關規則v交間交間(inter-transaction)的關規則的關規則 LOGOApriori 關規則演算法關規則演算法-1-1vThe Apriori principle:All nonempty subsets of a frequent itemset must also be frequentvJoin Step:Ck is generated by joining Lk-1with itself Ck 為為k-itemset 之之Candidate Lk-1為符合為符合minimum support 之之(k-1)-itemsetvPrune Step:Any(k-1)-i

8、temset that is not frequent cannot be a subset of a frequent k-itemsetLOGO找出所有的頻繁項目集合併Join Step掃瞄資料庫以計算各候選項目集之支持度產生候選項目集Ck修剪Prune Step分析出有意義的關聯法則假設先組好第一個 ItamsetsApriori 關規則演算法關規則演算法-2-2LOGOApriori 關規則演算法關規則演算法-範例範例產生產生Frequent ItemsetsFrequent ItemsetsDatabase DTIDList of item IDs1001,2,52002,43002

9、,34001,2,45001,36002,37001,38001,2,3,59001,2,3C1Scan DItemset Sup.1627364252ItemsetSup1627364252L1CompareLOGOApriori 關規則演算法關規則演算法-範例範例產生產生Frequent ItemsetsFrequent ItemsetsItemsetSup.1,241,341,411,522,342,422,523,403,514,50Scan DItemsetSup.1,241,341,522,342,422,52C2L2Itemset1,2,31,2,5Prune Step:1,4次

10、數=13,4次數=03,5次數=14,5次數=0故1,2,4,2,3,4,2,3,5不在C3C3ItemsetSup.count1,2,3 21,2,5 2L3Scan DItemset1,21,31,41,52,32,42,53,43,54,5C2ItemsetSup.1,2,3 21,2,5 2C3LOGOApriori 關規則演算法關規則演算法-範例範例產生產生Association RulesAssociation RulesAssociation rulesConfidenceConfidence=2/4=50%Confidence=2/2=100%Confidence=2/2=10

11、0%Confidence=2/6=33.3%Confidence=2/7=29%Confidence=2/2=100%LOGOApriori Performance BottlenecksvApriori algorithm:利用 frequent(k 1)-itemsets 產生candidate frequent k-itemsets利用 database scan 和 pattern matching 來產出 candidate itemsets 之次數vThe bottleneck of Apriori:candidate generation大量candidate sets:104

12、frequent 1-itemset will generate 107 candidate 2-itemsetsTo discover a frequent pattern of size 100,e.g.,a1,a2,a100,one needs to generate 2100 1030 candidates.多次 scans of database:Needs(n+1)scans,n is the length of the longest patternLOGOFP-growth 演算法演算法v有三個原因使得 FP-Tree 的績效能大幅領先原有的演算法：v（一）它把原資料庫的所有資

13、訊巧妙的儲存在樹狀結構與指標鏈結串列中；v（二）它設計了一個有效率的方法將關聯規則從資料結構中粹取出來；v（三）它只需掃描資料庫兩次。LOGOFP-growth 演算法演算法LOGOFP-growth 演算法演算法TIDList of item IDs1001,2,52002,43002,34001,2,45001,36002,37001,38001,2,3,59001,2,3Scan DItem IDSup.Node-link27163642522:71:45:14:13:24:15:13:2null1:23:2itemConditional Pattern BaseConditional

14、FP-treeFrequent Patterns Generated52,1:1,2,1,3:12,5:2,1,5:2,2,1,5:242,1:1,2:12,4:232,1:2,2:2,1:22,3:4,1,3:4,2,1,3:212:42,1:424142:41:21:2LOGO應用應用v探討某大旅行業務公司在所有網路交易之情況下網路交易、總價、區域之關聯性vSupport(總價=網路交易)vSupport(區域=網路交易)vSupport(總價 區域=網路交易)LOGO應用應用-1vSupport(總價=網路交易):包含包含總價與與網路交易的交易紀錄的交易紀錄/網路交易1357911 13

15、 15 17 19 21 23 25 27 29 31 33 35 37 39 410.000000%2.000000%4.000000%6.000000%8.000000%10.000000%12.000000%14.000000%LOGO應用應用-2vSupport(區域=網路交易):包含包含區域與與網路交易的交易紀錄的交易紀錄/網路交易A-01A-03A-05A-07B-02C-01C-03D-02D-04D-06E-02E-04F-02G-01G-03G-05G-07H-01I-01I-03J-02K-02L-01M-01N-010.000000%2.000000%4.000000%6

16、.000000%8.000000%10.000000%12.000000%14.000000%16.000000%18.000000%20.000000%LOGO應用應用-3vSupport(總價 區域=網路交易):包含包含總價、區域與與網路交易的交易紀錄的交易紀錄/網路交易3.5000%3.0000%2.5000%2.0000%1.5000%1.0000%0.5000%0.0000%A-01A-02A-03A-04A-05A-06A-07B-01B-02B-03C-01C-02C-03D-02D-03D-04D-05D-06E-01E-02E-04F-01F-02G-01G-02G-03G-

17、04G-05G-06G-07G-08H-01H-02I-01I-03J-01J-02K-01K-02L-01L-02Series1Series2Series3Series4Series5Series6Series7Series8Series9Series10Series11Series12Series13Series14Series15Series16Series17Series18LOGO應用應用-結論結論v1.取取min Confidence=4%網路交易總價小網路交易總價小 於於 11萬元以下萬元以下 2.取取min Confidence=4%網路網路交易之區域交易之區域 為為A-01、A-02、A-03、B-01、C-01、E-02、H-01、L-01 3.取取min Confidence=4%網路交易網路交易之總價之總價 約約2萬元區域為萬元區域為A-02、B-01、C-01 4.總價金額會是影響網路交易之因素總價金額會是影響網路交易之因素 5.限於資料之因素，可再分析限於資料之因素，可再分析A-02、B-01、C-01之共同關聯性，可依此資訊推論消費者使之共同關聯性，可依此資訊推論消費者使 用網路交易之因素用網路交易之因素報告完畢敬請指教LOGOApriori 關規則演算法關規則演算法-2-2以Apriori 演算法建構季節流行病關係模型