一、數據挖掘定義

今天我們來講述其中的關聯分析

三、關聯分析

典型例子：啤酒與尿布

常用方法 —— 關聯規則挖掘 (Association Rule Mining)

????????給出事務的集合, 能夠發現一些規則：𝐴 => 𝐵

????????當事務中某些子項出現時，預測其他子項也出現

基本概念：

Association Rule（關聯規則）

????形如X → Y的表達式，X, Y均為項集

????例：{Milk, Diaper} →{Beer}

Confidence (置信度)

????度量包含X的事務中同時出現Y的頻率

????例：對于關聯規則{Milk, Diaper} →{Beer}

????confidence({Milk, Diaper} →{Beer})= 2/3

強關聯規則

????用戶自行設定最小置信度閾值min _conf，置信度大于min _conf的規則稱為強關聯規則

????例：設min _conf = 0.5，則{Milk, Diaper} →{Beer}為強關聯規則

四、APriori算法

生成頻繁項集

核心思想：廣度優先搜索，自底而上遍歷，逐步生成候選集與頻繁項集

反單調性原理：如果一個項集是頻繁的，則它的所有子集一定也是頻繁

成立原因：

?????????X, Y: X ? Y → Support X ≥ Support(Y)

????????依據該性質，對于某k+1項集，只要存在一個k項子集不是頻繁項集， 則可以直接判定該項集不是頻繁項集

?

算法步驟

????????連接步：從頻繁 K-1 項集生成候選K項集

????????剪枝步：從候選 K 項集篩選出頻繁K項集

舉個例子：

下圖為某商店的用戶購買記錄，共有9個事務，A-Priori假定事務中的項按字典次序存放。

(1) 在算法的第一次迭代，每個項都是候選1項集的集合的成員。算法簡單地掃描所有的事務，對每個項的出現次數計數

(2) 設最小支持度計數=2，可以確定頻繁1項集的集合

(3) 使用L1? L1產生候選2項集的集合

(4) 掃描數據集，計算中每個候選項集的支持度

(5)最小支持度計數=2，確定頻繁2項集的集合

(6) 使用L2? L2產生候選3項集的集合

(7) 掃描數據集，計算中每個候選項集的支持度

(9) 使用L3? L3產生候選4項集的集合C4，盡管連接產生結果 ?，這個項集被

剪去，因為它的子集 不是頻繁的。則C4 = ? ,因此算法終止，找出了所有的

頻繁項集如下

五、生成規則

關聯規則挖掘的第二步：如何從頻繁項集中生成規則？

若{A,B,C,D}是頻繁項集, 候選規則有14種:

ABC →D, ABD →C, ACD →B, BCD →A,

A →BCD,B →ACD, C →ABD, D →ABC

AB →CD,AC → BD, AD → BC, BC →AD,BD →AC, CD →AB,

若, 則有 種候選的關聯規則(忽略L → 和?→ L)

六、辛普森悖論