基于关联规则的数据挖掘Apriori算法的两种优化分析

第40卷第9期韶关学院学报窑自然科学

JournalofShaoguanUniversity窑NaturalScienceSep.2019Vol.40No.9基于关联规则的数据挖掘Apriori算法的两种优化分析渊亳州学院电子与信息工程系袁安徽亳州236800冤

摘要院关联规则的数据挖掘算法要要要Apriori算法袁其优化的核心在于如何在找出事务数据库中所有的频繁数据项集方面.论文以关联规则挖掘算法中的经典Apriori算法为基础袁从删除无效连接袁以减少冗余的连接为前提条件袁进而实现减少剪枝步中的判断量提出了Apriori要A算法曰以候选事务数据库替代原数据库D袁大幅减少扫描次数为前提袁提出了Apriori要B算法.结合特定实例经对比分析和实验验证袁改进后的算法在效率方面优于经典算法.

关键词院关联规则曰数据挖掘曰Apriori算法曰优化分析中图分类号院TP311.1文献标识码院A文章编号院1007-5348渊2019冤09-0016-05

张超

法为基础袁它具有无可替代的独特地位袁其效率的优化研究已成为广大学者关注的热点.Apriori算法本质主要包含两个方面问题袁第一个是找出事务数据库中所有的频繁数据项集.第二个是如何生成强关联规则.两

Apriori算法是关联规则挖掘技术的最基本算法咱1暂.目前关联规则的并行数据挖掘算法大都以Apriori算

个方面相比较袁第一方面的问题是算法的核心咱2暂.基于此袁对算法进行优化袁就应把重点放在找出频繁数据项集方面.

1Apriori算法概述

1.1原理

Apriori算法的核心思想是基于频繁项集理论的递归方法袁采用逐层搜索的迭代方法挖掘出在目标事务

数据库中所有频繁项集袁直至找到最高阶频繁项集即止袁最后通过对获得的频繁项集进行计算得到强关联L1.执行第k渊k>1冤次扫描时袁由Lk-1生成Ck.然后根据Ck继续进行扫描袁对照每个元素的支持度袁删减不符合者袁最后即可求得Lk.依据此思路可依次求得Lk+1袁Lk+2袁Lk+3噎噎.若某次计算Ck为空时袁算法自然结束.1.2生成频繁项集的过程

Apriori算法的基本思想是基于频繁项集生成过程袁使用递推方式推演出频繁项集袁使用频繁项集Lk-1规则咱3-5暂.其中袁现设候选k-项集集合表示为Ck袁频繁k-项集集合表示为Lk.经过一次扫描后袁即可快捷得出

产生频繁项集Lk袁其过程分为连接和剪枝两步咱6暂.Apriori算法生成频繁相集的第一步骤为连接步袁即计算对于li袁使得li咱1暂Lk由Lk-1自身作连接得到Ck.假若Lk-1中含有项集l1及l2袁li为渊k-1冤项集袁规定li咱j暂为li的项袁j为项的序号.

应当分别对应相等.即渊l1咱1暂=l2咱1暂冤疑渊l1咱2暂=l2咱2暂冤疑噎疑渊l1咱k-2暂=l2咱k-2暂冤疑渊=l1咱k-1暂咱收稿日期暂2019-06-11咱基金项目暂安徽省高校优秀青年人才支持计划项目渊gxyq2017109冤曰安徽省计算机应用技术专业综合改革试点渊省级冤渊2015zy078冤曰关联规则

算法的优化分析及在教学评价中应用研究渊BZSZKYXM201308冤.

咱作者简介暂张超渊1979原冤袁男袁安徽濉溪人袁亳州学院电子与信息工程系副教授袁硕士曰研究方向院数据挖掘尧计算机课程论与教学论.

第9期1.3主要步骤

张超院基于关联规则的数据挖掘Apriori算法的两种优化分析窑17窑推导出L1曰渊3冤k>1时袁按照渊4冤尧渊5冤尧渊6冤的次序重复执行曰渊4冤对Lk-1执行连接和剪枝操作袁并得出Ck曰若Ck=椎袁执行渊7冤袁不然袁执行渊5冤曰渊5冤按照min-sup的要求袁由候选Ck推导出Lk曰渊6冤如L屹椎袁k=k+1袁执行渊4冤曰否则执行渊7冤曰渊7冤由min-sup的具体要求袁基于频繁项集进一步推导出强关联规则.

