[comment]: # 机器学习实战 - 读书笔记(11) - 使用Apriori算法进行关联分析
前言
最近在看Peter Harrington写的“机器学习实战”，这是我的学习心得，这次是第11章 - 使用Apriori算法进行关联分析。
基本概念
关联分析（association analysis）或者关联规则学习（association rule learning）
这是非监督学习的一个特定的目标：发现数据的关联（association）关系。简单的说，就是那些数据（或者数据特征）会一起出现。
关联分析的目标包括两项：发现频繁项集和发现关联规则。首先需要找到频繁项集，然后才能获得关联规则。
频繁项集告诉我们哪些项集会经常出现，以及出现的支持概率。
关联规则告诉我们频繁项集中出现的关联规则，哪些原因项的出现决定另外一些结果项的出现，以及规则的可信概率。关联（association）
一个关联是一个满足最小支持度的项集。关联规则（association rule）
关联规则
Where \\
\qquad X,Y\subseteq I \text{ and } X\cap Y=\emptyset \\
\qquad \text{I: an items set}
\]
前提集（antecedent）
也称为前件、左手边。是关联规则\(X \Rightarrow Y\)的\(X\)部分。结果集（consequent）
也称为前后件、右手边。是关联规则\(X \Rightarrow Y\)的\(Y\)部分。项集 (items set)
一个项集包含一个或者多个元素项。
比如：{a} {b} {c} {ab} {ac} {bc} {abc}是7个项集。子集
{a} {b} {c} {ab} {ac} {bc} 都是的{abc}一个子集。超集
与子集相反：{ab}是{a}的一个超集。支持度（support）
关联项集的频繁度。可信度（confidence）
关联规则的可信度。
核心算法
Apriori算法：生成频繁项集
Apriori 是 A priori, “一个先验”的意思。可以说是一种发现关联的优化算法。
以购买商品为例，每条数据是一个交易的商品清单。我们是否可以发现哪些商品组合更容易出现？
客户可能购买1个商品，或者最多n个商品，如果商店一共有m个商品，那么共有种 \(\textstyle \coprod_{i=1}^n {m + 1 -i}\) 组合方式。
计算每种组合方式的出现概率虽然看起来简单，但是效率非常低。
Apriori生成频繁项集算法的原理说明
如果一个项集是非频繁集，那么它的所有超集也是非频繁的。
假设数据集中只有4元素：1234
可能的关联规则根据结果项的项数分为4个level：
发现{4}是一个低支持度项集，则在Level 2中剪除含有{4}的项集，以此类推。
Level 1： 1; 2; 3; 4
Level 2： 12; 13; 14; 23; 24; 34
Level 3： 123; 124; 134; 234
Level 4： 1234-
输入
- DateSet
- 最小支持度：Minimum Support
-
输出
- 项集[项数 - 1, 项集]
- 项集的支持度[项集, 支持度]
逻辑过程
因此，它先计算1个元素的概率，去掉不满足最小支持度的项集，得到项集集合C1和每个项集的支持度；
然后在项集集合C1的基础上，找2个元素的支持度（这时将不会考虑去掉的项集，所以性能会优化），再去掉不满足最小支持度的2项项集，得到项集C2和每个项集的支持度；
以此类推，直到得到项集Cm和每个项集的支持度。
Apriori算法：从频繁项集中生成关联规则
Apriori生成关联规则算法的原理说明
在一个频繁项集中，如果p -> h是一条低可信度规则，那么，所有其它以h的超集作为后件的规则，可信度也会较低。
关联规则是根据每个项集生成的。我们举个有4个项的项集为例：
项集：1234
可能的关联规则根据结果项的项数分为3个level：
发现[123 > 4]是一个低可信度规则，则在Level 2中剪除结果项集中含有{4}的规则，以此类推。
Level 1： 234 > 1; 134 > 2; 124 > 3; 123 > 4
Level 2： 34 > 12; 24 > 13; 23 > 14; 14 > 23; 13 > 24; 12 > 34
Level 3： 4 > 123; 3 > 124; 2 > 134; 1 > 234-
generateRules
- 输入
- 频繁项集[项数 - 1, 项集]
- 项集的支持度[项集, 支持度]
- 最小可信度：Minimum confidence
- 输出
- 关联规则[因项集，果项集，可信度]
- 逻辑过程
- 输入
对每个Level的项集（Level>0）：
对当前Level的每个项集：
获取项集的元素List.
如果Level = 1(2个项数的项集)：
calculateConfidence(当前项集，元素List，项集的支持度，关联规则, 最小可信度)
如果Level > 1(至少3个项数的项集)：
rulesFromConsequence(当前项集，元素List，项集的支持度，关联规则, 最小可信度)
- calculateConfidence
- 输入
- 项集
- 目标项集List
- 项集的支持度[项集, 支持度]
- 关联规则[因项集，果项集，可信度]
- 最小可信度：Minimum confidence
- 输出
- 有效目标集
- 逻辑过程
- 输入
对每个目标项集
计算当前目标项集在当前项集上的可信度。
如果可信度大于最小可信度:
把[当前项集 - 目标项集, 目标项集, 可信度]加入关联规则；
把当前目标项集加入有效目标集。
返回有效目标集
- rulesFromConsequence
- 输入
- 项集
- 目标项集List
- 项集的支持度[项集, 支持度]
- 关联规则[因项集，果项集，可信度]
- 最小可信度：Minimum confidence
- 输出
- 无
- 逻辑过程
- 输入
得到目标项集长度m.
如果当前项集元素的长度 > m + 1:
得到目标项集元素个数为m + 1的目标项集List。
有效目标集 = calculateConfidence(当前项集，目标项集，项集的支持度，关联规则, 最小可信度)
如果有效目标集的长度 > 1:
rulesFromConsequence(当前项集，有效目标集，项集的支持度，关联规则, 最小可信度)。
核心公式
- 支持度（support level）:
where \\
\qquad S(C, X) : 项集C的支持度 \\
\qquad C : 项集 \\
\qquad X : 数据集
\]
- 可信度（confidence level）: 一条规则P -> H的可信度定义为:
where \\
\qquad C(P, H) : 关联规则P -> H的可信度 \\
\qquad P : 项集 \\
\qquad H : 项集 \\
\qquad support(P) : 项集P的支持度 \\
\qquad support(P | H) : 项集P,H并集的支持度
\]
参考
- Machine Learning in Action by Peter Harrington