3 頻繁模式關(guān)聯(lián)挖掘 - 浙江大學(xué)計算機科學(xué)與技術(shù)學(xué)院

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

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

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

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

5、A在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的次數(shù)占D中總事務(wù)的百分比叫做項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。,關(guān)聯(lián)規(guī)則基本模型（續(xù)）,關(guān)聯(lián)規(guī)則是形如X?Y的邏輯蘊含式，其中X?I，Y?I，且X?Y=?。如果事務(wù)數(shù)據(jù)庫D中有s%的事務(wù)包含X?Y，則稱關(guān)聯(lián)規(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的條件概率,設(shè)最小支持度為50%, 最小可信度為 50%,

7、則可得到A ? C (50%, 66.6%)C ? A (50%, 100%),,,,,,買尿布的客戶,二者都買的客戶,買啤酒的客戶,,關(guān)聯(lián)規(guī)則基本模型（續(xù)）,關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。 發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要經(jīng)歷如下兩個步驟： 找出所有頻繁項集。 由頻繁項集生成滿足最小信任度閾值的規(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算法命名源于算法使用了頻繁項集性質(zhì)的先驗（Prior）知識。 Ap

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

10、集合為 ，則三者之間滿足關(guān)系Lk ?Ck ? 。構(gòu)成潛在頻繁項集所遵循的原則是“頻繁項集的子集必為頻繁項集”。,,,關(guān)聯(lián)規(guī)則的性質(zhì)：,性質(zhì)1：頻繁項集的子集必為頻繁項集。 性質(zhì)2：非頻繁項集的超集一定是非頻繁的。 Apriori算法運用性質(zhì)1，通過已知的頻繁項集構(gòu)成長度更大的項集，并將其稱為潛在頻繁項集。潛在頻繁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（散列項集計數(shù)）Transaction reduction（事務(wù)壓縮）Partitioning（劃分）Sampling（采樣）,關(guān)聯(lián)規(guī)則挖掘算法,Agrawal等人提出的AIS，Apriori和AprioriTidCu

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

15、開發(fā)一種高效的基于FP-tree的頻繁集挖掘算法采用分而治之的方法學(xué)：分解數(shù)據(jù)挖掘任務(wù)為小任務(wù)避免生成關(guān)聯(lián)規(guī)則: 只使用部分?jǐn)?shù)據(jù)庫!,挖掘頻繁集 不用生成候選集,最小支持度 = 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},步驟:掃描數(shù)據(jù)庫一次，得到頻繁1-項集把項按支持度遞減排序再一次掃描數(shù)據(jù)庫，建立FP-tree,建立 FP-tree樹,完備: 不會打破交易中的任何模式包含了頻繁模式挖掘所需的全部信息緊密

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

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

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支持條件模式庫構(gòu)造的屬性,對每個模式庫計算庫中每個項的支持度用模式庫中的頻

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ān)聯(lián)規(guī)則價值衡量與發(fā)展,關(guān)聯(lián)規(guī)則價值衡量關(guān)聯(lián)規(guī)則最新進(jìn)展,規(guī)則價值衡量,對關(guān)聯(lián)規(guī)則的評價與價值衡量涉及兩個層面：系統(tǒng)客觀的層面用戶主觀的層面,系

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

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

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

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

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

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

30、一步發(fā)展了增量算法。如，基于Apriori框架的并行和分布式數(shù)據(jù)挖掘算法。Oates等人將MSDD算法改造為分布式算法。還有其他的并行算法，如利用垂直數(shù)據(jù)庫探求項集聚類等。,參考文獻(xiàn),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