基于Apriori 算法的关联规则分析应用

殷丽凤，李明状

（大连交通大学软件学院，辽宁 大连 116028）

目前，随着整个社会进入到信息化时代，大量的信息和数据成为了当前时代的特征。在大数据时代下，数据就是人类的无形财富和资产。在不断产生海量数据的情况下，必须利用新的技术手段和工具来处理海量的数据集，从而更加智慧地提取数据中有用的信息。关联规则挖掘技术是数据挖掘最重要的方法之一，凡是涉及从数据中获取知识的问题，关联规则挖掘都可能成为有力的工具。现如今关联规则挖掘已经应用到各行各业，例如销售行业、金融、教育等。文中利用关联规则挖掘中最经典的Apriori 算法，使用公共数据集MovieLens进行电影标签推荐的研究。

1 数据挖掘和关联规则

1.1 数据挖掘

数据挖掘技术是数据分析方法，它从大量的、模糊的、有噪音的数据中挖掘出具有潜在价值的、隐藏的、未知的概念、规则和模式。

1.2 关联规则

关联规则挖掘是一种处理大量数据集中各项之间隐藏的属性关系的方法。假设两项或者多项属性之间存在一定关联，则一项属性就能按照其他属性进行判定[1]。下面给出项、项集、项集的频数、支持度、置信度、作用度、最小支持度和最小置信度等关联规则的相关概念。

1）项与项集

设I={i1,i2,…,im}，i1,i2,…,im称为项，集合I称为项集。

2）项集的频数

包括项集的事务数称为项集的频数，事务数代表数据集中的记录数，数据库中的一条记录称为事务，频数被用于支持度的计数[3]。

3）支持度（Support）

关联规则X→Y的支持度反映了所有事务集中{X,Y}出现的可能性[2],公式如下所示。

式中，D表示整个事务集，| |D表示D中事务的总数，NUM(X∪Y)表示数据集中X与Y同时出现在一条事务记录中的次数[3]。

4）置信度（Confidence）

关联规则X→Y的置信度反映了事务{X,Y}在事务X单独发生的情况下所占的比重，公式如下所示。

5）作用度（Lift）

关联规则X→Y的作用度反映了事务Y发生的条件下，同时含有事务X的概率与仅关注事务X发生概率的之比，实质上就是置信度和期望置信度的比值[4]，公式如下所示。

6）确信度（Conviction）

关联规则X→Y的确信度反映了事务X出现而事务Y不出现的概率，公式如下所示。

7）最小支持度与最小置信度

最小支持度（min_Sup）与最小置信度（min_Conf）是根据实际情况人为设定的，通过比较事务集的支持度与最小支持度，进行剪枝操作。最小支持度反映了关联规则的最低重要程度，最小置信度规定了关联规则必须满足的最低可靠性[3]。

8）频繁项集

频繁项集即支持度大于min_Sup 的事务集。

9）强关联规则

在频繁项集中，置信度大于或等于最小置信度的关联规则称为强关联规则[5]。

2 Apriori算法原理

Apriori 算法是关联规则挖掘频繁项集的经典算法之一[6]，基本思想就是利用层层迭代的方式逐层获取频繁项集[7]。频繁k-项集Lk用于搜索频繁(k+1)-项集Lk+1，反复循环，直到不能找到新的频繁项集为止，然后通过频繁项集挖掘出强关联规则[8]。为了提高频繁项集产生的效率，Apriori 算法有如下两个性质：

性质1：事务数据库D中有两个项集分别为X与Y，假设满足X⊆Y，且Y是一个频繁项集，X≠∅，则推出X是频繁项集[9]。

性质2：事务数据库D中有两个项集分别为X与Y，假设满足X⊆Y，且当X是一个非频繁项集时，则Y也是非频繁项集。

Apriori 算 法步骤 如下[9]：

Step1：设定最小支持度及最小置信度。

Step2：通过扫描事务数据库后，计算每一个事务集的支持度。将其与最小支持度进行对比，所有支持度大于或等于最小支持度的事务集被称为频繁1-项集，该集合记为L1[10]。

Step3：扫描L1，将L1中的事务集进行自连接，形成频繁2-项集的候选集C2。

Step4：遍历C2中所有的事务项，计算每个事务项的支持度，支持度不低于最小支持度的项集则为频繁2-项集[10]，该集合记为L2。

Step5：重复Step3，Step4 过程，直到不能再找到频繁k-项集。

Step6：计算频繁k-项集中元素之间的置信度，根据min_Conf 筛选产生关联规则[11]。

算法流程图如图1 所示。

图1 Apriori算法流程图

3 算法实现与结果分析

3.1 获取数据集

