3 頻繁模式關聯挖掘 - 浙江大學計算機科學與技術學院

1、第3課 頻繁模式及關聯規(guī)則挖掘技術,徐從富，副教授 浙江大學人工智能研究所,浙江大學本科生《數據挖掘導論》課件,內容提綱,關聯規(guī)則挖掘簡介關聯規(guī)則基本模型關聯規(guī)則價值衡量與發(fā)展參考文獻,關聯規(guī)則簡介,關聯規(guī)則反映一個事物與其他事物之間的相互依存性和關聯性。如果兩個或者多個事物之間存在一定的關聯關系，那么，其中一個事物就能夠通過其他事物預測到。 典型的關聯規(guī)則發(fā)現問題是對超市中的貨籃數據（Market Basket）進行分析。通

2、過發(fā)現顧客放入貨籃中的不同商品之間的關系來分析顧客的購買習慣。,什么是關聯規(guī)則挖掘,關聯規(guī)則挖掘 首先被Agrawal, Imielinski and Swami在1993年的SIGMOD會議上提出在事務、關系數據庫中的項集和對象中發(fā)現頻繁模式、關聯規(guī)則、相關性或者因果結構頻繁模式: 數據庫中頻繁出現的項集 目的: 發(fā)現數據中的規(guī)律超市數據中的什么產品會一起購買？— 啤酒和尿布在買了一臺PC之后下一步會購買?哪種DNA對這

3、種藥物敏感?我們如何自動對Web文檔進行分類?,頻繁模式挖掘的重要性,許多重要數據挖掘任務的基礎關聯、相關性、因果性序列模式、空間模式、時間模式、多維關聯分類、聚類分析更加廣泛的用處購物籃分析、交叉銷售、直銷點擊流分析、DNA序列分析等等,關聯規(guī)則基本模型,關聯規(guī)則基本模型Apriori算法Fp-Tree算法,關聯規(guī)則基本模型,IBM公司Almaden研究中心的R.Agrawal首先提出關聯規(guī)則模型，并給出求解算法AI

4、S。隨后又出現了SETM和Apriori等算法。其中，Apriori是關聯規(guī)則模型中的經典算法。 給定一組事務產生所有的關聯規(guī)則滿足最小支持度和最小可信度,關聯規(guī)則基本模型（續(xù)）,設I={i1, i2,…, im}為所有項目的集合，D為事務數據庫，事務T是一個項目子集（T?I）。每一個事務具有唯一的事務標識TID。設A是一個由項目構成的集合，稱為項集。事務T包含項集A，當且僅當A?T。如果項集A中包含k個項目，則稱其為k項集。項集

5、A在事務數據庫D中出現的次數占D中總事務的百分比叫做項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。,關聯規(guī)則基本模型（續(xù)）,關聯規(guī)則是形如X?Y的邏輯蘊含式，其中X?I，Y?I，且X?Y=?。如果事務數據庫D中有s%的事務包含X?Y，則稱關聯規(guī)則X?Y的支持度為s%，實際上，支持度是一個概率值。若項集X的支持度記為support (X)，規(guī)則的信任度為support (X?Y)／suppo

6、rt (X)。這是一個條件概率P (Y | X)。 也就是： support (X?Y)=P (X ?Y) confidence (X?Y)=P (Y | X),規(guī)則度量：支持度與可信度,查找所有的規(guī)則 X & Y ? Z 具有最小支持度和可信度支持度, s, 一次交易中包含{X 、 Y 、 Z}的可能性可信度, c, 包含{X 、 Y}的交易中也包含Z的條件概率,設最小支持度為50%, 最小可信度為 50%,

7、則可得到A ? C (50%, 66.6%)C ? A (50%, 100%),,,,,,買尿布的客戶,二者都買的客戶,買啤酒的客戶,,關聯規(guī)則基本模型（續(xù)）,關聯規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。 發(fā)現關聯規(guī)則需要經歷如下兩個步驟： 找出所有頻繁項集。 由頻繁項集生成滿足最小信任度閾值的規(guī)則。,Let min_support = 50%, min_conf = 50%:A ? C (50

8、%, 66.7%)C ? A (50%, 100%),For rule A ? C:support = support({A}?{C}) = 50%confidence = support({A}?{C})/support({A}) = 66.6%,Min. support 50%Min. confidence 50%,Apriori算法的步驟,Apriori算法命名源于算法使用了頻繁項集性質的先驗（Prior）知識。 Ap

9、riori算法將發(fā)現關聯規(guī)則的過程分為兩個步驟：通過迭代，檢索出事務數據庫中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集；利用頻繁項集構造出滿足用戶最小信任度的規(guī)則。挖掘或識別出所有頻繁項集是該算法的核心，占整個計算量的大部分。,頻繁項集,為了避免計算所有項集的支持度（實際上頻繁項集只占很少一部分），Apriori算法引入潛在頻繁項集的概念。若潛在頻繁k項集的集合記為Ck ，頻繁k項集的集合記為Lk ，m個項目構成的k項集的

