關(guān)聯(lián)規(guī)則挖掘及相關(guān)算法的介紹課件

目錄關(guān)聯(lián)規(guī)則挖掘介紹Apriori算法介紹FP-growth算法介紹強(qiáng)規(guī)則、關(guān)聯(lián)與相關(guān)分析目錄關(guān)聯(lián)規(guī)則挖掘介紹1什么是關(guān)聯(lián)規(guī)則挖掘？關(guān)聯(lián)規(guī)則挖掘：從事務(wù)數(shù)據(jù)庫(kù)，關(guān)系數(shù)據(jù)庫(kù)和其他信息存儲(chǔ)中的大量數(shù)據(jù)的項(xiàng)集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。應(yīng)用：購(gòu)物籃分析、分類設(shè)計(jì)、捆綁銷售和虧本銷售分析、Web日志（點(diǎn)擊流）分析，和DNA序列分析。什么是關(guān)聯(lián)規(guī)則挖掘？關(guān)聯(lián)規(guī)則挖掘：2“尿布與啤酒”——典型關(guān)聯(lián)分析案例采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國(guó)，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個(gè)規(guī)律，在購(gòu)買嬰兒尿布的年輕父親們中，有30%～40%的人同時(shí)要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷售方面做各種促銷活動(dòng)。“尿布與啤酒”——典型關(guān)聯(lián)分析案例采用關(guān)聯(lián)模型比較典型的案例3購(gòu)物籃分析——一個(gè)誘發(fā)的例子購(gòu)物籃分析——一個(gè)誘發(fā)的例子4購(gòu)物籃分析——一個(gè)誘發(fā)的例子策略一：把經(jīng)常同時(shí)購(gòu)買的商品擺放在一起，以便進(jìn)一步刺激這些商品同時(shí)銷售。(如計(jì)算機(jī)和殺毒軟件)策略二：把經(jīng)常同時(shí)購(gòu)買的商品擺放在商店的兩端，使顧客多看更多的商品，用來(lái)帶動(dòng)其他商品的出售。購(gòu)物籃分析——一個(gè)誘發(fā)的例子策略一：把經(jīng)常同時(shí)購(gòu)買的商品擺放5購(gòu)物籃分析——一個(gè)誘發(fā)的例子如果問(wèn)題的全域是商店中所有商品的集合，則對(duì)每種商品都可以用一個(gè)布爾量來(lái)表示該商品是否被顧客購(gòu)買，則每個(gè)購(gòu)物籃都可以用一個(gè)布爾向量表示（0001001100）；而通過(guò)分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時(shí)購(gòu)買的模式，這些模式就可以用關(guān)聯(lián)規(guī)則表示。關(guān)聯(lián)規(guī)則的兩個(gè)興趣度度量支持度（support）置信度（confidence）購(gòu)物籃分析——一個(gè)誘發(fā)的例子如果問(wèn)題的全域是商店中所有商品的6關(guān)聯(lián)規(guī)則：基本概念給定：項(xiàng)的集合：I={i1,i2,...,in}任務(wù)相關(guān)數(shù)據(jù)D是數(shù)據(jù)庫(kù)事務(wù)的集合，每個(gè)事務(wù)T則是項(xiàng)的集合，使得每個(gè)事務(wù)由事務(wù)標(biāo)識(shí)符TID標(biāo)識(shí)；A,B為兩個(gè)項(xiàng)集，事務(wù)T包含A當(dāng)且僅當(dāng)則關(guān)聯(lián)規(guī)則是如下蘊(yùn)涵式：其中并且，規(guī)則在事務(wù)集D中成立，并且具有支持度s和置信度c關(guān)聯(lián)規(guī)則：基本概念給定：7規(guī)則度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer對(duì)所有滿足最小支持度（min-sup)和置信度(min-con)的關(guān)聯(lián)規(guī)則支持度s是指事務(wù)集D中包含的百分比置信度c是指D中包含A的事務(wù)同時(shí)也包含B的百分比假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則AC(50%,66.6%)CA(50%,100%)規(guī)則度量：支持度和置信度CustomerCustomerCu8由事務(wù)數(shù)據(jù)庫(kù)挖掘單維布爾關(guān)聯(lián)規(guī)則最簡(jiǎn)單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。最小支持度50%最小置信度50%對(duì)規(guī)則A

C，其支持度