设min-sup表示最小支持度袁则有以下步骤院渊1冤扫描数据袁并生成C1曰渊2冤根据min-sup的要求袁由C12Apriori算法的应用求解过程

务名袁Pi表示商品名袁Ci表示候选i要项集集合袁Li表示频繁项集袁规定min-sup=2袁T1={P1P2P5}尧T2={P2P4}尧T3={P2P3}尧T4={P1P2P4}尧T5={P1P3}尧T6={P2P3}尧T7={P1P3}尧T8={P1P2P3P5}尧T9={P1P2P3}.

{P5}}各项集的支持度分别为6尧7尧6尧2尧2.继而对C1扫描袁不需要删除任何项目袁求得L1=C1且支持度不变遥

具体求解过程如下院第一次C1寅L1袁按照min-sup=2的要求袁对原数据库D进行扫描C1={{P1}{P2}{P3}{P4}

一个大型购物中心的数据库事务包括T1尧T2噎噎T9袁|D|=9.基于Apriori算法求D中频繁项集袁Ti表示事

{P2袁P3}{P2袁P4}{P2袁P5}{P3袁P4}{P3袁P5}{P4袁P5}}袁在剪枝步中C2无须删除.对其扫描后可求得C2的各项支持度{{P1P2}{P1P3}{P1P4}{P1P5}{P2袁P3}{P2袁P4}{P2袁P5}}袁其中各项的支持度分别为4尧4尧1尧2尧4尧2尧2.可求得L3.步骤如下院

分别为4尧4尧1尧2尧4尧2尧2尧0尧1尧0.结合支持度min-sup=2的要求袁删除不满足后三项要求者即可得到L2遥L2=

第三次求解C3寅L3袁在第二次的结果的基础上袁对L2进行自身连接得到C3袁再由其对应的支持度数即

第二次求解C2寅L2袁在第一次求解出L1结果的基础上袁进一步求得C2=L1肄L1遥C2={{P1P2}{P1P3}{P1P4}{P1P5}

P5}袁{P2袁P3}袁{P2袁P4}袁{P2袁P5}}={{P1袁P2袁P3}袁{P1袁P2袁P5}袁{P1袁P3袁P5}袁{P2袁P3袁P4}袁{P2袁P3袁P5}袁{P2袁P4袁P5}}.{{P1袁P2袁P3}袁{P1袁P2袁P5}}.

