关联规则算法探讨

梁伟（中国地质大学信息工程学院，湖北武汉430074

摘要：本文对关联规则的发展进行了简单的介绍，分析了关联规则的经典算法，介绍进了一种新的关联规则算法，并对这三种算法在挖掘关联规则的特点进行了对比分析，最后对关联规则以后的发展进行了总结。

关键词：数据挖掘；关联规则；算法；探讨

1发展历史

随着信息技术的迅猛发展,许多领域搜集、积累了大量的数据,迫切需要一种新技术从海量的数据中自动、高效地提取所需的有用知识。对这些海量数据进行研究的过程中，数据挖掘技术受到越来越多的关注。我们可以使用数据挖掘技术从海量数据中发掘其中存在的潜在规律。并将这些规律进行总结，用于今后的决策。采用关联规则在大型事务数据库中进行数据挖掘是数据挖掘领域的一个重要研究内容。从大量数据中发现项之间有趣的、隐藏的关联和相关联系正是关联规则目的。

关联规则技术在不断成熟和发展，应用范围不断扩大，由最初的购物篮分析发展到计算机入侵检测、搜索引擎、警务预警、交通事故、保险业、金融业、农业专家系统、教学评估、股票分析等领域。在理论研究方面，由最简单的单维、单层、布尔关联规则逐渐向复杂形式扩展，由频繁模式挖掘不断扩展到闭合模式挖掘、扩展型关联规则、最大模式挖掘、衍生型关联规则、关联规则隐私保护、挖掘后处理、增量挖掘、规则主观兴趣度度量、相关模式、数据流等多种类型数据上的关联规则挖掘等。

2相关概念

设项的集合I={il，i2，…，im}，D为数据库事务集合，每个事务T是一个项目子集，似的TI。每个事务由事务标识符TID标识。若有XI，XT，则称T包含X；如果X有k个元素，称X为k-项集。

关联规则的逻辑蕴含式为：XY[s,c]，其中XI，YI且XY=。规则XY在事务集D中成立，并且具有支s和置信度c。支持s是指事务集XY含的百分比：support(XY)=P(XY)，置信度c是指D中包含X的事务同时也包含Y的百分比confidence(XY)=P(Y|X)。

对于一个事务集D，挖掘关联规则的问题就是找出支持度和可信度分别大于用户给定的最小支持度阀值(minsupp)和最小置信度(minconf)阀值的关联规则，这种规则成为强关联规则。

3经典算法

基于频繁集的方法是关联规则挖掘的主要方法,Aproiri算法是基于频繁集的算法最主要算法之一，在数据挖掘中具有里程碑的作用,但是Apriori算法本身存在着一些固有的无法克服的缺陷，而后出现的基于频繁集的另外一种算法FP-gorwth算法能较好地解决APriori算法存在的一些问题。下面分别介绍两种经典的算法。

3.1产生候选频繁项集

Apriori算法是RabeshAgrawal等人在1994年提出的，该算法采用了一种宽度优先、逐层搜索的迭代方法：首先产生所有的频繁1-项集，然后在此基础上依次产生频繁2-项集、频繁3-项集……，直到频繁k-项集为空集。在此过程中，产生每个频繁项集都需要扫描一次数据库，通过对数据库D的多趟扫描来发现所有的频繁项目集。

设Ck表示候选k-项集，Lk表示Ck中出现频率大于或等于最小支持数的k-项集，即k-频繁集或者是k-大项集。该算法的基本过程如下。

①首先计算所有的C1；

②扫描数据库，删除其中的非频繁子集，生成L1(1-频繁项集)；

③将L1与自己连接生成C2(候选2-项集)；

④扫描数据库，删除C2中的非频繁子集，生成L2(2-频繁项集)；

⑤依此类推，通过Lk-1((k-1)-频繁项集)与自己连接生成Ck(候选k-项集)，然后扫描数据库，生成Lk(频繁k-项集)，直到不再有产生频繁项集为止。

Apriori算法虽然能较有效地产生关联规则，同时也存在着不少缺点:

①数据库太大时对候选项集的支持度计算非常繁琐，当支持度、置信度阀值设置太低会产生过多的规则，致使用户难易人为地对这些规则进行出区分和判断。

②要对数据进行多次扫描，需要很大的I/O负载，算法的效率不高。

③当数据库D很大时，会产生庞大的候选集，导致算法的耗时太大。

3.2不产生候选频繁项集

FP-Tree算法由JiaweiHan提出。它的基本思路是将数据集中的重要信息压缩在一个称为频繁模式树(FP-Tree)的数据结构中，然后基于FP-Tree生成数据集中所有的频繁项集。该算法对所有频繁项集的挖掘分为以下两步：①构造频繁模式树FP-Tree。在FP-Tree中，每个结点有4个域组成结点名称、结点计数、结点链及父结点指针。另外，为方便树遍历，创建一个频繁项头表，它由两个域组成：项目名称及结点链头，其中结点链头指向FP-Tree中与之名称相同的第一个结点；②调用FP-Growth挖掘出所有频繁项集，具体算法描述如下。

