文档介绍：基于临时表的Apriori改进算法
 
 
摘要  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改进算法
基本思想
基于临时表的Apriori改进算法利用了以下两个事实：
(1)    对于已知规模的事务数据库D，任意一个项集I的出现频繁度与规模小于|I|的事务无关。所以在第|I|次扫描数据库D时，可以删除规模小于|I|的事务记录。
(2)    k-候选项集中不包含任何(k-1)-项集的项集一定不是频繁项集，因此k次扫描时可以将这样的事务记录立即删除，从而减少了下次需要扫描的记录数。
用临时表来完成频繁项集的选择。首先把(k-1)-项集中的第一个项集添加进临时表中；然后把最后一项不同的其它项集添加进临时表，生成k-项集， 计算 其频繁度，若频繁度大于最小频繁度，则生成该频繁项并保存，否则删除。依此循环，直至生成所有的频繁项。
改进算法的描述
输入：事务数据库D；最小支持度阈