數(shù)據(jù)挖掘挖掘頻繁模式關(guān)聯(lián)和相關(guān)性

數(shù)據(jù)挖掘挖掘頻繁模式關(guān)聯(lián)和相關(guān)性演示文稿現(xiàn)在是1頁\一共有45頁\編輯于星期六第二章挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性1基本概念2頻繁項集挖掘方法3模式評估方法目錄第一章現(xiàn)在是2頁\一共有45頁\編輯于星期六基本概念現(xiàn)在是3頁\一共有45頁\編輯于星期六購物籃分析：“尿布與啤酒”采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個規(guī)律，在購買嬰兒尿布的年輕父親們中，有30%～40%的人同時要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷售方面做各種促銷活動。4現(xiàn)在是4頁\一共有45頁\編輯于星期六購物籃分析關(guān)聯(lián)規(guī)則表示如果問題的全域是商店中所有商品的集合，則對每種商品都可以用一個布爾量來表示該商品是否被顧客購買，則每個購物籃都可以用一個布爾向量表示；而通過分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時購買的模式，這些模式就可以用關(guān)聯(lián)規(guī)則表示（0001001100，這種方法丟失了什么信息？）關(guān)聯(lián)規(guī)則的兩個興趣度度量支持度置信度5現(xiàn)在是5頁\一共有45頁\編輯于星期六頻繁項集、閉項集和關(guān)聯(lián)規(guī)則頻繁項集、閉項集基本概念k－項集：包含k個項的集合。例如：{牛奶，面包，黃油}是個3－項集項集的頻率是指包含項集的事務(wù)數(shù)如果項集的頻率大于最小支持度×D中的事務(wù)總數(shù)，則稱該項集為頻繁項集項集X在數(shù)據(jù)集D中是閉的，即不存在真超項集Y，使得Y與X在D中具有相同的支持度計數(shù)，則項集X是數(shù)據(jù)集D中的閉項集6現(xiàn)在是6頁\一共有45頁\編輯于星期六頻繁項集、閉項集和關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則：基本概念給定：項的集合：I={i1,i2,...,in}任務(wù)相關(guān)數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，每個事務(wù)T則是項的集合，使得每個事務(wù)由事務(wù)標識符TID標識；A,B為兩個項集，事務(wù)T包含A當且僅當則關(guān)聯(lián)規(guī)則是如下蘊涵式：其中并且，規(guī)則在事務(wù)集D中成立，并且具有支持度s和置信度c7現(xiàn)在是7頁\一共有45頁\編輯于星期六關(guān)聯(lián)規(guī)則基本概念——示例項的集合I={A,B,C,D,E,F}任務(wù)相關(guān)數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合每個事務(wù)T由事務(wù)標識符TID標識，它是項的集合比如：TID(2000)={A,B,C}TID購買的item2000A,B,C1000A,C4000A,D5000B,E,F8現(xiàn)在是8頁\一共有45頁\編輯于星期六規(guī)則度量：支持度和置信度對所有滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則支持度s是指事務(wù)集D中包含的百分比置信度c是指D中包含A的事務(wù)同時也包含B的百分比假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則A

C(50%,66.6%)；CA(50%,100%)TID購買的item2000A,B,C1000A,C4000A,D5000B,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeer9現(xiàn)在是9頁\一共有45頁\編輯于星期六關(guān)聯(lián)規(guī)則挖掘過程大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘包含兩個過程找出所有頻繁項集大部分的計算都集中在這一步由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則即滿足最小支持度和最小置信度的規(guī)則10現(xiàn)在是10頁\一共有45頁\編輯于星期六關(guān)聯(lián)規(guī)則挖掘分類根據(jù)規(guī)則中所處理的值類型布爾關(guān)聯(lián)規(guī)則量化關(guān)聯(lián)規(guī)則（規(guī)則描述的是量化的項或?qū)傩蚤g的關(guān)聯(lián)性）根據(jù)規(guī)則中涉及的數(shù)據(jù)維單維關(guān)聯(lián)規(guī)則（僅涉及buys這個維）多維關(guān)聯(lián)規(guī)則11現(xiàn)在是11頁\一共有45頁\編輯于星期六關(guān)聯(lián)規(guī)則挖掘分類根據(jù)關(guān)聯(lián)挖掘的各種擴充挖掘最大的頻繁模式挖掘頻繁閉項集（一個項集c是頻繁閉項集，如果不存在其真超集c’，使得每個包含c的事務(wù)也包含c’）最大的頻繁模式和頻繁閉項集可以用來減少挖掘中產(chǎn)生的頻繁項集根據(jù)規(guī)則集所涉及的抽象層單層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)則（在不同的抽象層發(fā)現(xiàn)關(guān)聯(lián)規(guī)則）12現(xiàn)在是12頁\一共有45頁\編輯于星期六由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則最簡單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘置信度最小支持度50%最小置信度50%對規(guī)則AC，其支持度=50%13現(xiàn)在是13頁\一共有45頁\編輯于星期六頻繁項集挖掘方法現(xiàn)在是14頁\一共有45頁\編輯于星期六Apriori算法：通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法Apriori算法利用的是Apriori性質(zhì)頻繁項集的所有非空子集也必須是頻繁的如果{beer,diaper,nuts}是頻繁的,{beer,diaper}也是非頻繁項集的超集一定是非頻繁的15現(xiàn)在是15頁\一共有45頁\編輯于星期六Apriori算法：通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集Apriori算法利用頻繁項集性質(zhì)的先驗知識（priorknowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數(shù)據(jù)庫掃描。16現(xiàn)在是16頁\一共有45頁\編輯于星期六Apriori算法步驟Apriori算法由連接和剪枝兩個步驟組成。連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合，該候選k項集記為Ck

