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

1、第3課 頻繁模式及關(guān)聯(lián)規(guī)則挖掘技術(shù),徐從富，副教授 浙江大學(xué)人工智能研究所,浙江大學(xué)本科生《數(shù)據(jù)挖掘?qū)д摗氛n件,內(nèi)容提綱,關(guān)聯(lián)規(guī)則挖掘簡(jiǎn)介關(guān)聯(lián)規(guī)則基本模型關(guān)聯(lián)規(guī)則價(jià)值衡量與發(fā)展參考文獻(xiàn),關(guān)聯(lián)規(guī)則簡(jiǎn)介,關(guān)聯(lián)規(guī)則反映一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過其他事物預(yù)測(cè)到。 典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對(duì)超市中的貨籃數(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會(huì)議上提出在事務(wù)、關(guān)系數(shù)據(jù)庫中的項(xiàng)集和對(duì)象中發(fā)現(xiàn)頻繁模式、關(guān)聯(lián)規(guī)則、相關(guān)性或者因果結(jié)構(gòu)頻繁模式: 數(shù)據(jù)庫中頻繁出現(xiàn)的項(xiàng)集 目的: 發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律超市數(shù)據(jù)中的什么產(chǎn)品會(huì)一起購買？— 啤酒和尿布在買了一臺(tái)PC之后下一步會(huì)購買?哪種DNA對(duì)這

3、種藥物敏感?我們?nèi)绾巫詣?dòng)對(duì)Web文檔進(jìn)行分類?,頻繁模式挖掘的重要性,許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)關(guān)聯(lián)、相關(guān)性、因果性序列模式、空間模式、時(shí)間模式、多維關(guān)聯(lián)分類、聚類分析更加廣泛的用處購物籃分析、交叉銷售、直銷點(diǎ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}為所有項(xiàng)目的集合，D為事務(wù)數(shù)據(jù)庫，事務(wù)T是一個(gè)項(xiàng)目子集（T?I）。每一個(gè)事務(wù)具有唯一的事務(wù)標(biāo)識(shí)TID。設(shè)A是一個(gè)由項(xiàng)目構(gòu)成的集合，稱為項(xiàng)集。事務(wù)T包含項(xiàng)集A，當(dāng)且僅當(dāng)A?T。如果項(xiàng)集A中包含k個(gè)項(xiàng)目，則稱其為k項(xiàng)集。項(xiàng)集

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

6、rt (X)。這是一個(gè)條件概率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)歷如下兩個(gè)步驟： 找出所有頻繁項(xiàng)集。 由頻繁項(xià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算法命名源于算法使用了頻繁項(xiàng)集性質(zhì)的先驗(yàn)（Prior）知識(shí)。 Ap

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

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

11、不同項(xiàng)集的支持度，因此在一定程度上減少了計(jì)算量。,Apriori算法,(1) L1={頻繁1項(xiàng)集}; (2) for(k=2;Lk-1??;k++) do begin (3) Ck=apriori_gen(Lk-1); //新的潛在頻繁項(xiàng)集 (4) for all transactions t?D do begin (5) Ct=subset(Ck,t); //t中包含的潛在頻繁項(xiàng)集 (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=,,實(shí)例,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（散列項(xiàng)集計(jì)數(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í)對(duì)頻繁集的挖掘又完備的避免代價(jià)較高的數(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-項(xiàng)集把項(xiàng)按支持度遞減排序再一次掃描數(shù)據(jù)庫，建立FP-tree,建立 FP-tree樹,完備: 不會(huì)打破交易中的任何模式包含了頻繁模式挖掘所需的全部信息緊密

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

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

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)造的屬性,對(duì)每個(gè)模式庫計(jì)算庫中每個(gè)項(xiàng)的支持度用模式庫中的頻

22、繁項(xiàng)建立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ī)則價(jià)值衡量與發(fā)展,關(guān)聯(lián)規(guī)則價(jià)值衡量關(guān)聯(lián)規(guī)則最新進(jìn)展,規(guī)則價(jià)值衡量,對(duì)關(guān)聯(lián)規(guī)則的評(píng)價(jià)與價(jià)值衡量涉及兩個(gè)層面：系統(tǒng)客觀的層面用戶主觀的層面,系

24、統(tǒng)客觀層面,使用“支持度和信任度”框架可能會(huì)產(chǎn)生一些不正確的規(guī)則。只憑支持度和信任度閾值未必總能找出符合實(shí)際的規(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ī)模對(duì)規(guī)則的挖掘時(shí)間有很大影響。Agrawal首先提出事務(wù)縮減技術(shù)，Han和Park等人也分別在減小數(shù)據(jù)規(guī)模上做了一些工作。 抽樣的方法是由Toivonen提出的。 Brin等人采用動(dòng)態(tài)項(xiàng)集計(jì)數(shù)方法求解頻繁項(xiàng)集。 Aggarwal提出用圖論和格的理論求解頻繁項(xiàng)集的方法。Prutax算法就是用格遍歷的辦法求解頻繁項(xiàng)集。,關(guān)聯(lián)規(guī)則新進(jìn)展（續(xù)）,關(guān)聯(lián)規(guī)則模型有很多擴(kuò)展，如順序模型挖掘，在順

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

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

29、時(shí)減少掃描次數(shù)的目的。 Srikant等人通過研究關(guān)聯(lián)規(guī)則的上下文，提出規(guī)則興趣度尺度用以剔除冗余規(guī)則。 Zakia還用項(xiàng)集聚類技術(shù)求解最大的近似潛在頻繁項(xiàng)集，然后用格遷移思想生成每個(gè)聚類中的頻繁項(xiàng)集。 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àng)集聚類等。,參考文獻(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