（计算机应用技术专业论文）基于改进蚁群算法的频繁项集挖掘的研究.pdf

嬲熘必 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：谭象雨 学位论文使用授权说明 h | 年6 只谣b 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 敝储虢 f 葺嚷雨新签毫，其矽年石月彩日 基于改进蚁群算法的频繁项集挖掘的研究 摘要 关联规则是数据挖掘研究领域中一项重要的研究课题。蚁群算法是受 到蚂蚁觅食的集体行为启示而设计的智能算法，作为智能算法的重要分支 受到研究人员的广泛关注，它具有鲁棒性、分布式、自组织性、正反馈性 等特点。 本文介绍了关联规则的相关知识，关联规则中频繁项集挖掘的经典算 法的思想、优缺点，同时介绍了蚁群算法的基本思想、算法和特点。在此 基础上，针对目前关联规则中频繁集的挖掘效率不高的问题，结合蚁群算 法在旅行商问题中最短路径求解过程与频繁项集的挖掘过程的共同点，借 鉴蚁群算法在旅行商问题的成功应用，本文将关联规则中频繁项集的挖掘 转化为t s p 最短路径问题，利用蚁群算法的思想进行挖掘，同时结合频繁 项集挖掘的特点，设计了一种新的信息素计算方法，以及一些调整措施， 提出了用于频繁项集挖掘的蚁群算法，该算法避免了大量候选集的产生， 提高算法的运行效率。在u c i 数据集上的实验结果表明：与传统的a p r i o r i 算法相比，利用蚁群算法可以在较短的时间里挖掘出绝大部分的频繁项集， 能够有效地进行频繁项集的挖掘。 同时，本文还针对现有算法在最小支持度取值比较小时，算法挖掘的 效率不高的缺陷分析了原因，主要是由于低支持度的频繁项集丢失，蚂蚁 选择低支持度事务项的概率不高，而集中于高支持度事务项的挖掘，可能 出现早熟收敛。为了提高现有算法的挖掘效率，本文在已有算法的基础上， 提出了三项改进措施：将蚂蚁初始位置限定在低支持度的事务项内，寻找 高频组合，局部减少信息素。通过采用这三项改进措施，减少了蚂蚁对低 支持度的事务项选择的随机性，缩小了蚂蚁的挖掘范围，降低了高支持度 事务项的影响，增大了蚂蚁对低支持度事务项的探索，从而减少低支持度 频繁项集丢失。实验结果表明：与改进前的算法相比，改进后的算法在保 持改进前的算法在时间上的优势的前提下，提高了频繁项集挖掘的百分比， 提高了挖掘的效率。 关键词：关联规则频繁项集蚁群算法高频组合 i i 一 一 - r e s e a r c h0 nm i n i n gt - r e q u e n ti t e m s e t s b a s e dt h ei m p r o v e da n tc o l o n ya l g o r i t h m a b s t r a c t a s s o c i a t i o nr u l ei sa l li m p o r t a n tr e s e a r c ht o p i co fd a t am i n i n g a n tc o l o n y a l g o r i t h mi s a ni n t e l l i g e n ta l g o r i t h mi n s p i r e df r o mt h eb e h a v i o ro ff i n d i n gf o o d i ns o c i a la n t sl i f e ，w h i c hc a t c h e st h ee y e so fr e s e a r c h e r sa st h ei m p o r t a n tb r a n c h o fi n t e l l i g e n t a l g o r i t h m ，i t h a sm a n yc h a r a c t e r i s t i c ss u c ha sr o b u s t n e s s ， d i s t r i b u t i o n ，s e l f - o r g a n i z a t i o n ，p o s i t i v ef e e d b a c ka n d s oo n i nt h i sp a p e r , i ti si n t r o d u c e dt h a ts o m ek n o w l e d g ea b o u ta s s o c i a t i o nr u l e ， t h et h e o r ya n dc h a r a c t e r i s t i c so ft h em e t h o d sa b o u tm i n i n gf r e q u e n ti t e m si n a s s o c i a t er u l e m e a n w h i l ei th a v et h e o r y ，t h eb a s i c a lm o d e la n dc h a r a c t e r i s t i c so f a n tc o l o n ya l g o r i t h m a f t e rt h i sb a s i ck n o w l e d g ei si n t r o d u c e d ，a g a i n s tt h el o w e f f i c i e n c yo fm i n i n gf r e q u e n t i t e m s e t si na s s o c i a t i o nr u l e sw i t he x i s t i n g a l g o r i t h m ，c o m b i n i n gt h ec o m m o ng r o u n do fs o l v i n gt s pa n dm i n i n gf r e q u e n t i t e m s d r a w i n go nt h es u c c e s so fs o l v i n gt s pw i t ha n tc o l o n ya l g o r i t h m ，t h i s p a p e rp r o p o s et h a tc o n v e r t i n gm i n i n gf r e q u e n ti t e m s e t st of i n d i n gt h es h o r t e s t p a t ht h e nm i n i n gf r e q u e n ti t e m s e t sw i t ha n tc o l o n ya l g o r i t h m m i n i n gf r e q u e n t i t e m s e t sb a s e da n tc o l o n ya l g o r i t h mi sp r o p o s e da f t e rd e s i g n i n gt h en e wm e t h o d t o c o m p u t ep h e r o m o n ea n dt a k i n gs o m ea d j u s t m e n t o ft h ea l g o r i t h m t h e a l g o r i t h ma v o i dal a r g eo f c a n d i d a t ei t e m s ，i m p r o v et h ee f f i c i e n c yo fa l g o r i t h m c o m p a r e dw i t hc l a s s i c a la p r i o r ia l g o r i t h m ，t h ee x p e r i m e n t sw i t ht h ed a t a s e t so f i i i u c is h o wt h a tt h ea n tc o l o n ya l g o r i t h mc a nm i n em o s tf r e q u e n ti t e m s e t si nt h e s h o r tt i m e ，i ti sc a ne f f i c i e n t l ym i n ef r e q u e n ti t e m s e t s m e a n w h i l e ，t h ep a p e ra l s oa n a l y s er e a s o no ft h el o we f f i c i e n c yw h e nv a l u e o ft h el e a s ts u p p o r ti sl e s si nt h ee x i s t i n ga l g o r i t h m ，i ti sc a u s e db yt h em i s s i n go f f r e q u e n ti t e m s e t sw h i c hi s l o w e rs u p p o r t ，t h ec h o o s i n gp r o b a b i l i t yo fl o w e r s u p p o r ti t e m si s n o th i g hw h e na n to n l ym i n et h eh i g hs u p p o r ti t e m s ，t h e n p r e m a t u r ec o n v e r g e n c em a y b ea p p e a r i no r d e rt oi m p r o v et h ee f f i c i e n c yo f t h e e x i s t i n ga l g o r i t h m ，t h i sp a p e rp r o p o s et h r e ei m p r o v e m e n tm e a s u r e sb a s e dt h e e x i s t i n ga l g o r i t h m ，t h e ya leb e i n gr e s t r i c t e dt h ea n t si n i t i a lp o s i t i o nw i t h i nl o w e r s u p p o r ti t e m s ，f i n d i n g t h e h i g hf r e q u e n t i t e m c o m b i n a t i o n ，r e d u c i n g l o c a l p h e r o m o n e t h r o u g ht h i s t h r e ei m p r o v e m e n tm e a s u r e s ，t h er a n d o m n e s so fa n t c h o o s el o w e rs u p p o r ti t e m si sd e c r e a s e d ，t h ea n t sm i n i n gr a n g ei sr e d u c e d ，t h e e f f e c to fh i g hs u p p o r ti t e m si sd e c r e a s e d ，t h ee x p l o r a t i o no fl o w e rs u p p o r ti t e m s i se n h a n c e d ，s ot h a tt h el o w e rs u p p o r ti t e m s e t sw i l ln o tm i s s i n gs om u s h c o m p a r e dw i t he x i s t i n ga l g o r i t h m ，t h ee x p e r i m e n t ss h o wt h a tt h ei m p r o v e d a l g o r i t h m r a i s et h e p e r c e n t a g e o ff r e q u e n ti t e m sm i n i n ga n dt h em i n i n g e f f i c i e n c yi sr a i s e d k e yw o r d s ：a s s o c i a t i o nr u l e ；f r e q u e n ti t e m s ；a n tc o l o n y a l g o r i t h m ； h i g hf r e q u e n ti t e mc o m b i n a t i o n i v 目录 摘要i a b s t r a c t i ii 第1 章绪论1 1 1j ；i 言1 1 2 国内外研究现状2 1 2 1 关联规则研究现状2 1 2 2 蚁群算法的研究与应用3 1 3 本文主要工作4 1 3 1 研究内容4 1 3 2 本文创新点5 1 4 论文组织结构5 第2 章关联规则与频繁项集概述7 2 1 关联规则的基本概念7 2 2 频繁项集的挖掘7 2 2 1 经典的a p r i o r i 算法及其优化一8 2 2 2 其他的频繁项集挖掘方法1 1 2 3 本章小结1 2 第3 章基于蚁群算法的频繁项集的挖掘1 3 3 1 蚁群算法的介绍1 3 3 1 1 蚁群算法的基本原理1 3 3 1 2 基本蚁群算法的算法1 4 3 1 3 蚁群算法的特点1 8 3 2 基于蚁群算法的频繁项集的挖掘1 9 3 2 1 算法的基本思想1 9 3 2 2 算法描述2 2 3 2 3 算法流程图2 3 3 2 4 算法实验及结果分析2 4 3 3 本章小结2 7 第4 章低支持度下蚁群频繁项集挖掘算法的优化2 9 4 1 现有算法的分析2 9 4 2 算法的改进3 0 4 3 算法描述3 2 4 4 算法流程图3 4 v 4 5 算法实验及结果分析3 5 4 5 1 实验数据3 5 4 5 2 实验步骤3 5 4 5 3 实验结果及分析3 5 4 6 本章小结3 7 第5 章总结与展望3 8 5 i 总结3 8 5 2 展望3 9 参考文献4 0 致谢4 4 攻读学位期间发表的学术论文4 5 v i 基于改置u 义群算法的频繁项集挖掘的研究 1 1 引言 第1 章绪论 随着数据库技术和互联网的高速发展，大量的网络数据以及各个领域的信息的飞速 增长，形成了基于i n t e r n e t 的全球信息系统。面对快速增长的海量数据，人们常常会认 为：数据丰富，但信息贫乏。在这一急切的局面下，数据挖掘的出现，弥补了数据与信 息之间的鸿沟。 数据挖掘( d a t am i n i n g ) ，又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e 。k d d ) ，就是从存放在数据库、数据仓库或者其他信息库中的大量数据中挖掘 有效的、新颖的、潜在有用的、可理解的有趣知识的过程。数据挖掘的方法很多，主要 有以下几类：传统的统计方法、关联规则、决策树、神经网络、遗传算法、粗糙集等几 种。 关联规则挖掘用于寻找大量数据库中项集之间有趣的关联或联系 ，是数据挖掘研 究中的一个重要内容。自1 9 9 3 年a g r a w a l 首次提出关联规则问题以来就引起了数据库、 信息检索、计算机网络、人工智能、统计学等领域的专家和学者的广泛关注，关联规则 挖掘已成为目前数据挖掘中发展最为快速、成熟、突出的研究内容，取得了众多的研究 成果。与此同时，关联规则也得到了广泛的应用，由最早的用于顾客购物数据的分析制 定帮助商务决策，如分类设计、交叉购物等营销策略，扩大为生物医学、金融数据分析、 电信数据分析、网站的个性化设计，如利用关联规则进行w e b 使用挖掘【2 1 ，了解用户的 访问模式，网站的个性化设计和优化提供参考。 在进行关联规则挖掘时，通常是先找出所有满足最小支持度的频繁项集，再由频繁 项集产生满足最小置信度的强关联规则。而在这一过程中，频繁项集的挖掘是整个挖掘 过程中最为关键的步骤，决定了关联规则挖掘的总体性能。因此，对关联规则挖掘方面 的研究，目前主要集中在如何高效地挖掘频繁项集。a g r a w a l 在提出关联规则问题的同 时也提出了目前频繁项集挖掘最有影响的算法一a p r i o r i 算法，此后有不少学者在此基础 上提出了不少的优化方法以及其他的挖掘方法。当前，如何将智能算法应用于关联规则 的挖掘是该领域研究的方向。 广西大学硕士学位论文基于改置e 蚁群算法的频繁项集挖掘的研究 1 2 国内外研究现状 1 2 1 关联规则研究现状 数据挖掘是美国计算机学会a c m 会议于1 9 9 5 年提出的。1 9 9 8 年a c ms i g k d d 的正式成立，标志着知识发现和数据挖掘由数据库和机器学习的分支正式转变成为一个 独立的学科。伴随着数据库和计算机网络技术的不断发展，数据挖掘逐渐成为计算机领 域研究的热点。至今，美国人工智能协会主办的k d d 国际研讨会已经召开了1 3 次。数 据挖掘在理论方面的研究不断深入的同时，实际开发应用方面也在同步进行，目前已经 开发出一些实用的数据挖掘系统，如i b m 公司的i n t e l l i g e n tm i n e r 等。在国内，对数据 挖掘的研究开始于上世纪9 0 年代，1 9 9 9 年，在北京召开的第三届p a k d d ( p a c i f i c a s i a c o n f e r e n c eo nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 收到1 5 8 篇论文，目前共举办了 1 3 届。中国计算机学会人工智能与模式识别专委会分别在成功主办了第一届和第二届中 国分类技术与应用研讨会之后，并于2 0 0 9 年与中国人工智能学会机器学习专委会联合 主办中国数据挖掘会议( c c d m ) 。此外，国内的许多科研单位和高等院校开展数据挖 掘的基础理论及其应用研究。 关联规则挖掘作为数据挖掘的一个重要分支，在国内外已被广泛地研究和应用，并 取得了不少的研究成果。 目前对关联规则挖掘算法的研究仍然集中于频繁集挖掘的研究，并已经提出不少挖 掘频繁集的算法。a p r i o d 算法【3 】是挖掘频繁集的经典算法，采用自底向上逐层搜索，利 用宽度优先策略，通过连接和剪枝步骤找出所有的频繁项集。同时，针对a p r i o r i 算法 可能产生大量的候选集而导致计算量过大的缺陷，目前也有许多优化方法，如基于散列 的优化方法、基于划分的优化方法、基于采样的优化方法、基于压缩事务集的优化方法 和基于动态项集的优化方法。此外，不少的算法采用不同的策略进行挖掘，如f p 增长 算法、s m a r t m i n e r 算法、p i n c e r - s e a r c h 算法、d m f i a 算法、m a x m i n e r 算法、m a f i a 算法【3 1 和g e n m a ) 【算、法【4 】等。 总体来说，目前已经有不少的关于关联规则中频繁项集挖掘的算法，发展得比较成 熟。但是仍然存在着不少的缺陷。如以上五种对a p r i o r i 算法的优化算法，虽然从不同 的方面进行的优化，但仍然没有克服a p r i o r i 算法固有的缺陷，即可能产生大量的候选 集；f p 增长算法在实现时c p u 和存储开销过大；m a x m i n e r 算法的i o 和计算开销过大； p i n c e r - s e a r c h 算法对于数据量过大时可能出现组合爆炸。 2 - 西大掌硕士掌位论文基于改盈u 良群算法的频繁项集挖掘的研究 此外，目前研究的另一方向是将智能算法应用于关联规则的挖掘，如神经网络【5 1 、 遗传算法【6 、人工免疫算法【即以及两者结合的免疫遗传算法【9 】等等。 1 2 2 蚁群算法的研究与应用 蚁群算法是由意大利学者d o r i g o 等人于2 0 世纪9 0 年代初期通过模拟自然界中蚂蚁 觅食的集体行为而提出的一种基于群体的启发式仿生进化系统，是现今群体智能算法研 究的热点之一。1 9 9 6 年，d o r i g om 在文献 1 0 中系统地阐述了蚁群算法的基本原理，将 其与遗传算法、模拟退火算法、禁忌搜索算法进行了实验比较，并将蚁群算法成功的应 用于解决对称和非对称t s p 问题、车间作业调度问题以及指派问题，同时还对算法中参 数的初始化所产生是影响做了初步的研究。在这之后蚁群算法逐渐引起世界学者的热情 关注和深入的研究，蚁群算法的理论研究和实际应用得到了快速的发展。蚁群算法的研 究进展包括几个方面： ( 1 ) 带精英策略的蚁群算法【l l 】：为使当前所找到的全局最优解在下一次的迭代循 环中更加吸引蚂蚁，会给每次循环后全局最优解添加额外的信息素，找到全局最优解的 蚂蚁则称为精英蚂蚁。带精英策略的蚁群可以在搜索过程的更早阶段找到更优的解，但 不恰当的选择精英蚂蚁的数量会出现早熟收敛，造成更好的解不被发现。 ( 2 ) 基于优化排序的蚁群算法【1 2 】：将遗传算法中排序的思想应用于蚁群系统中， 对蚂蚁按其构建的路径长度排序后，对w 只最好的蚂蚁的信息素轨迹根据其排名增加正 比于名次的信息量。 ( 3 ) 蚁群系统【l3 1 ，它主要做了三个方面的改进：首先是添加了伪随机比例的选择 规则，更好地利用了关于问题了先验知识；其次是全局更新规则只用于最优蚂蚁的路径 上；最后是类似于蚁密【1 4 】和蚁周【1 5 】模型中，构建路径的过程中进行信息素局部更新。 ( 4 ) 最大最小蚂蚁系统【l6 】：每次循环结束后只对一只蚂蚁的轨迹更新信息素，同 时为避免蚂蚁停滞搜索而将信息素的量控制在p 曲，f 一】范围内，并在初始化阶段将信 息素的值设为f 。使更多新的可行解在初始阶段被蚂蚁搜索。 ( 5 ) 最优最差蚂蚁系统【1 刀：由于一个越好的解决方案的附近越有可能存在更优的 解，因此通过消弱最差解同时更大限度地增强最优解，进一步增大属于最优和最差路径 的边之间信息素量的差异，从而使蚂蚁集中于最优解的附近进行搜索。 ( 6 ) 带有变异特征的蚁群算、法【1 8 】：该算法引入了变异机制，采用逆转变异的方式 3 广西大掌硕士掌位论文基于改爿擞群算法的频繁项集挖掘的研究 和随机的变异次数，使所需的信息量在进化时得以增强，克服了基本蚁群算法计算时间 较长的不足。 ( 7 ) 自适应蚁群算法 1 9 2 0 】：算法从两个方面进行了改进，首先保留每次循环结束 后的最优解，再者是自适应改变信息素的挥发系数p ，或自适应地改变表示信息素和启 发式因子相对重要程度的口与，从而提高了蚁群算法的收敛速度和全局搜索能力。 ( 8 ) 遗传算法与蚁群算法融合的算法【2 1 2 2 】：首先利用遗传算法的随机搜索、快速 性、全局收敛性产生有关问题的初始信息素分布，然后充分利用蚁群算法的并行性、正 反馈机制以及求解效率高等特性，融合后的算法在时间和求解效率都是比较好的。 除了以上几种改进以外，蚁群算法还与其他智能算法进行融合，如人工神经网络 【2 3 4 】、人工免疫算法【2 5 矧、微粒群算法【2 7 2 8 1 ，都取得了不错想效果。 在应用方面，蚁群算法被广泛应用于旅行商问题【2 9 1 、调度问题【3 0 】、网络路由问题 3 l j 、 图像处理【3 2 1 、集合覆盖问题吲等组合优化问题；在数据挖掘方面，蚁群算法已经成功的 应用于解决分类【3 4 】、聚类问题，如a n t m i n e r 【3 5 1 就是将蚁群算法应用于解决分类问题、 挖掘分类规则的算法算法，以及基于蚂蚁觅食原理【3 6 1 、自我聚集行为【3 7 1 、蚁堆形成原理 网等等的聚类算法。而蚁群算法在关联规则挖掘方面的应用较少，在文献 3 9 ，4 0 】中都利 用了蚁群算法的思想对关联规则进行快速的挖掘，但都有规则少的缺点；在文献 4 1 中 首先利用a p f i o f i 算法挖掘出频繁项集，再利用频繁项集构造完全图后，采用蚁群算法 在完全图挖掘关联规则。在文献 4 2 】中采用了蚁群算法思想与其提出的评价函数相结合 挖掘频繁项集，但其计算量很大，在支持度取值较大时时间花费较大，当支持度取值较 低时挖掘的效率不高。 1 3 本文主要工作 1 3 1 研究内容 本文首先介绍了关联规则的相关知识，关联规则中频繁项集挖掘的经典算法a p f i o f i 算法和一些针对a p f i o f i 算法的优化方法，以及简要介绍了其他的频繁集挖掘算法的思 想、优缺点，其次介绍了蚁群算法的基本思想、算法和特点。在此基础上，针对目前关 联规则中频繁集的挖掘效率不高的问题，结合蚁群算法在旅行商问题中最短路径求解过 程与频繁集的挖掘过程的共同点，借鉴蚁群算法在旅行商问题的成功应用，本文将于频 4 广西大掌硕士掌位论文基于改进蚁群算法的频繁项集挖掘的研究 繁集的挖掘转化为t s p 最短路径问题后应用蚁群算法进行挖掘，同时结合频繁集挖掘的 特点，设计了一种新的信息素计算方法，以及一些调整措施，提出了利用蚁群算法的思 想挖掘频繁集的算法，该算法避免了大量候选集的产生，提高算法的运行效率。实验结 果表明：与传统的a p f i o f i 算法相比，利用蚁群算法可以在较短的时间里挖掘出绝大部 分的频繁集，能够有效地进行频繁集的挖掘。 然而，本文提出的算法也存在着不足：在最小支持度取值比较小时，算法挖掘的效 率不高。分析其原理，可以发现主要是由于低支持度的频繁集丢失，蚂蚁选择低支持度 事务项的概率不高，而集中于高支持度事务项的挖掘，可能出现早熟收敛。为了提高现 有算法的挖掘效率，本文在已有算法的基础上，提出了三项改进措施：将蚂蚁初始位置 限定在低支持度的事务项内，寻找高频组合，局部减少信息素。通过采用这三项改进措 施，减少了蚂蚁对低支持度的事务项选择的随机性，缩小了蚂蚁的挖掘范围，降低了高 支持度事务项的影响，增大了蚂蚁对低支持度事务项的探索，从而减少低支持度频繁集 丢失。实验结果表明：与改进前的算法相比，改进后的算法在保持改进前的算法在时间 上的优势的前提下，提高了频繁集挖掘的百分比，提高了挖掘的效率。 1 3 2 本文创新点 本文的创新点如下： ( 1 ) 针对目前关联规则中频繁集的挖掘效率不高的问题，本文利用蚁群算法的思 想，同时结合频繁集挖掘的特点，设计了一种新的信息素计算方法，以及一些调整措施， 提出了用于频繁项集挖掘的蚁群算法。 ( 2 ) 针对在最小支持度取值较低时，现有算法挖掘频繁项集效果不高的缺陷，而 提出了将蚂蚁初始位置限定在低支持度的事务项内、寻找高频组合、局部减少信息素这 三项改进措施，进一步提高算法挖掘的效率。 1 4 论文组织结构 本文余下部分组织如下： 第二章，首先概述关联规则挖掘的相关知识和频繁项集的挖掘，然后详细介绍现今 主要的各种频繁项集挖掘的算法，分析算法基本思想，总结各算法的优缺点。 第三章，首先简要介绍了蚁群算法的相关知识，在探讨了旅行商问题中最短路径的 5 广西大掌硕士学位论文基于改进蚁群算法的频繁项集挖掘的研究 求解与频繁项集挖掘的共同点，借鉴蚁群算法在旅行商问题中的成功应用，结合频繁集 挖掘的特点设计了新的信息素的计算方法和一些调整措施，提出了用于频繁项集挖掘的 蚁群算法，并设计实验验证算法的有效性。 第四章，首先分析了现有算法优势和缺陷，并针对现有算法中的缺陷提出了三项改 进的措施，最后给出改进后算法的实验及结果分析。 第五章，总结全文，指出本文的后续研究工作与方向。 、 6 广西大掌硕士掌位论文基于改进蚁群：算法的频繁项集挖掘的研究 第2 章关联规则与频繁项集概述 关联规则挖掘是数据挖掘的一个重要分支，用于寻找大量数据库中项集之间有趣的 关联或联系。关联规则挖掘包含两个步骤，首先找出所有满足最小支持度的频繁项集， 再由频繁项集产生满足最小置信度的强关联规则。在这两个步骤中，强关联规则的产生 是比较容易的，而关联规则挖掘的主要工作是寻找频繁项集，因此频繁项集的挖掘决定 了关联规则挖掘的总体系能。因此，目前国内外许多学者大都在如何快速有效的挖掘频 繁项集进行研究。 2 1 关联规则的基本概念 设数据库是事务集合为d ，事务丁是项的集合，= f 。，如，i 3 ，i 。) 是项的集合，且 r 。关联规则是类似于a b 的蕴涵式，其中彳与b 是项集，并且 a t ，bst ，aci ，bci ，ar 、b = 矽。a 称为规则的前件，曰称为规则的后件。 衡量一个规则是否有趣，一般采用支持度和置信度作为兴趣度度量。对于规则 a b ，其支持度s 是包含4 u b 的事务在d 中的百分比，为概率p ( a u b ) ；而置信度 c 则是d 中包含a 的事务同时包含曰的百分比，为概率p ( bi 彳) ，即 s u p p o r t ( ajb ) = p ( a u b ) ，c o n f i d e n c e ( a b ) = p ( ba ) ，支持度和置信度反映了规 则的有用性和确定性。 关联规则挖掘的任务就是要找出同时满足最小支持度( m i ns u p ) 和最小置信度 ( m i nc o n f ) 的强规则。 项集是项的集合，k 项集是包含k 个项的项集，满足最小支持度的k 项集称为频繁 k 项集。对于满足最小支持度的规则ajb ，则4 u 占为频繁项集。 2 2 频繁项集的挖掘 对于一强关联规则ajb ，首先是在数据库中找到满足最小支持度的频繁项集 彳u 曰，然后根据最小置信度确定规则的前件和后件。因此，关联规则挖掘的主要过程 7 广西大掌硕士学位论文j 0 于改爱t 蚁群算法的频繁项集挖掘的研究 包括：找出所有满足最小支持度的频繁项集，再由频繁项集产生满足最小置信度的强关 联规则。在这个过程中，强关联规则的产生，即确定规则的前件和后件是比较容易的， 而关联规则挖掘的主要工作是寻找频繁项集，因此频繁项集的挖掘决定了关联规则挖掘 的总体系能。 频繁项集的挖掘是整个关联规则的产生中关键步骤，因此目前有关关联规则挖掘的 研究主要集中在如何高效地进行频繁项集的挖掘，并取得了不少的成果，提出了不少的 算法。 2 2 1 经典的a p r i o r i 算法及其优化 a p r i o r i 算法【4 3 1 是目前关联规则频繁项集挖掘的算法中最为经典也是最有影响力的 算法，于1 9 9 3 年由a g r a w a l 提出。a p r i o r i 算法采用逐层搜索的迭代方法，通过k - 项集 来探索( k + 1 ) 一项集，即通过扫描数据库找出频繁1 - 项集厶后，用厶寻找三：，如此下 去直到不能找到厶。然而每次寻找厶都要扫描一次数据库来计算支持度，因此同时采 用a p r i o r i 性质压缩搜索空间，提高挖掘的效率。a 州o r i 性质是指频繁项集的所有非空 子集都必须也频繁的，同时这也是频繁项集的性质，在整个a p r i o r i 算法起到了非常关 键的作用。 a 两o r i 算法由连接和剪枝构成。第一步是连接：通过将厶一。与自身连接产生候选k - 项集的集合g ，c 中的候选项集中既有频繁项集也有非频繁项集，但所有的频繁项集都 包含在g 中。为确定c 中频繁项集厶，则必须扫描数据库计算每个候选集的支持度， 从而确定满足最小支持度的频繁项集厶。然而当g 很大时，所涉及的计算量也会随之 增大，这时候就需要下一步剪枝来解决。第二步是剪枝：所谓剪枝是指压缩c ，主要 运用a p r i o r i 性质：任何频繁k 一项集的子集不可能是非频繁的( k 一1 ) 一项集。因此，只要 对每个候选k 一项集的( k 一1 ) 一项子集检测是否在厶一。中，则可以判定候选集是否为频繁 的，从而可以减少q 的数量，提高挖掘的速度。 如一数据库中的事务数据： 1 1 ，1 3 ) ， 1 1 ，1 2 ，1 4 ) ， 1 2 ，1 3 ) ， 1 1 ，1 2 ，1 3 ，1 5 ) ， 1 2 ，1 4 ) ， i l ，1 2 ，1 5 ) ， 1 1 ，1 3 ， 1 1 ，1 2 ，1 3 ) ， 1 2 ，1 3 ) ) ，最小支持度计数取值为2 。利用a p r i o r i 算法 8 广西大掌硕士掌位论文 基于改进蚁群算法的频繁项集挖掘的研究 进行频繁项集挖掘的过程如下： ( 1 ) 首先扫描事务数据得出每个事务项的支持度计数： 1 1 ) ：6 ， 1 2 ) ：7 ， 1 3 ) ： 6 ， 1 4 ) ：2 ， 1 5 ) ：2 。通过与最小支持度计数进行比较， 1 1 ) 、 1 2 ) 、 1 3 ) 、 1 4 ) 、 1 5 ) 均为频繁1 项集。 ( 2 ) 将频繁1 项集进行自身的连接，产生候选2 项集并扫描数据库统计候选集的 支持度计数： 1 1 ，1 2 ：4 ， 1 1 ，1 3 ：4 ， 1 1 ，1 4 ) ：1 ， 1 1 ，1 5 ) ：2 ， 1 2 ，1 3 ) ：4 ， 1 2 ，1 4 ：2 ， 1 2 ，1 5 ) ：2 ， 1 3 ，1 4 ) ：0 ， 1 3 ，1 5 ) ：1 ， 1 4 ，1 5 ) ：0 。通过与最小支持度计数进行比较可以 得出频繁2 项集： 1 1 ，1 2 ) 、 1 1 ，1 3 、 1 1 ，1 5 ) 、 1 2 ，1 3 、 1 2 ，1 4 、 i 2 ，1 5 ) 。 ( 3 ) 将频繁2 项集进行自身的连接，产生候选3 - 项集： 1 1 ，1 2 ，1 3 ) 、 1 1 ，1 2 ，1 5 ) 、 1 1 ，1 3 ，1 5 、 1 2 ，1 3 ，1 4 、 1 2 ，1 3 ，1 5 、 1 2 ，1 4 ，1 5 。 ( 4 ) 采用a p f i o f i 性质对候选3 项集进行剪枝： 1 1 ，1 2 ，1 3 ) 的2 - 项子集为 1 1 ，1 2 ) 、 1 1 ，1 3 ) 与 1 2 ，1 3 ) ，其子集都是频繁的，因而保留 1 1 ，1 2 ，1 3 ) ； 1 1 ，1 2 ，1 5 ) 的2 - 项子集为 i l ，1 2 ) 、 1 1 ，1 5 ) 与 1 2 ，1 5 ) ，其子集都是频繁的，因而保留 1 1 ，1 2 ，1 5 ) ； 1 1 ，1 3 ，1 5 ) 的2 一项子集为 1 1 ，1 3 ) 、 i l ，1 5 ) 与 1 3 ，1 5 ) ，而其中 1 3 ，1 5 ) 并非是频繁的，因而删除 1 1 ，1 3 ，1 5 ) ； 1 2 ，1 3 ，1 4 ) 的2 一项子集为 1 2 ，1 3 ) 、 1 2 ，1 4 ) 与 1 3 ，1 4 ) ，而其中 1 3 ，1 4 ) 并非是频繁的，因而删除 1 2 ，1 3 ，1 4 ) ； 1 2 ，1 3 ，1 5 ) 的2 项子集为 1 2 ，1 3 、 1 2 ，1 5 与 1 3 ，1 5 ) ，而其中 1 3 ，1 5 ) 并非是频繁的，因而删除 1 2 ，1 3 ，1 5 ) ； 1 2 ，1 4 ，1 5 ) 的2 项子集为 1 2 ，1 4 ) 、 1 2 ，1 5 ) 与 1 4 ，1 5 ) ，而其中 1 4 ，1 5 ) 并非是频繁的，因而删 除 1 2 ，1 4 ，1 5 ) 。 ( 5 ) 经过以上剪枝过程后，候选3 项集为： 1 1 ，1 2 ，1 3 ) 、 1 1 ，1 2 ，1 5 ) ，此时扫描数据 库得出候选3 项集的支持度计算，与最小支持度比较后得到频繁3 项集： i l ，1 2 ，1 3 ) ：2 、 1 1 ，1 2 ，1 5 ：2 。 ( 6 ) 将频繁3 项集进行自身的连接，产生候选4 项集： i l ，1 2 ，1 3 ，1 5 ) ，而其3 一项子 集 1 2 ，1 3 ，1 5 ) 却并非是频繁的，因此候选4 项集为空集。 ( 7 ) 最后就可以由 1 1 ，1 2 ，1 3 、 1 1 ，1 2 ，1 5 产生关联规则。 a p f i o f i 算法的描述如下： 输入：事务数据库d ，最小支持度m i ns u p 输出：d 中的频繁项集三 s t 印1 ：扫描数据库d ，得到所有的频繁1 - 项集厶，k _ 2 ； s t y 2 ：将厶一。进行自身连接产生候选集g ； o 广西大学硕士学位论文基于改进蚁群算法的频繁项集挖掘的研究 s t y 3 ：检测q 中每个候选集的子集是否属于厶- l ，若不在厶一。，则从c k 中去掉该 候选集，最终得到压缩后的候选集e ； s t e p 4 ：扫描数据库，计算q 中候选集的支持度，确定是否为频繁项集l 。； s t y 5 ：若厶一l 不为空集，则转向( 2 ) ，k 抖： s t y 6 ：返回频繁项集l = u i l 七。 从算法的描述可以看出，通过第s t y 2 步的连接步产生所有的可能的频繁集，再由 第s t y 3 步的剪枝步减少候选集的数量，对数据库进行扫描计算支持度后，并可以得到 所有的频繁项集。 在实际应用中，虽然算法利用了a p f i o f i 性质大幅度地压缩了侯选项集的大小，产 生了很好的性能，但该算法中存在某些实际情况下不能忽视的问题。在产生频繁k 项 集而最小支持度的取值比较小时，最终的k 将会比较大，频繁项集模式会比较长，此 时产生大量的候选集，对于一个大型的数据库而言，对这些相当数量的候选集检查和 累计其频繁性，则可能需要重复地对数据库进行扫描，所需要的空间和时间是非常巨 大的。在数据库和网络迅速发展的今天，数据的属性项数以及数据库的容量都是很大 的，a p f i o f i 算法的这一缺陷使其在实际应用中受到了限制。 为了提高a p f i o f i 算法的效率，目前的一些改进方法主要从缩小候选集的规模、减 少扫描数据库的次数这两方面着手进行优化： ( 1 ) 基于散列技术的优化方法【矧，该方法的基本思想是：在为检测c 。的中候选k 项集的频繁性而扫描数据库时，我们可以对每个事务生成所有的( k + 1 ) 项集，将其映 射到散列表中并统计支持