apriori算法的改进

《apriori算法的改进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10卷第l6期2010年6月科学技术与工程Vo1．10No．16June20101671·1815(2010)16—4028—04ScienceTechnologyandEn~neefing@2010Sci．Teeh．Engng．Apriori算法的改进刘东洋刘恩(辽宁石油化工大学计算机与通信工程学院，抚顺113001)摘要介绍数据挖掘中关联规则的情况。在分析关联规则挖掘算法的基础上，对经典Apfiofi算法进行改进，改进算法意在通过减少生成候选频繁项集的数量和扫描数据库次数。从而，加快算法的执行效率和节省空间。关键词数据挖掘关联规则Apfio

2、f中图法分类号TP391．3；文献标志码A数据挖掘(DataMining)，就是从大量的、不完项的集合，使得，。每一个事务有一个标识符，全的、有噪声的、模糊的、随机的实际应用数据中，称作TID。设A是一个项集，事务包含A当且仅提取隐含在其中的、人们事先不知道的、是潜在有当A。关联规则是形如A日的蕴涵式，其中用的信息和知识的过程¨J。数据挖掘算法有决策Ac，Bc，，并且AnB=。关联分析中还包树算法、分类算法、聚类分析算法、关联算法等。其括两个重要的参数，支持度(min—sup)和置信度中，随着数据量的逐年增加和人们对各个数据项之(min—conf

3、)。具体定义如下：间关系的关注，关联规则挖掘在数据挖掘中占有了支持度：suppo~(A曰)：P(Au曰)：—Na-'--~B—_一×重要的地位，也是数据挖掘的主要任务之一。1993年由Agrawal等人针对购物篮问题提出100％，即A和B这两个项集在事务集D中同时出的，其目的是为了发现数据库中不同项集之间的联系现的概率。规则。通过关联规则发现算法寻找形如“If(条件)，置信度：confidence()：P(BIA)：×』V^else(结论)”的规则，在关联规则挖掘算法的研究中，100％，即在出现项集的事务集中，项集也同时Agrawal提出的Apf

4、iofi算法最为经典，其基本思想是重复扫描数据库，根据一个频繁集的任意子集都是频出现的概率。同时满足最小支持度(min—sup)和最小置信度繁集的原理，可以从长度为k的频繁集迭代地产生长(min_conf)的规则称作强规则。度为k+1的候选集；再扫描数据库以验证其是否为频繁集。但该算法本身固有缺陷是在大数据量的项的集合称为项集(itemset)，包含个项的项时候多次扫描数据库及产生大量候选集。集称为一项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。如果1关联规则的基本概念项集的出现频率大于或等于最小支持度，则称为频繁项集

5、_4频繁一项集的集合通常记作。设，={i，i，⋯，}是项的集合。设任务相关联规则的挖掘问题就是生成所有满足用户指定的最小支持度(min—sup)和最小置信度(min—的数据D是数据库事务的集合，其中每个事务是conf)的关联规则，即这些关联规则的支持度suppo~2010年3月18日收到(AB)和置信度confidence(AB)分别不小于最小支第一作者简介：刘东洋(1982一)，男，辽宁石油化工大学硕士研究持度(min—sup)和最小置信度(min—conf)的关联规生，研究方向：数据挖掘。则。关联规则的挖掘是一个两步的过程：16期刘东洋，等：

6、Apriori算法的改进1)找出所有频率项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。3Apriori算法的缺陷及改进方法2)由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。3．1算法的缺陷Apriori算法使用逐层搜索的迭代方法，通过低2经典关联规则Apriori算法维频繁项目集产生高维频繁项目集。这就导致经典Apriori算法存在两个问题Aproiori算法是第一个关联规则挖掘算法，它开(1)多次扫描事务数据库，需要很大的I／O创性地使用基于支持度的剪枝技术，系统地控制候负载。选项集指数增长。

7、其核心是使用候选项集找频繁(2)可能产生庞大的候选集。由一，产生k一项集。该算法的优点在于利用Apriori性质：一个频候选集c是呈指数增长的，在处理大批量信息数据繁项集中任一子集也应是频繁项集。有效地剪枝时，使得消耗大量的时间和空问。项目集，尽可能不生成和不计算那些不可能成为频3．2改进方法繁项目集的候选项目集，从而生成了较小的候选项本文主要是针对产生大量的候选集进行改进。目集集合。以下是Aproiori算法产生频繁项集不分为了减少候选项集，就要删除非频繁项。我们这里的伪代码：利用Apriori的一个特性：如果k一频繁项目集中的n乃K：1某个项

8、目在k一频繁项目集中出现的次数小于k，那Fk={iIiE，A(⋯i)≥N×minsup}{发现所有的频繁1一么这个项目不可能出现在k+1