①生成频繁模式树，首先，扫描事务数据库D一次，产生频繁1-项集，并把它们按降序排列，放入L表中。其次，创建FP-Tree的根结点，以“null”标记。再一次扫描D，对于D中的每个事务按L中的次序排序，并对每个事务创建一个分枝。

②挖掘频繁项集，首先，从FP-tree的头表开始，按照每个频繁项集的链接遍历，列出能够到达此项的所有前缀路径，得到条件模式基。其次，用条件模式基构造对应的条件FP-tree。第三，递归挖掘条件FP-tree，直到结果FP-tree为空，或者只含有唯一的一个路径(此路径上的每个子路径对应的项集都是频繁项集)。

FP-Growth算法是一种基于模式增长的频繁模式挖掘算法，采用了“分而治之”策略，它能够在不产生候选频繁项集的情况下挖掘全部频繁项集，直接将数据库压缩成一个频繁模式树FP-tree，只需要两次扫描数据库，相对于Apriori算法效率快一个数量级。该算法虽然可以避免产生候选项目集，但在挖掘过程，当存在大量大项集，并且如果得到的频繁模式树FP-tree分支很多、分支长度很长时，该算法将需要构造出太多的条件FP-tree，这不仅费时且要占用大量存储空间，导致挖掘效率不高。另外构造FP-tree是自顶而下构造的，而生成条件模式基是自底而上生成的，在挖掘时需要反复地进行搜索FP-tree，存储结构采用双向链表，则会进一步增加内存的开销。

4一种新的关联规则算法

目前有许多新的关联规则算法出现，但大都是根据Apriori算法的框架结构来改进的。本文将介绍一种新的基于幂集的挖掘算法PS(PowerSet)，该算法将完全脱离Apriori算法的框架结构。

4.1算法的相关概念

①幂集合PS（A）定义：对于任意一个非空集合A，它的幂集合PS(A)就是由A的全部子集组成的集合。例如非空集合A：{a，b，c}，则它的幂集合PS（A）={{}，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}。

②对事务数据库D，I={il，i2……im}，XI，在D中包含X的事务数就称为D中的频度，也可简称为X的频度。

③集合A={a1，a2，a3，……，ai}中元素的个数称为该集合A的长度Length(A)。

4.2算法描述

PS算法的主要步骤为：

①首先扫描事务数据库D，并对每一条事务记录本身进行拆解，例如，XYZ为一事务记录，可以拆分为XY、XZ、YZ、X、Y、Z、XYZ七个子集。

②接着得到子集依据集合长度Length(A)存放在不同的结果表中，并做频度计数，如果结果表已存在对应的子集，则将该集合的计数值加1，如果不存在，则将该集合加入其中，并设置初始值为1。这样此事务记录的拆解才算结束。当事务数据库被扫描一次以后，所有的事务记录都拆解完毕。

③最后根据用户输入的最小支持度和最小置信度阀值来产生频繁项目集和关联规则。

该算法通过对数据库的一次扫描就能挖掘所有的频繁集，大大降低了I/O存取的时间；而且算法运算简单且速度较快，用户可以任意改变最小支持度阀值使算法弹性增大，执行的效率稳定，不受支持度的变动的影响，在增量式挖掘中可以运用该算法而不需要对数据库进行前期的处理。算法在新增记录时比Apriori算法节省许多重复搜索记录的时间，但是该算法在存储的空间上会花费比Apriori算法大上数倍的存储空间，所以PS算法是一种以存储空间换取挖掘时间的方式[1]。

5结语

本文对关联规则的发展做了简单的介绍，对关联规则的两个经典算法进行了分析并介绍了一种完全脱离Apriori算法的框架结构的新算法。重点分析了三种算法的特点，得出对于将来的挖掘关联规则的改进和研究重点仍会在减少I/O操作、减少存储空间、产生更少的候选项集和如何更有效地挖掘数据中更实用的关联规则上。

参考文献：

[1]王琳莎,林国龙,杨斌.新的关联规则算法在物流行业中的应用[J].物流工程与管理.2009(3):41-43.

[2]方风波.关联规则挖掘技术发展及应用[j].中小企业科技.2007(6):108-109.

[3]朱绍文,王泉德等.关联规则挖掘技术及发展动向[J].计算机工程.2000(9):4-6.

[4]白利果,乔钢柱,曾建潮.关联规则挖掘在农业产值分析中的应用[J].太原科技大学学报.2008(10):335-338.

[5]李新仕.基于FP-tree的关联规则挖掘算法的研究.广西大学硕士学位论文.2006:15-20