关联规则挖掘算法的研究与改进

武汉理工大学硕士学位论文关联规则挖掘算法的研究与改进姓名：周文秀申请学位级别：硕士专业：应用数学指导教师：王仲君20081201关联规则挖掘算法的研究与改进作者：周文秀学位授予单位：武汉理工大学相似文献(10条)1.学位论文郭秀娟基于关联规则数据挖掘算法的研究2004数据挖掘技术是伴随信息量的迅速增长而诞生的，如何满足人们对知识与信息的渴求，以快速地获取知识以及应用于决策领域，已经成为当前信息处理中的热门课题之一。本文是建立在从事计算机专业教学及生产应用的基础上，以关联规则挖掘算法中的Apriori算法为基础，从改进算法、提高扫描速度入手，结合数据库中可能出现的各种数据的属性及领域知识，对关联规则的算法进行了讨论，即Apriori算法、DHP算法、JAFLR算法、含有模糊数值约束的关联规则、关联规则解空间的优化问题、加权关联规则算法等，进行了算法对比及检验；JAFLR算法实现了一次扫描数据库，提出了解决模糊数值关联规则的模糊规则模板；在对关联规则解空间优化问题处理时，引进了意想不到的关联规则和与规则模板后项不同的意想不到的规则，提出了利用x2检验及信息增益法对其规则进行处理的方法；说明数据项集间的影响程度，借鉴数学的加权求平均值方法，提出加权关联规则的算法，从而减少了由于数据库中数据出现的频率差异而导致挖掘规则的不可信现象，进一步认识在领域决策中关联规则算法的有效性，对在不同领域中做出合理决策具有指导意义。本研究侧重于关联规则挖掘的算法，主要研究工作体现在以下几方面：①在详细讨论Apriori算法的基础上，分析了相关的改进算法，得出JAFLR算法能够实现一次扫描数据库，同时带来占用内存空间问题；②结合数据库中的数据性质，提出了含有模糊数值约束的关联规则，该方法得出的规则易于理解，接近自然语言；③关联规则解空间的优化问题，提出了意想不到的模板规则及与规则模板后项不同的意想不到的规则，这些规则是最终应提交给用户的主要结果，即那些事先无法遇见的规则，并提出了修改的Apriori框架；④借鉴数学分析中的加权平均方法，引进了加权关联规则的发现算法，从而使得数据库中数据出现频率不同，但意义较大的问题得以有效控制，使得关联规则算法解决问题的途径大大拓宽了；⑤在地球物理勘探数据处理中引用了关联规则挖掘算法，对塔河地区重磁数据进行了实验，并得到了较好的效果，对今后在地球物理勘探数据的处理中，拓宽数据挖掘的应用领域具有重要的指导意义。数据挖掘是指从大量的数据中发现人们事先不知道的、有用的知识(或模式)的处理过程，它是继数据库、人工智能等领域之后发展起来的一门重要学科。随着计算机软、硬件技术的发展以及在各行各业中的应用，使得人们对数据挖掘技术的需求越来越迫切。由于挖掘到的知识能够给其领域以有力的支持，因此，数据挖掘技术得到了广泛的应用。在数据挖掘算法的研究中，比较有影响的是关联规则发现算法，它是数据挖掘研究的一个重要分支，也是数据挖掘的众多知识类型中最为典型的一种。该问题于1993年由Agrawal等人在对市场购物篮问题(MarketRuleAnalysis)进行分析时首次提出的，用以发现商品销售中的顾客问题。关联规则可以发现存在于数据库中的项目(Items)或属性(Attributes)间的有趣关系，这些关系是预先未知的和被隐藏的，即不能通过数据库的逻辑操作或统计方法得出。这说明它们不是基于数据自身的固有属性，而是基于数据项目的同时出现的特征，所发现的规则可以辅助人们进行市场运作、决策支持、商业管理及网站设计等。因此对关联规则算法的研究是非常重要的。关联规则是指从一个大型的数据集(Dataset)中发现有趣的关联(Association)或相关(Correlation)的关系，即从数据集中识别出频繁出现的属性值集(SetsofAttribute-Values)，也称为频繁项集(FrequentItemsets，简称频繁集)，然后再利用这些频繁集创建描述关联关系的规则的过程。在关联规则描述中，需要指定规则必须满足的支持度和信任度的门限，即最小支持度和最小信任度；若给定一个事务数据集(TransactionDataset)D及用户指定的最小支持度(min_sup)与最小信任度(min_conf)，则关联规则挖掘问题即是发现所有满足最小支持度与最小信任度约束的关联规则；关联规则数据挖掘方法中规则的发现思路还可以用于序列模式的发现，寻找事务在时间上的规律等。关联规则挖掘的问题自提出以来，人们相继提出了许多关联规则挖掘的算法，这些算法基本上都是围绕如何快速高效的生成频繁集这一核心问题进行展开的，并在此基础上提出一些改进的方法。由于关联规则挖掘中最为耗时的操作是发现频繁集，因此大部分算法的主要特征是对这部分的工作进行有效的划分。在数据库中包含各种不同属性的数据，因此所采取的挖掘方法也不同，关联规则挖掘最初的算法是针对布尔关联规则的挖掘，以后又扩展到分类关联规则、数值型关联规则、多概念层次型关联规则等。目前，探索关联规则不同类型并提出相应的挖掘算法是一项重要的内容。本文围如何提高关联规则算法的效率，挖掘出更为有价值的规则，结合领域知识，从不同的角度进行了研究。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算法则通过统计任意两个属性间的组合次数直接获得最长频繁项目集。该算法实现了一次扫描数据库，但同时带来了占用庞大内存空间的问题，即程序设计中存在的运行时间与占用存贮空间的矛盾。第四章讨论了含有模糊数值约束的关联规则的定义、算法，将模糊查询与归纳模板有机结合，提出挖掘含有模糊数值约束的关联规则的定义、公式及挖掘算法，利用最小支持度和最小信任度约束进行前期挖掘，然后生成规则模板，利用模糊查询和语言量词概念对前期的挖掘结果进行进一步的挖掘，因此模糊关联规则是关联规则挖掘的一个扩展，模糊数值关联规则的优点是它所表达的语义与人的表达方式非常接近，易于理解。第五章讨论了关联规则解空间的优化问题，给出了意想不到的关联规则(即可能对用户是有趣的规则)的定义、算法。提出了两类意想不到的关联规则的基本定义，一类是意想不到的模板规则；另一类是与规则模板后项不同的意想不到的规则，这些规则是最终应提交给用户的主要结果，即那些事先无法遇见的规则。提出了利用x22检验的方法剔除那些缺乏相关的项集的方法，并给出了利用信息增益对第二类规则进行排序的方法，表明信息增益越大的规则越是有趣的规则。在算法设计时，给出了修改后的框架，使得Dx中的频繁集分为(γ)F1Dx和γFDx1两个部分，使得频繁集生成的数量大大的减少，从而提高了算法的效率，因此这一部分是对含有项目约束的关联规则挖掘的一个拓展。在对关联规则的算法的讨论中，发现在现实生活中的事物间往往存在着一定的关联关系，但是由于数据的分布不均匀，以至于出现频率相差较大时，导致最低支持度给高给低都可能产生得出与事实不符的规则。借鉴数学中的加权求平均的方法，引入了加权关联规则问题，即引入项目加权值概念，从而扩展了关联规则的算法，提出项目的k-支持期望，进一步讨论了加权关联规则的算法，特别需要指出的是在加权关联规则算法中，Apriori算法中的关于频繁项目集的任一子集必是频繁的不成立。因此，由于加权值的引入使得频繁项目集的子集不再一定是频繁的。本研究主要侧重于关联规则的算法，所做的工作有以下几点：①在详细讨论Apriori算法的基础上，总结分析了相关的改进算法，认为JAFLR算法虽然实现了一次扫描数据库，但同时带来了占用内存的问题；②结合数据库中的数据性质，提出了含有模糊数值约束的关联规则，该方法得出的规则易于理解，接近自然语言；③关于关联规则解空间的优化问题，提出了意想不到的模板规则及与规则模板后项不同的意想不到的规则，这些规则是最终应提交给用户的主要结果，即那些事先无法遇见的规则。并提出了修改的Apriori框架；④借鉴数学分析中的加权求平均的方法，引进了加权关联规则的发现算法，从而使得数据库中数据出现频率不同，但意义较大的问题得以有效控制，使得关联规则算法解决问题的途径大大拓宽了。在实际中有重要的指导意义。2.会议论文王珂.梁允荣基于不变数据库的关联规则增量更新算法的研究关联规则是数据挖掘中的重要研究内容之一.目前,已经提出了许多算法用于发现大规模数据库中的关联规则.但是,通常面对的数据库极为庞大,扫描一遍数据库需要花费很多的时间,降低了效率.另一方面,也需要高效的算法来更新维护这些已经挖掘出来的规则以达到节省资源的目的.针对这种情况,提出一种新的算法,它描述了在事务数据库和最小支持度都不变增加项目集时,如何高效地发现新的总项集的关联规则.这个算法充分利用已经挖掘的规则和已经实现的经典挖掘算法,简单高效.同时试验证明,该算法是有效可行的.3.学位论文王翔数据库中关联规则发现的研究2000关联规则是KDD中的一个重要研究方向,该文着重对这个方向进行了研究,包括关联规则算法效率的提高、关联规则增量式维护技术、数量型关联规则的发现、基于数据立方体的多维关联规则元规则制导发现、N-维事务间关联规则发现等多个方面的研究.同时对序贯模式也进行了一些研究.在分析评价现有关联规则发现算法的基础,针对关联规则发现中处理数据比较大和预处理代价昂贵等关键问题,对经典的关联规则算法进行了改进.此个,针对目前数据挖掘理论研究和实际需求中提出一些热点问题,对关联规则作了一些扩展,主要是:①讨论了数量型关联规则发现问题QARP,给出发现数量型关联规则的算法MAQA.②将n-维事务间关联规则跟经典的关联规则相比较,研究了发现事务间关联规则的可行性.实现了所提出的关联规则发现算法的原型系统KDD-AR.4.会议论文周水庚.胡运发.陶晓鹏分布数据库关联规则的递增挖掘1998本文对分布数据库关联规则的递增挖掘问题进行研究.结合有关关联规则的挖掘算法,提出一种分布数据库环境下关联规则的递增挖掘算法.5.学位论文陈富赞大型数据库中关联规则发现方法的研究2000数据挖掘是能够从大型数据库中自动抽取出新颖的、有用的、可理解模式的处理过程.复杂及超大规模的数据使得数据挖掘系统的性能至关重要.该文主要针对大型数据库中关联规则挖掘问题进行了比较深入地研究.6.会议论文陆建江.万谦集合值数据库的关联规则2000在信息处理领域，大型关系数据库中的数据挖掘是一个热点。这篇文章讨论集合值数据库的关联规则的挖掘方法，文中采用RFCM算法将数量属性划分成多个语言值，由此生成一系列的语言值关联规则，接着给出了语言值关联规则的挖掘方法，此方法能挖掘所有有意义的语言关联规则。最后通过一个实例说明此方法的正确性。7.学位论文汪慎文数据库中的多值关联规则及其挖掘算法研究2005面对海量的存储数据，如何从中发现有价值的信息或知识，成为一项非常艰巨的任务。数据挖掘就是迎合这种要求而产生并迅速发展起来的。数据挖掘，又称为数据库中的知识发现，就是从数据集合中发现隐含的、先前未知的、对决策有潜在价值的用户感兴趣的知识。关联规则是数据挖掘研究中的一个重要课题，关联规则为发现数据之间的潜在联系提供了一种有效的机制。关联规