關聯規則分析-數據挖掘入門

關聯規則分析主要用於分析Market-Based Problems，比如你在商城裡買了一本書，然後商城會推薦你買另一本書（這本書是通過推算買了上本書的人又會買的一本）。類似的例子有很多。現在簡單介紹一下關聯規則分析中名詞定義：

Item(I):Bread, Milk, Chocolate, Butter …(項，可理解為某商品)

Transaction(T):A non-empty subset of all items

.(可理解為購買小票，或某一條購買記錄上的商品集合，或資料庫里的一條購買記錄)

Itemset(項集):A set of items is referred to as itemset.

1.什麼是支持度？

Support(支持度)：The support of an item (or itemset) X is the percentage of transactions in which that item (or itemset) occurs.（其實就是X發生的頻率，也可以理解概率）

tips:當itemset越來越大的時候，我們會發現支持度是越來越小（單調不增的）

引申： 關聯規則的支持度，其實和上述說的支持度是一樣的，即同時發生X,Y的頻率。

2.什麼是置信度？

confidence(置信度)：The confidence of an association rule X→Y is the ratio of the number of transactions that contain {X, Y} to the number of transactions that contain X.(其實就是條件概率：P(Y|X) )

等價於：

明白了支持度和置信度的含義，現在我就來說下這兩個值有什麼作用？

3.支持度和置信度在關聯規則中的含義：

Support measures how often the rule occurs in the dataset.

（是否頻繁，比如同時買麵包和牛奶的人有多頻繁？）

Confidence measures the strength of the rule.(規則的強度，比如買了麵包的人又去買牛奶是否強相關？)

關聯的規則就是通過關聯度和支持度來反映關聯性，可以通過設定兩個閾值來量化這種規則。

Minimum support σ

Minimum confidence Φ

頻繁項集：A frequent (large) itemset is an itemset with support larger than σ.（頻繁項集就是說他的頻率大於最小支持度）

強相關：A strong rule is a rule that is frequent and its confidence is higher than Φ.

當給定I, D, σ and Φ找到且滿足規則，這就是我們所說的相關規則的挖掘。

4.Apriori演算法：

首先介紹下為什麼需要演算法，有很多人看了上面內容會覺得直接算不就可以了嗎？事實上，當item足夠多的時候，會產生組合爆炸，即兩個兩個組合，三個三個組合，四個四個組合...都要通過掃一遍，對於資料庫的壓力是非常大的，這時候我們就採用了apriori演算法，個人理解其實是一種思想。

Apriori演算法核心思想：

1. A subset of a frequent itemset must be frequent.
   (頻繁項的非空子集肯定頻繁)

   {Milk, Bread, Coke} is frequent → {Milk, Coke} is frequent

2. The supersets of any infrequent itemset cannot be frequent.(如果一個項不頻繁，那麼他的超項肯定不頻繁)
   {Battery} is infrequent → {Milk, Battery} is infrequent

舉例：如果B不頻繁，那麼BC,BD,BCD,ABCD都不頻繁。在資料庫掃描尋找頻繁項集的時候，就可以排除掃描BC,BD,BCD,ABCD，從而減輕資料庫的負擔。

Apriori框圖：

一層一層掃描，其中比較難理解的是L(k)如何生成C(k+1)。C(k+1)候選集盡量沒有冗餘的非頻繁集。

那麼apriori演算法是如何生成C(k+1)的呢？

X,Y集合的前K-1項都相同，K項不同，那麼把K項搬到前一項集即可。但是也有生成錯誤的時候，比如最後一個，但是此時C(3)也在K(3)當中。

推薦閱讀：