=50%置信度由事務(wù)數(shù)據(jù)庫(kù)挖掘單維布爾關(guān)聯(lián)規(guī)則最簡(jiǎn)單的關(guān)聯(lián)規(guī)則挖掘，即單維9大型數(shù)據(jù)庫(kù)關(guān)聯(lián)規(guī)則挖掘過(guò)程基本概念k－項(xiàng)集：包含k個(gè)項(xiàng)的集合{牛奶，面包，黃油}是個(gè)3－項(xiàng)集項(xiàng)集的頻率是指包含項(xiàng)集的事務(wù)數(shù)如果項(xiàng)集的頻率大于（最小支持度×D中的事務(wù)總數(shù)），則稱該項(xiàng)集為頻繁項(xiàng)集大型數(shù)據(jù)庫(kù)中的關(guān)聯(lián)規(guī)則挖掘包含兩個(gè)過(guò)程：找出所有頻繁項(xiàng)集大部分的計(jì)算都集中在這一步由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則即滿足最小支持度和最小置信度的規(guī)則大型數(shù)據(jù)庫(kù)關(guān)聯(lián)規(guī)則挖掘過(guò)程基本概念10目錄關(guān)聯(lián)規(guī)則挖掘介紹Apriori算法介紹FP-growth算法介紹強(qiáng)規(guī)則、關(guān)聯(lián)與相關(guān)分析目錄關(guān)聯(lián)規(guī)則挖掘介紹11Apriori算法Apriori算法利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)（priorknowledge），通過(guò)逐層搜索的迭代方法，即將k-1項(xiàng)集用于探察k項(xiàng)集，來(lái)窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。先找到頻繁1-項(xiàng)集集合L1,然后用L1找到頻繁2-項(xiàng)集集合L2，接著用L2找L3，直到找不到頻繁k-項(xiàng)集，找每個(gè)Lk需要一次數(shù)據(jù)庫(kù)掃描。Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集也必須是頻繁的。（

模式不可能比A更頻繁的出現(xiàn)）Apriori算法是反單調(diào)的，即一個(gè)集合如果不能通過(guò)測(cè)試，則該集合的所有超集也不能通過(guò)相同的測(cè)試。頻繁模式：是指頻繁地出現(xiàn)在數(shù)據(jù)集中的模式（如項(xiàng)集、子序列或子結(jié)構(gòu)）。頻繁項(xiàng)集：頻繁地同時(shí)出現(xiàn)在交易數(shù)據(jù)集中的數(shù)據(jù)集合。Apriori算法Apriori算法利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知12Apriori算法步驟Apriori算法由連接和剪枝兩個(gè)步驟組成。連接：為了找Lk，通過(guò)Lk-1與自己連接產(chǎn)生候選k-項(xiàng)集的集合，該候選k項(xiàng)集記為Ck。Lk-1中的兩個(gè)元素L1和L2可以執(zhí)行連接操作的條件是Ck是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項(xiàng)集都在Ck中（為什么？）。因此可以通過(guò)掃描數(shù)據(jù)庫(kù)，通過(guò)計(jì)算每個(gè)k-項(xiàng)集的支持度來(lái)得到Lk

。為了減少計(jì)算量，可以使用Apriori性質(zhì)，即如果一個(gè)k-項(xiàng)集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。Apriori算法步驟Apriori算法由連接和剪枝兩個(gè)步驟13Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2Apriori算法——示例DatabaseTDB1sts14使用Apiori性質(zhì)由L2產(chǎn)生C31．連接：C3=L2L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的，對(duì)候選項(xiàng)C3，我們可以刪除其子集為非頻繁的選項(xiàng)：{A,B,C}的2項(xiàng)子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個(gè)選項(xiàng)；{A,C,E}的2項(xiàng)子集是{A,C},{A,E},{C,E}，其中{A,E}

不是L2的元素，所以刪除這個(gè)選項(xiàng)；{B,C,E}的2項(xiàng)子集是{B,C},{B,E},{C,E}，它的所有2－項(xiàng)子集都是L2的元素，因此保留這個(gè)選項(xiàng)。3．這樣，剪枝后得到C3={{B,C,E}}使用Apiori性質(zhì)由L2產(chǎn)生C31．連接：15由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則同時(shí)滿足最小支持度和最小置信度的才是強(qiáng)關(guān)聯(lián)規(guī)則，從頻繁項(xiàng)集產(chǎn)生的規(guī)則都滿足支持度要求，而其置信度則可由以下公式計(jì)算：每個(gè)關(guān)聯(lián)規(guī)則可由如下過(guò)程產(chǎn)生：對(duì)于每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的所有非空子集；對(duì)于l的每個(gè)非空子集s，如果 則輸出規(guī)則“ ”由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則同時(shí)滿足最小支持度和最小置信度的才是強(qiáng)16例題：交易記錄事務(wù)數(shù)據(jù)庫(kù)有9個(gè)事務(wù)。用Apriori算法尋找D中的頻繁項(xiàng)集。

