挖掘頻繁模式、關(guān)聯(lián)和相關(guān)什么是頻繁模式分析?■頻繁模式是頻繁的出現(xiàn)在數(shù)據(jù)集中的模式a如項集、子序或者子結(jié)構(gòu)動機:發(fā)現(xiàn)數(shù)據(jù)中蘊含的內(nèi)在規(guī)律a那些產(chǎn)品經(jīng)常被一起購買?--啤酒和尿布?a買了PC之后接著都會買些什么?哪種DNA對這種新藥敏感a我們能夠自動的分類WEB文檔嗎?應(yīng)用¤購物籃分析、WEB日志(點擊流)分析、捆綁銷售、DNA序列分析等頻繁模式挖掘的重要性揭示數(shù)據(jù)集的內(nèi)在的、重要的特性作為很多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)a關(guān)聯(lián)、相關(guān)和因果分析口序列、結(jié)構(gòu)(e.g.子圖)模式分析¤時空、多媒體、時序和流數(shù)據(jù)中的模式分析a分類:關(guān)聯(lián)分類口聚類分析:基于頻繁模式的聚類a數(shù)據(jù)倉庫:冰山方體計算購物籃分析如果問題的全域是商店中所有商品的集合,則對每種商品都可以用一個布爾量來表示該商品是否被顧客購買,則每個購物籃都可以用一個布爾向量表示;而通過分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時購買的模式,這些模式就可以用關(guān)聯(lián)規(guī)則表示(e.g0000110,0這種方法丟失了什么信息?)關(guān)聯(lián)規(guī)則的兩個興趣度度量a支持度computer=antivirus_sofware[support=2%,confidence=60%]a置信度¤通常,如果關(guān)聯(lián)規(guī)則同時滿足最小支持度閾值和最小置信度閾值,則此關(guān)聯(lián)規(guī)則是有趣的關(guān)聯(lián)規(guī)則:基本概念給定口項的集合:={i,i2,…,in¤任務(wù)相關(guān)數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合,每個事務(wù)7則是項的集合,使得T≤1a每個事務(wù)由事務(wù)標識符T|D標識口A,B為兩個項集,事務(wù)7包含A當且僅當AcT則關(guān)聯(lián)規(guī)則是如下蘊涵式:A→B[s,C口其中Ac1,Bc1并且A⌒B=Φ,規(guī)則A→B在事務(wù)集D中成立,并且具有支持度s和置信度C規(guī)則度量:支持度和置信度CustomerbuyslothCustomer口支持度s是指事務(wù)集D中包含A∪B的百分比P148)=P(A∪B)a置信度c是指D中包含A的事務(wù)同時也包含B的百分比confidence(A→B)=P(B|A)=P(A∪B)/P(A)buysbeer口假設(shè)最小支持度閾值TID購買的tem50%,最小置信度閾值為2000AB50%,則有如下關(guān)聯(lián)規(guī)則A→C(50%66.6%)1000ACC→A(50%,100%4000AD¤同時滿足最小支持度閾值5000B.E.F積強題度閱值的規(guī)基本概念—一示例項的集合|={A,B,C,D,E,F每個事務(wù)7由事務(wù)標識符TD標識,它是項的集合TD(2000)={A,B,C}任務(wù)相關(guān)數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合TID購買的tem2000AB,C1000AC4000AD5000B.E.F頻繁項集基本概念ak一項集:包含k個項的集合{牛奶,面包,黃油}是個3一項集a項集的頻率是指包含項集的事務(wù)數(shù),簡稱為項集的頻率、支持度計數(shù)或計數(shù)口項集的支持度有時稱為相對支持度,而出現(xiàn)的頻率稱作絕對支持度。如果項集舶頻率大于(最小支持度閾值ⅩD中的事務(wù)總數(shù)),則稱該項集/為頻繁項集。頻繁k項集的集合通常記作Lk。nr(A∪B)sucout(A∪B)confidence(A→B)=P(BA)upport-Csupport(A)support-count(A)關(guān)聯(lián)規(guī)則挖掘的兩步過程一般來說,關(guān)聯(lián)規(guī)則的挖掘可以看作兩步的過程¤找出所有頻繁項集該項集的每一個出現(xiàn)的頻繁性≥minsup¤由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則即滿足最小支持度和最小置信度的規(guī)則主要挑戰(zhàn):會產(chǎn)生大量滿足minsup的項集,尤其當mInsup設(shè)置得低的時候口Eg.一個長度為100的頻繁項集{a1,a2…,2100包含的頻繁項集的總個數(shù)為21-1≈1.27×103閉頻繁項集和極大頻繁項集如果不存在真超項集Y使得Y與X在S中有相同的支持度計數(shù),則稱項集λ在數(shù)據(jù)集S中是閉的。項集乂是數(shù)據(jù)集S中的閉頻繁項集,如果X在S中是閉的和頻繁的。項集X是S中的極大頻繁瑣集或極大項集),如果X是頻繁的,并宜不存在超項集Y使得ⅹ∝γ并且Y在S中是頻繁的。設(shè)C是數(shù)據(jù)集S中滿足mInsup的閉頻繁項集的集合,令M是S中滿足misp的極大頻繁頃集的集合。假定我們有C和M中每個項集的支持度計數(shù),則C和他的計數(shù)信息可以用來導(dǎo)頻繁項集的完整集合(我們稱C包