英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料
The Apriori algorithm（关联规则算法）
- 算法描述
从一个事务数据集中发现频繁项集并推出关联规则是最流行的数据挖掘方式之一，查找频繁项集(频率大于或等于用户指定的最小支持的项集)并不简单，因为它是一个组合爆炸。一旦获得了频繁项集，就可以直接生成置信度大于或等于用户指定的最小置信度的关联规则
Apriori是一种使用候选生成来查找频繁项集的重要算法。它的特点是利用项集的反单调性，形成一个水平完备搜索算法，“如果一个项集不是频繁的，那么它的任何一个超集都不频繁”。按照惯例，Apriori假定事务或项目集中的项目是按字典顺序排序的。设大小为k的频繁项集为Fk，其候选项为Ck。Apriori首先扫描数据库，通过累加每个项目的计数并收集满足最小支持需求的项目，来搜索大小为1的频繁项目集。然后迭代以下三个步骤并提取所有频繁项集。
1.从大小为k的频繁项集中候选出大小为k 1的频繁项集，生成Ck 1。
2.扫描数据库，计算每个候选频繁项集的支持度。
3.将满足最小支持需求的项目集添加到Fk 1。
Apriori算法如图3所示。通过以下两个步骤，函数apriori-gen在第3行从Fk生成得到Ck 1:
1.连接步骤:将两个大小为k并拥有相同的第一k-1个元素的频繁项集Pk和Qk的合并，生成大小为k 1的频繁项集的初始候选项RK 1。
RK 1 = Pk cup; Qk = {iteml ,..., itemkminus;1, itemk , itemkrsquo; }
Pk = {it eml , item2,..., itemkminus;1, itemk }
Qk = {it eml , item2,..., itemkminus;1, itemklsquo; }
其中, iteml lt; item2 lt; ··· lt; itemk lt; itemklsquo;.
2.简化步骤:检查Rk 1中所有大小为k的项集是否频繁，并通过从Rk 1中删除那些没有通过此要求的项集来生成Ck 1。这是因为Ck 1中任何大小为k的不频繁子集都不可能是大小为k 1的频繁项集的子集。
第5行中的函数子集找到了事务t中包含的所有频繁项集的候选项。然后，Apriori通过扫描数据库只计算那些生成候选项的频率。
显然，当频繁项集的最大值设置为kmax时，Apriori算法最多扫描kmax 1次。
Apriori算法通过减小候选项集的大小来实现良好的性能(图3)。但是，在频繁项集非常多、项集很大或者最小支持度非常低的情况下，仍然需要生成大量的候选项集并重复扫描数据库来检查大量的候选项集。实际上，为了获得大小为100的频繁项集，需要生成2^100的候选项集。
图三 Apriori算法
二、算法的影响
在数据挖掘中经常使用的模式查找算法，如决策树、分类规则和聚类技术等，都是在机器学习研究领域中发展起来的。频繁模式和关联规则挖掘是这种传统的少数例外之一。该技术的引入促进了数据挖掘的研究，其影响是巨大的。该算法非常简单,容易实现。使用apriori类算法进行实验是数据采集器尝试做的第一件事。
三、当前和未来的研究
随着Apriori算法的引入和经验的积累，人们多次尝试设计更高效的频繁项集挖掘算法。这些算法中的许多与Apriori有相同的想法，因为它们也都产生了候选项。 其中包括基于散列的技术、分区、采样和使用垂直数据格式。基于哈希的技术可以减少候选项集的大小。通过使用适当的散列函数，将每个项集散列到一个相关的存储容器中。其中包括基于散列的技术、分区、采样和使用垂直数据格式。基于哈希的技术可以减少候选项集的大小。通过使用适当的散列函数，将每个项集散列到一个对应的bucket中。由于bucket可以包含不同的项目集，如果它的计数小于最小支持数，则可以从候选集中删除bucket中的这些项目集。可以使用分区将整个挖掘问题划分为n个更小的问题。数据集被划分为n个不重叠的分区，这样每个分区都适合放在主内存中，并且每个分区都是单独挖掘的。由于任何可能与整个数据集相关的频繁项集都必须作为一个频繁项集出现在至少一个分区中，因此通过这种方式找到的所有频繁项集都是候选项，可以通过只访问整个数据集一次来进行检查。抽样就是简单地从整个数据中随机抽取一小部分。由于不能保证可以找到所有的频繁项集，所以通常的做法是使用较低的支持阈值。必须在准确性和效率之间做出权衡。Apriori使用一种水平的数据格式，即频繁项目集与每个事务相关联。使用垂直数据格式是使用与每个项目集关联的事务IDs (TIDs)的不同格式。使用这种格式，可以通过取TIDs的交集来进行挖掘。支持计数就是项集的TID集的长度。因为TID集包含计算支持所需的完整信息，所以并不需要扫描数据库。
对Apriori最显著的改进是一种称为FP-growth(频繁模式增长)的方法，它成功地消除了候选生成[36]。它采用分而治之的策略(1)将表示频繁项的数据库压缩成一种称为FP-tree(频繁模式树)的结构，这种结构保留了所有的基本信息;(2)将压缩后的数据库分成一组条件数据库，每个条件数据库与一个频繁项集相关联，并分别挖掘每个频繁项集。它只需要扫描数据库两次。在第一次扫描中，所有的频繁项及其支持计数(频率)都是派生的，并且在每个事务中按照支持计数的降序排列。在第二次扫描中，将每个事务中的项合并到一个前缀树中，并计算不同事务中出现的公共项(节点)。每个节点都与一个项及其计数相关联。具有相同标签的节点由一个名为node-link的指针链接。由于项目是按频率降序排序的，所以更接近前缀树根的节点被更多的事务共享，从而导致存储所有必要信息表示的非常紧凑。模式增长算法应用在FP-tree上，是通过增加频率的顺序选择一个项，然后递归地在条件FP-tree上调用自身来提取包含所选项的频繁项集。FP-growth比原始的Apriori算法快一个数量级。
关于频繁模式挖掘的扩展还有其他几个方面。主要包括以下几点:(1)将分类法应用到项中:使用分类法可以提取出用高级概念表示的频繁项集，而使用基本级别的概念只能产生很少的频繁项集。(2)增量挖掘:在该设置中，假设数据库不是固定的，并不断添加新的事务实例。该算法在不重新开始的情况下就可以更新频繁项集。(3)对项使用有价值的数值:当项对应连续的数值时，当前的频繁项集挖掘算法不适用，除非将值离散化。利用子空间聚类的方法可以得到每个项目集中的每一项的最优值区间。(4)使用除频率外的其它方法,如信息增益或chi;2值:这些措施有助于发现判别模式但不好的是不满足反单调性。然而，这些方法有一个很好的性质，即它们的参数是凸化的，并且可以估计模式的超集的上界，从而有效地裁剪没有希望的模式。AprioriSMP使用了这个原则。(5)使用比项集更丰富的表达式:许多已经被提出并应用于序列、树和图的算法，可以从更复杂的数据结构中进行数据挖掘。(6)封闭项集:如果一个频繁项集不包含在任何其他频繁项集中，则该频繁项集是封闭的。因此，一旦找到了封闭项集，就可以从它们派生出所有频繁项集。LCM是求解封闭项集的最有效算法。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238776]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
