（计算机应用技术专业论文）基于蚁群算法的分类规则挖掘算法.pdf

摘要 摘要 蚁群算法是一种基于种群的启发式搜索算法，它通过模拟蚂蚁搜索从巢穴至 食物最短路径的行为来求解问题。蚁群算法由于其鲁棒性、并行性、易于并行实 现及与其他方法相结合等特点，越来越得到广泛应用。分类问题由于其潜在应用 领域的广泛性而成为数据挖掘领域中的一个研究热点。 本文在分另8 对蚁群算法和分类规则挖掘进行深入研究的基础上，提出了一种新 的分类规则挖掘方法 一基于蚁群算法的分类规贝q 挖掘算法。该算法是一种覆盖算 法：蚁群搜索一个规则，移去它覆盖的样例，再重复这一过程，从而得到共同覆 盖样例的一组规则。该算法采取用相对概率对每个属性依次进行搜索的方法，并 通过对五个公共数据进行试验，将试验结果与a 皿t m i n e r 算法的结果进行比较，试 验结果表明该算法能够发现更好的分类规则，包括更强的预测能力，有更少的规 则集以及更简单的规则。最后对算法中的参数进行了大量的分析和试验，得到了 针对该类问题的最佳参数设置，证明了用蚁群算法进行分类是一种比较可行的分 类方法。 关键词：蚁群算法，分类规则挖掘，数据挖掘，知识发现 a b s t r a c t a b s t r a c t a na n tc 0 1 0 n yo p t i m i z a t i o na l g o r i t h mi se s s e n t i a las y s t 锄b a s e do na g e n t si h a t s i m u l a t et l l e a t l l r a lb e h a v i o ro fa n t s ，i n d u d i n gc 0 叩e r a t i 伽a i l da d a p t a t i o n i lj s c o l l a t e r a l 、e a s yr e a l i z a t i 伽蛆dc o m b i 舱w i t ho t l l e rm e t l l o dt l l a ta na i l t ( l o n y o p t i m i z 州o na l g o i i t h mi sa p p l i e dm o f e 如dm o r ew i d e l y i et oi tw i d e 叩p l i c a t i o n ， a a s s i n c a t i o ni sa ni i l l p o r t a t 蚰b j e c to fd a l am i n i n 晷 t l l i sp a p e rp r o p o s e sa na 1 9 0 r i t l l m ，w h i c hi sb 雒e do n 卸tc 0 1 0 n ya l g o r i t l l ，f o f m i i l i n gc l 嬲s i f i c a t i o nm l e 舶mc a t e g o i i c a ld a 劬a 1 1 l em a i i d e ai ss e a r c h i n gam l e b ya i l t s ，r e l n 0 v i n g 蛐p l e sc o v e r e db yt h em l ea n dr c p t j l l gt l l i sp r o c c s su n t i l 舻ta 伊o u po fn 1 1 e sb yu s i n gm es t r a t e g yo fr c l a t i v ep m b a b i l i t y p e r i m e n t0 nf i v ep u b l i c d a t as e ts h o w st h a t m p a r c dw i t h ( = n 2 强da n t - m 妣r ，t h ca 1 9 0 r i t h mc a nd i s c o v e r d b e t t e rc l 醛s i f i c a t i o nm l e ，i n c l u d i n gn l l es e tw i t hb c n c fp r c d i c t i v ea c c l l m c yr a t ea l l d f e w e r r u l e s ，s i m p l c rm l e w i t hf e w e rt e 皿s i tp r 0 v e st h ea l g o r i t l l mi sab e t t e ra l g o r i t l l m k e y w o r d s ：a n c 0 i 锄y g o 蛐，m i n 沁a a s s 迁i 幽r m c ，d a t am i i n g ，d i s c o v e r y x n o w l c d 鐾e ； y 8 5 8 7 7 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名：盈盔垒 导师签名：函拯 日期芝i ：兰：叁z 日期堕：生! 避 第一章绪论 第一章绪论 1 1 选题背景与研究意义 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常 方便地获取和存储大量的数据。面对大规模的海量的数据，传统的数据分析工具( 如 管理信息系统) 只能进行一些表层的处理( 如查询、统计等) ，而不能获得数据之间 的内在关系和隐含的信息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要 一种能够智能地自动地把数据转换成有用信息和知识的技术和工具，这种对强有 力数据分析工具的迫切需求使得数据挖掘技术应运而生。 分类是一种重要的数据分析技术，可以用于提取描述重要数据类的模型和预 测未来的数据趋势。分类问题在人工智能、枧器学习以及模式识别等领域己经得 到了广泛的研究，并己产生了许多的分类方法。但是，面对大规模的海量的数据， 传统的分类算法在可扩展性和高效率性等方面面临大量的问题。因此，近年来在 “如何处理大规模数据”、“如何使获得的分类知识更易于为人所理解及应用”等问题 的激发下，分类问题已成为数据挖掘领域的一项重要研究内容【1 ，”，获得了更加广 泛的、深入的研究。 现实中的很多问题都可以转化为分类闯题，因而分类数据挖掘技术的潜在应用十 分广泛，从政府管理决策、商业经营、科学研究和工业企业决策支持等各个领域 都可以找到分类技术的用武之地。例如，可以建立一个分类模型，对银行的贷款 客户进行分类，以降低贷款的风险；也可以通过建立分类模型，对工厂的机器运转 情况进行分类，用来预游机器故障的发生。 因此，进行分类数据挖掘技术的进一步研究具有重要的理论意义和实际应用 价值。鉴于以上认识，本文对分类数据挖掘串的若干问题进行了研究，为构建可 扩展的、高鲁棒性的、高效性的数据挖掘分类算法做出自己的努力。 随着科学技术的飞速发展，计算机测量与控制系统的信息化、数字化及智能化 的发展趋势锐不可当，在自动化测试与控制系统中，存在着控制策略、规则、结 构以及控制参数的组合优化问题。2 0 世纪5 0 年代创立了仿生学，人们从生物进化 的机理中受至怕发，提出了许多用以解决复杂问题的新方法，如进化规划、进化 策略、遗传算法等，这些算法成功的解决了一些实际问题。2 0 世纪9 0 年代意大利 学者m d o d g o ，v m 姐i e z z o ，a c 0 1 0 f n i 等从生物进化的机制中受到启发，通过模拟 2 基于蚁群算法的分类规则挖掘算法 自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法蚁群算法。用 该方法求解t s p 问题、分配问题”、j o b - s h 叩调度问题”，取得了较好的实验结 果。虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂问题卜5 1 方 面有一定优势，表明它是一种有发展前景的算法。 1 2 本文的主要工作 分类( c l 勰s i f i c a t i o n ) 是数据挖掘的一个重要概念。数据分类( d a t ac l 够s i f i c a t i o n ) 一般分为两个过程。第一步是建立分类模型，描述预定的数据类集或者概念集。 通过分析有属性描述的数据库元组来构造模型。通常，这样的分类模型用分类规 则集、决策树或者数学公式的形式给出。第二步是使用分类对新的数据集进行划 分，主要涉及分类规则的准确性、过分适合、矛盾划分的取舍等。2 0 0 2 年p a 印i n e l l i rs ，l 0 p e shs 【8 1 等人提出了基于蚁群算法的数据挖掘系统a n t m i n e r ，它可以挖掘 分类规则。开创了分类算法的又一里程碑。它是一种覆盖算法，挖掘出分类规则。 我们知道求分类规则就是要求出腰( f 洲l4 耐鲫铆2d 棚) 晴删c 缸船 其中把，慨指的是第f 个属性的属性值。如果一个属性有多个属性值，那么，个属性 值称为f 硎# 。c f 船称为类别。其中细m 指的是绝对属性的属性值。如 ，我们不能说 。 评价一个分类规则集合好坏的标准应该是【9 】：( 1 ) 对新的数据集而言具有很高 的准确性；( 2 ) 较小的规则集：( 3 ) 比较简单的规则。a n t m i n c r 与上述分类方法 相比在以上三点上具有明显得优势。a n t m i n e f 蚂蚁对分类规则的搜索和t s p 问题 相似。把每个t 锄看成是一个节点。从一条空规则开始重复选择节点正加到路径 上。只不过t s p 问题是找最短路径，而分类规则是找最优路径，和路径长短没关 系。a n t m j n c r 在搜索规则时容易出现一个属性取几个属性值的情况，由于在分类 规则中，每条规则的每个属性最多只有一个属性值。a n t m i 鹏r 用增加记忆功能的 形式解决其问题，每当出现有属性有两个或两个以上属性值的情况概率溢出，规 则作废。但用这种方法对有些数据的效果很不好，尤其是对有些属性的几个属性 值概率差别不大的数据很难搜到规则。本文根据每条规则的每个属性最多只有一 个属性值的特点提出了用相对概率搜索路径的方式。蚂蚁首先从第一个属性开始， 在，个属性值中进行搜索，选择一个节点到路径上，再从第二个属性中进行搜索， 依此类推，直到把所有属性搜索完，得到一条路径为止。通过与a n t m i n e r 进行比 较，证明本文是比a n t m i n e r 更好的算法。 第一章绪论 1 3 结构与安排 第二章蚁群算法简介。主要介绍和蚁群算法相关的一些基础知识。首先概要 介绍了蚁群算法产生的背景及其思想原理，然后通过倦p 问题描述了蚁群算法的 数学模型和具体实施步骤。最后，对蚁群算法的发展状况和应用情况做了简要介 绍。 第三章分类规则挖掘。本章主要介绍了分类规则挖掘的概念、内容、过程， 最后介绍了分类规则挖掘研究的进展。提出了用蚁群算法挖掘分类规则的这一全 新的方法。 第四章基于蚁群算法的分类算法。主要是在第二章蚁群算法基本原理及第三 章的分类规则挖掘的基本知识介绍的基础上，提出了基于一群算法的分类规则挖 掘算法。该算法是：蚁群搜索一个规则，移去它覆盖的样例，再重复这一过程， 从而得到共同覆盖样例的一组规则。本文根据每条分类规则中每个属性只能取一 个属性值的特点，提出了采取用相对概率对每个属性依次进行搜索的方法。 第五章实验结果及分析。在前面第四章的基础上，通过对五个公共数据进行 试验，得出了与柚t m i n e r 相比，该算法能够发现更好的分类规则，包括更强的预 测能力，有更少的规则集以及更简单得规则。本章对本算法在信息素更新以及参 数设置等方面在本算法中的作用，通过试验做了进一步阐明。本章在最后还对算 法做了时间复杂度分析，说明本文算法是一个较好的算法。 结束语最后对本文所做的主要工作进行了总结。 本文的研究工作在国家自然科学基金项目( 编号：3 0 4 7 0 4 1 4 和6 0 5 7 4 0 3 9 ) 的支 持下完成。 4 基于蚁群算法的分类规则挖掘算法 第二章蚁群算法 2 1 蚂蚁算法概述 ( 一) 蚁群特性研究 蚂蚁的视力很有限，但蚂蚁在寻找食物的过程中，往往能找到从蚁穴到距离 很远的食物之间的最佳行进路线( 如图2 1 所示) 。仿生学家经过研究发现，蚂蚁寻 找食物的奥妙在于一种称为外激素的分泌物。 蚂蚁在行进的过程中，会不断分泌外激素。而外激素可以吸引后来的蚂蚁沿 相同的路线行进。这样，蚂蚁搜寻食物的过程中，对于较短的路径，在单位时间 内经过的蚂蚁数量较多，因此外激素水平较高。由于外激素水平较高，又吸引更 多的蚂蚁沿相同的路线进行搜索，这又使其外激素水平增加。对于距离较长的路 径，由于单位时间内经过的蚂蚁数量较少，蚂蚁分泌的外激素较少，外激素的挥 发作用较明显。因此，外激素水平逐渐降低，不再吸引蚂蚁沿这条路径运动。这 样，就形成了正反馈。即，对于较短路径，越来越多的蚂蚁会沿它运动；对于距 离较长的路径。即使一开始其外激素水平较高，由于经过的蚂蚁数量较少，也会 逐渐挥发，沿这条路径运动的蚂蚁数量也逐渐减少，最后由于外激素的数量太少 而不再吸引后来的蚂蚁沿该路径进行搜索。 图2 1 蚂蚁觅食示意图 另外，蚂蚁的搜索不是孤立的。事实上，假如只有一只蚂蚁进行搜索，由于 第二章蚁群算法 5 蚂蚁的短视，很难找到最佳路线。蚂蚁搜索的另一个特点，在于它们是群体搜索。 由于外激素对蚂蚁的行进具有指导作用，蚂蚁的搜索基于已有的搜索路线进行。 这样，蚂蚁在已经完成的搜索的基础上探索更好的行进路线，不断改进，直到找 到最优路线。通过以上分析容易发现，蚂蚁寻找食物的主要奥妙在于外激素。外 激素主要有两方面的作用，一是蚂蚁之间通过外激素互相通信，使得蚂蚁能够利 用以前的搜索结果：二是外激素的挥发作用，这使得搜索初期的距离较长的旅行 路线对蚂蚁的影响逐渐减小。另外，蚂蚁的搜索过程是一种正反馈，可以迅速搜 索到从蚁穴到食物之间的最佳路径。这对迅速找到问题的解决方案是非常有利的。 ( 二) 蚁群算法的起源 自2o 世纪5 0 年代中期创立了仿生学以来，人们从生物进化的机理中受到启发， 提出了许多用以解决复杂优化问题的方法，如遗传算法、进化规划、进化策略等。 蚁群优化算法( a n tc o l 锄yo p l i m i 髓t i 蛐a c o ) 是受到人们对自然界中真实的蚁群集 体行为的研究成果的启发而提出的一种基于种群的模拟进化算法，属于随机搜索 算法，它首先由意大利学者m d 面g 等人提出来，他们称之为蚂蚁系统( a ms y s t e 1 ) 。 蚂蚁算法充分利用了蚁群搜索食物的过程与著名的旅行商问题( t s n 之间的相似 性，通过人工模拟蚂蚁搜索食物的过程( 即：通过个体之间的信息交流与相互协作 最终找到从蚁穴到食物源的最短路径) 来求解骼p 。像蚂蚁这类群居昆虫，虽然单 个蚂蚁的行为极其简单，但由这样的单个简单个体所组成的蚁群群体却表现出极 其复杂的行为，能够完成复杂的任务，不仅如此蚂蚁还能够适应环境的变化，如： 在蚁群运动路线上突然出现障碍物时蚂蚁能够很快地重新找到最优路径( 如2 1 示1 。 蚂蚁算法来源于对自然界蚂蚁寻找从蚁巢弼食物的最短路径并找到回巢路径 方法的研究，是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生进化算法。 蚂蚁算法中采用有记忆的人工蚂蚁，通过个体之间的信息交流与相互协作来找到 从蚁穴到食物源的最短路径特别经研究发现，蚂蚁个体之间是通过一种称为信息 素( p h e 煳l o n e ) 的物质进行信息传递，从而相互协作，完成复杂任务。蚂蚁在运动 过程中能够在所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这 种物质的存在及其强度，并以此指导自己的运动方向。蚂蚁是自然界中常见的一 种生物，蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，它们总能找到一条从 食物到巢穴之问的最优路径。 ( 三) 人工蚁群系统研究 基于蚁群算法的分类规则挖掘算法 蚁群算法( 有称人工蚁群算法) 是受到对真实蚁群行为启发而提出来的。为 了说明人工蚁群系统的原理，先从蚁群搜索食物的过程谈起。像蚂蚁、蜜蜂、飞 蛾等群居昆虫，虽然单个昆虫的行为及其简单，但由单个简单的个体所组成的群 体却表现出及其复杂的行为。仿生学家经过大量细致观察研究后发现，蚂蚁个体 之间是通过一种成为外激素( p h e r o m o n e ) 的物质进行信息传递的。蚂蚁在运动过 程中，能够在它所经过的路径上留下该物质，而且蚂蚁在运动过程中能够感知该 物质，并以此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的集体便表现 出一种信息的正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的 概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 串砗且雌 培o 对捌 b l 淄 图2 2 蚁群系统示意图 下面用文1 2 】所举的例子来说明蚁群系统的原理。如图2 2 所示，设每个时间单 位由3 0 只蚂蚁由a 到达b ，又有3 0 只由e 到达d 点，蚂蚁过后留下外激素为1 。 为便于讨论，设外激素停留时间为l 。在初始时刻，由于路径b h ，b c ， ，d c 上均无信息存在，位于b 和e 上的蚂蚁可以随即选择路径。从统计的角度可以认 为他们以相同的概率选择b h ，b c d h ，d c 。经过一个时间单位后，在路径b c d 上 的信息量是路径b h d 上信息量的两倍。在t = 1 时刻，将由2 0 只蚂蚁由b 和d 到 达c ，由1 0 只蚂蚁由b 和d 到达h 。随着时间的推移，蚂蚁将会以越来越大的概 率选择b c d ，最终完成选择路径b c d ，从而找到由蚁巢到食物源的最短路径。由 此可见，蚂蚁个体之间的信息交换是一个正反馈过程。 ( 四) 蚁群算法的特点 蚁群算法是受到对真实的蚂蚁行为研究的启发而提出的，他是群体智能系统 的最成功的例子之一，己被应用到从典型的旅行商问题到数据挖掘问题等许多类 问题，并从中体现出了这种新思想在求解n p 难题过程的寻优能力。 该算法的主要特点在于： ( 1 ) 较强的鲁棒性：对基本蚁群算法模型稍加修改，便可以应用于其他问 第二章蚁群算法 7 题； ( 2 ) 分布式计算：蚁群算法是一种基于种群的进化算法，具有本质并行性， 易于并行实现； ( 3 ) 易于与其他方法结合：蚁群算法很容易与多种启发式算法组合，以改 善算法的性能。 众多研究已经证明蚁群算法具有很强的发现较好解的能力，这是因为该算法 不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质并行 算法，不同个体之间不断进行信息交流和传递，从而能够相互写作，有利于发现 较好解。 2 2 蚁群算法模型及实现 ( 一) 求解t s p 阚题的蚁群算法的模型 以求解n 个城市鸭p 问题为例来说明蚁群系统模型。为了模拟实际蚂蚁行为， 令卅表示蚁群中蚂蚁的数量；如( f ，- 1 刀) 表示城市i 和城市j 之间的距离，4 ( f ) 表示t 时刻位于城市l 的蚂蚁个数，拼一z 岛( f ) 勺( f ) 表示f 时刻在f 、j 连线上残 留的信息量。在初始时刻，设( 0 ) - c ( c 为常数) ，各条路径上信息量相等。蚂蚁 t 似一1 ，2 ，。埘) 在运动过程中，根据各条路径上的信息量决定转移方向。p 。o ) 表示 在f 时刻蚂蚁由位置碡章移到位置j 的概率： 露o ) - o j 4 加舰噍 0其他 ( 2 1 ) 其中，n f f d w 咄= o ，1 ，2 ，棚一1 ) 表示蚂蚁七下一步允许选择的城市。与真实蚁群 系统不同，人工蚁群系统具有一定的记忆功能，这里用细施。 zl 2 ，m ) 来记录 蚂蚁七日前已经走过的城市。随着时间的推移，以前留下的信息逐渐消逝，用参数 ( 1 一p ) 表示信息消逝的程度，经过弹个时刻，蚂蚁完成一次循环。各路径上的 基于蚁群算法的分类规删它掘算法 信息量要根据下式作调整： o ) ap o o ) + o ) ( f ) 2 荟弓 ( 2 2 ) ( 2 3 ) 表示第七只蚂蚁在本次循环中留在路径 上的信息量，表示本次循环中留 在路径盯上的信息量： f q ； i 【0 若第七只蚂蚁在本次循环中经过j ( 2 4 ) 其他 其中，q 是常数，l 。表示第k 只蚂蚁在本次循环中所走的路径的长度。在初始时 刻，( o ) ；c ( c 鲫s f ) ，2 0 ，其中，f ，j o 工，露一l 。口，分别表示蚂蚁在运 动过程中所积累的信息及启发式因子在蚂蚁路径选择中所起的不同作用。表示 由城市i 转移到城市j 的期望程度，可以根据某种启发式算法具体确定。根据具体 算法的不同，勺及瞄( f ) 表达形式可以不同，要根据具体问题而定。m d 嘶g o ， v ：m a 玎i e z z o ，a c o l o m i 等给出三种不同的模型，分别成为锄t - c y c l es y s t e m ， a n t q u a l l t i t ys y s t e m ，如l - d c n s i t ys y s t e m 参数q ，c ，口，厉p 可以用试验方法确定起最有 组合。停止条件可以用固定循环次数或当进化趋势不明显对便停止计算。 ( 二) 求解t s p 问题蚁群算法的流程 以上是蚁群系统模型，这是一个递推过程，很容易在计算机上实现，实现可 以用为代码表示： b e 百n 初始化过程； n c y c l e = o ； b e s t c y c l e = o ； 吼= c ； 2 0 ； 第二章蚁群算法 由某种启发式算法确定； t a b u ( k ) = 咖； w h i l e ( n o tt e m i n a t i o nc o n d i t i o n ) n c y c l e = n c y d e + l ； f o r ( i n d c x = 0 ；i n d e x - m a 5 i n d e x = 1 ： i fi n d e x 1 m l e a = m l e a l ) w l l i l e ( i n d e x - 1 ) ； n l l e a ： 其中n 1 1 e b = m l e a l 。表示规则b 由规则a 移去第i 个前件得到的。 4 2 3 信息素浓度更新 当路径构造结柬并经过规则剪枝得出一条分类规则后，所有路径节点的信息 素浓度都将依据这条分类规则的效率被更新。规则中包含路径节点的信息素浓度 将被增加( 外激素累积) ，而没有被包含的路径节点酶信息素浓度将减小( 外激素 散发) 。对包含在规则中的任意一路径节点f e 册口，有： b ；巧+ 畸q ( 4 8 ) 其中q 为规则的有效性。对于没包含在路径节点蛔铆# 的信息素浓度。 基于蚁群算法的分类规则挖掘算法 ； 蓍薹弓 = o 4b 们删y 孓o 钉箭” 口 w 明了亨瓦。o 白角” 4 3 算法描述 ( 4 9 ) 下面是基于蚁群算法的分类算法的算法描述： c b o a c a ( c l a s s i 丘c 撕o nb 娼e do n 蛐tc o l o n ya l g o r i t h m ) 定义： u n c o v c r e d c 勰e s t h f c s h o l d ：允许剩余训练集样例数； r u l e - c o n v e r g e n c e t h r e s h o l d ：规则收敛值； n u m b c r o f a n t s ：蚂蚁数目： a r u l e ：一条规则； p r c v i o u s r u l e ：前一个蚂蚁搜索到的规则； b e s t m l e ：最好规则； 算法： w h i l et h en u m b e ro fc a s e si n1 b i n i n gs e t u n v e r e d c a s e s t l l r e s h o l d d o b e 西n i n t i - o ： r e p e a l i = i + 1 ： i n t j = 0 ； a m l e = c o n s t m c t r u l e ( i ) 第f 只蚂蚁构造一条路径；肌、m l e ：一条规则 p n l n e r u l e p 咖l e ) ；规则剪枝 u p d a l e p h e r o m 呻c l e ) ；依据规则更新外激素 i f a m l e = p r e v i o 邺r u l e ；j - j + 1 ；p r e v i 咖s r u l e ：前一个蚂蚁搜索到的 规则 e l s e p r e v i o u s r l i i e 咖l l e j = 0 ) i f a n l l ei sb e t t e ft l i 柚b e s t n l l ed ob 镐t n l l e = a m l e ；b e s t n l l e ：最好规则 u n t i l ( ( j n u n l b 盯 o f 锄t s ) o r ( i r u l e c o n v e r g c n c e - t h r e s h o l d ) ) r u l e - c o n v e r g c n c c - t h f e s h o l d ：规则收敛值； 第四章基于蚁群算法的分类算法 n u m b e r o fa l l t s ：总的蚂蚁数量； r e m o v ec a s e sc o v e r c db yb e s t n l l ef 如mt r 血i n gs e t ； a d db e s t n l l et or u l e i j s t ；规则有序存储； e n d ： 总的算法如上述描述：首先，一只蚂蚁从空规则开始，构造一条规则。造规 则方法是：蚂蚁首先从第一个属性的万个属性值中以概率式( 4 1 ) 随机选择一个 属性值作为该规贝i j 的一个属性，再用同样的方法从训练集的第二个属性中选择规 则的第二个属性，依此类推，知道把训练集中所有属性搜完为止。然后在对该规 则进行剪枝，以出去规则中的冗余，使规则简单化。修剪完后我们对属性的属性 质进行信息素更新，规则中包含的属性的属性值外激素增加，而末被包含的属性 的属性值外激素浓度减少，更薪法则参照本文4 2 3 。这样我们构造了一条规则， 我们把该规则放入规则集中。再用下一只蚂蚁用同样的方法构造第二条规则，依 此类推，直到所有蚂蚁全部用尽为止，我们构造了一个规则集，再从规则集中选 出一条最好规则( b c s 仃1 l l e ) ，b c s h u l e 的选择标准是规则的有效性0 ，一条规则的 有效性q 越大，我们认为该规则越好，根据这条法则，我们选出最好规则，把它 存到最好规则集中。然后从训练集中移去它覆盖的样例，然后我们再用同样的方 法从剩余样例中构造下一条规则。直到训练集中剩余的样例数小于我们规定的允 许剩余训练集样例数为止。 4 4 用规则集对新样本进行分类 如图3 1 、3 2 所示，我们在对训练集建立如图3 1 所示的模型，通过模型挖 掘出分类规则集以后，所得到的规则集还要对测试集进行分类，以判断本规则集 的预测准确性。在作预测时，我们必须用有序规则集进行预测，先用第一个规则 进行测试，减去它覆盖的样例，再用第二个规则进行测试，依此类推，直到把所 有规受b 几种规赃用完为止。用所有规则覆盖的样例数除以训练集样例总数即得预 测准确率。 一般情况下，在用相同算法对不同的训练集作分类，所得到的规则集的预测准 确率是不同的，这时预测准确率得高低由测试集的性质决定。 4 5 本章小结 本章在前面第二章蚁群算法基本原理及第三章的分类规贝q 挖掘的基本知识介 绍的基础上，提出了基于一群算法的分类规则挖掘算法。该算法是：蚁群搜索一 基于蚁群算法的分类规则挖掘算法 个规则，移去它覆盖的样例，再重复这一过程，从而得到共同覆盖样例的一组规 则。本文根据每条分类规则中每个属性只能取一个属性值的特点，提出了采取用 相对概率对每个属性依次进行搜索的方法。具体的实验结果及分析将在下一章介 绍。 第五章实验结果及分析 5 1 1 试验数据 第五章实验结果及分析 5 1 试验数据及离散化方法 第四章给出了基于蚁群算法的分类的算法，在本章我们要对该算法进行实 验，以确定该算法进行实验，以确定该算法的好坏。 本文用了5 组数据如表5 1 所示：一列给出了数据的名称，第二列给出了样例 数个数，第三列给出了数据的离散属性的属性个数，第四列给出了连续属性的属 性个数，第五列给出了类别数。 表5 1 公共数据集 离散 连续属 数据集样例数属性 性数 类别数 数 1 1 i c o a c - 自0 e9 5 89 +2 d e n n a t o l o g y 3 6 63 316 w i s c o n s j nb r e a s t 6 8 392 c a n c e r h e p a n 6 s 1 5 51 362 c 1 e v e i 粕dh e a t t 3 0 3855 d i s e a s e 4 中标注的属性是连续属性。其实是离散属性 5 1 2 本文离散方法 本文指针对只有离散属性的数据进行分类，而对于有连续属性的数据必须进 行离散后才能对其进行分类。离散方法采取c 4 - 5 d i s cd i s m 如a t i d 丑m e t h o d 。这种 方法采用著名的c 4 5a l 鲥m m 嘲来离散连续属性。c 4 j 为决策树离散法，其方法 方法采用著名的c 4 5a l 鲥m m 嘲来离散连续属性。c 4 j 为决策树离散法，其方法 基于蚁群算法的分类规则挖掘算法 采用决策树分类法为：首先从连续属性中选择一个属性值，把所有次连续的属性 分为大于次属性值的集合、等于此属性值的集合和小于此属性质的集合，然后再 分别把这三个集合进行离散。当每个连续属性都被离散时，表5 1 中数据的属性只 剩下两个，即离散属性和类别属性。因此离散后的数据即可用本文算法进行分类 了。 表5 2 预测准确 预测准确率( ) 数据集 c n 2a n t - m i n e rc b o a c a t i c 协c t o e 9 7 3 8 o 5 2 7 3 0 4 蛇5 39 1 4 2 蛇9 4 d e m l a t o l o g y 9 0 3 8 士1 1 6 69 4 2 9 1 。2 09 6 3 2 1 9 8 w i s c o n s i nb r e a s t 9 4 8 8 0 8 89 6 0 4 o 9 3 9 7 3 8 0 5 7 c a n c e r h 印a t i t i s 9 0 0 0 2 5 09 0 0 0 3 1 19 0 3 4 0 2 5 c l e v e l 卸dh e a r t 5 7 8 4 1 7 8 5 9 6 7 2 5 05 8 3 2 0 3 2 d i s e a s e 表5 3 规则集及规则简洁性 规则集规则数平均每个规则的属性数+ 数据集 c n 2 a n t m i n e rc b o a c ac n 2a n t - m i n e rc b q a c a 1 1 c t a c t o e3 9 7 0 2 5 28 5 0 0 6 26 7 0 o - 3 22 9 01 1 81 o d e n n a t 0 1 0 9 y 1 8 5 0 4 77 3 0 0 1 5 6 4 0 o 2 92 4 73 1 62 7 8 w i s c o n s i n b r e a s t 1 8 6 0 0 4 56 2 0 0 2 5 6 1 0 o 1 7 2 3 91 9 71 4 0 c a n c e r h e p a t i t i s 7 2 0 土o 。2 53 。4 0 o 。1 63 。2 0 o 2 31 。5 82 4 12 。2 4 c l e v e l a n d h e a n 4 2 4 0 0 7 19 5 0 0 9 28 7 0 o 4 32 7 91 7 11 7 3 d i s e a s e + 指的是规则前件的属性 第五章实验结果及分析 5 2 1 参数设置 5 2 仿真实验研究及参数设置 3 1 1 ) 蚂蚁数( m b e r o f a m s ) ：这是一次d o u n t i l 循环时所进行的循环次数， 即构成的候选规则数，因为一只蚂蚁构造一个规则。蚂蚁数越多，每次循环 所构造的候选规则数越多，结果越好，但程序运行时间越长。 2 ) 每条规则所包含的最少样例数( m i n c a s e 眇m i e ) ：每条规则所包含的最少的 少样例的个数，引入它可以帮助我们避免训练数据的冗余。 3 ) 允许剩余的样例数( u n c o v e r e d c a s e s t h r e s h o l d ) ：算法总体循环时结束的条 件为剩余的样例数小于允许剩余的样例数( u n c o v e 脚c a s e s t h r e s h o l d ) 。 4 ) 规则收敛值( r u l e - c o n v e 增锄c e - t l i r e s h o l d ) ：如果当前蚂蚁构造的规则和前 r 出e c o n v e 瑁e n 。e t h 磷h o l d 1 只蚂蚁构造的规则一样，系统的本次d o u n t i l 循环结束，另一次d o u n l i l 循环开始。r u l e - c o n v e 珞e n c e t l l r e s h o l d 越大，结 果越好，但时间越长。 5 ) 信息素o ) 权重a ，a 越大，( f ) 所占的比重越大， 6 ) 的权重声，芦越大，嘞所占，的比重越大； 在本次试验中，我们参数设置为： 1 )n 啪b e ro f 觚t s = 3 0 0 0 ； 2 ) m i n - c a - p e r n l l e = 1 0 ； 3 )u n v 盱e d - c a s e s t h f e s l l o l d = 1 0 ； 4 ) r m l c c o n v e r g c n c c 也r e s h o l d = l o ； 5 )a 一1 ； 回 箩一1 ； 5 2 2 仿真实验 采用c 实现算法。实验条件为p e t i u m 2 6 6 g ，2 5 6 m 内存，x p 操作系统。 并与c n 2 和a - i l t - m i i i c r 在同样实验条件下进行比较进行了比较。 基于蚁群算法的分类规则挖掘算法 分两个方面进行比较1 ) 分类规则的预测准确率；2 ) 规则的简洁性。实验采用著名的 十字交叉法进行实验l s “，这种方法是将数据随机分成