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