《关联规则挖掘算法研究_1.docx》由会员分享，可在线阅读，更多相关《关联规则挖掘算法研究_1.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关联规则挖掘算法研究关联规则挖掘算法的研究摘要：Apriori算法是发现频繁项目集的经典算法，但是该算法需反复扫描数据库，因而效率较低。本文介绍了Apriori算法的思想，同时对已经提出的经典的关联规则更新算法FUP和IUA算法进行分析，指出其优缺点；最后对另外的改良算法，做一个简单的叙述。关键词数据挖掘；关联规则；Apriori算法Keywords：datamining；relationrule；Apriorialgorithm关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其
2、中以R.Agrawal等人提出的Apriori、AprioriTid等算法最具有影响力和代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。但实际中，碰到的情况可能是：随着时间的推移，挖掘数据库的规模可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整进而逐步聚集到我们感兴趣的频繁项目集上。因此怎样从数据发生变动后的数据库中高效地对已经推导出的关联规则进行更新，具有非常重要的应用价值，这就是所谓的增量式挖掘关联规则的问题。1关联规则问题描绘：设I=i1，i2，.，im是m个不同项目的集合，给定一个事务数据库D，其中D每一个事务T是I中一组项目的集合，即TI，T有一
3、个唯一的标志符TID。假如对于I中的一个子集X，有XT，我们就讲一个事务T包含X。一条关联规则(associationrule)就是一个形如X=Y的蕴涵式，其中X，YT，而XY=。关联规则成立的条件是：它具有最小支持度s，即事务数据库D中至少有s%的事务包含XY；它具有最小可信度c，即在事务数据库D中包含X的事务中至少有c%同时也包含Y。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。关联规则的挖掘问题能够分解为下面两个问题：(1)找出事务数据库中所有具有用户最小支持度的项目集。具有用户指定最小支持度的项目集称
4、为频繁项目集，反之称为非频繁项目集。一个项目中所含项目的个数称为该项目的长度。(2)利用频繁项目集生成关联规则。对于每一个频繁项目集A，若BA，B，且support(A)/support(B)minconf，则有关联规则B=(A-B)。目前大多数的研究主要集中在第一个问题上面。2Apriori核心算法Agrawal等人于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法Apriori算法，其核心是基于两个阶段频繁项集思想的递推算法。算法的基本思想是首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频繁项集产生强关联规则，这些规则必须知足最小支持度和最小
5、可信度。Apriori核心算法思想扼要描绘如下：该算法中有两个关键步骤连接步和剪枝步。(1)连接步：为找出Lk(频繁k一项集)，通过Lk-1与本身连接，产生候选k-项集，该候选项集记作Ck；其中Lk-1的元素是可连接的。 (2)剪枝步：Ck是Lk的超集，即它的成员能够是可以以不是频繁的，但所有的频繁一项集都包含在Ck中。扫描数据库，确定Ck中每一个候选的计数，进而确定Lk(计数值不小于最小支持度计数的所有候选是频繁的，进而属于Lk)。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，使用Apriori性质：任何非频繁的(k-1)-项集都不可能是频繁k-项集的子集。因而，假如一个候选k-
6、项集的(k-1)项集不在Lk中，则该候选项也不可能是频繁的，进而能够由Ck中删除。这种子集测试能够使用所有频繁项集的散列树快速完成。这个方法要求屡次扫描可能很大的交易数据库，即假如频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。3关联规则增量更新关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其中以R.Agrawal等人提出的Apriori、AprioriTid等算法最
7、具有影响力和代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。实际中，数据库的规模随着时间，可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整进而逐步聚集到我们感兴趣的频繁项目集上。因此怎样高效地从更新后的数据库中对已经推导出的关联规则进行更新是具有非常重要的价值的，这就是关联规则增量更新问题。广义上的关联规则的更新问题就是，在原有数据库DB的基础上，对其加上(或减去)数据库db，在新的数据库DB上挖掘新关联规则的问题。关联规则的增量式更新问题主要有三个：在给定的最小支持度和最小置信度下，当一个新的数据集db添加到旧的数据库DB中时，怎样生成dbDB中的关联规
8、则；在给定的最小支持度和最小置信度下，当从旧的数据库DB中删除数据集db时，怎样生成DB-db中的关联规则；给定数据库DB，在最小支持度和最小置信度发生变化时，怎样生成数据库DB中的关联规则。文献2中AgrawalR，和SrikantR提出的FUP算法是一个与Apriori算法相一致的针对第一个问题的更新算法。文献3中，BrinS，MotwaniR，和SilversteinC提出的FUP2算法是一个同时考虑第一个问题与第二个问题的算法。第三类问题则有冯玉才、冯剑琳提出的算法IUA和PIUA7。下面给出两个比拟经典算法：FUP和IUA算法的基本思想，并分析了各自的优缺点。(1)FUP算法的基本思
9、想对任意一个k(k1)项集，若其在DB和db中都是频繁项集，则其一定是频繁项集；若其在DB和db中都是非频繁项集，则其一定是非频繁项集；若其仅在DB(db)中是频繁项集，则其支持计数应加上其在db(DB)中的支持数以确定它能否为频繁项集。FUP算法假设在DB中发现的频繁项集LiLUni1=(n为L中最大元素的元素个数)已被保存下来。它需要对DB和db进行屡次扫描，在第一次扫描中，算法先扫描db，将L1中的元素仍为dbDB中的频繁项集的元素记入L1，并生成候选频繁1项集C1，C1中的元素为db中的频繁1项集且不包含在L1中；然后扫描DB以决定C1中的元素能否为dbDB中的频繁项集，并将是dbDB
10、中的频繁项集的元素记入L1中。在第k(k1)此扫描前，先对Lk-1用Apriori_Gen函数生成候选频繁k项集Ck，并除去Lk中的元素，即Ck=Ck-Lk，对Lk进行剪枝，即对于XLk，若存在XY且YLk-1Lk-1，则X肯定不是dbDB中的频繁k项集，应将其在Lk中删除；然后扫描db，将Lk中的元素仍为dbDB中的频繁项集的元素记入Lk，记录候选频繁k项集Ck中的元素在db中的支持数；最后扫描DB，记录Ck中的元素在DB中的支持数，扫描结束时，将Ck中是dbDB中频繁项集的元素记入Lk中。算法在Lk和Ck均为空时结束。性能分析：FUP算法利用原数据库集DB的挖掘结果，即频繁项集L，需要对D
11、B和db进行n次扫描(n为L中最大的元素的元素个数)，最后得到DBdb中的频繁项集L，所以FUP算法的效率比使用Apriori算法和DHP算法重新对dbDB进行挖掘的效率要高得多。不过，FUP算法也存在其缺点，固然它利用此算法利用了原数据库集DB的挖掘结果，但是在对新的数据库进行更新时，又需要重复的扫描原数据库DB，对候选集进行形式匹配，由于原数据库集DB相对增加的数据集db是很大的，所以在利用FUP算法对关联规则进行更新时，会消耗大量时间处理规模宏大的候选集，浪费了时间。(2)IUA3算法基本思想算法IUA采用了一个独特的候选频繁项集生成算法iua_gen，在对每一次对数据库DB扫描之前生成
12、较小的候选频繁项集，进而提高了算法的效率。它也要求上一次对数据库DB进行采掘时发现的频繁项集LiLUni1=(n为L中最大元素的元素个数)在本次挖掘时是可使用的。由于人们在发现关联规则时，经常需要不断地调整最小支持度和最小可信度来聚集到那些真正令其感兴趣的关联规则上，因此该算法具有很重要的意义。IUA算法的基本框架也和Apriori算法一致，也需要对交易数据库DB进行多趟扫描.由于有s次iua_gen函数，通过该函数的拼接将会使一些已明显不是频繁k-项目集的k-项目集成为候选k-项目集C3k中的元素，进而给iua_gen函数中的修剪增加运算量，增加了算法的时间复杂性。(2)IUA算法在关联规则
13、更新时，对k-项目集的开采，只是注意到利用已存在的频繁k-项目集的集合Lk，没有注意到基于“一个频繁项目集的任一非空子集必定也是频繁项目集性质的在本次更新时，对新产生的频繁(k-1)-项目集的集合Lk-1加以利用。由于IUA充分利用已挖掘的结果及采用有效的候选频繁项目集生成方法，并且采取以空间换时间的策略，这样以来就显著地减少了各层候选频繁项目集数目，有效地提高了关联规则的更新效率.但IUA受Apriori框架的局限，主要存在着下面缺乏：多遍扫描数据库，扫描次数取决于新增最大频繁项目集的长度；需产生大量的候选项目集。(3)其它算法还有一些关联规则更新算法，也都以IUA算法或者以FUP算法为基础
14、，在此算法的基础上进行分析，在某一方面进行改良，进而提出了一些效率相对更高改造方法，以IUA算法为基础的，例如：宋海生的UA算法10，皋军等提出的My_IUA算法11，周海岩提出的NEWIUA算法等；还有以FUP算法为基础的，例如李宝东，宋翰涛的EFUP算法8，朱全玉，汪晓刚的NEWFUP算法9等。下面简单介绍两种。1)NEWIUA算法NEWIUA算法的基本框架与IUA算法和Apriori算法一致，对k=1，2，m，采用某种策略生成候选k-项目集Ck，然后扫描数据库来确定Ck中那些k-项目集是频繁项目集。NEWIUA算法与传统的增量式更新算法不同之处主要体如今下面两点：由于有s传统的关联规则用
15、于挖掘顾客事务数据库中项集间的关联关系，而传统的关联规则挖掘算法仅能用来发现强形式，即那些具有高频率和强相关的显式。实际上数据库中还存在着很多采用目前挖掘技术所不能发现的隐式形式，这些重要的隐士形式之一便是负关联规则，即两件事情很少同时出现，但却具有较高的相关度，它具有低频率、强相关的性质，表现了数据项目集间的不容易直接观察到的强相关性质，这些隐式规则告诉我们哪些数据项目较少的一起发生，但它们却包含了非常有价值的信息，因而发现负关联规则具有特别重要的意义。几乎大部分的关联规则挖掘及其算法都只是涉及到项集间的关联规则，即正关联规则，例如“买了尿布的顾客可以能买啤酒这样的规则。可是形如“买了牛奶的
16、顾客可能不买咖啡这样的负关联规则，在实际中能够和正关联规则一样提供有价值的信息。例如，负关联规则能够帮助市场监督部门在诸多的非公平交易的警报信号中判定哪些是能够忽略的；企业能够通过综合考虑正、负关联规则进而捉住更多的商机。实际上，负关联规则的增量更新与关联规则的增量更新类似，都是在更新后的数据库中挖掘负关联规则。但目前对负关联规则增量更新的研究还处于初始阶段，在以后的学习与研究中，将重点研究负关联规则的增量更新这方面的知识。4结束语本文首先提出了关联规则的经典Apriori算法，并分析了该算法的优点以及存在的缺乏，接着引入了关联规则的相关知识，并着重讨论关联规则的更新算法，重点对FUP与IUA算法进行分析与总结，最后介绍了两种好的改良算法，希望以后对负关联规则的增量式更新的研究有所帮助。