关于关联规则挖掘综述

关联规则挖掘综述潮娇娇摘要：关联规则挖掘是数据挖掘中的一个很重要的研究内容之一，近年来很多国内外研究人员对其进行了大量的研究。为了更进一步的了解关联规则挖掘技术，并掌握其发展方向和目前的研究现状。本文对关联规则挖掘技术进行了相关综述。首先介绍了关联规则的基本概念，其次分析了近年来一些经典关联规则算法的改进，并概述了相关算法在实际中的应用。最后对关联规则挖掘技术未来的发展趋势进行了讨论。关键字：关联规则；算法；数据挖掘；Abstract:associationruleminingisoneoftheimportantdataminingresearchcontentsinthisyear,manydomesticandforeignresearchershavedonealotofresearchonit.Inordertounderstandfurthertheassociationruleminingtechnology,andgraspthedevelopmentstatusanddirectionofresearchatpresent.Thisarticleofassociationruleminingtechnologyrelatedreview.Firstlyintroducesthebasicconceptsofassociationrules,thenanalyzestheimprovementofsomeclassicalalgorithmofassociationrulesinrecentyears,andsummarizestheapplicationofrelatedalgorithmsinpractice.Attheendoftheassociationruleminingtechnologydevelopmenttrendinthefuturearediscussed.Keywords:associationrules;algorithms;datamining;引言随着计算机技术与数据库技术的飞速地发展，数据资源越来越多。但巨大的数据，依然没有解决我们的信息需求问题，针对这种情况，产生了数据库的数据挖掘。与传统技术相比，数据挖掘技术是一种新型的信息处理技术，能够自动和智能地把位置数据或者大量数据中潜在信息转换成人们需要的信息和知识的技术。它可以从数据库提取有用的知识、规律以及更高层次的信息，对这些进行分析，帮助人们更有效的利用海量数据中存在的价值。目前对数据挖掘的发展趋势及研究方向主要集中在数据挖掘的数据总结、分类、聚类、关联规则等方面。而关联规则挖掘作为数据挖掘的核心内容之一，进来得到了很快的发展。并已经成为当今数据挖掘的热点。为此，对关联挖掘技术的研究具有重要的意义。本文将重点介绍关联规则挖掘技术的相关研究。主要对近年来关联规则挖掘技术的算法改进进行综述以及未来的发展方向。1、关联规则基本概念1.1相关介绍关联规则作为数据挖掘的核心研究内容之一，它是大量数据中发现信息之间可能存在的某种关联或者相关联系。通过分析这些挖掘出的数据联系，可以在现实中帮助我们预测或决定某些事情将会发生。有效的提高了我们制定出准确的决策。目前，关联规则挖掘技术广泛应用于金融、互联网、医学等多个领域。最早的关联挖掘是未来发现交易数据库中不同商品之间的联系，通过分析这种联系获得有关购买者的一般的购买模式。从而有助于商家合理地安排进货、库存及货架设计，更好的制定发展计划和规避风险。1.2相关定义关联规则是通过形如X→Y的一种蕴涵式表达的，其中X和Y是不相关的项集，（X，Y）∈I，并且有X∩Y=NULL成立。关联规则强度可用通过支持度和置信度进行度量。支持度确定规则可以用于给定数据集的频繁程度，而置信度确定Y在包含X的事物中出现的频繁程度。支持度和置信度两个关键的相关形式定义[1]如下:（1）规则X→Y的支持度：规则X→Y在交易数据库D中的支持度（support）是指交易集中包含X和Y的交易数与所有交易数之比，记为support(X→Y)，即：support(X→Y)=|X∩Y|/|D|。（2）规则X→Y置信度（confidence）：是指规则X→Y在交易集中的同时包含X和Y的交易数与只包含X的交易数之比，记为confidence(X→Y)，即：confidence(X→Y)=|X∩Y|/|X|。规则的支持度和置信度是两个不同的量化标准。2、关联规则算法2.1典型的关联规则算法Apriori算法是最著名的关联规则挖掘算法，它是一种以概率为基础的关联规则算法。通过迭代检索方法找出数据库中的项集，该项集的支持度要不低于用户设定的阀值。最后将这些项集合成得到所有数据库的频繁项集，利用这个构造出满足用户最小置信度的规则。但随着数据的增大，对于大型数据库的挖掘，该算法仍存在一些不足。其一，在产生大量的候选集时，需要花费大量的时间处理，降低了算法的效率。其二，该算法在对数据库进行扫描时，由于数据库的庞大，需要相当大的I/O负载。这两个缺点也是如今很多研究人员在改进该算需要重点研究的方向。本文在该节中简单的介绍了关于Apriori算法的相关改进研究。随着数据挖掘技术的发展，大量基于分布式结构的大数据系统也相继被提出。其中以MapReduce方法作为实现自动分布式计算的方法为很多算法的并行化提供了新的思路。也为Apriori算法的并行化提供了一种全新的思路。但是算法并行化后仍存在很多不完备的地方。例如在计算频繁项集时使用的时间增加了。为此，文献[2]针对这个问题进行了研究，通过将基于矩阵关联规则算法与MapReduce算法结合，提出了一种基于矩阵的并行关联规则算法Apriori_MMR。该算法结合了数据划分的思想进行并行化改进，只需要对事务数据库进行两次扫描。第一次是产生频繁1-项集的集合；另一次是生成候选项集的局部支持度，利用局部支持度可以得出全局支持频度，最后生成所有频繁项集的集合。该算法利用高度并行化执行频繁项集的计算过程，大幅度的减少了候选项集，有利于降低系统通信等的能量消耗。对事物数据库减少扫描次数的同时，还通过矩阵化使事物数据库得到了进一步的压缩，从而降低了空间复杂度和时间复杂度。最后还将该算法与Apriori_MR算法进行了对比，实验结果表明，该文改进的算法比Apriori_MR算法在扫描同等事务数据库时耗时更短、加速比更大。则可以证明，改进后的Apriori算法能提高对大型数据库进行挖掘的效率。文献[3]针对Apriori算法的两个缺陷进行了改进。改进算法Improve_Apriori_1主要通过构建辅助表来减少访问表中的无效记录来大幅降低访问数据库的次数，从而提升运算效率．另外，将由事务中包含的项目情况生成的数据库表装入内存中，之后的扫描过程无需再访问数据库，而是直接访问内存以减少I/O开销，提高访问速度。改进算法Improve-Apriori2是采用对项集事务列表求交集的策略减少扫描数据库的次数，使算法达到较高效率.该算法全过程只扫描一次事务数据库，而Apriori算法则反复扫描数据库致使I/O开销较大。经过试验证明，这个两个算法的改进能有效的压缩搜索空间，减少了不必要事务的扫描时间，提高频繁项集的生成率，其性能比传统Apriori算法更优。2.2基于序列的关联规则挖掘算法Agrawal和Strikant最早提出了序列模式挖掘的概念，即从序列数据库中挖掘满足最小支持度的频繁子序列的过程。序列模式挖掘不同于关联规则挖掘项集属性内部的联系，它主要研究项集之间的联系。基于序列的关联规则挖掘算法，文献[4]提出了一种基于逻辑的频繁序列模式挖掘算法。序列模式挖掘不同于关联规则挖掘项集属性内部的联系，它主要研究项集之间的联系。传统的类Apriori频繁序列模式挖掘算法都是基于支持度框架理论，必须预先设定一个最小支持度阈值作为判断是否为频繁模式的标准，而这通常需要较深的领域知识或大量的实践来设定，因此目前仍没有统一的评判标准。同时，挖掘的规则数量庞大，挖掘结果对于用户来说难以理解。该文主要针对这两个问题，首次在频繁序列模式挖掘中引入了逻辑的思想，通过逻辑规则过滤，去除大量不合逻辑的、无用的规则集，有效的解决了挖掘结果对支持度阈值的依赖性，同时压缩了规则集的规模，较大地提高了规则集的可理解性和可用性。不同于上面的序列模式挖掘，文献[5]中提出的是带通配符约束的序列模式挖掘，是基于传统的模式挖掘问题上的提高。他们的研究背景是，对人类的很多疾病,如细菌病毒等,都与基因中某部分的重复片段有关.然而,重复模式并不是简单地复制自己,它们在序列中每次出现的形式可能不一样,模式中相邻两个字符之间可能插入或删除较短的序列片段。因此,带有通配符的序列模式挖掘比传统的序列模式挖掘更具有重要的研究价值。该论文设计的带有通配符约束的序列模式挖掘问题,用户可以定义灵活的通配符约束,模式的任意两个出现都不共享序列中同一位置的字符,使得问题定义在实际应用中更加合理。并设计了两种模式支持度的计算方法，对不同的支持度计算方法对算法的时间性能和解的完备性的影响进行了分析讨论。结果表明，与相关的序列模式挖掘算法相比,One-OffMining具有更好的时间性能和解的完备性。2.3基于约束的规则挖掘方法关联规则挖掘在实际应用中，用户的参与决定规则的有效性、可行性。因此，根据用户信息的需求设定约束条件以达到更实用、使用户更感兴趣的规则目的。基于约束的规则挖掘方法则满足这个需求，该方法将提前设定的约束条件与算法有机结合，增强了挖掘的实用性。文献[6]提出了一种深度优先遍历FP-tree的约束概念格建立算法DFTFH(depth-firsttraversalFP-treetoHasse)，进行实际应用中用户更为关心的约束关联规则挖掘问题。DFTFH算法旨在构造以规则后件固定为约束条件的约束概念格，提取频繁项集上的约束关联规则。该算法只进行一次深度优先遍历FP-tree产生所有候选节点组合，解决了现有算法重复扫描FP-tree的问题。然后依据最小支持度阈值和规则约束条件进行节点过滤，使约束概念格中的每一节点都是满足约束条件的频繁节点。最后只需扫描约束概念格中的父子节点便可提取出后件固定的约束关联规则。解决了现有算法进行约束关联规则挖掘时，构造的构造的概念格中存在冗余节点的问题。该论文最后通过实际通过实际项目中大气腐蚀数据集进行算法实验，结果表明，提出的算法效率优于现有算法，比现有算法具有更高的挖掘效率且腐蚀规则结果对材料腐蚀现状研究具有重要指导价值。并且能够通过不存在冗余节点的约束概念格提取出用户感兴趣的全部约束关联规则。以上算法还避免了Apriori类约束算法在高密度数据集出现的候选集爆炸问题。2.4基于层次的关联规则挖掘算法多媒体信息的快速增长对于内容管理的需求日益迫切，基于内容的信息检索是内容管理的一种方法。图像分类作为信息检索中的重要领域，近些年得到广泛研究[7-8]。关联规则分类[9]是图像分类中的一种新方法，是低层次视觉特征和语义概念的融合。随着图像分类问题的复杂度越来越高，传统关联规则方法，在计算效率上不是很高。层次结构是减少分类问题复杂度的一种常用方法，特别是在处理大量类别时。为进一步提高分类系统性能，文献[10]提出一种基于公理化模糊集的语义图像层次关联规则分类器，采用公理化理论（AFS）和层次结构关联规则进行算法设计。首先，在建立AFS模糊规则库基础上，这里利用层次分类方法进行语义图像分类。该论文中，利用四层结构将图像数据库组织为层次结构，它们被组织在一个层次结构中，对应于图像数据库的层次结构。为提高算法精度，在对图像数据集进行特征提取基础上，采用公理化理论（AFS）构建图像集模糊概念的AFS属性表达，提高图像集属性辨识度；其次，为提高算法计算效率，考虑采用层次结构关联规则，构建语义图像分类器，利用概念之间的本体信息，提高并行分类能力；最后，通过对算法参数及横向对比实验，显示所提算法具有较高的计算精度和计算效率。通过PASCALVOC2007和Cal