關聯規則

購物籃資料:

TID	項集
1	{面包, 牛奶}
2	{面包, 尿布, 啤酒, 雞蛋}
3	{牛奶, 尿布, 啤酒, 可樂}
4	{面包, 牛奶, 尿布, 啤酒}
5	{面包, 牛奶, 尿布, 可樂}

關聯分析除了用于購物籃資料外, 也可以用于生物資訊學, 醫療診斷, 網頁挖掘和科學資料分析等.

在對購物籃資料進行關聯分析時, 需要處理兩個關鍵的問題:

- 大資料集計算代價很高

- 發現的模式可能是偶然發生的, 不可信

關聯規則算法

1. 将購物籃資料轉化為二進制形式來表示, 如下表, 出現過為1, 沒出現為0

TID	面包	牛奶	尿布	啤酒	雞蛋	可樂
1	1	1
2	1	1	1	1
3	1	1	1
4	1	1	1	1
5	1	1	1	1

2. 計算項集和支援度計數

- 項集: 包含k個項的集合稱為k項集, k=0,1,… 如:

- 1項集: {面包}

- 2項集: {面包, 牛奶}

- 3項集: {面包, 牛奶, 啤酒}

- 支援度計數: 包含該項集的事務的個數(即購物籃中該項集出現過幾次), 如上例中:

- {面包, 牛奶}的支援度計數為3

- {啤酒, 尿布}的支援度計數為3

1. 求解關聯規則的支援度和置信度

定義:

- 關聯規則:

形如項集X–>項集Y的表達式, 其中X與Y無交集, 則稱之為一個關聯規則

- 支援度:

一個關聯規則X–>Y的支援度s=該規則組成的項集(X+Y)的支援度計數/總事務數.

如上例中: {面包, 牛奶} –> {啤酒} 的支援度={面包, 牛奶, 啤酒}的支援度計數1/總事務數5=0.4

- 置信度:

一個關聯規則X–>Y的置信度=X+Y的支援度計數/X的支援度計數.

如上例中: {面包, 牛奶} –> {啤酒} 的支援度={面包, 牛奶, 啤酒}的支援度計數1/{面包, 牛奶} 的支援度3 = 1/3

注意:

為什麼要用支援度和置信度?

- 支援度很低則說明是偶然發生的規則, 多半無意義, 是以支援度常用來删除那些無意義的規則

- 置信度越高, Y在包含X的事務中出現的可能性就越大, 這樣推理具有可靠性

1. 關聯規則發現

定義:

- 關聯規則發現

給定事務集合T, minsup(支援度門檻值), minconf(置信度門檻值), 找出大于門檻值的規則的過程就是關聯規則發現

- 頻繁項集

支援度大于支援度門檻值的項集稱為頻繁項集

- 強規則(強關聯規則)

從頻繁項集中提取出的高置信度的規則稱為強規則

- 先驗原理

如果一個項集是頻繁的, 則它的所有子集也是頻繁的

如果一個項集是非頻繁的, 則它的所有超集(包含該項集的項集)也是非頻繁的

算法:

- 蠻力法: 求出每個可能的規則的支援度和置信度, 挨個剔除.

這個方法代價很高, 從d個項中提取的可能規則總數為3d−2d+1+1

3

d

−

2

d

+

1

+

1

- Apriori算法

1. 産生頻繁項集

1. 給定事務T, minsup支援度門檻值, minconf置信度門檻值
2. 掃描一遍T, 對每個一項集計數, 得出表C1={a:3, b:4, c:5, ...}.
   挑出大于minsup的一項集F1假設為[{a},{b},{c},{d}]
3. 根據F1得出所有二項集=[{a,b}, {a,c}, {a,d}, ...{c,d}]
4. 在掃描一遍T, 從3中産生的二項集篩出大于minsup的二項集F2假設為[{a, b}, {a,c}]
5. 根據F2得出所有三項集=[{a,b,c}], 重複3和4的過程, 直到不再産生新的頻繁項集算法結束