最大频繁项集的挖掘在关联规则挖掘中起着非常重要的作用,将其抽象为带约束条件的子集问题,利用蚁群算法进行求解。实验结果表明,与传统的Apfiori算法相比,在最小支持度较小的情况下,蚁群算法具有较快的挖掘速度,在大部分情况下能够获得所有的最大频繁项集,实验表明了蚁群算法在求解最大频繁项集挖掘问题上的有效性。

第 2卷第 2期 9 0 VO. 129 N O. 20

计算机工程与设计 Co u e g n e i g a d De i n mp t r En i e rn n s g

20年 1月 08 0 0 c.20 8 t 0

蚁群算法在最大频繁项集挖掘问题中的应用 宋洁，刘华，谭庆，顾军华 (河北工业大学计算机科学与软件学院，天津 3 0 0 ) 04 1 摘要：最大频繁项集的挖掘在关联规则挖掘中起着非常重要的作用，将其抽象为带约束条件的子集问题，利用蚁群算法

进行求解。实验结果表明，与传统的 Ap o算法相比， ii rf在最小支持度较小的情况下，蚁群算法具有较快的挖掘速度，大部在

分情况下能够获得所有的最大频繁项集，实验表明了蚁群算法在求解最大频繁项集挖掘问题上的有效性。 关键词：关联规则；最大频繁项集；蚁群算法；正反馈机制；启发式信息中图法分类号：P0. T 31 6文献标识码： A文章编号：0 072 (0 8 2 .2 00 10—0 4 2 0) 059 3

Ap l ain o p i t f c o ACS f r n n xmu fe u n e s t o mi ig ma i m r q e t tm es i S NG e L U a T N n, GU nh a O J, I Hu, A Qig i J—u u (co l f o p t c n e n otae H b i nvr t o cn l y Taj 04 hn) S h o o m ue S i c d f r, ee U ie i f eh oo, i i 3 0 0,C ia C r e a S w sy T g nn 1 Abtat ni xmu f q e tt e e ot tnmiigasca o l, at oo yss m loi m ( S i s c:Mi n ma i m eun e ti vr i r n n soit nr e n ln t a rh r g r ims s s y mp a i n i us c ye g t AC ) s p o o e o v i r b e a o s an d s b e r b e . Co a e t ro i l o t m, t esmu ai nr s l f r p s d t s l e h s o lm sac n t i e u s t o lm o t p r p mp r dwi Ap i r ag r h h i h i lto e u t o ACS s

o s h w

t a r f ce t nt e o r nmu s p o t o dt n a d io t i s l tema i m e u n e s t i s i s n e .Th h tts i i mo ee in we i m u p r c n i o, n b an l h x mu f q e t tm e s nmo t n t c s i i h l mi i t a r i a e r s l l e t y i f ce c nn x mu fe u n e st . e u t as t s f se in y i mi i g ma i m q e t tm es s o i t i n r i

Ke r s a s ca i nr l; ma i m r q e t t ms t; a t o o y s se; p u -e d a k h u it f r t n y wo d: s o it e o u x mu fe u n e e s n ln y tm i c l sf e b c; e rsi i o mai cn o

0引言 频繁项集的挖掘是关联规则挖掘中的关键部分，于最由大频繁项集隐含了所有的频繁项集，以挖掘频繁项集问题所 可以转化为挖掘最大频繁项集的问题。 pir算法是挖掘最 Ar i o

合，中每个事务 T项的集合，得 T I每个事务有~个标其是使 _ C, 识符，作 TD。设 A是一个项集，含项集 A的事务的个数称 I包称为 A在 D中的出现频率，作 cut )A的支持度定义为记 on(。 A s p=—— _ ) u ) c u, o n( iA t 一

,

』V

其中Ⅳ是 D中事务的个数。最大频繁项集相

关概念的定义如下：

大频繁项集的经典算法，后出现了许多快速挖掘最大频繁随 项集的算法， F .rwh'Ma— nr1 MI,用了相如 Pgo tt 1 xMi I DF等采 . e2 .

定义 1支持度不小于最小支持度 mi spmi s p为给 n u( n u _

关的搜索策略和剪枝技术，以力求在应用于海量数据时运行 效率上得以改善，都还存在一定的缺陷，如 F—rwt但例 Pgo h因为要枚举所有的频繁项集而导致不适合挖掘频繁模式长的情况， xMie未能很好的利用自顶向下的信息进行剪枝等。 Ma. n r

定的最小支持度值 )项集 A

称为频繁项集， spA≥mi的即 u( ) l l s p。 u

定义 2若频繁项集 A包含 k项则称 A为频繁 k项集，个’

频繁项集 A的长度为k。 频繁项集具有如下性质：

蚁群算法是一种基于群体智能原理的优化算法，在求解复杂组合优化问题上显示出了强大的优势，已经成功解决过旅行 商问题分配问题、、调度问题、合覆盖问题等。群算法集蚁具有正反馈性、行性、布性、并分自组织性等特点，根据不同可 问题的内在启发式信息逐步构建可行解，文利用蚁群算法从本

性质 1若 A是频繁项集， A的任意子集是频繁项集。则 性质 2若 A是非频繁项集，则 A的任何超集都是非频繁项集。

定义 3若 A是频繁项集，它的任何超集都是非频繁项集，称 A为最大频繁项集。则 Api i算法是一种用于发现布尔型关联规则的传统算 rr o

另一个角度考虑最大频繁项集挖掘问题，购物篮这一关联规在则挖掘中的经典问题的背景下求解最大频繁项集问题。

1最大频繁项集问题的描述 设，<, )项的集合，数据 D是数据库事务的集= f…,是，

法，用逐层搜索的迭代方法，-集用于探索 ( 1.集。使七项 )项首 先找出频繁 l项集的集合，作 L。对 L进行连接剪枝得出一记。 频繁 2项集的集合 L,用 L得到 L,此下去，到不能找一再 ]如直

收稿日：20 .01期 071—5 E ma:l h a2 0@1 3 o . r i u 01 6 . r l u cn作者简介：宋洁 (9 7,女，天津人，副教授，研究方向为人工智能；刘华 (9 2,女，河北正定人，硕士研究生，研究方向为智能信息 16一) 】8一) _

处理与软计算；谭庆 (9 4,男，天津人，硕士研究生，研究方向为免疫算法；顾军华 (9 6,男，河北赵县人，博士，教授，研究方 18一) 16一) 向为智能信息处理与软计算。 ——

5 9 - 2 0——