例題：交易記錄事務(wù)數(shù)據(jù)庫(kù)有9個(gè)事務(wù)。用Apriori算法尋找17關(guān)聯(lián)規(guī)則挖掘及相關(guān)算法的介紹課件18關(guān)聯(lián)規(guī)則挖掘及相關(guān)算法的介紹課件19例題：交易記錄事務(wù)數(shù)據(jù)庫(kù)有9個(gè)事務(wù)。用Apriori算法尋找D中的頻繁項(xiàng)集。

算法使用L3

L3產(chǎn)生候選4-項(xiàng)集的集合C4。C4={{I1，I2，I3，I5}}，因?yàn)樗淖蛹瘂I2,I3，I5}不是頻繁的，這個(gè)項(xiàng)集被剪去，這樣C4=?

，因此算法終止，找出了所有的頻繁項(xiàng)集。例題：交易記錄事務(wù)數(shù)據(jù)庫(kù)有9個(gè)事務(wù)。用Apriori算法尋找20提高Apriori算法的有效性(1)Apriori算法主要的挑戰(zhàn)要對(duì)數(shù)據(jù)進(jìn)行多次掃描；會(huì)產(chǎn)生大量的候選項(xiàng)集；對(duì)候選項(xiàng)集的支持度計(jì)算非常繁瑣；解決思路減少對(duì)數(shù)據(jù)的掃描次數(shù)；縮小產(chǎn)生的候選項(xiàng)集；改進(jìn)對(duì)候選項(xiàng)集的支持度計(jì)算方法方法1：基于hash表的項(xiàng)集計(jì)數(shù)將每個(gè)項(xiàng)集通過(guò)相應(yīng)的hash函數(shù)映射到hash表中的不同的桶中，這樣可以通過(guò)將桶中的項(xiàng)集技術(shù)跟最小支持計(jì)數(shù)相比較先淘汰一部分項(xiàng)集。提高Apriori算法的有效性(1)Apriori算法主要的21提高Apriori算法的有效性(2)方法2：事務(wù)壓縮（壓縮進(jìn)一步迭代的事務(wù)數(shù)）不包含任何k-項(xiàng)集的事務(wù)不可能包含任何(k+1)-項(xiàng)集，這種事務(wù)在下一步的計(jì)算中可以加上標(biāo)記或刪除。方法3：劃分挖掘頻繁項(xiàng)集只需要兩次數(shù)據(jù)掃描D中的任何頻繁項(xiàng)集必須作為局部頻繁項(xiàng)集至少出現(xiàn)在一個(gè)部分中。第一次掃描：將數(shù)據(jù)劃分為多個(gè)部分并找到局部頻繁項(xiàng)集第二次掃描：評(píng)估每個(gè)候選項(xiàng)集的實(shí)際支持度，以確定全局頻繁項(xiàng)集提高Apriori算法的有效性(2)方法2：事務(wù)壓縮（壓縮進(jìn)22提高Apriori算法的有效性(3)方法4：選樣（在給定數(shù)據(jù)的一個(gè)子集挖掘）基本思想：選擇原始數(shù)據(jù)的一個(gè)樣本，在這個(gè)樣本上用Apriori算法挖掘頻繁模式通過(guò)犧牲精確度來(lái)減少算法開(kāi)銷，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來(lái)減少遺漏的頻繁模式可以通過(guò)一次全局掃描來(lái)驗(yàn)證從樣本中發(fā)現(xiàn)的模式可以通過(guò)第二此全局掃描來(lái)找到遺漏的模式方法5：動(dòng)態(tài)項(xiàng)集計(jì)數(shù)在掃描的不同點(diǎn)添加候選項(xiàng)集，這樣，如果一個(gè)候選項(xiàng)集已經(jīng)滿足最少支持度，則在可以直接將它添加到頻繁項(xiàng)集，而不必在這次掃描的以后對(duì)比中繼續(xù)計(jì)算。提高Apriori算法的有效性(3)方法4：選樣（在給定數(shù)據(jù)23目錄關(guān)聯(lián)規(guī)則挖掘介紹Apriori算法介紹FP-growth算法介紹強(qiáng)規(guī)則、關(guān)聯(lián)與相關(guān)分析目錄關(guān)聯(lián)規(guī)則挖掘介紹24FP-Growth算法AProiri算法需要產(chǎn)生大量候選項(xiàng)集,而且需要多次掃描數(shù)據(jù)庫(kù),然后通過(guò)模式匹配檢查一個(gè)很大的候選集合,在挖掘長(zhǎng)模式時(shí),算法性能退化很快。Han提出了一種頻繁模式