MovieLens 数据集是推荐系统领域最为经典的数据集之一[12]。文中采用MovieLens 数据集中的movie.csv 文件，该文件包括movieId（电影编号）、title（电影名称）、genres（电影标签）三个属性参数[13]。

3.2 用One-hot编码进行数据预处理

One-hot 编码也称“独热编码”，又称一位有效编码，使用One-hot 编码，主要是采用N位状态寄存器来对N个状态进行编码，每个状态都有独立的寄存器位，并且在任意时候只有一位有效[14]。在数据处理任务中，为了加快速度，通常需要对数据进行特征数字化，三个特征属性的例子如下：

性别：[“male”，“female”]

地区：[“China”，“US”，“Asia”]

浏览器：[“Firefox”，“Chrome”，“Safari”，“Microsoft Edge”]

对于某一个样本，如[“female”，“ China”，“Safari”]，在进行数据预处理之前，要将这个样本值的特征采用序列化的方式进行数字化。如性别的两个特征属性值“male”和“female”对应的数值分别为0和1；地区的三个特征属性值“China”“US”“Asia”对应的数值为0、1、2，浏览器四个特征属性值对应的数值分别为0、1、2、3。样本[“female”，“China”，“Safari”]序列化的结果为[1,0,2]。但序列化特征处理并不能直接放入算法中，为了解决此问题，可以采用Onehot 编码处理。在One-hot 编码中，样本值中有多少特征属性值，就用多少维来表示这个特征[15]。采取One-Hot 编码处理方式对样本“[“female”，“China”，“Safari”]”进行编码，“female”对应[0,1]，“China”对应[1,0,0]，“Safari”对应[0,0,1,0]。则完整的编码结果为[0,1,1,0,0,0,0,1,0]。

文中采用的MovieLens 数据集非常规则，对于数据预处理分为如下步骤：

Step1:查看genres 数据列的类型；

Step2:将genres 列数据进行One-hot 编码；

Step3:电影类型之间使用“|”分隔符隔开；

Step4:把genres 列去掉，分割之后再拼接上；

Step5:把genres 转换为字符串类型，然后按竖线进行分割。

用One-hot 编码处理MovieLens 数据集得到的部分结果如图2 所示。

图2 用One-hot编码处理数据后的部分数据集

3.3 实验过程

利用Apriori 算法生成频繁项集，通过与最小置信度比较生成关联规则[8]。例如关联规则X→Y，用户喜欢X类型标签电影，则该用户很可能喜欢Y类型标签的电影。文中设定最小作用度，只返回高于最小作用度的关联规则。作用度反映了在用户给电影标签为X时，推荐用户标签Y的电影出现概率发生了多大的变化[16]。整个实验的过程如下：

1）扫描事务数据集，累计每个事务出现的次数，设置最小支持度为0.02；

2）按照支持度大小输出频繁项集；

3）根据所产生的频繁项集计算关联规则，设定最小作用度为2；

4）按照作用度从大到小排序，得到的关联规则本地保存。

3.4 结果分析

根据实验过程中步骤2，通过Apriori 算法遍历每条电影数据，大于最小支持度0.02 的项集则为频繁项集，共计频繁项集38 条，输出的部分频繁项集如表1 所示。

表1 部分频繁项集

根据实验过程步骤3，设置最小作用度为2，得到部分关联规则为表2 所示。

表2 部分关联规则结果

查看表2 中列出的六条数据，可以得出实验结果如下：从表中的关联规则可以看出，关联规则(Thriller)→(Mystery)的作用度为3.428 351 5，这个作用度大于设置的最小作用度2 时，代表事务{′Thriller′}的出现对于事务{′Mystery′}的出现有很大的影响，则可以说明事务{′Thriller′}与事务{′Mystery′}之间具有很强的关联关系，同时数据确信度的数值越高也代表两者关联性越高。则当用户给电影打{′Thriller′}标签后，通过得到的关联规则结果可以得出，程序会有很大概率给用户推荐标签为{′Mystery′}的电影，从而提升电影推荐的准确度。

从表2 实验数据来看，几条规则在数据集上的作用度、确信度很高，所以表明当用户给自己喜欢的电影标注标签时，使用Apriori 算法进行的电影推荐效果很好，从而提升了用户体验。

4 结束语

文中首先利用机器学习中的One-hot 编码原理对电影评分数据集MovieLens 进行数据处理，利用Apriori 算法找出数据集中的频繁项集，根据频繁项集找出关联规则完成电影的推荐，实例分析表明，用Apriori 算法进行电影推荐效果很好，能很好提升用户体验。但由于Ariori 算法的自身缺陷会产生大量的候选集，以及需要重复扫描数据库，而会加大加剧计算机系统的I/O 开销，所以进一步的研究方向将会放在如何优化Apriori 算法减少计算机系统I/O 开销和优化算法精度上。