10、集合為 ，則三者之間滿足關系Lk ?Ck ? 。構成潛在頻繁項集所遵循的原則是“頻繁項集的子集必為頻繁項集”。,,,關聯規(guī)則的性質：,性質1：頻繁項集的子集必為頻繁項集。 性質2：非頻繁項集的超集一定是非頻繁的。 Apriori算法運用性質1，通過已知的頻繁項集構成長度更大的項集，并將其稱為潛在頻繁項集。潛在頻繁k項集的集合Ck 是指由有可能成為頻繁k項集的項集組成的集合。以后只需計算潛在頻繁項集的支持度，而不必計算所有

11、不同項集的支持度，因此在一定程度上減少了計算量。,Apriori算法,(1) L1={頻繁1項集}; (2) for(k=2;Lk-1??;k++) do begin (3) Ck=apriori_gen(Lk-1); //新的潛在頻繁項集 (4) for all transactions t?D do begin (5) Ct=subset(Ck,t); //t中包含的潛在頻繁項集 (6) f

12、or all candidates c?Ct do (7) c.count++; (8) end; (9) Lk={c?Ck|c.count?minsup} (10) end; (11) Answer=,,實例,Database TDB,1st scan,,C1,L1,L2,C2,C2,,2nd scan,,,C3,L3,3rd scan,,,,Visualization of Association

13、Rules: Pane Graph,Visualization of Association Rules: Rule Graph,提高Apriori算法的方法,Hash-based itemset counting（散列項集計數）Transaction reduction（事務壓縮）Partitioning（劃分）Sampling（采樣）,關聯規(guī)則挖掘算法,Agrawal等人提出的AIS，Apriori和AprioriTidCu

14、mulate和Stratify，Houstsma等人提出的SETMPark等人提出的DHPSavasere等人的PARTITIONHan等人提出的不生成候選集直接生成頻繁模式FPGrowth其中最有效和有影響的算法為Apriori，DHP和PARTITION，FPGrowth。,用Frequent-Pattern tree (FP-tree) 結構壓縮數據庫, 高度濃縮，同時對頻繁集的挖掘又完備的避免代價較高的數據庫掃描

15、開發(fā)一種高效的基于FP-tree的頻繁集挖掘算法采用分而治之的方法學：分解數據挖掘任務為小任務避免生成關聯規(guī)則: 只使用部分數據庫!,挖掘頻繁集 不用生成候選集,最小支持度 = 0.5,TIDItems bought (ordered) frequent items100{f, a, c, d, g, i, m, p}{f, c, a, m, p}200{a, b, c, f, l, m, o}{f, c,

16、 a, b, m}300 {b, f, h, j, o}{f, b}400 {b, c, k, s, p}{c, b, p}500 {a, f, c, e, l, p, m, n}{f, c, a, m, p},步驟:掃描數據庫一次，得到頻繁1-項集把項按支持度遞減排序再一次掃描數據庫，建立FP-tree,建立 FP-tree樹,完備: 不會打破交易中的任何模式包含了頻繁模式挖掘所需的全部信息緊密

17、去除不相關信息—不包含非頻繁項支持度降序排列: 支持度高的項在FP-tree中共享的機會也高決不會比原數據庫大（如果不計算樹節(jié)點的額外開銷),FP-tree 結構的好處,基本思想 (分而治之)用FP-tree遞歸增長頻繁集方法 對每個項，生成它的 條件模式庫, 然后是它的 條件 FP-tree對每個新生成的條件FP-tree，重復這個步驟直到結果FP-tree為空, 或只含唯一的一個路徑 (此路徑的每個子路徑對應的項集都

18、是頻繁集),用FP-tree挖掘頻繁集,為FP-tree中的每個節(jié)點生成條件模式庫用條件模式庫構造對應的條件FP-tree遞歸構造條件 FP-trees 同時增長其包含的頻繁集如果條件FP-tree只包含一個路徑，則直接生成所包含的頻繁集。如果條件FP-tree包含多個路徑，則采用混合的方法,挖掘 FP-tree的主要步驟,從FP-tree的頭表開始按照每個頻繁項的連接遍歷 FP-tree列出能夠到達此項的所有前綴路徑，得到

19、條件模式庫,條件模式庫itemcond. pattern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1,步驟1: 從 FP-tree 到條件模式庫,Node-link propertyFor any frequent item ai, all the possible patterns containing only frequent item

20、s and ai can be obtained by following ai’s node-links, starting from ai’s head in the fp-tree header.Prefix path propertyTo calculate the frequent patterns with suffix ai, only the prefix subpathes of nodes labeled ai

21、in the FP-tree need to be accumulated, and the frequency count of every node in the prefix path should carry the same count as that in the corresponding node ai in the path.,FP-tree支持條件模式庫構造的屬性,對每個模式庫計算庫中每個項的支持度用模式庫中的頻

22、繁項建立FP-tree,m-條件模式庫:fca:2, fcab:1,All frequent patterns concerning mm, fm, cm, am, fcm, fam, cam, fcam,?,?,{},f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,頭表Item frequency head f4c4a3b3m3p3,,,,,,,,,,,

