Apriori算法的改进

第 10 卷 第 16 期 2010 年 6 月 1671-1815(2010)16-4028-04 科 学 技 术 与 工 程 Science Technology and Engineering Vol 10 No 16 June 2010  2010 Sci Tech Engng Apriori算法的改进 刘东洋 刘 恩 (辽宁石油化工大学计算机与通信工程学院，抚顺 113001) 摘 要 介绍数据挖掘中关联规则的情况。在 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 关联规则挖掘算法的基础上，对经典 Apriori 算法进行改进，改进算法意 在通过减少生成候选频繁项集的数量和扫描数据库次数。从而，加快算法的执行效率和节省空间。 关键词 数据挖掘 关联规则 Apriori 中图法分类号 TP391. 3; 文献标志码 A 2010 年 3 月 18 日收到 第一作者简介:刘东洋(1982—) ，男，辽宁石油化工大学硕士研究 生，研究方向:数据挖掘。 数据挖掘(Data Mining) ，就是从大量的、不完 全的、有噪声的、模糊的、随机的实际应用数据中， 提取隐含在其中的、人们事先不知道的、是潜在有 用的信息和知识的过程［1］。数据挖掘算法有决策 树算法、分类算法、聚类分析算法、关联算法等。其 中，随着数据量的逐年增加和人们对各个数据项之 间关系的关注，关联规则挖掘在数据挖掘中占有了 重要的地位，也是数据挖掘的主要任务之一。 1993年由 Agrawal 等人［2］针对购物篮问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 提出 的，其目的是为了发现数据库中不同项集之间的联系 规则。通过关联规则发现算法寻找形如“If(条件) ， else(结论)”的规则，在关联规则挖掘算法的研究中， Agrawal提出的 Apriori算法最为经典，其基本思想是 重复扫描数据库，根据一个频繁集的任意子集都是频 繁集的原理，可以从长度为 k的频繁集迭代地产生长 度为 k +1的候选集;再扫描数据库以验证其是否为 频繁集。但该算法本身固有缺陷［3］是在大数据量的 时候多次扫描数据库及产生大量候选集。 1 关联规则的基本概念 设 I ={i1，i2，…，im}是项的集合。设任务相关 的数据 D是数据库事务的集合，其中每个事务 T 是 项的集合，使得 T I。每一个事务有一个标识符， 称作 TID。设 A 是一个项集，事务 T 包含 A 当且仅 当 A T。关联规则是形如 AB 的蕴涵式，其中 A I，B I，并且 A∩ B = Φ。关联分析中还包 括两个重要的参数，支持度(min _ sup)和置信度 (min_conf)。具体定义如下: 支持度:support(AB)= P(A∪ B)= NA → B N × 100% ，即 A和 B这两个项集在事务集 D 中同时出 现的概率。 置信度:confidence(AB)= P(B | A)= NA → B NA × 100% ，即在出现项集 A的事务集 D中，项集 B也同时 出现的概率。 同时满足最小支持度(min_sup)和最小置信度 (min_conf)的规则称作强规则。 项的集合称为项集(itemset) ，包含 k 个项的项 集称为 k －项集。项集的出现频率是包含项集的事 务数，简称为项集的频率、支持计数或计数。如果 项集的出现频率大于或等于最小支持度，则称为频 繁项集［4］频繁 k －项集的集合通常记作 Lk。 关联规则的挖掘问题就是生成所有满足用户 指定的最小支持度(min_sup)和最小置信度(min_ conf)的关联规则，即这些关联规则的支持度 support (AB)和置信度 confidence(AB)分别不小于最小支 持度(min_sup)和最小置信度(min_conf)的关联规 则。关联规则的挖掘是一个两步的过程: 1)找出所有频率项集:根据定义，这些项集出 现的频繁性至少和预定义的最小支持计数一样。 2)由频繁项集产生强关联规则:根据定义，这 些规则必须满足最小支持度和最小置信度。 2 经典关联规则 Apriori算法 Aproiori算法是第一个关联规则挖掘算法，它开 创性地使用基于支持度的剪枝技术，系统地控制候 选项集指数增长。其核心是使用候选项集找频繁 项集。该算法的优点在于利用 Apriori 性质:一个频 繁项集中任一子集也应是频繁项集。有效地剪枝 项目集，尽可能不生成和不计算那些不可能成为频 繁项目集的候选项目集，从而生成了较小的候选项 目集集合。以下是 Aproiori算法产生频繁项集不分 的伪代码［5］: K =1 Fk ={i | i∈ I∧σ( {i})≥N × minsup} {发现所有的频繁 1 － 项集} Repeat K = k + 1 Ck = apriori － gen(Fk － 1) {产生候选项集} For 每个事务 t∈ Tdo Ct = subset(Ck，t) {识别属于 t的所有候选} For(每个候选项集 c∈ Ct do σ(c)= σ(c)+ 1 {支持度计数增值} End for End for Fk ={c | c∈ Ck∧ σ(c)≥ N × minsup} {提取频繁 k －项 集} UntilFk =  Result = ∪ Fk 算法的频繁项集产生的部分有两个重要的特 点:第一，它是一个逐层算法，即从频繁 1 －项集到 最长的频繁项集，它每次遍历项集格中的一层;第 二，在每次迭代，新的候选项集由前一次迭代发现 的频繁项集产生，然后对每个候选的支持度进行计 数，并与最小支持度阈值进行比较。在候选项集剪 枝操作中，算法必须确定 k －项集的所有真子集是 否都是频繁的。如果其中一个是非频繁的，则将会 被立即剪枝［5］。 3 Apriori算法的缺陷及改进方法 3. 1 算法的缺陷 Apriori算法使用逐层搜索的迭代方法，通过低 维频繁项目集产生高维频繁项目集［6］。这就导致 经典 Apriori算法存在两个问题 (1)多次扫描事务数据库，需要很大的 I /O 负载。 (2)可能产生庞大的候选集。由 Lk － I产生 k － 候选集 Ck 是呈指数增长的，在处理大批量信息数据 时，使得消耗大量的时间和空间。 3. 2 改进方法 本文主要是针对产生大量的候选集进行改进。 为了减少候选项集，就要删除非频繁项。我们这里 利用 Apriori的一个特性:如果 k －频繁项目集中的 某个项目在 k－频繁项目集中出现的次数小于 k，那 么这个项目不可能出现在 k + 1 频繁项目集中。 4 Apriori改进算法示例 下面给出住房公积金中还贷信息 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中 Ia 到 If 共 6 个属性。最小支持数 minsupport = 3。我们现在 对这个样本数据库采用本文中提供的改进 Apriori 算法进行演算。样本数据库如表 1 所示。 表 1 TID Item T1 Ia，Ic，Id，If T2 Ib，Ic，Id T3 Ia，IbI，c T4 Ib，If T5 Ib，Ic，Id，Ie T6 Ib，Ic，Ie T7 Ia，Ib，Ic，Id，If T8 Ia，Ic，Id，Ie，If T9 Ia T10 Ia，Ie 首先扫描数据库生成候选集 C1，如表 2。 920416 期 刘东洋，等:Apriori算法的改进 表 2 Item Ia Ib lc ld le lf Support 6 6 7 5 4 4 第一步，可以看出 Ia到 If都满足最小支持数 3.如 C1 可以直接为 L1。由 L1 连接生成候选集 C2，如表 3。 表 3 Item a，b a，c a，d a，e a，f b，c b，d b，e b，f c，d c，e c，f d，e d，f e，f Support 2 4 3 2 3 5 3 2 2 5 3 3 2 3 1 第二步，由最小支持数为 3 可知，删除小于 3 的 项，生成 L2 项集，如表 4。 表 4 Item a，c a，d a，f b，c b，d c，d c，e c，f d，f Support 4 3 3 5 3 5 3 3 3 根据本文提出的改进 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，现在对 L2 中各频繁 项目出现的次数计数，得出如表 5。 表 5 Item a b c d e f Support 3 2 5 4 1 3 第三步，由改进原理可知，保留最小支持数不 小于 2 的频繁项目，故项目 e被删除。得出表 6。 表 6 Item a，c a，d a，f b，c b，d c，d c，f d，f Support 4 3 3 5 3 5 3 3 第四步，由 L2 连接生成 C3，如表 7。 表 7 Item a，b，d a，c，f a，d，f b，c，d c. d，f Support 3 3 3 3 3 表 7 中所有项集的支持数都满足最小支持数， 可知 C3 是 L3。统计 L3 中各项目出现次数，可知: 表 8 Item a b c d f Support 3 1 4 4 3 第五步，故可知项集 b小于 3 不满足改进条件。 对 L3 进行修剪，得表 9 表 9 Item a，c，f a，d，f c. d，f Support 3 3 3 第六步，再由 L3 连接成 C4，得频繁项目集，如 表 10。 表 10 Item a，c，d，f Support 3 由以上对样本数据库部分数据的算法演算可见 得，在第三步和第五步利用改进算法可删除部分不满 足条件的项目集，以达到减少频繁项目集的作用。从 而加快算法的执行速度和缩减产生频繁项集的数量。 5 结束语 本文在描述挖掘关联规则 Apriori 算法的基础 上，提出了针对减少频繁项集的改进 Apriori 算法， 此改进算法减少了算法中连接时产生的部分候选 项，进而提高了算法的运算速度和算法的空间。 参 考 文 献 1 李宝东，宋瀚涛. 数据挖掘语言研究现状及发展. 计算机工程与 应用，2003;(06) :62—64，94 2 Agrawal R，Imielinske T，Swami A. Mining association rules between sets of items in large databases. Proc of the ACM SIGMOD Interna- tional Conference on the Management of Data，Washington D. C， 1993;207 一 216 3 毛国君，段立娟. 数据挖掘原理与算法. 北京:清华大学出版 社，2005 4 马秀红，宋建社，董晨飞.数据挖掘中决策树的探讨.计算机工程 与应用，2004;(01) :185—214 5 (美)Tan Pang-Ning，Steinbach M，Kumar V. 数据挖掘导论. 北京: 范 明，范宏建，等译.人民邮电出版社，2006 6 朱 烨，叶高英. 关联规则挖掘 Apriori算法的改进.数据库技术， 2008;(03) :78 一 80 0304 科 学 技 术 与 工 程 10 卷 Improvement for the Apriori Algorithm LIU Dong-yan，LIU En (School of Computer ＆ Communication Engineering，Liaoning Shihua University，Fushun 113001，P. R. China) ［Abstract］ Data mining is the process of discovering hidden structure or patterns in large quantities of data by using kinds of analytic tools. A survey of the study in association rule generation is provided. On the basis of mining association rules theory，improved algorithm aims to accelerate its executing efficiency and save space via reducing the quantity of candidate frequent item sets as well as the frequency of saving database. ［Key words］ 檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸檸 data mining association rules Apriori (上接第 4027 页) /* 总线掉线指示灯报警* / IO0CLR | = 0x08000000; /* 输出全部清零，相当于急停* / IO0CLR | = 0xffffffff; /* 释放总线函数* / CanBufOffLinePrg(CAN1) ; } } 6 结束语 为了系统可靠地运行，同时还要在芯片选型， PCB布线，制造工艺，外部接线，掉电保护机制等诸 多细节方面完善考虑，这样才能提高嵌入式系统的 整体抗干扰性能，从各个方面保证控制系统的安全 性，可靠性。 参 考 文 献 1 马习仿. 开关电源的电磁抗干扰设计. 电力与能源，2007;35: 847—848 2 张 涛，马拥军，唐跃军，等. 基于多机的埋弧焊机控制系统的研 究. 可编程控制器与工厂自动化，2000;1:72—73 3 韦婉琰，陈树君，吴日光，等. 弧焊设备的抗扰性研究. 电焊机， 2009;12(32) :7—17 4 陈 波，廖 颖，黄 强. 一种嵌入式系统复位时现场自动恢复 的方法. 电磁兼容，2009;2:84—86 5 王铁钢，王忠庆. 基于 LPC2294 的 CAN总线智能节点设计. 微计 算机信息，2008;24(7) :81—82 Anti-interference Design of Signal Acquisition Module in the Arc Welding Environment HUANG Zan，ZHAO Gang，WANG Wei (School of Electronics and Information Engineering，Sichuan University，Chengdu 610064，P. R. China) ［Abstract］ Accroding to the industrial welding environment，the signal acquisition module was designed through internal IIC bus and external CAN bus，which used LPC2294 as the microprocessor. The measures of anti-interfer- ence on the module are presented. After a series of indicators and continuous interference testing，results show that the system is stable，reliable，and low cost，which has broad application prospects. ［Key words］ CAN bus embeded system welder LPC2294 130416 期 刘东洋，等:Apriori算法的改进