论文部分内容阅读
摘 要：近年来国内外学者对关联规则进行了大量的研究。为了更好地了解关联规则的挖掘技术，对研究现状有更深入的了解，首先本文对数据挖掘技术进行了介绍，接着介绍了关联数据挖掘的基本原理，最后对经典的挖掘算法进行分类介绍。
关键词：数据挖掘；关联规则；算法；综述
1.引言
数据挖掘是从海量的数据里寻找有价值的信息和数据。数据挖掘中常用的算法[1]有：关联规则分析法（解决事件之间的关联问题）、决策树分类法（对数据和信息进行归纳和分类）、遗传算法（基于生物进化论及分子遗传学理论提出的）、神经网络算法（模拟人的神经元功能）等。
数据挖掘最早使用的方法是关联分析，主要应用于零售业。其中最有名的是售货篮分析，帮助售货商制定销售策略。随着信息时代的到来，数据挖掘在金融[2]、医疗[3]、通信[4]等方面得到了广泛的应用。
2.关联规则基本原理
设项的集合I = { I1 ，I2 ，...，Im }，数据库事务的集合为D，我们用|D|表示事务数据库所有事务的个数，其中用T表示每个事务，使得T I。我们用TID作为每个事务的唯一标识符。用X表示一个项集，满足X T，那么交易T包含X。根据上述相关描述，给出关联规则的相关定义。
2.1项集支持度
用X表示数据库事务D中的项集，项集X的支持度表示项集X在D中事务数所占的比例，用概率P（X）表示，那么
Support（X）=P（X）=COUNT（X）/|D| （1）
2.2关联规则置信度
X Y关联规则的置信度是数据库事务D中包含X Y的事务数与包含X的事务数之比，表示方法如下：
confidence（X Y）= support（X Y）/support（X） = P（Y|X） （2）
3.关联规则算法
3.1经典的Apriori挖掘算法
大多数关联规则的算法是将关联规则挖掘任务分为两个子任务完成。一是频繁项集的产生，频繁项集的目的是找到大于等于给定的最小支持度阈值的所有项集，这些项集我们称之为频繁项集。二是规则的产生，即从频繁项集中找到置信度比较高的规则，我们称之为强规则。Apriori挖掘算法是众多挖掘关联规则中比较经典的算法，它采用布尔关联规则，是一种宽度优先算法。
3.2Apriori算法优化
Apriori算法的思想是每产生一次候选集就需要扫描一次数据库，但是当数据库中的数据庞大，无法直接完全放于內存中，扫描过程中数据需要不断的换入换出，加重了I/O的负担。可见当数据信息大的时候，算法效率低下，同时也消耗的大量的内容。
3.2.1哈希表技术（散列项集到对应的桶中）：
Park等提出了一种基于散列的产生频繁项集的高效算法DHP算法。即将产生的所有的候选k-项集（k>1）散列到哈希表结构对应的桶中并增加对应的桶计数， 利用哈希表技术可以有效减少候选k-项集（k>1）所占用的空间，进而提高了Apriori算法的效率。
3.2.2 划分技术（为寻找候选项集划分数据）：
Savasere等提出了一个基于数据划分的算法，即将数据库中的记录划分成几个互不相交的块，各块可以高度并行执行，由最小支持度得到每块中对应的最小支持度。第一次扫描数据库，得到各块的频繁项集，即局部频繁项集。当算法进行数据库的第二次扫描时，需得到每个候选项集的支持数，进而得到全局频繁项集的值。
3.2.3事务压缩技术（即压缩未来迭代扫描的事务数据）：
该技术用于压缩迭代扫描数据库的大小，即将不包含任何k-项集的事务肯定不包含任何（k+l）-项集，这种事务在以后考虑时，可以加上标记或者删除项集，因为产生j项集（j>k）时不再需要从数据库加上它们进行扫描，如此就可以减小需要扫描的数据库的规模，从而在一定程度上提高算法的效率。
3.2.4 连续关联规则算法
C. Hidber提出了一种新型的名为CARMA（连续关联规则的算法挖掘算法）算法，该算法用来在线计算大项集。随着每个项集的支持区间的减少不断产生大项集。他已证明：当相应的支持区间的规模快速减少时，CARMA的项集数迅速接近所有大项集的超集。CARMA的内存效率比Apriori是一个数量级的提高。当支持度阈值比较低时，Apriori和DIC 落后CARMA，此外，CARMA的内存使用效率是两者的六十倍以上。
3.3基于频繁模式树的算法FP-growth
由Zaki提出的Eclat算法被认为是产生频繁项集的深度优先方式的原型。在这以后不同深度优先算法被提出，其中由韩家炜等提出的FP-growth算法是最著名和最广泛使用的。韩家炜等人提出了基于频繁模式树（FP-Tree）的算法。该算法首先两次扫描事务数据库，得到频繁项目集的支持度，然后将它们降序排序，并且存储到FP-Tree中。在以后寻找频繁项目集的过程中，不需要再对事务数据库进行遍历，只需要在FP-Tree中寻找新的频繁项目集即可。
3.4并行算法
随着高性能多核处理器的出现，学者们开始借助并行系统的强大运算能力，将并行算法引入到研究中。在Bodon工作的基础上，Yanbin Ye等实现了并行Apriori算法，并分析并行计算的性能，分割事务数据库的每个分区执行Apriori算法。
3.5其它关联规则算法
Mohammed J. Zaki等提出了CHARM（闭关联规则挖掘），它在优势主要体现在挖掘所有频繁闭项集。Hua-Fu Li等提出了就是通过整个历史数据流挖掘所有频繁项集的DSM-FI（数据流挖掘频繁项集），。Jian Pei等提出了H-mine频繁模式挖掘算法。
3.6关联规则的评估
3.6.1基于兴趣度约束的关联规则挖掘算法
Silberschatz.A等提出了可执行规则的概念，并统一了关联规则挖掘过程中主客观评价标准。Srikant R提出了基于项目约束的关联规则挖掘的概念和相应的算法描述。Balaji Padmanabhan等提出了一种发现未知模式的置信驱动方法，在挖掘过程中考虑到与置信评判的结合，从而使挖掘出的关联规则更加有效。
3.6.2加权关联规则挖掘算法
Cai等提出了基于K-支持期望的加权关联规则挖掘算法模型：MINWAL（O）模型和MINWAL（W）模型。张文献等采用权重集归一化的思想对Cai给出的算法做了改进。Wei Wang等[5]提出了一个挖掘加权关联规则的方法，其方法不仅缩短了平均执行时间，但也比已知的方法产生高质量的关联规则。
4.小结
数据挖掘是一门新鲜的学科，有着广阔的应用前景，因而吸引了众多的学者对它进行研究，其中关联规则是其中应用最早也是很重要的一个领域。关联规则的挖掘受到越来越多的企业和研究者们的重视，算法模型的建立、算法效率的提高、算法的扩展应用、挖掘潜在有趣的规则等具有重大的理论意义和实用价值。
参考文献
[1]方骏，方云，肖杰.数据挖掘的工业标准的现状和展望[J].计算机应用研究，2004，4：8-1。
[2] 余波，朱东华，刘卓君.加权关联规则挖掘算法在电子商务中的应用[J].计算机工程与应用，2008，44（17）：128-129.
[3] 刘智，伊卫国，鲁明羽，等.向量法关联规则挖掘在冠心病诊断中的应用[J].计算机工程， 2010，36（6）：42-44.
[4] 羡晨静，张维石，刘伟光.关联规则分析在电信交叉销售中的应用研究[J].计算机工程与设计， 2008，29（22）.
[5] 张文献，陆建江.加权布尔关联规则的研究[J].计算机工程， 2003，29（9）：55-57.
关键词：数据挖掘；关联规则；算法；综述
1.引言
数据挖掘是从海量的数据里寻找有价值的信息和数据。数据挖掘中常用的算法[1]有：关联规则分析法（解决事件之间的关联问题）、决策树分类法（对数据和信息进行归纳和分类）、遗传算法（基于生物进化论及分子遗传学理论提出的）、神经网络算法（模拟人的神经元功能）等。
数据挖掘最早使用的方法是关联分析，主要应用于零售业。其中最有名的是售货篮分析，帮助售货商制定销售策略。随着信息时代的到来，数据挖掘在金融[2]、医疗[3]、通信[4]等方面得到了广泛的应用。
2.关联规则基本原理
设项的集合I = { I1 ，I2 ，...，Im }，数据库事务的集合为D，我们用|D|表示事务数据库所有事务的个数，其中用T表示每个事务，使得T I。我们用TID作为每个事务的唯一标识符。用X表示一个项集，满足X T，那么交易T包含X。根据上述相关描述，给出关联规则的相关定义。
2.1项集支持度
用X表示数据库事务D中的项集，项集X的支持度表示项集X在D中事务数所占的比例，用概率P（X）表示，那么
Support（X）=P（X）=COUNT（X）/|D| （1）
2.2关联规则置信度
X Y关联规则的置信度是数据库事务D中包含X Y的事务数与包含X的事务数之比，表示方法如下：
confidence（X Y）= support（X Y）/support（X） = P（Y|X） （2）
3.关联规则算法
3.1经典的Apriori挖掘算法
大多数关联规则的算法是将关联规则挖掘任务分为两个子任务完成。一是频繁项集的产生，频繁项集的目的是找到大于等于给定的最小支持度阈值的所有项集，这些项集我们称之为频繁项集。二是规则的产生，即从频繁项集中找到置信度比较高的规则，我们称之为强规则。Apriori挖掘算法是众多挖掘关联规则中比较经典的算法，它采用布尔关联规则，是一种宽度优先算法。
3.2Apriori算法优化
Apriori算法的思想是每产生一次候选集就需要扫描一次数据库，但是当数据库中的数据庞大，无法直接完全放于內存中，扫描过程中数据需要不断的换入换出，加重了I/O的负担。可见当数据信息大的时候，算法效率低下，同时也消耗的大量的内容。
3.2.1哈希表技术（散列项集到对应的桶中）：
Park等提出了一种基于散列的产生频繁项集的高效算法DHP算法。即将产生的所有的候选k-项集（k>1）散列到哈希表结构对应的桶中并增加对应的桶计数， 利用哈希表技术可以有效减少候选k-项集（k>1）所占用的空间，进而提高了Apriori算法的效率。
3.2.2 划分技术（为寻找候选项集划分数据）：
Savasere等提出了一个基于数据划分的算法，即将数据库中的记录划分成几个互不相交的块，各块可以高度并行执行，由最小支持度得到每块中对应的最小支持度。第一次扫描数据库，得到各块的频繁项集，即局部频繁项集。当算法进行数据库的第二次扫描时，需得到每个候选项集的支持数，进而得到全局频繁项集的值。
3.2.3事务压缩技术（即压缩未来迭代扫描的事务数据）：
该技术用于压缩迭代扫描数据库的大小，即将不包含任何k-项集的事务肯定不包含任何（k+l）-项集，这种事务在以后考虑时，可以加上标记或者删除项集，因为产生j项集（j>k）时不再需要从数据库加上它们进行扫描，如此就可以减小需要扫描的数据库的规模，从而在一定程度上提高算法的效率。
3.2.4 连续关联规则算法
C. Hidber提出了一种新型的名为CARMA（连续关联规则的算法挖掘算法）算法，该算法用来在线计算大项集。随着每个项集的支持区间的减少不断产生大项集。他已证明：当相应的支持区间的规模快速减少时，CARMA的项集数迅速接近所有大项集的超集。CARMA的内存效率比Apriori是一个数量级的提高。当支持度阈值比较低时，Apriori和DIC 落后CARMA，此外，CARMA的内存使用效率是两者的六十倍以上。
3.3基于频繁模式树的算法FP-growth
由Zaki提出的Eclat算法被认为是产生频繁项集的深度优先方式的原型。在这以后不同深度优先算法被提出，其中由韩家炜等提出的FP-growth算法是最著名和最广泛使用的。韩家炜等人提出了基于频繁模式树（FP-Tree）的算法。该算法首先两次扫描事务数据库，得到频繁项目集的支持度，然后将它们降序排序，并且存储到FP-Tree中。在以后寻找频繁项目集的过程中，不需要再对事务数据库进行遍历，只需要在FP-Tree中寻找新的频繁项目集即可。
3.4并行算法
随着高性能多核处理器的出现，学者们开始借助并行系统的强大运算能力，将并行算法引入到研究中。在Bodon工作的基础上，Yanbin Ye等实现了并行Apriori算法，并分析并行计算的性能，分割事务数据库的每个分区执行Apriori算法。
3.5其它关联规则算法
Mohammed J. Zaki等提出了CHARM（闭关联规则挖掘），它在优势主要体现在挖掘所有频繁闭项集。Hua-Fu Li等提出了就是通过整个历史数据流挖掘所有频繁项集的DSM-FI（数据流挖掘频繁项集），。Jian Pei等提出了H-mine频繁模式挖掘算法。
3.6关联规则的评估
3.6.1基于兴趣度约束的关联规则挖掘算法
Silberschatz.A等提出了可执行规则的概念，并统一了关联规则挖掘过程中主客观评价标准。Srikant R提出了基于项目约束的关联规则挖掘的概念和相应的算法描述。Balaji Padmanabhan等提出了一种发现未知模式的置信驱动方法，在挖掘过程中考虑到与置信评判的结合，从而使挖掘出的关联规则更加有效。
3.6.2加权关联规则挖掘算法
Cai等提出了基于K-支持期望的加权关联规则挖掘算法模型：MINWAL（O）模型和MINWAL（W）模型。张文献等采用权重集归一化的思想对Cai给出的算法做了改进。Wei Wang等[5]提出了一个挖掘加权关联规则的方法，其方法不仅缩短了平均执行时间，但也比已知的方法产生高质量的关联规则。
4.小结
数据挖掘是一门新鲜的学科，有着广阔的应用前景，因而吸引了众多的学者对它进行研究，其中关联规则是其中应用最早也是很重要的一个领域。关联规则的挖掘受到越来越多的企业和研究者们的重视，算法模型的建立、算法效率的提高、算法的扩展应用、挖掘潜在有趣的规则等具有重大的理论意义和实用价值。
参考文献
[1]方骏，方云，肖杰.数据挖掘的工业标准的现状和展望[J].计算机应用研究，2004，4：8-1。
[2] 余波，朱东华，刘卓君.加权关联规则挖掘算法在电子商务中的应用[J].计算机工程与应用，2008，44（17）：128-129.
[3] 刘智，伊卫国，鲁明羽，等.向量法关联规则挖掘在冠心病诊断中的应用[J].计算机工程， 2010，36（6）：42-44.
[4] 羡晨静，张维石，刘伟光.关联规则分析在电信交叉销售中的应用研究[J].计算机工程与设计， 2008，29（22）.
[5] 张文献，陆建江.加权布尔关联规则的研究[J].计算机工程， 2003，29（9）：55-57.