23、,步驟2: 建立條件 FP-tree,通過建立條件模式庫得到頻繁集,“am”的條件模式庫: (fc:3),“cm”的條件模式: (f:3),{},f:3,cm-條件 FP-tree,“cam”條件模式庫: (f:3),{},f:3,cam-條件 FP-tree,遞歸挖掘條件FP-tree,關聯規(guī)則價值衡量與發(fā)展,關聯規(guī)則價值衡量關聯規(guī)則最新進展,規(guī)則價值衡量,對關聯規(guī)則的評價與價值衡量涉及兩個層面：系統(tǒng)客觀的層面用戶主觀的層面,系

24、統(tǒng)客觀層面,使用“支持度和信任度”框架可能會產生一些不正確的規(guī)則。只憑支持度和信任度閾值未必總能找出符合實際的規(guī)則。,用戶主觀層面,只有用戶才能決定規(guī)則的有效性、可行性。所以，應該將用戶的需求和系統(tǒng)更加緊密地結合起來。 可以采用基于約束（Consraint-based）的數據挖掘方法。具體約束的內容有：數據約束、 限定數據挖掘的維和層次、規(guī)則約束。如果把某些約束條件與算法緊密結合，既能提高數據挖掘效率，又能明確數據挖掘的目標。,關聯

25、規(guī)則新進展,在基于一維布爾型關聯規(guī)則的算法研究中先后出現了AIS、SETM等數據挖掘算法。 R.Agrawal等人提出的Apriori 是經典算法。隨后的關聯規(guī)則發(fā)現算法大多數建立在Apriori算法基礎上，或進行改造，或衍生變種。比如AprioriTid和AprioriHybrid算法。 Lin等人提出解決規(guī)則挖掘算法中的數據傾斜問題，從而使算法具有較好的均衡性。Park等人提出把哈希表結構用于關聯規(guī)則挖掘。,關聯規(guī)則新進展（續(xù)）

26、,數據挖掘工作是在海量數據庫上進行的，數據庫的規(guī)模對規(guī)則的挖掘時間有很大影響。Agrawal首先提出事務縮減技術，Han和Park等人也分別在減小數據規(guī)模上做了一些工作。 抽樣的方法是由Toivonen提出的。 Brin等人采用動態(tài)項集計數方法求解頻繁項集。 Aggarwal提出用圖論和格的理論求解頻繁項集的方法。Prutax算法就是用格遍歷的辦法求解頻繁項集。,關聯規(guī)則新進展（續(xù)）,關聯規(guī)則模型有很多擴展，如順序模型挖掘，在順

27、序時間段上進行挖掘等。還有挖掘空間關聯規(guī)則，挖掘周期性關聯規(guī)則，挖掘負關聯規(guī)則，挖掘交易內部關聯規(guī)則等。 Guralnik提出順序時間段問題的形式描述語言，以便描述用戶感興趣的時間段，并且構建了有效的數據結構SP樹（順序模式樹）和自底向上的數據挖掘算法。 最大模式挖掘是Bayardo等人提出來的。,關聯規(guī)則新進展（續(xù)）,隨后人們開始探討頻率接近項集。Pei給出了一種有效的數據挖掘算法。 B.Özden等人的周期性關聯規(guī)

28、則是針對具有時間屬性的事務數據庫，發(fā)現在規(guī)律性的時間間隔中滿足最小支持度和信任度的規(guī)則。 貝爾實驗室的S.Ramaswamy等人進一步發(fā)展了周期性關聯規(guī)則，提出挖掘符合日歷的關聯規(guī)則（Calendric Association Rules）算法，用以進行市場貨籃分析。 Fang等人給出冰山查詢數據挖掘算法。,關聯規(guī)則新進展（續(xù)）,T.Hannu等人把負邊界引入規(guī)則發(fā)現算法中，每次挖掘不僅保存頻繁項集，而且同時保存負邊界，達到下次挖掘

29、時減少掃描次數的目的。 Srikant等人通過研究關聯規(guī)則的上下文，提出規(guī)則興趣度尺度用以剔除冗余規(guī)則。 Zakia還用項集聚類技術求解最大的近似潛在頻繁項集，然后用格遷移思想生成每個聚類中的頻繁項集。 CAR，也叫分類關聯規(guī)則，是Lin等人提出的一種新的分類方法，是分類技術與關聯規(guī)則思想相結合的產物，并給出解決方案和算法。,關聯規(guī)則新進展（續(xù)）,Cheung等人提出關聯規(guī)則的增量算法。Thomas等人把負邊界的概念引入其中，進

30、一步發(fā)展了增量算法。如，基于Apriori框架的并行和分布式數據挖掘算法。Oates等人將MSDD算法改造為分布式算法。還有其他的并行算法，如利用垂直數據庫探求項集聚類等。,參考文獻,Agrawal R, Imielinski T, and Swami A. Mining association rules between sets of items in large databases. SIGMOD, 207-216, 1993.

31、Agrawal R, and Srikant R. Fast algorithms for mining association rules in large databases. VLDB, 478-499, 1994. Han J W, Pei J, Yin Y W. Mining frequent patterns without candidate generation. SIGMOD, 1-12, 2000.Han J