渊1冤执行连接操作院C3=L2肄L2={{P1袁P2}袁{P1袁P3}袁{P1袁P5}袁{P2袁P3}袁{P2袁P4}袁{P2袁P5}}肄{{P1袁P2}袁{P1袁P3}袁{P1袁

分别包括{P1袁P3}尧{P1袁P5}尧{P3袁P5}.L2中存在{P1袁P3}尧{P1袁P5}但不包括{P3袁P5}袁因而不是频繁的.剪枝后得到C3=

渊3冤结合统计支持度袁C3的各元素均符合.即L3={{P1袁P2袁P3}袁{P1袁P2袁P5}}.

第四次扫描院求解C4=L3肄L3袁L3肄L3={{P1袁P2袁P3袁P5}}袁但其子集{P2袁P3袁P5}不属于L3范畴袁因此它不是频

渊2冤执行剪枝操作院根据有关性质袁上步结果中的后4个均要删除.以{P1袁P3袁P5}为例袁其对应的2项子集

繁的袁理应删除.至此求解全过程结束.

3Apriori算法效率的优化

综上分析袁进行推导Ck的连接操作通常要做大量繁杂的比较.但即便如此袁却并不保证得到的一定为候选项集.这样一来袁连接操作的有效性就比较差袁往往在许多时候都是无效的.若能够去除无效的连接比较袁简化剪枝步骤袁而使执行连接之后得到的都归属于候选项集袁那么算法效率将得到真正的优化提升.基于这种思路袁笔者提出一种优化后的Apriori-A算法.3.1Apriori-A算法思想

首先袁执行对Lk-1扫描袁并记录项集院{l1咱1暂}袁{l1咱1暂袁l1咱2暂}袁噎袁{l1咱1暂袁l1咱2暂袁噎袁l1咱k-2暂袁l1咱k-1暂}袁{l2咱1暂}袁

{l2咱1暂袁l2咱2暂}袁噎袁{l2咱1暂袁l2咱2暂袁噎袁l2咱k-2暂袁l2咱k-1暂}袁{l3咱1暂}袁噎.基于描述方便袁令li是一个k项集袁li={li咱1暂袁li析袁进而得到规律院在扫描中袁设项集{li咱1暂}袁{li咱1暂袁li咱2暂}的出现机会分别为Q1和Q2袁那么必有Q1逸k-1袁Q2逸k-2.以此类推袁项集{li咱1暂袁li咱2暂袁噎袁li咱k-1暂暂}出现机会Qk-1逸1.假定Q1尧Q2分别是{li咱1暂}袁{li咱1暂袁li咱2暂}的扫描次数袁若k-1跃Q1袁则执行删除操作袁即将Lk-1中凡是以li咱1暂开始的k-1项集一律删除.假若k-1臆Q1袁则将Q2与k-2进行比较.依此类推分析袁假若k-2跃Q2袁把Lk-1中凡是以项集{li咱1暂袁li咱2暂}起头的全部删除袁如果咱2暂袁噎袁li咱k-1暂袁li咱k暂}袁由算法性质可知袁若li归属于Ck袁那么Lk-1应包含其以下的k-1个k-1项集.综上分

窑18窑韶关学院学报窑自然科学2019年k-2臆Q2袁就接着与后面的项集扫描次数继续比较.

这种优化的策略袁实际上是以数字比较和删除操作为手段袁进而实现了删除Lk-1中大量的无效项集.此

优化算法的优点在于事先大大减少了冗余的连接袁最后以连接操作生成k项集袁只要通过一次比较操作即得出是否归属于Ck.该优化思想基于先删除后连接袁以减少冗余的连接为前提条件袁进而实现减少剪枝步中的判断量袁最终实现提升数据挖掘效率的目的.3.2Apriori-A算法应用分析

例1院L3={{O袁P袁Q}袁{O袁P袁T}袁{P袁Q袁R}袁{P袁Q袁S}袁{P袁R袁S}袁{Q袁R袁S}袁{Q袁S袁T}袁{R袁S袁T}}.

基于Apriori-A算法袁其删减操作过程见表1.执行得到结果={{P袁Q袁R}袁{P袁Q袁S}}袁然后执行它的自连接操作袁最终得到{P袁Q袁R袁S}的四项集.由于子集{Q袁R袁S}沂L3袁所以C4={P袁Q袁R袁S}袁通过验证袁得出结论是完全正确.

表1删减L3中项集的过程

扫描对象

OO袁PPP袁QP袁RQ袁RQ袁SRQ

次数k1223212111

比较次数k2323223223

涉及操作

因为k2>k1袁删除L3内O开始的所有项集袁继续比较P开始的项集

因k1=k2袁对L3内所有以P袁Q开始的项集都留存袁继续比较

因为k1=k2袁对所有P开始的项集执行统计

由于k2>k1袁把所有以P袁R开始的袁都作删除处理袁接着以Q进行比较以此类推袁k2>k1袁将以Q开始的项集一律删除袁不再继续.继续从R起

k2>k1袁将L3中凡以R起头的项集一律清除

本例中袁如执行经典Apriori算法袁则首先执行连接操作袁求得{O袁P袁Q袁T}尧{P袁Q袁R袁S}两个项集.然后执行剪枝步骤袁若在最坏的极端情况下袁则要对{O袁P袁Q}尧{O袁P袁T}尧{O袁Q袁T}尧{P袁Q袁T}尧{P袁Q袁R}尧{P袁Q袁S}尧{P袁R袁S}尧{Q袁R袁S}等8个项集都要判断其是否在L3范围之内.综上分析袁在本优化算法中袁只需执行连接操作求得相应的四项集袁在后面的剪枝步骤中袁再判断其子项集{Q袁R袁S}同L3有无归属关系成立即可.相比而言袁优化后的Apriori-A算法效率明显地提升.3.3Apriori-B算法思想

通过深入分析和研究后袁还可得知另一结论院判别一个项集是否归属于Lk袁对Ck中的所有对象还需进

一步明确其支持度计数.一般来说袁用于关联规则挖掘的数据库的数据量都是非常庞大的.从先前分析来看袁繁琐冗余的扫描则在很大程度上使得算法的效率大幅降低.试想袁假如能够应用某种策略使得扫描次数大幅简略袁则算法的优化就自然轻松实现.这样一来袁问题的根源在于运用何种恰当的策略能够使得数据库的扫描大幅精简.

{XK}>袁XK表示为潜在的频繁K要项集.C爷K作如下特性的定义袁数据库表示为D袁事务表示为T袁若k=l袁C爷K示为院.归结到实际袁就是先得到频繁1-项集袁并同步生成了C爷1.

按照上述思路袁现提出另一种优化策略.具体如下院引入一个C爷K袁在此集合中的任一对象标记成和D是一致的袁其本质上可看作是用{I}代替了项目i.若K>1袁C爷K中包含的对象同T保持完全相同袁即可表

从第二步起始袁诸如此类袁即可往复循环袁直至不再有频繁项目集的生成.现假定第k步出现了循环袁基

生成集合C爷K袁继续在C爷K中搜索袁即可统计出对应CK的支持度.究其根源是基于这一理论院如果一个事务

于描述方便袁分为两步说明.其一袁先由第K-1步中得到LK-1袁对其连接生成候选频繁K-项目集CK袁并同步

第9期张超院基于关联规则的数据挖掘Apriori算法的两种优化分析窑19窑数据袁特别是当k值很大时咱8-10暂.并且这种情况袁极有可能因k值的增长袁而呈现愈来明显的趋势.进而可以若当K值较小时袁对于任一个T的候选K-项目集袁C爷K的一个目录就可以完全涵概袁所以任一目录同对应事务T相比袁均较大.3.4实例算法应用分析

不包含任何候选K-项集袁则C爷K中将没有这个事务的目录袁所以C爷K的目录数据必然小于数据库中事务的

推知袁当K值较大时袁由于事务T基本上没什么候选项袁所以任一目录同对应事务T相比袁均要小于.同理袁

P3袁P5}袁T30={P1袁P2袁P3袁P5}袁T40={P2袁P5}袁最小支持度min-sup=2.

例2院有一数据库D袁包含4个事务表示为T10尧T20尧T30尧T40袁support表示其支持度袁T10={P1袁P3袁P4}袁T20={P2袁

求解得到各自的support分别对应为2尧3尧3尧1尧3.由min-sup=2袁在C1中继续扫描则需要删除{P4}袁即求得L1的4项分别包括{P1}尧{P2}尧{P3}尧{P5}.对L1扫描后袁可得到上述4项各自的support分别对应为2尧3尧3尧3.继续分别对应为1尧2尧1尧2尧3尧2.由min-sup=2袁在C2中继续扫描后需要删除{P1P2}尧{P1P5}袁剩余的即构成了L2袁其内在四项分别为{P1P3}尧{P2P3}尧{P2P5}尧{P3P5}等袁扫描后得到对应的支持度分别为2尧2尧3尧2.继续求解C3=P3P5}且支持度为2.

求C2=L1肄L1袁其分别包括{P1P2}尧{P1P3}尧{P1P5}尧{P2P3}尧{P2P5}尧{P3P5}等6项袁对其扫描得到各自的support

按照经典的Aprior算法对数据库D进行扫描后得到C1袁其中TSD分别包括{P1}尧{P2}尧{P3}尧{P4}尧{P5}五项袁

L2肄L2袁求其结果仅包括{P2P3P5}袁扫描后其支持度为2袁符合min-sup要求袁因此L3=C3袁其结果也仅包括{P2务的构成分别为{P1}袁{P3}袁{P4}曰{P2}袁{P3}袁{P5}曰{P1}袁{P2}袁{P3}袁{P5}曰{P2}袁{P5}等四项.对C爷1继续扫描可得到L1袁其四个事务的构成分别为{P1}尧{P2}尧{P3}尧{P5}四项袁对应support分别为2尧3尧3尧3.

扫描后可以得到C爷2袁其内在的四个事务的值分别为{{P1P3}}尧{{P2P3}{P2P5}{P3P5}}尧{{P1P2}{P1P3}{P1P5}{P2其分别为{P1P3}尧{P2P3}尧{P2P5}尧{P3P5}袁对应支持度分别是2尧2尧3尧2.一个对象{P2P3P5}袁且其支持度为2.

P3}{P2P5}{P3P5}}尧{{P2P5}}等四项.继续对C爷2扫描袁结合最小支持度min-sup=2的要求袁即可求得L2的四项

第三步求解L3袁首先计算C3=L2肄L2袁求得C3仅包含一项{P2P3P5}袁继续对C3扫描可得到C爷3.C爷3包含第二步求解L2袁先计算C2=L1肄L1袁其构成包括{P1P2}尧{P1P3}尧{P1P5}尧{P2P3}尧{P2P5}尧{P3P5}等六项.对C2若执行优化的Apriori-B算法袁其步骤可分为三步.第一步求解L1袁对数据库D扫描得到C爷1袁其四个事

两个事务T20尧T30袁对应的构成值分别为{{P2P3P5}}尧{{P2P3P5}}.以此类推袁继续扫描C爷3即可求出L3袁只含有

经对比分析后不难看出袁应用Apriori-B算法仅仅是在第一步扫描对象是原数据库D袁而在后续的第

二和第三步中袁扫描对象均为前一次所得到的候选数据库C爷k.并且可知袁若k值不断增大袁同原数据库D相比而言袁前者要远远小于后者.如此来看袁采用Apriori-B算法袁确实可减少I/O时间袁可以大幅提升算法效率.

3.5算法效率实验验证

以亳州学院教学评价系统数据进行挖掘为例袁实验环境院Win7袁eclipse袁Java编程语言袁计算机配置酷睿i53.0GHz袁内存4G袁硬盘1T.算法运行时长对比分析见图1.经典Apriori如淤袁Apriori-A如于袁Apriori-B如盂.从图1的情况可观测到淤的线条始终位于于尧盂之上.运用改进后的Apriori-A算法尧Apriori-B算法在法效率改善的愈加明显袁算法优化具有较强的应用意义.

事务数相等的情况下运行时间较经典Apriori算法更短袁效率更高.从事务数规模不断增大的趋势来看袁算

窑20窑韶关学院学报窑自然科学2019年/件图1算法运行对比分析

4结语

频繁数据项集的生成是关联规则挖掘的核心问题.Apriori要A算法思想是从删除无效连接袁以减少冗余的连接为前提条件袁进而实现了减少剪枝步中的判断量曰Apriori要B算法则以候选事务数据库替代原数据库D袁实现了大幅减少扫描次数.经定性分析和定量验证袁两种优化策略均在特定案例可以使之效率有效提升.但两种优化算法依然存在较为繁琐的数据库扫描操作袁算法效率仍有较大的提升空间.参考文献院

咱1暂李佐军.关联规则兴趣度挖掘在选课中的应用探讨咱J暂.西昌学院学报渊自然科学版冤袁2019渊2冤院103-105袁119.咱2暂张超.基于关联规则的数据挖掘在高校教学评价中的应用研究咱D暂.合肥院安徽大学袁2011.咱3暂曾子贤袁巩青歌袁张俊.改进的关联规则挖掘算法要要要MIFP-Aprior算法咱J暂.科学技术与工程袁2019渊16冤院216-220.咱4暂CuiW袁BaoZQ.Overviewofassociationrulesmining咱J暂.JournalofComputerApplications袁2016渊2冤院330-334.咱5暂唐晓东.基于关联规则映射的生物信息网络数据挖掘算法咱J暂.计算机应用研究袁2015渊6冤院1614-1616.咱6暂叶强袁李一军.基于支持度-显著度的关联规则分类方法研究咱C暂.南京院中国系统工程学会袁2005.咱7暂熊学栋.数据库中关联规则及效用模式挖掘算法的研究咱D暂.湘潭院湘潭大学袁2007.咱8暂李娟.数据挖掘技术在高校教学模型中的应用研究咱D暂.南京院南京理工大学袁2009.咱9暂吴瑕.数据挖掘技术在教学管理中的应用研究咱D暂.哈尔滨院哈尔滨工程大学袁2007.咱10暂于玲玲.数据挖掘在教务管理中的应用研究咱D暂.长春院长春理工大学袁2010.

AnalysisofTwoOptimizationStrategiesforAprioriAlgorithmof

DataMiningAlgorithmBasedonAssociationRules

渊DepartmentofElectronicsandInformationEngineering,BozhouUniversity,

Bozhou236800,Anhui,China冤

Abstract院Dataminingalgorithmforassociationrules-Apriorialgorithmoptimizationcoreliesinhowtofindallthefrequentdatasetsinthetransactiondatabase.BasedontheclassicApriorialgorithminassociationrulemin鄄ingalgorithm,thispaperproposesApriori-Aalgorithmfromdeletinginvalidconnectionstoreducingredundantconnectionsasthepremisecondition,andthenrealizingthereductionofjudgmentquantityinpruningstep曰basedonthepremisethatcandidatetransactiondatabasereplacestheoriginaldatabaseDandsignificantlyreducesthescanningtimes,Apriori-Balgorithmisproposed.TheimprovedalgorithmissuperiortotheclassicalApriorialgo鄄rithmintermsofefficiencythroughcomparativeanalysisandexperimentalverificationwithspecificexamples.Keywords院associationrules曰datamining曰Apriorialgorithm曰optimizationanalysis

渊责任编辑院欧恺冤

ZHANGChao