增長(zhǎng)算法(FP-Growth)，不產(chǎn)生候選集而直接產(chǎn)生全部頻繁項(xiàng)集。FP-Growth算法采用了分而治之策略:首先，將提供頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮成一棵頻繁模式樹(shù)(FP)，

該樹(shù)仍保留項(xiàng)集關(guān)聯(lián)信息,然后，將這種壓縮后的數(shù)據(jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)庫(kù)關(guān)聯(lián)一個(gè)頻繁項(xiàng)，并分別挖掘每個(gè)條件數(shù)據(jù)庫(kù)。FP-Growth算法AProiri算法需要產(chǎn)生大量候選項(xiàng)集25使用FP-Growth算法挖掘頻繁模式

數(shù)據(jù)庫(kù)中有9個(gè)事務(wù),即|D|=9,如表所示，事務(wù)中的項(xiàng)按字典次次序存放。

表中有9個(gè)交易的數(shù)據(jù)庫(kù)事務(wù)項(xiàng)ID列表事務(wù)項(xiàng)ID列表T100I1,I2,I5T600I2,I3T200I2,I4T700I1,I3T300I2,I3T800I1,I2,I3,I5T400I1,I2,I4T900I1,I2,I3T500I1,I3使用FP-Growth算法挖掘頻繁模式

