英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
改进的Apriori关联规则挖掘算法
Darshan M. Tank
印度，L.E.College，信息技术专业，Morbi-363642
电子邮件：dmtank@gmail.com
摘要：关联规则是数据挖掘的主要技术，而Apriori算法是关联规则挖掘算法中的一种经典的算法。许多的关于关联规则和其转变的算法都是在Apriori算法的基础上提出来的，但是传统的算法的效率不高，对于频繁项集挖掘的两个瓶颈：大量的候选项目集，计算他们的支持度的效率较差。改进的算法降低了C2的一个冗余修剪的操作。如果频繁1项集的数量为n,当修剪操作为Cn时，连接候选2项集的数量为Cn。所提出的该算法减小了候选2项集的修剪操作，从而节省了时间，提高了效率。对于瓶颈：计算支持度的效率低下，提出的算法优化自己的操作，通过事务标记，以加快支持度的计算。Apriori算法是最古老和最通用的频繁模式挖掘（FPM）算法之一。它的优点和有节制的搜索空间的变量在对于非常大的数据库进行挖掘是很有优势。提出的算法通过减少修剪操作来改进Apriori算法，通过先验根操作产生候选2项集。此外，它采用了级数标签法快速地计算出支持度，从而使瓶颈被克服。
关键词：关联规则挖掘，频繁项集的产生，支持度和置信度。
I、引言
- 基本概念
许多商业企业从他们的日常操作中积累了大量的数据。例如，每天在杂货店收银台的大量的客户的购买记录的数据，表格1展示出来这样的数据的一个例子，俗称市场篮子交易。在此表中的每一行对应于交易，它包含一个唯一的标识符标记的TID和一组由一给定客户购买的物品。零售商对于分析这些数据以了解客户的购买行为很感兴趣。这样的有价值的信息可以被用来支持各种业务相关的应用程序，如市场推广，库存管理，及客户关系管理。
关联分析对于发现隐藏在大型数据集[1]椎间盘买个有趣的关系是很有用的。未覆盖的关系可以用关联规则或频繁项目集来表示。下面的规则可以从表1中所示的数据集来提取：
{尿布}→{啤酒}
表1.市场篮子交易的例子
该规则表明，销售尿布和啤酒之间存在很强的关系，很多买尿布的顾客也会买啤酒。零售商可以使用这种类型的规则，以帮助他们确定交叉销售产品从而给客户新的机遇。
除了购物篮数据关联分析也适用于其他应用领域，如生物信息学，医学诊断，Web挖掘和科学的数据分析。在地球的科学数据分析中，例如，关联图案可以揭示海洋、陆地和大气过程之间的有趣的联系。这些信息可以帮助地球科学家更好地了解地球系统的不同元素之间的相互影响的作用。
B、项目集和支持度
让市场购物集的数据为T1={i1, i2. . . id} ,T={t1, t2. . . tN} 为所有的交易，每个事务Ti包含一系列从I中选择而来的项目。在关联分析，零个或多个项目的集合称为项目集。如果一个项集包含k个项目，它被称为第k项集。空集是不包含任何项目的项目集。
该事务宽度被定义为存在于交易中的项目数。如果X是TJ的一个子集，则事务TJ被认为包含项目集x。项集的一个重要特性是它的支持度，它是指包含特定项目集交易的数量。
C.关联规则
关联规则是形如X→y的含义表达，其中X和Y是不相交的项集, 即Xcap;Y =empty;。关联规则的强度可以由它的支持度和置信度来衡量。支持度用来确定规则是否适用于所给出的数据集，而置信度决定了在Y中出现的包含X的事务的概率。这些指标的通常定义为：
D、支持度和置信度
支持度是一个很重要的测量，因为具有非常低的支持度可能只是简单的偶然发生的事。低支持度从商业的角度看了也很可能是没有意义的，因为它不能通过促进客户购买很少一起购买的商品而盈利。支持度经常被用来消除无用的项，支持度有一种有价值的性能就是能够用来发掘关联规则的有效的发现。
置信度用来测量有一个规则作出的推论的可靠性。对于给定的X-gt;Y，置信度越高，对于Y就越有可能存在含有X的交易。置信度还提供了Y给与X的条件概率的估测。
E.频繁项集生成
点阵结构可以用于枚举所有可能的项集。在一般情况下，包含k个项目的数据集可以潜在地产生多达2K-1频繁项目集，包括空集。因为K在许多实际应用中可能非常大，这需要探索项目集的搜索空间也成倍增大。
寻找频繁项集蛮力方法是确定在晶格结构中每名候选项集的支持度。要做到这一点，我们需要将每个候选项与每一笔交易比较，即图4所示的操作。1。如果候选项包含在事务中，其支持度将增加。这样的方法花销是很大的，因为它需要一个（BMW）比较，其中N是记录的数目，M =2K-1是候选集的个数，w是最大事务宽度。
图1.计算候选项集的支持度
有几种方法来减少频繁项目集产生的计算复杂度。
- 减少候选项目集（M）的数量。先验原则，在下一节介绍，是消除某些候选项目集不计其支持率的有效途径。
- 减少比较次数。我们可以通过使用更先进的数据结构减少比较次数，无论是存储的候选项集或压缩数据集，而不是针对每个事务的每个候选项目集进行匹配。
II、Apriori原则
支持度方法有助于减少频繁项集生成过程中探索候选项集的数量。对于修剪候选项集使用支持由Apriori原则的指导“一个项目集频繁，它所有的子集也必须是项目频繁集”。考虑图所示的项集晶格。2，假设{C，D，E}是频繁项集。包含{C，D，E}还必须包含其子集的任何交易，{C，D}，{C，E}，{D，E}，{c}里，{D}和{Eacute;}。其结果是，如果{C，D，E}是频繁，则{C，D，E}的所有子集也必须是频繁的[6]。
图2.Apriori原理图解
相反，如果一个项集，如{A，B}不是频繁项集，那么它的所有超集也不是频繁项集。如图3所示：整个子图包含{a,b}的超集，一旦{a,b}被发现不少频繁项集就马上被修剪。在此基础上，支持度修剪指数搜索空间的策略称为基于支持度的修剪，这样的修剪策略由支持度，即一关键特性，变成可能，对于一个项集的支持度不会超过其子集的支持度。该属性也被称为支撑措施的反单调属性。
图3.基于支持修剪的图解
该具有一个反单调属性的任何措施可直接掺入到挖掘算法以有效地修剪候选项集的指数的搜索空间。
- Apriori算法中的频繁项集生成
Apriori算法是第一个率先使用了基于支持修剪来系统地控制候选项集的指数增长的关联规则挖掘算法。图4提供的频繁项目集生成部的一个高层次的插图，Apriori算法为如表1。考虑到支持阈所示的交易是60％，这相当于一个最小支持计数等于3。
图4.Apriori算法频繁项集产生图解
最初，每个项目被视为候选1项集。计数它们的支持度后，因为它们出现在少于三个交易候选项集{可口}和{鸡蛋}中而被丢弃。在接下来的迭代中，因为Apriori原则确保了1项集的超集都必须是频繁使用，只能频繁1项集产生候选2项集。由于只有四个频繁1项集，由算法产生候选2项集数，这六个候选集中的两个，{啤酒，面包}和{啤酒，牛奶}，随后发现计算的支持值之后不是频繁项集。其余四个候选集为频繁项集，因此将被用于生成候选3项集。如果没有基于支持度的修剪，个候选可使用六个项目来形成3项集。根据Apriori原则，我们只需要保持候选3项集的子集是频繁。具有此属性的唯一候选集是{面包，尿布，牛奶}。
Apriori剪枝策略的有效性可以通过计算产生的候选项目集的数量显示。蛮力策略枚举所有项目集（最多3号）的候选项将产生
候选集。使用Apriori原则，这个数目将减少到：候选，它代表在候选项目集的数量减少68％。Apriori算法的频繁项目集生成部的伪代码如下所示。
Apriori算法的频繁项集生成：
Ck表示候选K项集，Fk表示频繁K项集：
- 该算法最初可以使通过数据集来确定每个项目的支持单遍，在该步骤完成后，该组所有的频繁1项集F1将被给出（步骤1和2）。
- 接着，算法将迭代地生成使用新频繁候选k-项集（K - 1）项集在先前迭代（步骤5）中找到。候选生成是使用一种称为apriorigen函数实现的。
- 要计算候选集的支持度，该算法需要做出对数据集的附加（步骤6-10）。子集函数用来确定被包含在每个事务T中的所有Ck中的候选项目集。
- 当不产生新的频繁项集时算法终止，
Apriori算法的频繁项集产生部分有两个重要特征。
- 首先，它是一个水平逐算法;即，它遍历一次项集格一个级别，从频繁1项集到频繁项集的最大值。
- 其次，它采用了生成与测试策略来寻找频繁项集。在每次迭代中，都从上一次迭代中得到的频繁项集产生新的候选项目集。然后计算每个候选项的支持度，并针对最小支持度阈值进行测试。该算法所需的迭代的总数为：，是频繁项集的最大项目值。
B.产生候选剪枝
在Apriori算法的第五步中通过执行以下两种操作产生候选项目集：
- 产生候选：该操作产生基于在先前迭代中找到的（k-1）项候选集的k项候选集。
- 候选集修剪：此操作消除了一些使用基于支持修剪战略候选k-项集。
考虑候选k-项集该算法必须确定是否所有的适当的子集，为频繁项。如果其中一项不是频繁的，那么X立即被修剪。这种方法可以有效地减少支持度计数期间考虑的候选项目集的数量。该操作的复杂度对于每个候选k-项集[6][7]为O(k).
原则上，有许多方法来生成候选项目集。以下是一种有效的候选项产生过程的需求的列表：
- 应避免产生太多无用的候选项。如果一个候选项集的子集至少有一个是不频繁的，则该候选项目集是多余的。按照支持反单调的属性来看这样一个候选项是不频繁的。
- 必须确保候选集筛选完成之后，即不频繁项集在产生候选项的过程中被舍弃。为了确保完整性，候选的项目集必须归入所有集合频繁项集。
- 它不应该不止一次地产生相同的候选项集。重复候选项的产生会导致计算的花费，因此应该避免这样的操作来影响效率。
III、算法的关联规则挖掘
- 增强程序子集
它的运行时间是，是一个非常大的数字，假设K=3，事务t为(x2, x6, x7, x9)，项集s为(x4, x6, x10)，这句话的详解：在下面的判断条件中t包含s:如果（t 包含 X4）cap;（t 包含 X6）cap;（t 包含 X10）那么......”显然，T不包含S，但还是要逐一比较[8]。
该算法通过在事务数据库上添加一个标签栏提高了子集的操作，其值是第一个和最后一个项目集的号码。如果（x的第一项gt;=min）(x的最后一项lt;=max),那么t包含s,否则t不包含s。
B.提出Apriori算法
该算法可以分成两个步骤：首先，算法找出所有的频繁项集，然后从频繁项集中产生所有的关联规则。
输入：数据库D和最小支持度
输出：数据库中的所有频繁项集
C2由L1修剪两个生成项集而得，其中修剪操作用来测试C2的子集是否为频繁项集。因为，该集的子集必须为频繁项。因此，所提出的算法通过L1的直接连接产生C2，而不是通过修剪操作[14][17]。
IV、算法工作
一个事务型数据库如表2所示，最小支持阀度为20%，由提出的关联规则算法得到的结果说明如下：
表2.事务数据库D
表3. 算法数据库
首先解决表3中的数据，最后一个标有最小和最大序列号的的相应的事务。数据库的第一遍扫描之后，开始寻找L1，可以比较该交易的各个标签，因为1L不在[2,4]，或[2，3]中等等，以避免操作的过多的比较，从而节省了时间。
计算了支持度后，L1 = {I1, I2, I3, I4, I5}。根据改进后的算法，由L1直接连接得到2C不需要进行修剪操作。这样，C 2 = {(I1, I2), (I1, I3), (I1, I4), (I1, I5), (I2, I3), (I2, I4), (I2, I5), (I3, I4), (I3, I5), (I4, I5)}。因为（I1，I2）在[1，5]中，它包括事务T100，并增加了相应的支持。同样，L 2 = {(I1, I2), (I1, I3), (I1, I5), (I2, I3), (I2, I4), (I2, I5)} ，连接后，经过修剪C3 = {(I1, I2, I3), (I1, I2, I5)}， 项 (I1, I2, I3) 在
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[146707]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
