关联规则挖掘算法研究

知识就是力量。当前快速发展的新的IT技术、电子商务及互联网的迅速普及，导致在各个应用领域的数据库中存储了大量的数据，这些数据集中包含了很多有用的知识，因此如何发现各种大型数据库中所隐藏的、预先未知的信息以辅助相应的应用显得尤为重要，这正是数据挖掘所要完成的任务。近年来国外学者提出了一系列的数据挖掘理论，世界上的主要IT公司，如IBM、Oracle及Microsoft等也已相继推出了各自的数据挖掘产品。关联规则挖掘作为数据挖掘的一个重要研究分支，其主要的研究目的是从大型数据集中发现隐藏的、有趣的、属性间存在的规律。由于形式简单、易于理解，且是从大型数据中提取知识的主要手段，因此关联规则挖掘的研究与应用已经得到了数据库、人工智能及统计学等领域里的学者的极大关注，并取得了不少的研究成果。与人工智能中的神经网络、遗传算法及统计学不同的是，关联规则挖掘处理的对象是大型的数据集，而神经网络和遗传算法等人工智能方法通常处理的数据对象通常相对较小，且人工智能的方法重在寻找输入输出间的模型，而关联规则的挖掘则是用于发现数据集合中所包含的属性间的规律，其结果不是一个具体的模型而是数量众多的规则。此外，统计学中的方法尽管处理的对象也可以是大量的数据，然而其主要作用是用于确定数据的统计分布或统计模型，而不能描述数据集中所包含的属性间的规律。本文在国家863项目的资助下，主要对含有项目约束的关联规则挖掘、模糊数值约束的关联规则挖掘、优化关联规则的解空间、Web使用挖掘及数值型关联规则挖掘的统计方法进行了深入的研究和探讨，提出了一系列的定义、定理及新算法，解决了若干理论和实际方面的问题。第2章系统地介绍了含有约束的关联规则挖掘的分类，给出了含有约束的关联规则挖掘的定义、定理及算法。从技术的观点详细介绍了其目前的发展状况，给出了关联规则挖掘中(特别是含有项目约束的关联规则挖掘中)相关的定义及名词解释，提出了挖掘含有项目约束的关联规则的一些重要定理，设计了高效的挖掘算法，本文提供的方法可以有效地解决低支持度、长模式的关联规则挖掘问题。第3章利用模糊集理论解决了现有的关联规则挖掘方法中未考虑与项目相关的数值信息的缺陷，提出了含有模糊数值约束的关联规则的定义、算法。将模糊查询和规则模板的概念有机的结合起来，给出了挖掘含有模糊数值约束的关联规则的公式和完整的挖掘方法，给出了相关的实验设计。实验结果表明本文给出的研究方法对于挖掘含有数值约束的关联规则具有一定的指导意义。第4章讨论了如何优化关联规则的解空间的问题。提出了意想不到的关联规则(即对用户来说是有趣的规则)的定义、算法。给出了两类意想不到的关联规则的定义，一类是意想不到的模板规则，本文认为模板规则中的一部分有必要进 行更新，以纠正领域知识的偏差，纠正后的模板规则对于以后的挖掘具有非常重 要的作用。另外一类是与规则模板后项不同的意想不到的规则，这类规则实际上 就是我们最终需要提交给用户的主要结果，即那些事先无法预见的规则。给出了 相关的挖掘算法，提出了利用 X‘检验的方法去除那些缺乏相关的项集的方法，提 出了利用信息增益对第二类规则进行排序的方法，并指出信息增益越大的规则是 有趣度越大的规则。在算法设计时，提出了修改后的Apriori框架，使得生成的频 繁集数量得到了大大的减少，从而提高了算法的效率。 第5章给出了对Web日志数据进行挖掘的相关定义及算法作Web使用挖掘＼ 给出了聚合记录、客户记录、及客户序列的定义及它们间的包含关系等，这些定 义为进一步的算法设计提供了有力的工具和理论基础。在讨论对Web日志文件进 行挖掘的相关算法时，本文充分考虑了时间约束的问题，给出了利用新颖的数据 结构oT树）生成备选集的重要方法，这与其他文献中利用散列树生成备选集的 方法相比具有很大优越性，第一减少了不必要的节点的生成，因此树的体积变得 相对较小；此外，PT树的查找方法更为简单，无需采用散列函数，因此降低了算 法的运行时间，提高了效率。设计了相关的实验数据，并用实验说明了所给算法 的有效性。 第6章给出了多概念层次的数值型关联规则挖掘定义及算法的框架，多概念 层次的数值关联规则挖掘实际上是利用了统计学中的假设检验的方法来确定规则 的有趣程度，由于这类规则在提交给用户的时候需要一个比较项，因此有利于用 户的理解，同时对它的挖掘可以回避最小信任度门限的指定。介绍了利用修正差 值分析作为有趣度评判标准的数值型关联规则挖掘的定义及算法，该算法的优点 是既可以发现正相关的规则也可以发现负相关的规则，同时可以避免人为指定最 小信任度门限的麻烦，特别是该算法发掘的规则往往是其他算法所忽略的重要规 则。本文所有各章的工作均是围绕如何提高关联规则的挖掘效率进行的，所不同 的是研究角度不一样罢了。