基于关联规则数据挖掘算法的研究

数据挖掘是指从大量的数据中发现人们事先不知道的、有用的知识（或模式）的处理过程，它是继数据库、人工智能等领域之后发展起来的一门重要学科。随着计算机软、硬件技术的发展以及在各行各业中的应用，使得人们对数据挖掘技术的需求越来越迫切。由于挖掘到的知识能够给其领域以有力的支持，因此，数据挖掘技术得到了广泛的应用。 在数据挖掘算法的研究中，比较有影响的是关联规则发现算法，它是数据挖掘研究的一个重要分支，也是数据挖掘的众多知识类型中最为典型的一种。该问题于1993年由Agrawal等人在对市场购物篮问题（Market Rule Analysis）进行分析时首次提出的，用以发现商品销售中的顾客问题。关联规则可以发现存在于数据库中的项目（Items）或属性（Attributes）间的有趣关系，这些关系是预先未知的和被隐藏的，即不能通过数据库的逻辑操作或统计方法得出。这说明它们不是基于数据自身的固有属性，而是基于数据项目的同时出现的特征，所发现的规则可以辅助人们进行市场运作、决策支持、商业管理及网站设计等。因此对关联规则算法的研究是非常重要的。 关联规则是指从一个大型的数据集（Dataset）中发现有趣的关联（Association）或相关（Correlation）的关系，即从数据集中识别出频繁出现的属性值集（Sets of Attribute-Values），也称为频繁项集（Frequent Itemsets，简称频繁集），然后再利用这些频繁集创建描述关联关系的规则的过程。在关联规则描述中，需要指定规则必须满足的支持度和信任度的门限，即最小支持度和最小信任度；若给定一个事务数据集（Transaction Dataset）D及用户指定的最小支持度（minsup）与最小信任度（minconf），则关联规则挖掘问题即是发现所有满足最小支持度与最小信任度约束的关联规则；关联规则数据挖掘方法中规则的发现思路还可以用于序列模式的发现，寻找事务在时间上的规律等。 关联规则挖掘的问题自提出以来，人们相继提出了许多关联规则挖掘的算法，这些算法基本上都是围绕如何快速高效的生成频繁集这一核心问题进行展开的，并在此基础上提出一些改进的方法。由于关联规则挖掘中最为耗时的操作是发现频繁集，因此大部分算法的主要特征是对这部分的工作进行有效的划分。在数据库中包含各种不同属性的数据，因此所采取的挖掘方法也不同，关联规则挖掘最初的算法是针对布尔关联规则的挖掘，以后又扩展到分类关联规则、数值型关联规则、多概念层次型关联规则等。目前，探索关联规则不同类 型并提出相应的挖掘算法是一项重要的内容。本文围如何提高关联规则算法的效率，挖掘出更为有价值的规则，结合领域知识，从不同的角度进行了研究。 R.Agrawal等人提出的Apriori算法是关联规则的基本算法，以后出现的各种算法基本上都是基于Apriori算法改进的。Apriori算法利用了如下两个基本性质：即任何强项集的子集必定是强项集及任何弱项集的超集必定是弱项集，该算法的关键是尽可能生成较小的侯选项目集，它的依据是一个频繁项目集的任一子集必定是频繁项目集，进而提出算法的基本框架描述。本算法的突出特点是利用第k-1趟扫描中得到的强项集的集合Lk-1来生成k-项集Ck，由apriori-gen（Lk）实现。同时分析了Apriori算法的缺点是Ck中的每个元素需要在交易数据库中进行验证，从而决定是否加入Lk，此验证过程是该算法的一个瓶颈，这个方法要求多次扫描很大的交易数据库，I/O的负载过大。因此，引入了快速更新算法、DHP、JAFLR算法。 DHP算法重点是侯选2-项集的生成，侯选项个数少于以前所述方法生成的个数，解决了生成L2时的性能瓶颈问题，对数据进行了剪枝，减少了数据量。而JAFLR算法则通过统计任意两个属性间的组合次数直接获得最长频繁项目集。该算法实现了一次扫描数据库，但同时带来了占用庞大内存空间的问题，即程序设计中存在的运行时间与占用存贮空间的矛盾。 第四章讨论了含有模糊数值约束的关联规则的定义、算法，将模糊查询与归纳模板有机结合，提出挖掘含有模糊数值约束的关联规则的定义、公式及挖掘算法，利用最小支持度和最小信任度约束进行前期挖掘，然后生成规则模板，利用模糊查询和语言量词概念对前期的挖掘结果进行进一步的挖掘，因此模糊关联规则是关联规则挖掘的一个扩展，模糊数值关联规则的优点是它所表达的语义与人的表达方式非常接近，易于理解。 第五章讨论了关联规则解空间的优化问题，给出了意想不到的关联规则（即可能对用户是有趣的规则）的定义、算法。提出了两类意想不到的关联规则的基本定义，一类是意想不到的模板规则；另一类是与规则模板后项不同的意想不到的规则，这些规则是最终应提交给用户的主要结果，即那些事先无法遇见的规则。提出了利用(2检验的方法剔除那些缺乏相关的项集的方法，并给出了利用信息增益对第二类规则进行排序的方法，表明信息增益越大的规则越是有趣的规则。在算法设计时，给出了修改后的框架，使得中的频繁集分为和两个部分，使得频繁集生成的数量大大的减少，从而提高了算法的效率，因此这一部分是对含有项目约束的关联规则挖掘的一个拓展。 在对关联规则的算法的讨论中，发现在现实生活中的事