數(shù)據(jù)庫(kù)中有9個(gè)事務(wù),26FP樹(shù)構(gòu)造FP-樹(shù)構(gòu)造如下:1）創(chuàng)建樹(shù)的根節(jié)點(diǎn),用”null”標(biāo)記。2）第二次掃描數(shù)據(jù)庫(kù),每個(gè)事務(wù)中的項(xiàng)按L中的次序處理(處理后的數(shù)據(jù)庫(kù)見(jiàn)表1-2),并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分枝,若節(jié)點(diǎn)或分枝已經(jīng)存在,則共享節(jié)點(diǎn)或分枝,同時(shí)將共享前綴上的每個(gè)結(jié)點(diǎn)的計(jì)數(shù)加1，為前綴之后的項(xiàng)創(chuàng)建結(jié)點(diǎn)和鏈接。若不存在，則以根結(jié)點(diǎn)為父結(jié)點(diǎn)將該事務(wù)中的項(xiàng)按L中的次序依次插入。掃描所有的事務(wù)之后得到的樹(shù)如圖所示。FP樹(shù)構(gòu)造FP-樹(shù)構(gòu)造如下:27第一步、構(gòu)造FP-tree掃描事務(wù)數(shù)據(jù)庫(kù)得到頻繁1-項(xiàng)目集F定義minsup=20%，即最小支持度為2重新排列FI1I2I3I4I567622I2I1I3I4I576622第一步、構(gòu)造FP-tree掃描事務(wù)數(shù)據(jù)庫(kù)得到頻繁1-項(xiàng)目集F28重新調(diào)整事務(wù)數(shù)據(jù)庫(kù)TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3重新調(diào)整事務(wù)數(shù)據(jù)庫(kù)TidItems1I2,I1,I52I229創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表Item-nameNode-headI30加入第一個(gè)事務(wù)(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:1加入第一個(gè)事務(wù)(I2,I1,I5)Item-nameNode31加入第二個(gè)事務(wù)(I2,I4)Item-nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1I4:1加入第二個(gè)事務(wù)(I2,I4)Item-nameNode-he32加入第三個(gè)事務(wù)(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:1加入第三個(gè)事務(wù)(I2,I3)Item-nameNode-he33加入第四個(gè)事務(wù)(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1加入第四個(gè)事務(wù)(I2,I1,I4)Item-nameNode34加入第五個(gè)事務(wù)(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:1加入第五個(gè)事務(wù)(I1,I3)Item-nameNode-he35加入第六個(gè)事務(wù)(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:1加入第六個(gè)事務(wù)(I2,I3)Item-nameNode-he36加入第七個(gè)事務(wù)(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:2加入第七個(gè)事務(wù)(I1,I3)Item-nameNode-he37加入第八個(gè)事務(wù)(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:1加入第八個(gè)事務(wù)(I2,I1,I3,I5)Item-nameN38加入第九個(gè)事務(wù)(I2,I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:2加入第九個(gè)事務(wù)(I2,I1,I3)Item-nameNode39第二步、FP-growth首先考慮I5，得到條件模式基<(I2,I1:1)>、<I2,I1,I3:1>構(gòu)造條件FP-tree得到I5頻繁項(xiàng)集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}Item-nameNode-headI2I1NullI2:2I1:2I3:1第二步、FP-growth首先考慮I5，得到條件模式基Ite40第二步、FP-growth接著考慮I4，得到條件模式基<(I2,I1:1)>、<I2:1>構(gòu)造條件FP-tree得到I4頻繁項(xiàng)集：{{I2,I4:2}}Item-nameNode-headI2NullI2:2I1:1第二步、FP-growth接著考慮I4，得到條件模式基Ite41第二步、FP-growth然后考慮I3，得到條件模式基<(I2,I1:2)>、<I2:2>、<I1:2>構(gòu)造條件FP-tree由于此樹(shù)不是單一路徑，因此需要遞歸挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:2第二步、FP-growth然后考慮I3，得到條件模式基Ite42第二步、FP-growth遞歸考慮I3，此時(shí)得到I1條件模式基<(I2:2)>,即I1I3的條件模式基為<(I2:2)>構(gòu)造條件FP-tree得到I3的頻繁項(xiàng)目集{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}}Item-nameNode-headI2NullI2:2第二步、FP-growth遞歸考慮I3，此時(shí)得到I1條件模式43第二步、FP-growth最后考慮I1，得到條件模式基<(I2:4)>構(gòu)造條件FP-tree得到I1的頻繁項(xiàng)目集{{I2,I1:4}Item-nameNode-headI2NullI2:4第二步、FP-growth最后考慮I1，得到條件模式基Ite44項(xiàng)條件模式基條件FP樹(shù)產(chǎn)生的頻繁模式I5{{I2,I1:1},{I2,I1,I3:1}}<I2:2,I1:2>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}I4{{I2,I1:1},{I2:1}}<I2:2>{I2,I4:2}I3{{I2,I1:2},{I2:2}{I1:2}}<I2:4,I1:2>,<I1:2>{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}I1{{I2:4}}<I2:4>{I2,I1:4}通過(guò)創(chuàng)建條件模式基挖掘FP樹(shù)的結(jié)果項(xiàng)條件模式基條件FP樹(shù)產(chǎn)生的頻繁模式I5{{I2,I1:45FP-Growth算法的優(yōu)點(diǎn)分治策略:根據(jù)當(dāng)前已獲得的頻繁模式分解挖掘任務(wù)和DB搜索更小的數(shù)據(jù)庫(kù)其它因素?zé)o需產(chǎn)生候選，從而測(cè)試候選項(xiàng)壓縮的數(shù)據(jù)庫(kù):FP-tree結(jié)構(gòu)無(wú)需重復(fù)掃描整個(gè)數(shù)據(jù)庫(kù)基本操作:統(tǒng)計(jì)局部頻繁項(xiàng)，建立子FP-tree,無(wú)需模式搜索和匹配FP-Growth算法的優(yōu)點(diǎn)分治策略:46目錄關(guān)聯(lián)規(guī)則挖掘介紹Apriori算法介紹FP-growth算法介紹強(qiáng)規(guī)則、關(guān)聯(lián)與相關(guān)分析目錄關(guān)聯(lián)規(guī)則挖掘介紹47關(guān)聯(lián)規(guī)則的興趣度度量客觀度量?jī)蓚€(gè)流行的度量指標(biāo)支持度置信度主觀度量最終，只有用戶才能確定一個(gè)規(guī)則是否有趣的，而且這種判斷是主觀的，因不同的用戶而異；通常認(rèn)為一個(gè)規(guī)則（模式）是有趣的，如果：它是出人意料的可行動(dòng)的（用戶可以使用該規(guī)則做某些事情）挖掘了關(guān)聯(lián)規(guī)則后，哪些規(guī)則是用戶感興趣的？強(qiáng)關(guān)聯(lián)規(guī)則是否就是有趣的？關(guān)聯(lián)規(guī)則的興趣度度量客觀度量48對(duì)強(qiáng)關(guān)聯(lián)規(guī)則的批評(píng)（1）例1：(Aggarwal&Yu,PODS9