“啤酒和尿布的榮譽(yù)”

概念

• 項(xiàng) item：單個(gè)的事物個(gè)體 ，I={i1,i2…im}是所有項(xiàng)的集合，|I|=m是項(xiàng)的總數(shù)
• 項(xiàng)集（item set)/模式（pattern)：項(xiàng)的集合，包含k個(gè)項(xiàng)的項(xiàng)集稱為k-項(xiàng)集
• 數(shù)據(jù)集(data set)/數(shù)據(jù)庫(data base)：D={T1,T2,…Tn}是與任務(wù)相關(guān)的數(shù)據(jù)庫事務(wù)/記錄/交易的集合，每個(gè)事務(wù)有一個(gè)標(biāo)識(shí)符，稱作TID。|D|=n為數(shù)據(jù)集中包含的事務(wù)總數(shù)。
• 支持度support ：項(xiàng)集的出現(xiàn)頻率（0~1）/比例（絕對(duì)數(shù)）
• 置信度/可信度(confidence)：在D中的那些包含A的事務(wù)中，B也同時(shí)出現(xiàn)的條件概率P(B|A)=P(AB)/P(A)
• 頻繁項(xiàng)集(frequent itemset)/模式(pattern)：項(xiàng)集的支持度>=最小支持度(min support)
• 關(guān)聯(lián)規(guī)則(association rules):關(guān)聯(lián)規(guī)則是形如A=>B的蘊(yùn)含式，具有支持度s=support(A$\cup$B)，c=confidence(A=>B)=P(B|A)=support(A$\cup$B)/support(A)
• 強(qiáng)規(guī)則：同時(shí)滿足最小支持度和最小置信度的規(guī)則稱作強(qiáng)規(guī)則。關(guān)聯(lián)規(guī)則發(fā)掘分為兩步：
  • 找出所有頻繁項(xiàng)集
  • 產(chǎn)生強(qiáng)規(guī)則

例子

結(jié)論與注意事項(xiàng)

1.非頻繁項(xiàng)集的超集都是非頻繁的
support(y)<=support(x)<min_sup
y=x$\cup$其他
2.頻繁項(xiàng)集的子集是頻繁的

1.強(qiáng)規(guī)則不一定有價(jià)值
2.相關(guān)分析：corr(A,B)=P(A$\cup$B)/P(A)P(B)
正相關(guān)>1,負(fù)相關(guān)<1，獨(dú)立=1

問題分類

根據(jù)規(guī)則中所處理的值的類型分類：

• 布爾關(guān)聯(lián)規(guī)則(boolean association rule)：規(guī)則考慮的關(guān)聯(lián)是項(xiàng)的在與不在
• 量化關(guān)聯(lián)規(guī)則(quantitative association rule)：規(guī)則描述的是量化的項(xiàng)或?qū)傩灾g的關(guān)聯(lián)

根據(jù)規(guī)則中所涉及的數(shù)據(jù)維數(shù)分類：

• 單維關(guān)聯(lián)規(guī)則(single-dimensional association rule) ：規(guī)則中的項(xiàng)或?qū)傩悦總€(gè)只涉及一個(gè)維
• 多維關(guān)聯(lián)規(guī)則(multi-dimensional association rule):規(guī)則涉及多維度

根據(jù)規(guī)則中所涉及的抽象層分類：

• 單層關(guān)聯(lián)規(guī)則(single-level association rule)：規(guī)則不考慮項(xiàng)的分層
• 多層關(guān)聯(lián)規(guī)則(multi-level association rule)：考慮項(xiàng)的分層 buys(X,milk)=>buys(X,food)

頻繁模式挖掘的分類：

• 頻繁模式挖掘
• 交互挖掘
• 增量挖掘
• 效用頻繁模式挖掘
• 最大頻繁模式挖掘
• 頻繁閉合模式挖掘
• 并行/分布式挖掘

經(jīng)典算法

基于候選項(xiàng)生成與測(cè)試(candidate generation and test)

非頻繁項(xiàng)集的超集都是非頻繁的
代表作：apriori（1994）

基于分治的模式增長(zhǎng)（pattern growth)

采用分而治之的方法：頻繁項(xiàng)集的子集是頻繁的
代表作:FP-growth(2000)