数据挖掘学习日记3·关联规则挖掘
目录
1 关联规则挖掘概念
一、定义
关联规则反映一个事物与其它事物之间的依赖和相互关联性。
经典例子为购物篮分析，通过分析购物篮数据来分析顾客经常同时购买哪些商品（购买习惯）。这是BI(Business Intelligence)的一项应用。
二、目的
关联规则挖掘的目的是从数据中发现有趣的规律。
“有趣”是指发现的规律是有意义的、能够指导实践的。
上述购物篮分析有一个举烂了的例子：早期沃尔玛超市的一次购物篮分析发现，啤酒和尿布位于榜单的第三位，即部分顾客经常同时购买啤酒和尿布。其原因竟然是，下班回家的丈夫经常会在顺路帮妻子购买尿布的同时，买些喜欢的啤酒犒劳自己。
听说之后沃尔玛超市立刻就推出了啤酒和尿布捆绑消费的优惠活动，大获好评。
总之，沃尔玛超市从消费数据中提取的这项规律显然是有现实意义的，是“有趣”的。
另外还可以做以下关联思考：
1. 购买了笔记本电脑后，下一步会买什么？
当然是鼠标和键盘了，又或者是一个相匹配的电脑包/保护套。
因此，很多商家都推出了套餐购买方案，买电脑，送相关套装。
2. 我们如何对文档进行分类？
可以尝试提取出文档的关键词，比较文档之间关键词的关联关系，再通过聚类分析等方法进行分类。
我们还可以从购物篮分析的例子中得到引申。在网购中，也悄悄进行着购物篮分析，并为您推荐相关商品。
另外还有视频网站、新闻网站等等，通过分析您的行为与其它用户行为的关联性，进行相关推荐。
2 关联规则基本模型
2.1 基本概念
先用通俗的语言进行介绍，不甚准确，仅帮助理解。
现在开始进行购物篮分析，分析A，D商品被同时购买的可能性。
装着A，D商品的购物篮称为项集，因为现在购物篮中只有两件商品，故叫做“2项集”。
假设我们拥有无限多的购物篮，且顾客结算后都保留购物篮的拷贝，那么将所有的购物篮放在一起做统计（当然你的也是），发现：
同时装着A，D商品的购物篮占总购物篮数的50%，装有A商品的购物篮有60%的可能也装有D商品！
可你还记得做这该死的统计之前，你曾和朋友打赌，只要这两项指标超过50%，就承认这件事是绝对有趣的……
很遗憾，你必须苦着脸承认了。
咳咳。
现在对以上出现的概念给出系统的介绍：
设 I={i1, ..., im} 为所有项目的集合，D为数据库，事务T是一个项目子集，每一个事务具有唯一的事务标识TID。
- 频繁项集：频繁出现在数据集中的模式。上述沃尔玛的例子中，频繁出现在交易数据集中的“啤酒”和“尿布”的集合就是频繁项集。
- 项集：项的集合称为项集，设为集合A。包含k个项的项集称为k项集。
- 项集的出现频度（相对支持度）：包含项集的事务数，简称为项集的频度、支持度计数或计数（下称出现频度）。
- 规则兴趣度的两种度量：支持度，置信度。
- 支持度（相对支持度）：项集A在事务数据库中出现的次数占D中总事务的百分比。即A中所有元素在D中同时出现的概率。有：
support(A蕴含D) = P(A ∪ D)
反映规则的有用性：k项集中元素的关联性。
- 置信度（可信度）：A出现的条件下，D出现的概率，即
confidence(A蕴含D) = P( D | A )
反映规则的有趣性：结论的可靠性。
- 最小支持阙值&最小置信度阙值：由专家确定。当支持度和置信度分别满足最小阙值时，关联规则被认为是有趣的。
若项集I的相对支持度满足预定义的最小支持度阙值，则I是频繁项集(frequent itemset)；若支持度和置信度同时满足最小支持度阙值和最小置信度阙值，则规则被称为强规则。
▲ 其中需要特别注意的是，支持度没有方向性，而置信度是有方向的。
现在将数据集整理如下，令min_sup = 50%，min_conf = 50%：
则有：
support(A蕴含D) = P(A∪D) = 3/5 = 60%
confidence(A蕴含D) = P(D | A) = 100%
confidence(D蕴含A) = P(A | D) = 3/4 = 75%
则关联规则Association rules：
(1) A → D （60%,100%）
(2) D → A （60%,75%）
故，可认为A，D之间的关联规则是有用且可信的。
其中，(1)式表示商品A和商品D同时购买的可能性为60%，而购买A的顾客中所有的人都会购买商品D；
(2)式表示商品A和商品D同时购买的可能性为60%，而购买D商品的顾客中有75%的人会购买商品A。
(1)(2)两式应证了支持度的无方向性以及置信度的方向性。
举一个例子加深理解：
买电脑的时候经常会推荐购买包含电脑包的套餐，但购买电脑包时不见得会推荐你买一个电脑吧？
2.2 关联规则的挖掘步骤
- 找出所有的频繁项集：根据定义，这些项集的每一个频繁出现的次数至少与预定义的最小出现频度min_sup一样。
- 由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。
3 Apriori算法
3.1 介绍
Apriori算法是一种发现频繁项集的基本算法，是Agrawal和R.Srikant于1994年提出的，为布尔关联规则挖掘频繁项集的原创性算法。
这里回顾几个概念：
- 频繁项集：频繁出现在数据集中的模式。
- 布尔关联规则：项集中的每一项都用一个布尔值表示的关联规则。
- 支持度
- 相对支持度：由support(A蕴含B) = P(A∪B)定义
- 绝对支持度：出现频率，又称支持度计数，简称为频率、计数。
Apriori算法使用逐层搜索的迭代方法，使用k项集（记作Lk）探索(K-1)项集（记作Lk-1）。
为提高频繁项集逐层产生的效率，使用先验性质压缩搜索空间：
频繁项集的所有非空子集也一定是频繁的。——这一类特殊性质被称为反单调性。
3.2 实现步骤
1. 令k=1，创建初始候选1项集C1。
2. 扫描C1，对每个候选项计算支持计数（在数据库D中的出现频率）。
3. 去除支持度计数小于最小支持度计数的项，得到L1。
4. 连接步：为找出Lk，通过Lk-1自连接产生候选k项集合，记为Ck。
5. 剪枝步：利用先验性质进行剪枝，从Ck中剔除包含非频繁项集的项（即Lk-1的补集），得到频繁k项集，记为Lk。
6. 若步骤5得到的Ck集合不为空，返回步骤4继续执行；否则，得到所有频繁项集，算法终止。
举书上的例子如下：
该数据库有9个事务，设最小支持度计数为2，频繁项集的产生过程如图6.2。
3.3 伪代码
/***
输入：
* D：事务数据库
* min_sup：最小支持度阈值
输出：L，D中的频繁项集
***/
/**主函数**/
procedure main()
//1 从事务数据库D找出频繁1项集
L1 = find_frequent_1itemset(D);
//2 扫描
for(k=2;Lk-1≠空集;k++){
//2.1 调用函数：从频繁k-1项集Lk-1得到候选k项集
Ck = aproiri_gen(Lk-1);
//2.2 分别计算候选k项集中项的支持度
for each 事务 t∈D{ //遍历事务数据库中的每一个事务t
Ct = subset(Ck,t); //得到事务t在候选集Ck中的子集
for each 候选 c∈Ct;
c.count++; //累加计数
}
//2.3 剪枝：去除小于最小支持度阈值min_sup的项
Lk = {c(Ck|c.count >= min_sup)}
}
//3 返回频繁k项集
return L = ∪kLk;
/**产生候选k项集**/
procedure apriori_gen(Lk-i:frequent(k-1) itemset)
for each 项集 l1∈Lk-1
for each 项集 l2∈Lk-1
if (l1[1] = l2[1])∧...∧(l1[k-2] = l2[k-2])∧(l1[k-1] = l2[k-2]) then
c = l1 ▷◁ l2;
//调用函数：若候选k项集当前项包含非频繁项，则删除该项
if has_infrequent_subset(c,Lk-1) then
delete c;
//否则将该项加入频繁k项集
else add c to Ck;
return Ck;
/**
判断目标集合是否包含非频繁项
若包含返回TRUE，否则返回FALSE
**/
procedure has_infrequent_subset(c:candidate k itemset; Lk-1:frequent(k-1)itemsets)
for each(k-1)subset s of c
if s 不属于 Lk-1 then
return TRUE;
return FALSE
注：文章内容中未说明的引用部分，为教材《概念与技术（中文第三版）》和课堂讲义的整理。