关联规则挖掘算法研究与应用

江苏大学硕士学位论文关联规则挖掘算法研究与应用姓名：陈晨申请学位级别：硕士专业：计算机应用技术指导教师：鞠时光20091216关联规则挖掘算法研究与应用作者：陈晨学位授予单位：江苏大学相似文献(10条)1.期刊论文基于Web数据挖掘的高效关联规则研究-计算机工程与科学2005,27(11)随着网络资源越来越丰富,Web数据挖掘逐渐成为因特网上资源有效利用的研究热点.本文提出通过对因特网上非结构化数据的XML格式进行筛选等处理,然后转化为结构化数据存储在SQLServcr数据库中.并在此基础之上利用关联规则发现以生成最小关联规则集来代替完全关联规则集,就可以有效地剪除弱关联规则,大幅度地减少候选频繁项目集,从而提高规则发现效率.最后,在传统经典算法Apriori基础上,利用弱关联规则的向上关闭特性设计了一个相应的高效算法.2.学位论文郭秀娟基于关联规则数据挖掘算法的研究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框架；④借鉴数学分析中的加权求平均的方法，引进了加权关联规则的发现算法，从而使得数据库中数据出现频率不同，但意义较大的问题得以有效控制，使得关联规则算法解决问题的途径大大拓宽了。在实际中有重要的指导意义。3.会议论文徐慧英.熊岳山.薛建新基于关联规则的数据挖掘系统体系结构设计本文对基于关联规则的数据挖掘系统体系结构设计进行了研究。文章阐述了数据挖掘的定义；介绍了数据挖掘在科学研究、市场营销、金融投资、产品制造、通信网络管理等领域的应用；论述了数据挖掘和AR3基于关联规则的数据挖掘系统体系结构。4.学位论文邹庆轩基于关联规则的文本数据挖掘研究2006本文提出并设计了一个文本数据挖掘系统原型，给出了系统原型体系结构并实现了该文本数据挖掘系统原型。。文本数据挖掘是通过自动提取文本信息在大量文本数据中发现未知的知识的过程，与自然语言密切相关，其关键是把提取的信息组合起来发现未知知识。文本数据挖掘不同于Web搜索，Web搜索是人们事先已知要查找什么，而文本数据挖掘是发现未知知识，事先可能并不存在。文本数据挖掘也不同于常规意义上的数据挖掘，常规数据挖掘是在数据库中发现感兴趣的模式，而文本数据挖掘是从自然语言文本中发现模式。关联规则是大量数据中各数据项之间的关联或相互联系。关联规则数据挖掘是要在给定的数据集中找出数据项之间的联系。关联规则主要描述数据集一组数据项间关系的密切程度，可以分为布尔型关联规则和量化型关联规则。关联规则的形式为X()Y。关联规则包含前提(X)和结果(Y)两部分，还用两个数值来度量规则的确定度。第一个度量值是支持度，是所有包含X和Y的项集占全部项集的比例。第二个度量值是置信度，是指包含X和Y的项集与包含X的项集之比。最为著名的关联规则发现发法是R.Agrawal提出的Apriori算法。Apriori算法用于发现单维、单层、布尔关联规则。其基本思想是基于这样一个结论：频繁项目集的任一非空子集必然是频繁项集。关联规则的挖掘一般可分成两个步骤：第一步是找出所有的支持度不低于用户设定的支持度最低值的频繁项目集；第二步是从频繁项目集中生成置信度不低于用户设定的置信度最低值的规则。FP-Growth(Frequent-Patterntree)算法由HanJW等人提出的，是一种不产生候选频繁项目集的方法。加权关联规则算法从用户的角度来解决数据库中各个项目对不同的用户的重要性不同，挖掘出对用户来说确实感兴趣的关联规则。5.期刊论文肖冬荣.杨磊.XIAODong-rong.TANGLei基于遗传算法的关联规则数据挖掘-通信技术201