论文部分内容阅读
摘 要 主要介绍Apriori算法的基本思想和执行步骤，以及对算法的优缺点进行分析，并介绍了目前针对Apriori算法的缺点所做的改进算法。
关键词 APRIORI算法；关联规则；置信度
中图分类号：TP301 文献标识码：A 文章编号：1671-7597（2013）22-068-01
随着信息技术的不断发展，人们获得数据的能力越来越强。但是当大量的数据被收集而需要从中找到对人类有用的信息时，我们却又苦于没有使用的工具。因此，人们希望能有一种新的技术或是工具能自动帮助我们整理和分析当前的数据，发现当中隐含的信息，为人类的决策而服务。数据挖掘都是当今人们对人工智能和数据库研究中最热点的问题。而关联规则又是数据挖掘中重要的研究对象，所以关联规则挖掘也是人们研究的重中之重。
目前，关联规则的在专家系统的应用也十分重要。专家系统是在一个特定的领域内，依靠计算机模拟大量的专家的知识和推理方法来求解实际生产或生活中遇到的问题。这是人工智能领域的问题，属于人工智能的一个分支。很多专家和学者也不断完善专家系统使它的发展越来越智能。
综上所述，正由于关联规则在生产和生活中应用众多，才使得很多的专家学者对其十分重视，也不断产生很多改进的算法，使其性能进一步优化。
1 Apriori算法
Apriori算法是第一个也是最经典的数据挖掘算法。关联规则的挖掘是为了从数据库大量的数据项中找到数据之间隐含的关联性。
1.1 关联规则的定义
定义1，我们选定一个事务数据库D，D={I1，I2，I3......，Ij......，In}，I是其中每个事务集，而Ij则为其中的一项事务，它可以由若干个项目构成，可以表示为{X1，X2，X3，......}，我们称为项目集X，如果X属于Ij，那么我们称事务Ij包含项目集X。
定义2，事务数据库D中包含的项目集X中的事务的个数，我们称为项目集X的支持数，我们用α（X）表示。我们用support（X）表示项目集X的支持度。支持度是项目集X的支持数和数据集D的事务个数的比值。公式如下：
（1）
定义3，如果项目集X的支持度大于用户定义的最小支持度，则称X为频繁项目集。
定义4，如果同时存在A，B两个项目集，并且，A和B中都包含相同的元素，我们就称为关联规则。为关联规则的支持度，可以表示为。并且用表示关联规则的置信度，推导公式为。
假如事务数据库D有2个项目集，分别为项目集A和项目集B，根据以上定义，我们还可以推导出如下定理：
1）如果项目集A包含项目集B，也就是，一定有项目集B的支持度大于等于项目集A的支持度，也就是。
2）如果项目集A包含项目集B，也就是，并且项目集B不是频繁项目集，那么A一定也不是频繁项目集；反过来，也同样，如果A是频繁项目集那么B一定也是频繁项目集。
1.2 关联规则挖掘
Apriori算法就是挖掘关联规则的一种重要方法。这个算法的基本思想是，首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。具体算法步骤如下。
1）扫描整个事务数据库D，找到候选项集1-的集合A1。
2）根据最小支持度，从找到的候选项集A1中产生频繁项集1-的集合I1，如果没查找到，则算法退出。
3）如果，重复步骤4）5）6）。
4）对LK进行连接和剪枝操作，生成候选（K+1）-项集的集合AK+1。
5）根据最小支持度，从AK+1中产生频繁（K+1）-项集的集合LK+1。
6）如果，则K=K+1，转到步骤4），否则，转到步骤7）。
7）根据最小置信度，由频繁项集产生强关联规则。
1.3 Apriori算法的分析
Apriori算法的优点比较多，算法思想简单，并且容易实现，它是以递归统计算法为基础，产生频繁项集，这大大压缩了频繁项集的大小，取得了很好的性能。但是，通过实验分析，Apriori算法有一些比较明显的不足。首先，算法执行过程中，每次迭代过程都需要重新扫描数据库，如果事务数据库中包含N个项集，那么Apriori算法至少要重复扫描N遍，这会增加挖掘系统的负担。其次，Apriori算法会产生大量的频繁集。由于数据量庞大，可能产生的候选项集就越多，当频繁1-项集I有1000个，候选2-项集个数将会超过100万，这是一指数形式增长，这些对机器的运行时间和运行空间都有较高的要求，这使得算法的执行效率很低。
2 算法的改进
为了提高Apriori算法的效率，国内外的专家学者都提出过一系列的改进方式，对算法的过程进行各种优化，主要是为了克服上面提到的两个主要缺点。常见的改进算法较多，主要是混合搜索策略和高效剪枝策略。比如：使用概率的方法求候选频繁项集的Apriori改进算法；基于事务地址索引表来约简事务的Apriori优化算法；适用于数字资源访问日志数据库的关联规则挖掘改进算法。本文主要介绍一种基于临时表的改进算法。临时表法主要根据以下事实改进算法：首先，对于任一个事务数据库D，任意一个项集I的频繁度与规模小于的事务无关。所以当第I次扫描事务数据库D时，可以删除所有规模小于的事务。其次，根据上述定理2），亦可以删除不符合条件的事务，从而减少扫描的事务。
根据这两个事实，临时表用来构建频繁项集。首先把（K-1）-项集中的第一个项集填入临时表R中，然后把最后一项不同的其它项集填入，构成K-项集，并计算R的频繁度，如果R的频繁度小于最小频繁度，则生成R的频繁项并保存，否则删除。重复上述操作，直到生成所有频繁项。实验证明，随着数据量的不断增加，临时表法能很好的解决经典Apriori算法在时间和空间上的效率较低的问题。
参考文献
[1]乌文波.应用Apriori关联规则算法的数据挖掘技术挖掘电子商务潜在客户[D].2012.
[2]王伟.关联规则中的Apriori算法的研究与改进[D].2012.
[3]齐俊鹏.基于产生式规则的信息安全风险评估专家系统研究[D].2008.
关键词 APRIORI算法；关联规则；置信度
中图分类号：TP301 文献标识码：A 文章编号：1671-7597（2013）22-068-01
随着信息技术的不断发展，人们获得数据的能力越来越强。但是当大量的数据被收集而需要从中找到对人类有用的信息时，我们却又苦于没有使用的工具。因此，人们希望能有一种新的技术或是工具能自动帮助我们整理和分析当前的数据，发现当中隐含的信息，为人类的决策而服务。数据挖掘都是当今人们对人工智能和数据库研究中最热点的问题。而关联规则又是数据挖掘中重要的研究对象，所以关联规则挖掘也是人们研究的重中之重。
目前，关联规则的在专家系统的应用也十分重要。专家系统是在一个特定的领域内，依靠计算机模拟大量的专家的知识和推理方法来求解实际生产或生活中遇到的问题。这是人工智能领域的问题，属于人工智能的一个分支。很多专家和学者也不断完善专家系统使它的发展越来越智能。
综上所述，正由于关联规则在生产和生活中应用众多，才使得很多的专家学者对其十分重视，也不断产生很多改进的算法，使其性能进一步优化。
1 Apriori算法
Apriori算法是第一个也是最经典的数据挖掘算法。关联规则的挖掘是为了从数据库大量的数据项中找到数据之间隐含的关联性。
1.1 关联规则的定义
定义1，我们选定一个事务数据库D，D={I1，I2，I3......，Ij......，In}，I是其中每个事务集，而Ij则为其中的一项事务，它可以由若干个项目构成，可以表示为{X1，X2，X3，......}，我们称为项目集X，如果X属于Ij，那么我们称事务Ij包含项目集X。
定义2，事务数据库D中包含的项目集X中的事务的个数，我们称为项目集X的支持数，我们用α（X）表示。我们用support（X）表示项目集X的支持度。支持度是项目集X的支持数和数据集D的事务个数的比值。公式如下：
（1）
定义3，如果项目集X的支持度大于用户定义的最小支持度，则称X为频繁项目集。
定义4，如果同时存在A，B两个项目集，并且，A和B中都包含相同的元素，我们就称为关联规则。为关联规则的支持度，可以表示为。并且用表示关联规则的置信度，推导公式为。
假如事务数据库D有2个项目集，分别为项目集A和项目集B，根据以上定义，我们还可以推导出如下定理：
1）如果项目集A包含项目集B，也就是，一定有项目集B的支持度大于等于项目集A的支持度，也就是。
2）如果项目集A包含项目集B，也就是，并且项目集B不是频繁项目集，那么A一定也不是频繁项目集；反过来，也同样，如果A是频繁项目集那么B一定也是频繁项目集。
1.2 关联规则挖掘
Apriori算法就是挖掘关联规则的一种重要方法。这个算法的基本思想是，首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。具体算法步骤如下。
1）扫描整个事务数据库D，找到候选项集1-的集合A1。
2）根据最小支持度，从找到的候选项集A1中产生频繁项集1-的集合I1，如果没查找到，则算法退出。
3）如果，重复步骤4）5）6）。
4）对LK进行连接和剪枝操作，生成候选（K+1）-项集的集合AK+1。
5）根据最小支持度，从AK+1中产生频繁（K+1）-项集的集合LK+1。
6）如果，则K=K+1，转到步骤4），否则，转到步骤7）。
7）根据最小置信度，由频繁项集产生强关联规则。
1.3 Apriori算法的分析
Apriori算法的优点比较多，算法思想简单，并且容易实现，它是以递归统计算法为基础，产生频繁项集，这大大压缩了频繁项集的大小，取得了很好的性能。但是，通过实验分析，Apriori算法有一些比较明显的不足。首先，算法执行过程中，每次迭代过程都需要重新扫描数据库，如果事务数据库中包含N个项集，那么Apriori算法至少要重复扫描N遍，这会增加挖掘系统的负担。其次，Apriori算法会产生大量的频繁集。由于数据量庞大，可能产生的候选项集就越多，当频繁1-项集I有1000个，候选2-项集个数将会超过100万，这是一指数形式增长，这些对机器的运行时间和运行空间都有较高的要求，这使得算法的执行效率很低。
2 算法的改进
为了提高Apriori算法的效率，国内外的专家学者都提出过一系列的改进方式，对算法的过程进行各种优化，主要是为了克服上面提到的两个主要缺点。常见的改进算法较多，主要是混合搜索策略和高效剪枝策略。比如：使用概率的方法求候选频繁项集的Apriori改进算法；基于事务地址索引表来约简事务的Apriori优化算法；适用于数字资源访问日志数据库的关联规则挖掘改进算法。本文主要介绍一种基于临时表的改进算法。临时表法主要根据以下事实改进算法：首先，对于任一个事务数据库D，任意一个项集I的频繁度与规模小于的事务无关。所以当第I次扫描事务数据库D时，可以删除所有规模小于的事务。其次，根据上述定理2），亦可以删除不符合条件的事务，从而减少扫描的事务。
根据这两个事实，临时表用来构建频繁项集。首先把（K-1）-项集中的第一个项集填入临时表R中，然后把最后一项不同的其它项集填入，构成K-项集，并计算R的频繁度，如果R的频繁度小于最小频繁度，则生成R的频繁项并保存，否则删除。重复上述操作，直到生成所有频繁项。实验证明，随着数据量的不断增加，临时表法能很好的解决经典Apriori算法在时间和空间上的效率较低的问题。
参考文献
[1]乌文波.应用Apriori关联规则算法的数据挖掘技术挖掘电子商务潜在客户[D].2012.
[2]王伟.关联规则中的Apriori算法的研究与改进[D].2012.
[3]齐俊鹏.基于产生式规则的信息安全风险评估专家系统研究[D].2008.