机器学习入门笔记12

关联分析

系列文章

关联分析

关联分析通过深入分析数据集，寻找事物间的关联性，挖掘频繁出现的组合，并描述组合内对象出现的模式和规律。

关联分析技术也可应用于智能推荐系统。

关联分析基本概念

给定以下用户的购买商品信息：

userpurchased
1(A, B, C, E)
2(A, E, D)
3(A, C, E)
4(B, C)
5(B, C, D)
6(A, C, E)
7(A, B, C, D, E)

在分析前，以下是一些基本的概念：

由以上基本概念，可以引出以下核心概念：

\\[ P(Y|X) = \frac {P(XY)} {P(X)} \\]

Apriori算法

算法原理

Apriori算法是一个经典的强关联算法，其步骤为：

  1. 设定最小支持度和最小置信度
  2. 根据最小支持度找出所有的频繁项集
  3. 根据最小置信度发现强关联规则

接下来以上文列出的简单数据演示Apriori算法的计算过程。

首先，设定最小支持度为 50% ，最小置信度为 85% 。

然后根据最小支持度，找出所有的频繁项集。例如，项集 \\( {B,C} \\) 的支持度为 60% ，大于该最小支持度，属于频繁项集，可能发现其中蕴含的关联。

除了根据排列组合依次计算每个组合的置信度，Apriori算法采用了一种更好的思路：先找出所有长度为 1 的项集中的频繁项集，再对得到的频繁项集排列组合，找出这部分长度为 2 的项集中的频繁项集，以此类推。既然长度为 \\( n-1 \\) 的项集都不是频繁项集，那么它参与构成的长度为 \\( n \\) 的项集肯定更不是。

以上示例的数据中，长度为 1 的频繁项集只有 {A}、{B} 和 {C} ，且它们构成的长度为 2 的频繁项集有 {A,C} 和 {B,C} ，进一步构成的长度为 3 的频繁项集只有 {A,C,E} 。关联只可能从找到的长度大于等于 2 的项集中找到。

最后一步从各个频繁项集中推导出可能的关联规则，再利用最小置信度来检验这些关联规则是否为强关联规则。

例如，频繁项集 {A,C,E} 可能推导出 6 条关联规则：

关联规则置信度最小置信度检验是否删除
{A,C}→{E}1通过保留
{A,E}→{C}0.75未通过删除
{C,E}→{A}0.1通过保留
{A}→{C,E}0.75未通过删除
{C}→{A,E}0.75未通过删除
…………

暂时不想算了，编数据有点麻烦

其中，置信度计算中，分子是项集 {A,C,E} 出现的次数，分母是前件在所有事务中出现的次数。

对其它频繁项集使用此操作，得到所有的强关联规则。

代码实现：使用apyori库

apyori 库是一个专门用来实现 Apriori 算法的库，它使用较为简单。

可以通过 pip 安装该库：

(sci) PS D:\MachineLearning\demo> pip install apyori

如果通过代码使用该库，其示例为：

from apyori import apriori
transactions = [
    ['Item A', 'Item B', ...],
    ['Item A', 'Item C', ...],
    ...
]
results = list(apriori(transactions))

apriori() 函数可以通过 min_support 和 min_confidence 参数设置最小支持度和最小支持度。返回的结果可以通过打印相关变量查看。

安装完成 apyori 库后，它同时会在本地提供名为 apyori-run.exe 的命令行工具。可以使用该工具便捷地完成计算，而不需要任何代码。

可以通过 -h 命令行参数查看它支持的所有参数。

以下给出了一个调用示例：

D:\MachineLearning\demo>apyori-run -s 0.2 -c 0.9 -d "," < tvshow.csv
{"items": [""], "support": 0.9998968008255934, "ordered_statistics": [{"items_base": [], "items_add": [""], "confidence": 0.9998968008255934, "lift": 1.0}]}
{"items": ["", "Sex Education"], "support": 0.25552115583075335, "ordered_statistics": [{"items_base": ["Sex Education"], "items_add": [""], "confidence": 0.9995962858296327, "lift": 0.9996994539879389}]}

得到的是一个 json 格式的文件，可以将其读入并解析。

（这个数据集有点糟糕）

代码实现：使用mlxtend库

mlxtend 是一个机器学习的扩展库（machine learning extensions），提供了一些常用的算法。

该库可以通过 pip 安装，如果安装失败，可以在 https://pypi.org/project/mlxtend/ 上下载源文件到本地安装：

(sci) PS D:\MachineLearning\demo> tar -zxvf .\mlxtend-0.19.0.tar.gz
(sci) PS D:\MachineLearning\demo> cd .\mlxtend-0.19.0\
(sci) PS D:\MachineLearning\demo\mlxtend-0.19.0> python .\setup.py install

使用 mlxtend 库中的函数，同样可以挖掘出强关联规则。首先，需要对数据预处理，将原始数据转换为布尔值：

from mlxtend.preprocessing import TransactionEncoder
temodel = TransactionEncoder()
data = temodel.fit_transform(transactions)

得到的结果是一个只包含布尔值的二维数组。接下来将其转换为 DateFrame ：

data = pd.DataFrame(data, columns=temodel.columns_)

此时得到的数据类型已经可以使用 mlxtend 里的函数来计算了：

from mlxtend.frequent_patterns import apriori
items = apriori(data, min_support=0.2, use_colnames=True)

可以利用最小置信度在得到的频繁项集中挖掘强关联规则：

from mlxtend.frequent_patterns import association_rules
rules = association_rules(items, min_threshold=0.7)

置信度除了用之前的公式计算外，还可以使用以下公式：

\\[ \text{conf}(\{A\}\rightarrow \{B\})=\frac{\text{support}({A,B})}{\text{support}(A)} \\]

除此之外，输出结果中还包含了 lift 、leverage 、conviction 几项，它们都是用来衡量关联度强弱的。

lift 代表提升度，计算公式为：

\\[ \text{lift}(\{A\}\rightarrow \{B\})=\frac{\text{support}(\{A,B\})}{\text{support}(A)\times \text{support}(B)} \\]

该值越大，代表两者的关联度越强。

leverage 代表杠杆率，计算公式为：

\\[ \text{leverage}(\{A\}\rightarrow \{B\})=\text{support}(\{A,B\})- \text{support}(A)\times \text{support}(B) \\]

该值越大，同样代表两者的关联度越强。

conviction 代表确信度，计算公式为：

\\[ \text{conv}(\{A\}\rightarrow \{B\})=\frac{1-\text{support}(B)}{1-\text{conf}(\{A\}\rightarrow \{B\})} \\]

该值越大，同样代表两者的关联度越强。