关联规则之apriori算法的一种改进算法.doc

关联规则之Apriori算法的一种改进算法 李若兰 [摘 要] 关联规则是数据挖掘研究的一个重要分支。Apriori算法是关联规则挖掘中最有影响的经典算法。本文在介绍了关联规则的概念，在分析Apriori算法的基础上提出一种基于划分的Apriori改进算法，该改进算法大大提高了数据挖掘的效率。 [关 键 词] 数据挖掘；关联规则；Apriori算法 [作者简介] 李若兰，女，柳州运输职业技术学院信息工程系教师。广西柳州，545007 数据挖掘是一种从大量数据中提取出隐含的、未知的、潜在的和有用的信息的过程。数据挖掘技术和数据库知识发现（Knowledge Discovery in Database，KDD）都是近年来随着数据库技术、人工智能技术，以及计算机科学技术的发展而出现的一种全新信息技术。虽然数据挖掘技术的发展仅有短短十余年的历史，但发展势头却相当迅猛，现已在实际领域中得到广泛的应用，并且产生了良好效果。关联规则挖掘是数据挖掘研究的一个重要分支，关联规则是数据挖掘的众多知识类型中最为典型的一种。 一、关联规则的概念 关联规则挖掘可以发现存在于数据库中的项目或属性间的有趣关系，这些关系是预先未知的或者被隐藏的。为了准确描述关联规则挖掘问题，需要给出关联规则挖掘问题的正式定义，下面用事务数据库来定义关联规则。 设交易(transaction) 的集合，，这里交易是项的集合，可以表述为：并且。中的元素称为项。对应每一个交易有唯一的标识，如交易号，记作。设是数据集中所有项的集合，是二进制文字的集合。中的任何子集称为项目集(itemset)，若，则称集合为项集。设和分别为中的事务和项目集，如果，称事务包含项目集。项目集的支持率,若不小于用户指定的最小支持率(记作：minsupport)，则称为频繁项目集，否则称为非频繁项目集。设，是数据集中的项目集。若，则；若，如果是非频繁项目集，则也是非频繁项目集；若，如果是频繁项目集，则也是频繁项目集。 一个关联规则是形如的蕴涵式，这里，都是项目集，且，，并且，，分别称为关联规则的前提和结论。 一般使用支持度（support）和置信度（confidence）两个参数来描述关联规则的属性。 （1）支持度 规则在数据库中的支持度是交易集中同时包含， 的事务数与所有事务数之比，记为 。支持度描述了，这两个项集在所有事务中同时出现的概率。 （2）置信度 规则在事务集中的置信度(confidence)是指同时包含，的事务数与包含的事务数之比，它用来衡量关联规则的可信程度。记为＝。 一般情况下，只有关联规则的置信度大于期望可信度，才说明的出现对的出现有促进作用，也说明了它们之间的某种程度的相关性。给定一个事务集，挖掘关联规则的问题就是产生支持度和置信度分别大于用户事先给定的最小支持度和最小置信度的关联规则。关联规则挖掘的任务就是要挖掘出中所有的强规则。强规则对应的项目集必定是频繁项目集，频繁项目集导出的关联规则的置信度可由频繁项目集和的支持度计算。因此，可以把关联规则挖掘划分为两个子问题：一个是找出所有的频繁项目集：即所有支持度不低于给定的最小支持度的项目集。另一个是由频繁项目集产生强关联规则：即从第一个子问题得到的频繁项目集中找出置信度不小于用户给定的最小置信度的规则。其中，第一个子问题是关联规则挖掘算法的核心问题，是衡量关联规则挖掘算法的标准。 二、Apriori算法 关联规则的算法相当多，其中经典算法Apriori是最有影响的挖掘布尔关联规则频繁项目集的算法，同时大部分关联规则算法也都是经典算法Apriori的演绎和改进。Apriori算法是通过有候选项集的方法来产生频繁项集，它的核心思想 ：任何频繁项集的所有子集一定是频繁项集。 在Apriori算法中，遍历数据库，得到大一项集。如果非空，由产生长度为2的候选项集合，对事务处理数据库中的每一个事务，求出在中的全部子集，对于中的每一个长度为2的候选取项集，令的计数c. count加1。当扫描事务处理数据库一遍后，筛选取出候选项集合中所有计数满足最小支持度的项集组成了长度为2的频繁项集合。用以上步骤重复处理新得到的频繁项集合，直到没有频繁项集合产生。 在这里，由于从候选项集中产生频繁项集的过程需要遍历数据库，因此如何正确地产生最少数目的候选项集十分关键。候选项集产生的过程Apriori - gen(Fk-1)被分为两个部分：联合与剪技。采用这种方式，使得所有的频繁项集既不会遗漏又不会重复。剪枝的目的是减少扫描数据库时需要比较的候选项集的数量。剪枝的原则是：候选项集的个长度为的子集都在中，则保留；否则被剪枝。 Apriori算法的描述如下。 输入： ①事务数据库； ②最小支持度阀值min_sup。 输出：中的频繁项集。方法： 第1步 产生频繁项集