。Lk-1中的兩個元素l1和l2可以執(zhí)行連接操作的條件是剪枝Ck是Lk的超集（LkCk），即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中。因此可以通過掃描數(shù)據(jù)庫，通過計算每個k-項集的支持度來得到Lk

為了減少計算量，可以使用Apriori性質(zhì)，即如果一個k-項集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除

17現(xiàn)在是17頁\一共有45頁\編輯于星期六Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{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}2Itemsetsup{A}2{B}3{C}3{D}1{E}3最小支持度計數(shù)為218現(xiàn)在是18頁\一共有45頁\編輯于星期六使用Apiori性質(zhì)由L2產(chǎn)生C3連接L2={{A,C},{B,C},{B,E}{C,E}}L2

*L2使用Apriori性質(zhì)剪枝頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：{A,B,C}的2項子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個選項；{A,C,E}的2項子集是{A,C},{A,E},{C,E}，其中{A,E}不是L2的元素，所以刪除這個選項；{B,C,E}的2項子集是{B,C},{B,E},{C,E}，它的所有2－項子集都是L2的元素，因此保留這個選項。這樣，剪枝后得到C3={{B,C,E}}19現(xiàn)在是19頁\一共有45頁\編輯于星期六由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則同時滿足最小支持度和最小置信度的才是強關(guān)聯(lián)規(guī)則，從頻繁項集產(chǎn)生的規(guī)則都滿足支持度要求，而其置信度則可由一下公式計算：每個關(guān)聯(lián)規(guī)則可由如下過程產(chǎn)生對于每個頻繁項集L，產(chǎn)生L的所有非空子集對于每個非空子集s，如果 則輸出規(guī)則“ ”20現(xiàn)在是20頁\一共有45頁\編輯于星期六提高Apriori算法的效率低效率的Apriori可能需要產(chǎn)生大量的候選項集

可能需要重復(fù)掃描整個數(shù)據(jù)庫，通過模式匹配檢驗一個很大的候選集合102

個頻繁1項集發(fā)掘一個頻繁模式,｛a1,…a100｝多達103

個候選2項集1030

