关联规则挖掘Apriori算法的研究

关联规则挖掘Apriori算法的研究

吴常辉,左春荣

吴常辉WuChanghui；左春荣ZuoChunrong（合肥工业大学南区，合肥230009）

摘要：关联规则反映了大量数据中项集之间的相互依存性和关联性。Apriori算法是关联规则挖掘中的经典算法。本文在对Apriori算法分析的基础上，针对该算法存在的缺陷，即会产生大量冗余的候选集并频繁扫描数据库，提出了改进的Apriori算法，并给予验证。实践证明，改进后的算法效率优于传统的算法。

关键词：数据挖掘；频繁项集；Apriori算法；关联规则

中图分类号：TP3文献标识码：A文章编号：1006-4311（2010）02-0194-02

0引言

数据挖掘（DataMining）是一门新兴起的交叉学科，是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。关联规则挖掘试图从一组给定的数据项以及事务数据库（每个事务是一个数据项的集合）中，筛选出数据项集在事务数据库中出现的频度关系[1]。联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组（FrequentItemsets），第二阶段再由这些高频项目组中产生关联规则（AssociationRules）。最经典的关联规则挖掘算法是Aprior算法[2]，该算法的主要思想是采用逐层迭代的方法通过低维频繁项集得到高维频繁项集，本文将着重探讨这个算法。

1关联规则与Apriori算法

1.1关联规则描述

关联规则是如下形式的逻辑蕴涵：A-B，其中A，B是项集，A∈I，B∈I，A∩B=Ф。一般用两个参数描述关联规则的属性。

（1）可信度（置信度）Confidence[3]：

（2）支持度（Support）

1.2关联规则的种类

基于规则中处理变量的类型，关联规则可以分为布尔型和数值型。布尔型考虑的是项集的存在与否，而数值型则是量化的关联。

2Apriori挖掘算法的改进与实现

2.1算法的改进

在扫描数据库的过程中，有些项目或事务是不必多次扫描的，如果能避免这些不必要的扫描，则可以提高Apriori算法的效率[6]。笔者认为在每次生成候选项集之后，删除其中没有用的项集，可以大大减少下一步接连生成的项集数量，从而减少数据库扫描次数，节省算法过程所需的存储空间，减少运算时间。可以根据Apriori以下的一个性质对算法进行改进。

改进的算法如下：

输入：事务数据库D，最小支持度minsup；输出：频繁项集L

（1）C1={全体项}

（2）forallc∈C1doS（c）=<；endfor

（3）forallt∈Ddo

（4）ct=subset（t，C1）；

（5）forallc∈ctdoS（c）=S（c）∪t.TIDendfor//为每个项建立相应的TID列表

（6）endfor

（7）forallc∈C1dobegin

（8）c.sup=|S（c）|；//得到1_项集的支持度

（9）if（c.sup<minsup）thenc.flag=1；//将支持度小于minsup的1_项集删除

（10）end

（11）endfor

（12）L1={c∈C1|c.flag=0};S1={S（c）|c∈L1}

（13）sort（L1）//对频繁1_项集按支持度升序进行排序

（14）for（k=2；|Lk-1|>k-1；k=k+1）do//由(k-1)_频繁项集得到k_频繁项集

（15）sort（Lk-1）//对频繁k-1_项集按支持度升序进行排序

（16）Ck=AprioriL_gen（Lk-1）//由Lk-1∞L1得到候选k_项集

（17）forallc∈Ckdobegin

（18）c.sup=|S（c）|；//得到k_项集的支持度

（19）if（c.sup<minsup）then

（20）c.flag=1；//将支持度小于minsup的k_项集删除

（21）end

（22）endfor

（23）Sk={S（c）|c∈Ck}//k_频繁项集相应的TID列表

（24）endfor

（25）L=∪kLk

其中产生候选项集的AprioriL_gen（Lk-1）过程：

foralllk-1∈Lk-1do

foralll1∈L1do

lk=lk-1∞l1

S（lk）=S（lk-1）∩S（l1）//求lk-1的TID列表与l1的TID列表的交集即lk的TID列表endfor

2.2算法的验证与实现

设有一组IP地址以及访问所对应的目的端口，IP地址相当于I={192.168.0.1，192.168.0.2，192.168.0.3，192.168.0.4，192.168.0.5，192.168.0.6，192.168.0.7，192.168.0.8，192.168.0.9，192.168.0.10，}，端口地址相当于Item={80，88，433，8080，21，22}，其对应关系如表1所示。设minsupport=3。对这个样本数据库采用改进后的Apriori算法进行演算。

首先扫描数据库得到D，生成候选集C1

第二步根据LK连接生成Ck+1也就是C2

删除支持度小于min_support的项集，生成Lk+1也就是L2

同时统计各频繁项目集在L2中出现的次数

利用L2更新数据表D，修剪不包含其中任一项集的事物

在新的数据表中，删除出现次数小于3的项集，获得L3，统计L3中各元素出现的次数

经过不断利用Lk+1更新数据表，最后得到下表。

从频繁项集产生的过程看出，采用改进后的Apriori算法可以使扫描次数减少大概一半，当数据库规模非常大时，扫描和比较时间的缩减将更加明显，这将大幅度缩短数据更新处理的时间，对提高关联规则挖掘的效率起到积极作用。

3结束语

本文深入研究了Apriori算法,尤其是通过对Apriori算法的不足的研究,针对此算法的不足，提出了自己的改进方法，大大节省了扫描数据库的时间，从而提高了算法效率。而算法的验证也证明确实提高了Apriori算法的效率。相信对于解决一些数据挖掘方面的问题会有一定的帮助。

参考文献：

[1]范明，范宏建著.数据挖掘导论，2005.12.

[2]陆丽娜，陈亚萍.挖掘关联规则中Apriori算法的研究[J].小型微型计算机系统，2000.21（9）.

[3]杨晓平.关联规则Apriori算法的改进[J].浙江海洋学院学报，2006，25（2）：176-182.

[4]PhilipJoung,AnilPochiraju.FirewallPerformanceTestingMethodology[J].SpirentCommunications：ApplicationNote03，2003，7.

[5]谈冉，陆正球，严新平.分布式环境基于相似度的关联规则挖掘模型的研究[J].计算机应用研究，2008，25（3）：695-6971.

[6]ChenG，WeiQ，LiuD，etal.SimpleAssociationRules（SAR）andtheSAR-basedRuleDiscovery[J].Computers&IndustrialEngineering，2002，43（7）：721-7331.