1.概念
1.1 引论
关联规则（AssociationRules）是无监督的机器学习方法，用于知识发现，而非预测。
关联规则的学习器（learner）无需事先对训练数据进行打标签，因为无监督学习没有训练这个步骤。缺点是很难对关联规则学习器进行模型评估，一般都可以通过肉眼观测结果是否合理。
关联规则主要用来发现Pattern，最经典的应用是购物篮分析，当然其他类似于购物篮交易数据的案例也可以应用关联规则进行模式发现，如电影推荐、约会网站或者药物间的相互副作用。
1.2 例子 - 源数据
点击流数据。
不同的Session访问的新闻版块，如下所示：
| Session ID | List of media categories accessed |
| 1 | {News, Finance} |
| 2 | {News, Finance} |
| 3 | {Sports, Finance, News} |
| 4 | {Arts} |
| 5 | {Sports, News, Finance} |
| 6 | {News, Arts, Entertainment} |
1.3数据格式
关联规则需要把源数据的格式转换为稀疏矩阵。
把上表转化为稀疏矩阵，1表示访问，0表示未访问。
| Session ID | News | Finance | Entertainment | Sports |
| 1 | 1 | 1 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 |
| 5 | 1 | 1 | 0 | 1 |
| 6 | 1 | 0 | 1 | 0 |
1.4术语和度量
1.4.1项集 ItemSet
这是一条关联规则：
括号内的Item集合称为项集。如上例，{News, Finance}是一个项集，{Sports}也是一个项集。
这个例子就是一条关联规则：基于历史记录，同时看过News和Finance版块的人很有可能会看Sports版块。
{News,Finance} 是这条规则的Left-hand-side (LHS or Antecedent)
{Sports}是这条规则的Right-hand-side (RHS or Consequent)
LHS（Left Hand Side)的项集和RHS（Right Hand Side）的项集不能有交集。
下面介绍衡量关联规则强度的度量。
1.4.2支持度 Support
项集的支持度就是该项集出现的次数除以总的记录数（交易数）。
Support({News}) = 5/6 = 0.83
Support({News, Finance}) = 4/6 =0.67
Support({Sports}) = 2/6 = 0.33
支持度的意义在于度量项集在整个事务集中出现的频次。我们在发现规则的时候，希望关注频次高的项集。
1.4.3置信度 Confidence
关联规则 X -> Y 的置信度 计算公式
规则的置信度的意义在于项集{X，Y}同时出现的次数占项集{X}出现次数的比例。发生X的条件下，又发生Y的概率。
表示50%的人 访问过{News, Finance}，同时也会访问{Sports}
1.4.4提升度 Lift
当右手边的项集（consequent）的支持度已经很显著时，即时规则的Confidence较高，这条规则也是无效的。
举个例子：
在所分析的10000个事务中,6000个事务包含计算机游戏,7500个包含游戏机游戏,4000个事务同时包含两者。
关联规则（计算机游戏，游戏机游戏） 支持度为0.4，看似很高，但其实这个关联规则是一个误导。
在用户购买了计算机游戏后有 （4000÷6000）0.667 的概率的去购买游戏机游戏，而在没有任何前提条件时，用户反而有（7500÷10000）0.75的概率去购买游戏机游戏，也就是说设置了购买计算机游戏这样的条件反而会降低用户去购买游戏机游戏的概率，所以计算机游戏和游戏机游戏是相斥的。
所以要引进Lift这个概念，Lift(X->Y)=Confidence(X->Y)/Support(Y)
规则的提升度的意义在于度量项集{X}和项集{Y}的独立性。即，Lift(X->Y)= 1 表面 {X}，{Y}相互独立。[注：P(XY)=P(X)*P(Y),if X is independent of Y]
如果该值=1,说明两个条件没有任何关联,如果<1,说明A条件(或者说A事件的发生)与B事件是相斥的,一般在数据挖掘中当提升度大于3时,我们才承认挖掘出的关联规则是有价值的。
最后，lift(X->Y) = lift(Y->X)
1.4.5出错率 Conviction
Conviction的意义在于度量规则预测错误的概率。
表示X出现而Y不出现的概率。
例子：
表面这条规则的出错率是32%。
1.5生成规则
一般两步：
- 第一步，找出频繁项集。n个item，可以产生2^n- 1 个项集（itemset）。所以，需要指定最小支持度，用于过滤掉非频繁项集。
- 第二部，找出第一步的频繁项集中的规则。n个item，总共可以产生3^n - 2^(n+1) + 1条规则。所以，需要指定最小置信度，用于过滤掉弱规则。
第一步的计算量比第二部的计算量大。
2.Apriori算法
Apriori Principle
如果项集A是频繁的，那么它的子集都是频繁的。如果项集A是不频繁的，那么所有包括它的父集都是不频繁的。
例子：{X, Y}是频繁的，那么{X}，{Y}也是频繁的。如果{Z}是不频繁的，那么{X,Z}, {Y, Z}, {X, Y, Z}都是不频繁的。
生成频繁项集
给定最小支持度Sup，计算出所有大于等于Sup的项集。
第一步，计算出单个item的项集，过滤掉那些不满足最小支持度的项集。
第二步，基于第一步，生成两个item的项集，过滤掉那些不满足最小支持度的项集。
第三步，基于第二步，生成三个item的项集，过滤掉那些不满足最小支持度的项集。
如下例子：
| One-Item Sets | Support Count | Support |
| {News} | 5 | 0.83 |
| {Finance} | 4 | 0.67 |
| {Entertainment} | 1 | 0.17 |
| {Sports} | 2 | 0.33 |
| Two-Item Sets | Support Count | Support |
| {News, Finance} | 4 | 0.67 |
| {News, Sports} | 2 | 0.33 |
| {Finance, Sports} | 2 | 0.33 |
| Three-Item Sets | Support Count | Support |
| {News, Finance, Sports} | 2 | 0.33 |
规则生成
给定Confidence、Lift 或者 Conviction，基于上述生成的频繁项集，生成规则，过滤掉那些不满足目标度量的规则。因为规则相关的度量都是通过支持度计算得来，所以这部分过滤的过程很容易完成。
Apriori案例分析（R语言）
1. 关联规则的包
arules是用来进行关联规则分析的R语言包。
library(arules) 2. 加载数据集
源数据：groceries 数据集，每一行代表一笔交易所购买的产品（item）
数据转换：创建稀疏矩阵，每个Item一列，每一行代表一个transaction。1表示该transaction购买了该item，0表示没有购买。当然，data frame是比较直观的一种数据结构，但是一旦item比较多的时候，这个data frame的大多数单元格的值为0，大量浪费内存。所以，R引入了特殊设计的稀疏矩阵，仅存1，节省内存。arules包的函数read.transactions可以读入源数据并创建稀疏矩阵。
groceries <- read.transactions("groceries.csv", format="basket", sep=",")format=c("basket", "single")用于注明源数据的格式。如果源数据每行内容就是一条交易购买的商品列表（类似于一行就是一个购物篮）那么使用basket；如果每行内容是交易号+单个商品，那么使用single。
cols=c("transId", "ItemId") 对于single格式，需要指定cols，二元向量（数字或字符串）。如果是字符串，那么文件的第一行是表头（即列名）。第一个元素是交易号的字段名，第二个元素是商品编号的字段名。如果是数字，那么无需表头。对于basket，一般设置为NULL，缺省也是NULL，所以不用指定。
signle format的数据格式如下所示，与此同时，需要设定cols=c(1, 2)
