论文部分内容阅读
[摘 要]随着信息技术的发展，我们获得越来越多庞大而复杂的数据，如何从众多数据中提取出有用的信息，数据挖掘为我们提供了思路。关联规则挖掘是数据挖掘中的一个重要部分。Weka是一个开放的数据挖掘平台，它提供了几种关联规则挖掘算法，本文介绍了其中的三种算法：Apriori算法，FP-Growth算法，PredictiveApriori算法。
[关键词]关联规则挖掘； Apriori算法；FP-Growth算法；PredictiveApriori算法；
中图分类号：S155 文献标识码：A 文章编号：1009-914X（2018）02-0238-01
0 前言
关联规则的概念是在1993年由Agrawal等人提出的，最初的提出动机是针对购物篮分析问题的。“尿布与啤酒”的故事就是一个经典的例子。关联分析的目的就是找出数据库中隐藏的关联网。关联规则挖掘技术已被广泛应用于金融，电子商务，医疗等领域。并且，对于经典的关联规则挖掘算法，人们也不断将其进行改进或与其他算法结合，以提高算法效率。
1 Weka简介
Weka全称是Waikato Environment for Knowledge Analysis，即怀卡托智能分析环境。它是一款免费的、非商业化的、基于Java环境下开源的机器学习以及数据挖掘平台。 Weka是一个公开的数据挖掘工作平台，汇集了大量能承担数据挖掘任务的机器学习算法。此外，还可以对算法进行性能评测。若用户想要实现自己的数据挖掘算法，可以参考weka的接口文档，将自己设计的算法集成于weka中。
2 关联规则
2.1 关联规则
关联规则是形如的蕴涵式，X和Y分别称为关联规则的先导和后继。其中，关联规则，存在支持度和信任度。给定一个交易数据库，其中，假设是m个不同项的集合，每个事务T是I的非空子集，T有一个唯一的标识符TID。假设X，Y是I的任意非空子集，关联规则在D中的支持度是D中事务同时包含X、Y的百分比，即support（）=P（XY）；置信度是D中事务已经包含X的情况下，包含Y的百分比，若X的支持度是support（X），则规则的置信度为：support（）/support（X），即confidence（XY）=P（Y|X）。
2.2 关联规则挖掘
关联规则的挖掘问题，也就是发现所有同时满足最小支持度与最小置信度的强关联规则。此过程分为两步：
第一步：在数据库中识别所有满足给定的最小支持度的频繁项集；
第二步：由频繁项集产生满足给定的最小置信度的关联规则。
3 关联规则挖掘算法
3.1 Apriori算法
Apriori算法是挖掘布尔关联规则频繁项集的算法，它是一种经典的关联规则挖掘算法，通过对数据库进行多次扫描发现所有频繁项目集，每一次扫描过程只考虑具有同一长度的所有项目。实际应用中，为了减少生成候选项目集的计算量，Apriori算法利用了以下性质：（1）一个频繁项集的任意非空子集必是频繁项集。
（2）k项数据项集是频繁项集的必要条件是它的所有k-1项子集都是频繁项集。
Apriori算法将发现关联规则的过程分为两个步骤：
第一步：通过迭代，检索出事务数据库中的所有满足设定阈值的频繁项集。Apriori算法通过连接步和剪枝步两个步骤来找出所有的频繁项集。
第二步：利用频繁项集构造出满足最小置信度的规则。
（1）对于每个频繁项集L，产生其所有非空真子集；
（2）对于每个非空真子集s，如果support_count（l）/support_count（s）>=min_conf，则输出s->（-s），其中，min_conf是最小置信度阈值。
其中，识别出所有频繁项集是该算法的核心，占整个计算量的大部分。
3.2 FP-growth算法
FP-growth算法又称为FP-增长算法，是它是通过FP-Tree数据结构对原始数据进行压缩，只需要对数据库进行两次扫描。因此，FP-growth算法要比Apriori算法效率高。
FP-growth算法发现频繁项集的基本过程如下：
第一步：构建FP-Tree。
（1）扫描整个数据集，统计各元素项出现次数，得到频繁1-项集，然后按照频数递减排序，移除频数不满足最小支持度的元素项，得到频繁项表F，按照F重新调整事务数据库。
（2）第二次遍历数据集，创建FP树。新建一个根结点，标记为null，把每个事务中的数据项按照调整后的数据库次序依次插入到以null为根结点的树中，同时在每个结点处记录该结点出现的支持度。
第二步：从FP-Tree中挖掘频繁项集。
（1）从FP-Tree中获得条件模式基；
（2）利用条件模式基，构建一个条件FP树；
（3）迭代重复步骤1步骤2，直到树包含一个元素项为止。
3.3 Predictive Apriori算法
经典关联规则算法Apriori和FP-Growth算法都需要设置固定的支持的和置信度阈值，而Predictive Aprior算法是一种多层关联算法，只需设定输出最好的n个规则，就可以挖掘出n个预测精度最大的规则。Predictive Apriori算法的核心思想是：通过不断增大规则前项支持度和观察置信度来逐步逼近獲得最大的预测精度E，从而返回n个最好的关联规则。假设事务数据库D，给定关联规则，则预测精度E定义如下：
其中，代表规则置信度，代表观察到的置信度，代表规则前项支持度，代表已计算的最优结果，代表先验预测精度。
4 总结
本文对weka中关联规则及三种不同的关联规则挖掘算法进行了介绍，不同的算法各有优势和短处。针对各个算法的缺点，大家提出了很多的改进算法，或是与其它算法相结合，现在也逐渐将它们与遗传算法、云计算等相结合。
参考文献
[1] 郭瑞.大数据关联规则挖据研究[D].兰州交通大学，2016.
[2] 曾雷.关联规则挖掘中Apriori算法的研究[D].重庆交通大学，2016.
[3] 朱涛.基于FP-growth关联规则挖掘算法[D].南昌大学，2010.
[4] 吴芝明，钱程，伍少梅.关联规则挖掘的PredictiveApriori算法的研究及改进[J].四川大学学报（自然科学版），2012，（01）.
作者简介
赵妍（1994.01--）女，陕西省商洛市人，学历：硕士研究生，专业：交通信息工程及控制。
[关键词]关联规则挖掘； Apriori算法；FP-Growth算法；PredictiveApriori算法；
中图分类号：S155 文献标识码：A 文章编号：1009-914X（2018）02-0238-01
0 前言
关联规则的概念是在1993年由Agrawal等人提出的，最初的提出动机是针对购物篮分析问题的。“尿布与啤酒”的故事就是一个经典的例子。关联分析的目的就是找出数据库中隐藏的关联网。关联规则挖掘技术已被广泛应用于金融，电子商务，医疗等领域。并且，对于经典的关联规则挖掘算法，人们也不断将其进行改进或与其他算法结合，以提高算法效率。
1 Weka简介
Weka全称是Waikato Environment for Knowledge Analysis，即怀卡托智能分析环境。它是一款免费的、非商业化的、基于Java环境下开源的机器学习以及数据挖掘平台。 Weka是一个公开的数据挖掘工作平台，汇集了大量能承担数据挖掘任务的机器学习算法。此外，还可以对算法进行性能评测。若用户想要实现自己的数据挖掘算法，可以参考weka的接口文档，将自己设计的算法集成于weka中。
2 关联规则
2.1 关联规则
关联规则是形如的蕴涵式，X和Y分别称为关联规则的先导和后继。其中，关联规则，存在支持度和信任度。给定一个交易数据库，其中，假设是m个不同项的集合，每个事务T是I的非空子集，T有一个唯一的标识符TID。假设X，Y是I的任意非空子集，关联规则在D中的支持度是D中事务同时包含X、Y的百分比，即support（）=P（XY）；置信度是D中事务已经包含X的情况下，包含Y的百分比，若X的支持度是support（X），则规则的置信度为：support（）/support（X），即confidence（XY）=P（Y|X）。
2.2 关联规则挖掘
关联规则的挖掘问题，也就是发现所有同时满足最小支持度与最小置信度的强关联规则。此过程分为两步：
第一步：在数据库中识别所有满足给定的最小支持度的频繁项集；
第二步：由频繁项集产生满足给定的最小置信度的关联规则。
3 关联规则挖掘算法
3.1 Apriori算法
Apriori算法是挖掘布尔关联规则频繁项集的算法，它是一种经典的关联规则挖掘算法，通过对数据库进行多次扫描发现所有频繁项目集，每一次扫描过程只考虑具有同一长度的所有项目。实际应用中，为了减少生成候选项目集的计算量，Apriori算法利用了以下性质：（1）一个频繁项集的任意非空子集必是频繁项集。
（2）k项数据项集是频繁项集的必要条件是它的所有k-1项子集都是频繁项集。
Apriori算法将发现关联规则的过程分为两个步骤：
第一步：通过迭代，检索出事务数据库中的所有满足设定阈值的频繁项集。Apriori算法通过连接步和剪枝步两个步骤来找出所有的频繁项集。
第二步：利用频繁项集构造出满足最小置信度的规则。
（1）对于每个频繁项集L，产生其所有非空真子集；
（2）对于每个非空真子集s，如果support_count（l）/support_count（s）>=min_conf，则输出s->（-s），其中，min_conf是最小置信度阈值。
其中，识别出所有频繁项集是该算法的核心，占整个计算量的大部分。
3.2 FP-growth算法
FP-growth算法又称为FP-增长算法，是它是通过FP-Tree数据结构对原始数据进行压缩，只需要对数据库进行两次扫描。因此，FP-growth算法要比Apriori算法效率高。
FP-growth算法发现频繁项集的基本过程如下：
第一步：构建FP-Tree。
（1）扫描整个数据集，统计各元素项出现次数，得到频繁1-项集，然后按照频数递减排序，移除频数不满足最小支持度的元素项，得到频繁项表F，按照F重新调整事务数据库。
（2）第二次遍历数据集，创建FP树。新建一个根结点，标记为null，把每个事务中的数据项按照调整后的数据库次序依次插入到以null为根结点的树中，同时在每个结点处记录该结点出现的支持度。
第二步：从FP-Tree中挖掘频繁项集。
（1）从FP-Tree中获得条件模式基；
（2）利用条件模式基，构建一个条件FP树；
（3）迭代重复步骤1步骤2，直到树包含一个元素项为止。
3.3 Predictive Apriori算法
经典关联规则算法Apriori和FP-Growth算法都需要设置固定的支持的和置信度阈值，而Predictive Aprior算法是一种多层关联算法，只需设定输出最好的n个规则，就可以挖掘出n个预测精度最大的规则。Predictive Apriori算法的核心思想是：通过不断增大规则前项支持度和观察置信度来逐步逼近獲得最大的预测精度E，从而返回n个最好的关联规则。假设事务数据库D，给定关联规则，则预测精度E定义如下：
其中，代表规则置信度，代表观察到的置信度，代表规则前项支持度，代表已计算的最优结果，代表先验预测精度。
4 总结
本文对weka中关联规则及三种不同的关联规则挖掘算法进行了介绍，不同的算法各有优势和短处。针对各个算法的缺点，大家提出了很多的改进算法，或是与其它算法相结合，现在也逐渐将它们与遗传算法、云计算等相结合。
参考文献
[1] 郭瑞.大数据关联规则挖据研究[D].兰州交通大学，2016.
[2] 曾雷.关联规则挖掘中Apriori算法的研究[D].重庆交通大学，2016.
[3] 朱涛.基于FP-growth关联规则挖掘算法[D].南昌大学，2010.
[4] 吴芝明，钱程，伍少梅.关联规则挖掘的PredictiveApriori算法的研究及改进[J].四川大学学报（自然科学版），2012，（01）.
作者简介
赵妍（1994.01--）女，陕西省商洛市人，学历：硕士研究生，专业：交通信息工程及控制。