关联规则挖掘算法

关联规则挖掘算法所谓的数据关联，是指数据库中一类可被发现的价值信息.。其中，如果两个或两个以上取值之间具有一定规律，也就是数据关联，其反映了一定数据集中各元素间的有趣关系。关联规则是数据挖掘的主要分支，最初是由Agrawal等专家学者于20世纪90年代初分析市场购物而提出，主要用于发现顾客的商品消费模式，经过了十几年的发展，已日益成熟和完善，可协助人们完成各项任务，比如顾客分析，、因素分析,、关系分析等。通常来讲，关联规则挖掘是目前运用最普遍的一种数据挖掘类型，起初主要被运用于商业分析，逐渐也被运用于医疗、建筑工程、通讯、保险、银行证券等领域行业的错误检验方面，其整体发展形势不容小觑。另外，关联规则算法作为关联规则挖掘的重要内容，一直受到广大专家和学者的关注和重视，至今已发展出许多有效的关联规则挖掘算法。事实上，关联规则挖掘就是发现符合事先限定标准和频率的任何规则，主要研究对象是各类数据库。因此，本文结合大数据环境的背景，基于经典频繁集算法的简介，着重分析了基于Apriori的算法优化和多层关联规则挖掘算法，最后阐述了几种经典算法的实现方式，从而提高关联规则挖掘的质量和效率，最大限度地发挥数据价值，如此才能满足大数据时代发展的需要。1经典频繁集算法关联规则挖掘的一个经典算法是Apriori算法，其核心思想是把发现关联规则的工作分两步：（1）通过迭代检索出事物数据库中的所有频繁项集；（2）从频繁项集中构造出满足用户最低信任度的规则。挖掘或识别所有频繁项集是Apriori算法的核心，占整个计算量的大部分。挖掘关联规则的总体性能由第（1）步决定，第（2）步相对容易实现。为了生成所有频集，使用了递推的方法。其核心思想简要描述如下：首先产生频繁1-项集L1,然后是频繁2-项集L2,直到有某个r值使得Lr为空,这时算法停止。在第k次循环过程中，先产生候选k-项集的集合Ck,Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个（k-2）连接来产生的。Ck中的项集是用来产生频繁集的候选集，最后的频繁集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk,这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频繁集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。2基于Apriori的算法优化和改进为了提高Apriori算法的效率，人们对该算法进行了优化和变形，其中算法的变化主要集中在两点：产生候选项集的方法和候选项集支持度的计算。以下是一些典型的优化算法：1基于HASH的算法在Apriori算法产生候选项频繁集的过程中，如何高效产生频繁2-项集是提高数据挖掘性能的关键，DHP（Directhashingandpruning）算法很好地解决了这一问题。使用该算法产生频繁项集的过程分几步：首先获得频繁卜项集并且产生候选2-项集的散列表；然后基于散列表产生候选2-项集，进而得到频繁2-项集并且产生3-项集的散列表，……，直到产生频繁b项集。这种基于散列技术大大减少了需要考虑的k-项集的个数，尤其是2-项集，并且随着k的增加候选项集的个数急剧减小，解决了性能上的瓶颈问题。2.2基于划分的算法当数据库中的数据量特别大时，对数据进行处理是很困难的，基于划分的算法可以在不增加I/O和CPU使用的基础上解决这一问题。该算法分两步：（1）根据内存容量，在逻辑上把交易数据库划分为若干非重叠的部分，然后把每个部分看作一个独立的数据库寻找其中的频繁集，即局部频繁集。在第（1）步结束时把每个划分的局部频繁集进行合并得到全局频繁集的候选集。第（2）步计算每个局部频繁集在原交易数据库中的支持度，得到全局频繁集。2.3基于采样的算法针对大型数据库可以使用基于采样的算法挖掘其中的关联规则。首先由数据库中随机采样得到的数据产生可能在整个数据库范围满足参数指标的规则，然后使用剩余数据对这些规则进行检验。为了不遗漏可能满足设定参数的频繁集，对于采样数据集一般使用比用户定义的最小支持度小的支持度阐值。基于采样的算法是一种在精确度和效率之间取得平衡的方法，这种算法减少了扫描次数，显著降低了I/O代价，但是牺牲了一些精度，即存在数据扭曲问题。2.4减少事务数根据Apriori性质，当一个事务中不包含k一项集时，它一定不包含k+1一项集,这样可以给这些事务加上标记，在下一次扫描数据库时对这些事务不予考虑，减少需要扫描的事务数。3多层关联规则的挖掘算法多层关联规则挖掘算法是根据概念层的每个抽象层上定义最小支持度阈值的特性，使用多种策略，挖掘多层关联规则，不同于前面基于支持度一可信度框架的方法。目前，已经提出很多挖掘多层关联规则的算法，Han等提出的MLJ2L1及其变种MLT1LA,MLTML1,MLT2LA和R.Srikant等提出的Cumulate、stratify及其变种Etimate,EstMergc等。4多维关联规则挖掘算法对于多维数据库而言，除维内的关联规则外，还有一类多维的关联规则。例如：年龄（X,“20…30”）职业（X,“学生"）==>购买（X,“笔记本电脑”）在这里就涉及到三个维上的数据：年龄、职业、购买。根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。年龄（X,“20…30”）购买（X,“笔记本电