文档介绍：摘要 Apriori 算法在关联规则领域有很大的影响力,然而由于需要过于频繁的扫描数据库及较大的空间消耗,仍然有需要改进的地方。通过对 Apriori 算法进行深入研究,本文提出了基于临时表的 Apriori 改进算法,通过比较分析,获得了较好的效率和性能。关键词关联规则 Apriori 算法频繁项集临时表 0 引言数据挖掘( Data Mining) 是数据库知识发现 KDD(Knowledge Discovery in Database) 的核心, 是指从数据库中提取潜在的、有用的、最终可理解的知识的过程。关联规则算法则是数据挖掘的一个重要研究方向, 其侧重于确定数据库中不同领域间的联系, 找出满足给定支持度和可信度的多个域之间的相互关系[4] 。简单的说,关联规则就是给定一组项目 Item 和一个记录集合,通过分析记录集合,推导出 Item 间的相关性。 1 Apriori 算法介绍 Apriori 算法基本思想 Apriori 算法是发现关联规则领域的经典算法。该算法将发现关联规则的过程分为两个步骤:第一步通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集;第二步利用频繁项集构造出满足用户最小信任度的规则[5] 。具体做法就是: 首先找出频繁 1- 项集,记为 L1 ;然后利用 L1 来产生候选项集 C2 ,对 C2 中的项进行判定挖掘出 L2 ,即频繁 2- 项集;不断如此循环下去直到无法发现更多的频繁 k- 项集为止。每挖掘一层 Lk 就需要扫描整个数据库一遍。 Apriori 算法描述 Apriori 利用层次循环发现频繁项集,算法如下: 输入:交易数据库 D ,最小支持阈值 min-sup 输出: D 中的频繁项集 L 然后利用 Apriori 性质删除那些子集为非频繁项集的候选项集,一旦产生所有候选,就要扫描数据库,对于数据库中的每个交易利用 subset 函数来帮助发现该交易记录的所有(已成为候选项集)的子集,由此累计每个候选项集的支持频度。最终满足最小支持频度的候选项集组成了频繁项集 L 。然而, 像这样产生候选集的开销极大, 特别是频繁集很长或最小支持度非常小时。例如, 当有 104 个频繁 1- 项集时,Apriori 算法就会产生多于 107 个的候选 2- 项集。针对 Apriori 算法的瓶颈,本文提出了一种基于临时表的改进算法。 2 基于临时表的 Apriori 改进算法 基本思想基于临时表的