個候選項集21現(xiàn)在是21頁\一共有45頁\編輯于星期六提高基于Apriori挖掘效率的算法基于散列的技術(shù)事物歸約技術(shù)劃分計術(shù)抽樣技術(shù)動態(tài)項集計數(shù)計術(shù)頻繁模式增長但是它們?nèi)匀恍枰a(chǎn)生大量的候選集或者反復(fù)的瀏覽數(shù)據(jù)庫22現(xiàn)在是22頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法頻繁增長模式適應(yīng)了分治策略，如下所示將代表頻繁項集的數(shù)據(jù)庫壓縮到一顆頻繁模式樹（FP-tree），該樹仍保留項集的關(guān)聯(lián)信息。把這種壓縮后的數(shù)據(jù)庫分解成一組條件數(shù)據(jù)庫,每個數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項或“模式段”并且分別挖掘每個條件數(shù)據(jù)庫。23現(xiàn)在是23頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法示例TIDListofitem_IDsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I324現(xiàn)在是24頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法第一步規(guī)定最小支持度計數(shù)，例子中最小支持度計數(shù)是2數(shù)據(jù)庫的第一次掃描和Apriori算法一樣，它導(dǎo)出頻繁項的集合并得到它們的支持度計數(shù)頻繁項的集合按支持度計數(shù)的遞減排序。結(jié)果集或表記為L25現(xiàn)在是25頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法第一步的結(jié)果項支持度計數(shù)(frequencies)I27I16I36I42I5226現(xiàn)在是26頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法第二步:頻繁模式樹生成I1:1I36支持度計數(shù)I2I1I4I57622項ID節(jié)點鏈I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:1Null{}Null{}Null{}Null{}Null{}2342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}27現(xiàn)在是27頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法第三步:頻繁模式樹挖掘由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基構(gòu)造它的（條件）FP樹,并遞歸地在該樹上進行挖掘模式增長通過后綴模式與條件FP樹產(chǎn)生的頻繁模式連接實現(xiàn)28現(xiàn)在是28頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法頻繁模式樹I1:1Null{}Null{}Null{}Null{}Null{}I36支持度計數(shù)I2I1I4I57622項ID節(jié)點鏈I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:12342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}29現(xiàn)在是29頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法對項I5挖掘項條件模式基條件FP樹{{I2,I1:1},{I2,I1,I3:1}}<I2:2,I1:2>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}I5產(chǎn)生的頻繁模式T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}30現(xiàn)在是30頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法頻繁模式樹I1:1Null{}Null{}Null{}Null{}Null{}I36支持度計數(shù)I2I1I4I57622項ID節(jié)點鏈I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:12342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}31現(xiàn)在是31頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法對項I4挖掘產(chǎn)生的頻繁模式產(chǎn)生的頻繁模式條件模式基條件FP樹I4{{I2,I1:1},{I2,I1,I3:1}}{{I2,I1:1},{I2:1}}<I2:2,I1:2><I2:2>I5{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}{I2,I4:2}T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}32現(xiàn)在是32頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法頻繁模式樹I1:1Null{}Null{}Null{}Null{}Null{}I36支持度計數(shù)I2I1I4I57622項ID節(jié)點鏈I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:1234225226374233現(xiàn)在是33頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法對I3挖掘產(chǎn)生的頻繁模式產(chǎn)生的頻繁模式項條件模式基條件FP樹I4I3{{I2,I1:1},{I2,I1,I3:1}}{{I2,I1:1},{I2:1}}{{I2,I1:2},{I2:2},{I1:2}}<I2:2,I1:2><I2:2><I2:4,I1:2>,<I1:2>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}{I2,I4:2}{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}I5T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}34現(xiàn)在是34頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法頻繁模式樹I1:1Null{}Null{}Null{}Null{}Null{}I36支持度計數(shù)I2I1I4I57622項ID節(jié)點鏈I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:12342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}35現(xiàn)在是35頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法與條件節(jié)點I1相關(guān)聯(lián)的條件FP樹I2I144項ID支持度計數(shù)節(jié)點鏈Null{}I1:2I2:4I1:2T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}36現(xiàn)在是36頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法挖掘結(jié)果項條件模式基條件FP樹I4I3I1{{I2,I1:1},{I2,I1,I3:1}}{{I2,I1:1},{I2:1}}{{I2,I1:2},{I2:2},{I1:2}}{{I2:4}}<I2:2,I1:2><I2:2><I2:4,I1:2>,<I1:2><I2:4>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}{I2,I4:2}{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}{I2,I1:4}I537現(xiàn)在是37頁\一共有45頁\編輯于星期六挖掘頻繁項集的模式增長方法局限性當數(shù)據(jù)庫很大時,構(gòu)造基于主存的FP樹有時是不現(xiàn)實的將數(shù)據(jù)庫劃分成投影數(shù)據(jù)庫的集合，然后在每個投影數(shù)據(jù)庫上構(gòu)造FP樹并在每個投影數(shù)據(jù)庫中挖掘優(yōu)勢將發(fā)現(xiàn)的長頻繁模式問題轉(zhuǎn)換成較小的條件數(shù)據(jù)庫中遞歸地搜索一些較短的模式，然后連接后綴對于挖掘長的頻繁模式和短的頻繁模式它都是有效的和可伸縮的，并且大約比Apriori算法快一個數(shù)量級38現(xiàn)在是38頁\一共有45頁\編輯于星期六使用垂直數(shù)據(jù)格式挖掘頻繁項集最小支持度計數(shù)為2DatabaseTDBL1L2TID-集TID-集10A,C,D20B,C,E30A,B,C,E40B,E項集TID-集