Apriori算法的改进

Apriori算法的改进 姓名：赵仓仓 学号：200812219 [摘 要] 关联规则是数据挖掘研究的一个重要分支。Apriori算法是关联规则挖掘中最有影响的经典算法。本文在介绍了关联规则的概念，在 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 Apriori算法的基础上提出一种基于划分的Apriori改进算法，该改进算法大大提高了数据挖掘的效率。 [关 键 词] 数据挖掘；关联规则；Apriori算法 数据挖掘是一种从大量数据中提取出隐含的、未知的、潜在的和有用的信息的过程。数据挖掘技术和数据库知识发现（Knowledge Discovery in Database，KDD）都是近年来随着数据库技术、人工智能技术，以及计算机科学技术的发展而出现的一种全新信息技术。虽然数据挖掘技术的发展仅有短短十余年的历史，但发展势头却相当迅猛，现已在实际领域中得到广泛的应用，并且产生了良好效果。关联规则挖掘是数据挖掘研究的一个重要分支，关联规则是数据挖掘的众多知识类型中最为典型的一种。 一、关联规则的概念 关联规则挖掘可以发现存在于数据库中的项目或属性间的有趣关系，这些关系是预先未知的或者被隐藏的。为了准确描述关联规则挖掘问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，需要给出关联规则挖掘问题的正式定义，下面用事务数据库来定义关联规则。 设 交易(transaction) 的集合， ，这里交易 是项的集合，可以表述为： 并且 。 中的元素 称为项。对应每一个交易有唯一的标识，如交易号，记作 。设 是数据集中所有项的集合， 是二进制文字的集合。 中的任何子集称为项目集(itemset)，若 ，则称集合 为 项集。设 和 分别为 中的事务和项目集，如果 ，称事务 包含项目集 。项目集 的支持率 ,若 不小于用户指定的最小支持率(记作：minsupport)，则称 为频繁项目集，否则称 为非频繁项目集。设 ， 是数据集 中的项目集。若 ，则 ；若 ，如果 是非频繁项目集，则 也是非频繁项目集；若 ，如果 是频繁项目集，则 也是频繁项目集。 一个关联规则是形如 的蕴涵式，这里 ， 都是项目集，且 ， ，并且 ， ， 分别称为关联规则 的前提和结论。 一般使用支持度（support）和置信度（confidence）两个参数来描述关联规则的属性。 （1）支持度 规则 在数据库 中的支持度 是交易集中同时包含 ， 的事务数与所有事务数之比，记为 。支持度描述了 ， 这两个项集在所有事务中同时出现的概率。 （2）置信度 规则 在事务集中的置信度(confidence)是指同时包含 ， 的事务数与包含 的事务数之比，它用来衡量关联规则的可信程度。记为 ＝ 。 一般情况下，只有关联规则的置信度大于期望可信度，才说明 的出现对 的出现有促进作用，也说明了它们之间的某种程度的相关性。给定一个事务集 ，挖掘关联规则的问题就是产生支持度和置信度分别大于用户事先给定的最小支持度和最小置信度的关联规则。关联规则挖掘的任务就是要挖掘出 中所有的强规则 。强规则 对应的项目集 必定是频繁项目集，频繁项目集 导出的关联规则 的置信度可由频繁项目集 和 的支持度计算。因此，可以把关联规则挖掘划分为两个子问题：一个是找出所有的频繁项目集：即所有支持度不低于给定的最小支持度的项目集。另一个是由频繁项目集产生强关联规则：即从第一个子问题得到的频繁项目集中找出置信度不小于用户给定的最小置信度的规则。其中，第一个子问题是关联规则挖掘算法的核心问题，是衡量关联规则挖掘算法的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 。 二、Apriori算法 关联规则的算法相当多，其中经典算法Apriori是最有影响的挖掘布尔关联规则频繁项目集的算法，同时大部分关联规则算法也都是经典算法Apriori的演绎和改进。Apriori算法是通过有候选项集的方法来产生频繁项集，它的核心思想 ：任何频繁项集的所有子集一定是频繁项集。 在Apriori算法中，遍历数据库，得到大一项集 。如果 非空，由 产生长度为2的候选项集合 ，对事务处理数据库中的每一个事务 ，求出 在 中的全部子集 ，对于 中的每一个长度为2的候选取项集 ，令 的计数c. count加1。当扫描事务处理数据库一遍后，筛选取出候选项集合 中所有计数满足最小支持度的项集组成了长度为2的频繁项集合。用以上步骤重复处理新得到的频繁项集合，直到没有频繁项集合产生。 在这里，由于从候选项集中产生频繁项集的过程需要遍历数据库，因此如何正确地产生最少数目的候选项集十分关键。候选项集产生的过程Apriori - gen(Fk-1)被分为两个部分：联合与剪技。采用这种方式，使得所有的频繁项集既不会遗漏又不会重复。剪枝的目的是减少扫描数据库时需要比较的候选项集的数量。剪枝的原则是：候选项集 的 个长度为 的子集都在 中，则保留 ；否则 被剪枝。 Apriori算法的描述如下。 输入： ①事务数据库 ； ②最小支持度阀值min_sup。 输出： 中的频繁项集 。方法： 第1步 产生频繁项集 第2步 产生频繁 项集 产生频繁候选 项集 由频繁 项集连接成为k项集 检测 项集的所有的 子集是否为频繁项集，若是该 项集就 成为了频繁候选项集 扫描事务数据库 对每个候选 项集计数 达到最少支持度的频繁候选 项成为频繁 项集 三、Apriori算法的改进 Apriori算法的优点是结构简单，易于理解，没有复杂的推导。另外算法应用Apriori性质而设计的候选产生-检查方法在许多情况下大大缩小了需要检查的候选规模，使算法效率大幅度提高。但Apriori算法依然存在两个主要的问题： （1）多次扫描数据库。Apriori算法需要在每进行一次迭代的时候扫描一次数据库，一般的挖掘出的最大频繁项集的长度为N时，需要扫描N次数据库，而在实际应用中经常需要挖掘很长的模式，多次扫描数据库带来巨大开销。 （2）可能产生大量候选。Apriori算法在迭代过程中要在内存中产生、处理和保存候选频繁项集，这个数量有时候是非常巨大的，导致算法在广度和深度上的适应性很差。 即Apriori算法有个严重的缺陷：因为需要多次扫描数据库和产生大量的频繁项集，使得算法的花费在I/0上的时间很多，从而导致挖掘的效率非常低。因此，为了提高Apriori算法的有效性,需要对Apriori算法进行改进。人们对Apriori算法进行了大量的改进，希望能够找出一个高效、可靠的挖掘频繁项集的算法。因此本文对Apriori算法进行了改进，提出一种基于划分的Apriori改进算法。 Apriori算法需要频繁扫描整个数据库。与Apriori算法相比，基于划分的改进算法只需要扫描整个数据库两次。在第一遍扫描中，将产生一组潜在的频繁项目集，这组项目集是最后要确定的频繁项目集的超集，它也许包含错误的选择，但绝对不会漏掉正确的选择。在第二遍扫描中，针对这些潜在的频繁项目集确定它的针对整个数据库的实际支持度，从而可以最后确定所求的真正的频繁项目集。 基于划分的Apriori改进算法分4步进行： 第1步：将数据库划分成n个规模相当的部分 第2步：针对每个部分单独产生一组频繁项目集（潜在的）。 第3步：最后将这些项目集合并为一个全局的候选频繁项目集 第4步：针对整个数据库，计算每个候选频繁项目的实际支持度，从而确定最后的频繁项目集。 基于划分的Apriori改进算法的具体描述如下： 输入：事务数据库D；最小支持度阀值min_sup 输出：D的频繁项集L 变量说明： ：划分块中的局部候选项目集 ：划分块中的局部频繁项目集 ：划分块中的局部频繁项目集的合集 ：全局的候选项目集 ：全局的候选项目集的合集 ：全局的频繁项目集 P=partion_database(D) //划分数据块 n=number of partitions for i=1 to n begin read_in_partition(Pi P) =gen_large_itemset(Pi) end //生成划分块中的局部频繁项目集 for(i=2; ,J=1,2,…,n; i++) do = EMBED Equation.3 //合并生成全局的候选项目集 forall candidates c EMBED Equation.3 do begin //从全局的候选项目集中计算出全局的频繁项目集 c.count++; Lk={c Ck|c.count min_sup} end answer=UkLk; Produce gen_large_itemset(Pi,min_sup) L1={Pi};//某个划分块 for(k=2;Lk-1 ;k++) do begin Ck=apriori_gen(Lk-1,min_sup); //产生候选k-项集Ck forall transactions t Pi do begin Ct=subset(Ck,t); //t所包含的候选项集 forall candidations c Ct do c.count++; end Lk={c= Ck|c.count min_sup*n} end return Lk //根据Lk-1产生候选k-项集Ck的方法 Produce apriori_gen(Lk-1,min_sup) forall items l1 Lk-1 forall items l2 Lk-1 if((l1[1]=l2[2] ( l1[k-1]= l2[k-2]) ( l1[k-1] l2[k-2])) do begin c=l1 l2; //连接两个项集 if has_infrequent_itemset(c, Lk-1) delete c; else Ck=Ck {c} end; return Ck //去掉子集非频繁项集的候选项集的方法 Produce has_infrequent_subset(c,Lk-1) forall (k-1) subset s of c if s Lk-1 return true; else return false 经过以上对基于划分的Apriori改进算法的分析，发现该改进算法有以下几个优点。 （1）与Apriori算法相比，基于划分的Apriori算法只需要扫描数据库两遍，使得在挖掘过程中花费在I/0上的时间大大减少，从而大大提高挖掘的效率。 （2）根据对基于划分的Apriori改进算法的分析，在第一遍扫描数据库中，将产生一组潜在的频繁项目集，它保证了挖掘得出的规则在第二遍扫描中，针对这些潜在的频繁项目集确定它对整个数据库的实际支持度，从而最后确定所求的真正的频繁项目集，即保证尽可能挖掘出所有的关联规则，为挖掘得出有用的规则奠定了有效的基础。 （3）而基于划分的Apriori算法的挖掘是将数据库划分成n个规模相当的部分，先是针对每个部分单独产生一组频繁项目集，最后再将这些项目集合并为一个全局的候选频繁项目集，这种“以大划小，以小并行”的挖掘方法，在数据量逐渐增多的情况下，可以使得挖掘的效率将不会受到太大的影响。如果本系统选择该改进算法的话，则可以保证挖掘的效率尽可能不受到数据量增大的影响。 基于以上分析，基于划分的Apriori改进算法相对于Apriori算法有了很大的改进，大大提高了数据挖掘的效率。 参 考 文 献 [1] 秦国锋,李启炎.基于数据挖掘的知识获取与发现[J]，计算机工程,2003 [2] 段云峰，宋俊德等.基于数量的关联规则挖掘[J]，北京邮电大学学报,2002 [3] 周剑雄,王明哲.基于关联规则的数据挖掘技术的快速算法[J]，计算机工程,2003（7） [4] 何兵.关联规则数据挖掘算法的相关研究[D]，西安交通大学硕士学位论文，2004（4） [5] 李飞.关联规则算法的改进及应用研究[D]，贵州大学硕士学位论文，2003（5） [6] 曲建华.关联规则挖掘算法研究[D]，青岛大学硕士学位论文，2003（6） [7] 康晓东.基于数据仓库的数据挖掘技术[M]，北京：机械工业出版社,2004（4） [8] 高飞.关联规则数据挖掘算法研究[D]，西安电子科技大学硕士研究生论文,2006（7） _1248040668.unknown _1248042605.unknown _1248042734.unknown _1248533619.unknown _1256558849.unknown _1256559254.unknown _1256559644.unknown _1268459669.unknown _1256559666.unknown _1256559267.unknown _1256559423.unknown _1256559107.unknown _1256559134.unknown _1256558418.unknown _1256558523.unknown _1256558559.unknown _1256558796.unknown _1256558477.unknown _1256556450.unknown _1256556610.unknown _1256556927.unknown _1256558373.unknown _1256556752.unknown _1256556493.unknown _1256556338.unknown _1248110207.unknown _1248523533.unknown _1248523558.unknown _1248110775.unknown _1248262046.unknown _1248110221.unknown _1248043727.unknown _1248044734.unknown _1248044985.unknown _1248043758.unknown _1248042780.unknown _1248043570.unknown _1248043628.unknown _1248042816.unknown _1248043543.unknown _1248042747.unknown _1248042672.unknown _1248042710.unknown _1248042718.unknown _1248042664.unknown _1248042643.unknown _1248041097.unknown _1248042108.unknown _1248042567.unknown _1248042585.unknown _1248042133.unknown _1248041323.unknown _1248041547.unknown _1248041247.unknown _1248040980.unknown _1248041028.unknown _1248041084.unknown _1248041003.unknown _1248040936.unknown _1248040961.unknown _1248040734.unknown _1248040760.unknown _1248040681.unknown _1247601896.unknown _1248040549.unknown _1248040584.unknown _1248040648.unknown _1248040576.unknown _1247922645.unknown _1247922948.unknown _1247985970.unknown _1248040517.unknown _1247923042.unknown _1247922709.unknown _1247922513.unknown _1236334668.unknown _1247601274.unknown _1247601625.unknown _1247601697.unknown _1247601843.unknown _1247601303.unknown _1236335513.unknown _1236342025.unknown _1247601174.unknown _1236335093.unknown _1236335472.unknown _1236334628.unknown _1236334650.unknown _1236334556.unknown _1236334607.unknown