“啤酒和尿布的榮譽”

概念

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

例子

結論與注意事項

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

1.強規(guī)則不一定有價值
2.相關分析：corr(A,B)=P(A$\cup$B)/P(A)P(B)
正相關>1,負相關<1，獨立=1

問題分類

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

• 布爾關聯(lián)規(guī)則(boolean association rule)：規(guī)則考慮的關聯(lián)是項的在與不在
• 量化關聯(lián)規(guī)則(quantitative association rule)：規(guī)則描述的是量化的項或屬性之間的關聯(lián)

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

• 單維關聯(lián)規(guī)則(single-dimensional association rule) ：規(guī)則中的項或屬性每個只涉及一個維
• 多維關聯(lián)規(guī)則(multi-dimensional association rule):規(guī)則涉及多維度

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

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

頻繁模式挖掘的分類：

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

經(jīng)典算法

基于候選項生成與測試(candidate generation and test)

非頻繁項集的超集都是非頻繁的
代表作：apriori（1994）

基于分治的模式增長（pattern growth)

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