（系统工程专业论文）基于改进蚁群算法的数据分类研究.pdf

大连理工大学硕士学位论文 摘要 数据分类一直是数据挖掘领域中的一个重要分支，随着信息技术和互联网的飞速发 展，传统的方法已经不能满足人们的需要。蚁群算法是近年来一种新兴的群智能算法， 在解决大规模组合优化问题中取得很好的效果，并在数据分类的解决中表现出了很好的 发展潜力，具有广阔的发展前景。然而，现有蚁群算法的内在机制存在不足，限制了其 性能的充分发挥。因此，提高数据分类应用中的蚁群算法性能，具有很强的理论和现实 意义。 本文首先对t s p 问题和数据分类的规则提取过程进行了对比研究，并利用t s p 问 题模型来建立数据分类的数学模型，然后通过蚁群算法对模型进行处理，得到数据分类 所要提取的规则。在此过程中，本文分析了现有蚁群算法在内在机制方面的不足并进行 了改进。本文的创新工作主要包括： 1 、针对蚁群的“近视”效应，提出了“贡献边”的概念，并据此引入“贡献函数” 对蚂蚁的选择策略进行改进，使得蚂蚁能够具有更全面的全局认识； 2 、将“贡献函数”应用到信息素平滑机制中，使得算法在接近收敛的情况下动态 地根据“贡献”大小对信息素含量进行更新，保证了搜索空间的多样性，进而提高了算 法对全局最优解的获取能力： 3 、针对蚁群选择策略的“盲目性”所导致的算法低效问题，引入“信息段”，使 得算法在不降低解的质量的前提下，动态降低搜索空间的维度，提高了算法的性能。 最后，本文实现了蚁群算法解决t s p 问题和数据分类的原型系统，并以此为基础对 改迸算法进行了性能测试。实验结果表明，相对于a n t m i n c r 和c n 2 算法，本文的改进 算法提取出的分类规则能够更精确地预测未知分类的数据，并且分类规则更简单、更易 理解。 关键词：蚁群算法；数据分类；t s p ；贡献函数 基于改进蚁群算法的数据分类研究 r e s e a r c ho ni m p r o v e da n t c o l o n ya l g o r i t h mb a s e dd a t ac l a s s i f i c a t i o n a b s tr a c t d a t ac l a s s i f i c a t i o ni sa l li m p o r t a n tb r a n c hi nd a t am i n i n g w i t ht h ef a s td e v e l o p m e n t so f i n f o r m a t i o nt e c h n o l o g ya n di n t e r a c t ，t r a d i t i o n a lc l a s s i f i c a t i o nm e t h o d sc a n n o tm e e tp e o p l e ，s n e e d a sas w a r l ni n t e l l i g e n c ea l g o r i t h md e v e l o p e di nr e c e n ty e a r s ，a n tc o l o n ya l g o r i t h m o b t a i n sg o o dr e s u l t sf o rl a r g e s c a l ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s f u r t h e r m o r e ，a n t c o l o n ya 1 9 0 r i t 1 m 1h a sb e e na p p i e dt 0s o l v ec l a s s i f i c a t i o np r o b l e m s a n dp r e s e n t sag r e a t p o t e n t i a la n daw i d ed e v e l o p m e n tp e r s p e c t i v e n e v e r t h e l e s s ，i t sp e r f o r m a n c ei sn o tf u l l y d e v e l o p e db e c a u s eo ft h ed i s a d v a n t a g e si ni t so w nm e c h a n i s m t h e r e f o r e ，i ti sm e a n i n g f u l b o t hi nt h e o r ya n da p p l i c a t i o nt oi m p r o v ei tw h e n a p p l i e dt od a t ac l a s s i f i c a t i o n t ob e g i nw i t h ，t h ec o m p a r i s o ns t u d yb e t w e e nt s pa n dt h ep r o c e s so fr u l e se x t r a c t i o ni s c o n d u c t e d t h e nt h er o o d e lo ft s pi sa p p l i e dt oc o n s t r u c tt h em o d e io fd a t ac l a s s i f i c a t i o n w h i c hi sp r o c e s s e db ym e a n so fa n tc o l o n ya l g o r i t h ma n da c q u i r e st h ec l a s s i f i c a t i o nr u l e s f u r t h e r m o r e ，t h ed i s a d v a n t a g e si nt h ei n t e r n a lm e c h a n i s mo fa n tc o l o n ya l g o r i t h ma r e a n a l y z e da n dt h u si m p r o v e d t h em a i nw o r k so ft h i sp a d e ra r ea sf o l l o w s ： 1 t h ec o n c e p to f “c o n t r i b u t i o na r c s ”i si n t r o d u c e dt oa v o i dt h ee f f e c to ft h e “s h o r t s i g h t o f a n t s b a s e do nt h i sc o n c e p t , t h e “c o n 砸b u t ef u n c t i o n w a sp r e s e n t e dt oi m p r o v et h es e l e _ 贮t i o n s t r a t e g yo fa n t s ，w h i c hr e s u l t si nt h a ta n t sc a nh a v em o r ec o m p r e h e n s i v ek n o w l e d g ea b o u t g l o b a ls e a r c hs p a c e ； 2 t h e c o n t r i b u t i o nf u n c t i o n ”w a sa l s oa p p l i e dt ot h es m o o t h i n go fp h e r o m o n et r a i l st o d y n a m i c a l l yu p d a t et h ep h e r o m o n et r a i l sa c c o r d i n gt o “c o n t r i b u t i o n ”w h e na l g o r i t h mi sc l o s e t oc o n v e r g e n c e n i si m p r o v e m e n tc a nk e e pt h ed i v e r s i t yo fs e a r c h s p a c e ，a n di nt u r n e n h a n c e dt h ea b i l i t yo fa l g o r i t h mt oe x p l o r et h eg l o b a lo p t i m a ls o l u t i o n s ； 3 d u et ot h e “b l i n d n e s ss e l e c t i o n ”o fa n t s t h ec o n c e p to f “i n f o r m a t i o ns e g m e n t ”w a s i n t r o d u c e dt od y n a m i c a l l yd e c r e a s et h ed i m e n s i o no fs e a r c hs p a c et om a k ea l g o r i t h mm o r e e f f i c i e n t ，b u tn o td e c r e a s e dt h eq u a l i t yo fs o l u t i o n s f i n a l l y , ap r o t o t y p es y s t e mt o s o l v et b ct s pa n dd a t ac l a s s i f i c a t i o nw a sd e v e l o p e d , a n d a c c o r d i n g l yt h ep e r f o r m a n c eo fi m p r o v e da l g o r i t h mw a se v a l u a t e d 孔ce x p e r i m e n tr e s u l t i n d i c a t e dt h a tc o m p a r e dw i t ha n t m i n e ra n dc n 2 ，t h ec l a s s i f i c a t i o nr u l e se x t r a c t e db y i m p r o v e da l g o r i t h ma r es i m p l e rt ob eu n d e r s t o o da n dc a l lp r e d i c tt h ed a t aw i t hu n k n o w n c l a s s i f i c a t i o n sm o r e e x a c t l y k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；d a t ac l a s s i f i c a t i o n ；t s p ；c o n t r i b u t i o nf u n c t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意。 作者签名：邀蛊丝日期：鲨z ：! ：2 大连理二 大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩e 口或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 邈 到盔丝 4 娑2 年月上日 大连理工大学硕士学位论文 1 引言 从上世纪9 0 年代以来，随着互联网和信息技术的大规模普及和应用，特别是数据 库技术的迅猛发展，教育、商业、工业、科学研究、医疗保健等各行各业所产生的数据 量正呈现出一种指数增长的趋势。虽然人们已经可以非常方便的获取和存储大量的数 据，但是在面对海量数据的时候，人们往往不能够再利用传统的信息处理、分析工具对 所获得的数据之间的内在关系和一些隐含的信息进行深入的探索，例如利用管理信息系 统对数据进行简单的查询、统计等。海量数据带来的不仅仅是越来越复杂的信息处理过 程和冗长的处理周期，还造成了“丰富的数据，贫乏的信息”这一局面。人们对于能够 智能地、自动地把数据转化成有用的信息或知识的技术和工具的迫切需求，促使了数据 挖掘技术的诞生和发展。如何从大量的数据中提取出潜在的、隐藏的规则，并用其来发 现有用的、准确的、可理解的信息，已经成为了当今数据挖掘和信息论领域中的热点问 题之一。 数据分类是数据挖掘领域中的一种重要的分析手段【1 】，它通过提取出现有数据中的 规则来描述数据的类别，并以此来预测未知的数据和信息。数据分类的目的就是从一堆 事务或对象当中判断出某一事物或对象的类别。特别是在当今数据量庞大的网络信息时 代，数据分类的重要性愈加突出。人们可以利用数据分类工具对海量的数据进行处理， 从中提取出有助于决策的信息和知识，从而使得人们减轻甚至摆脱“信息贫乏”的窘境。 1 1 问题的提出 在现实世界中，人们每时每刻都对出现在周围的事务进行着分类，并且根据分类的 结果进行判断。但是，人们判断所依赖的规则大多数来自人们的对事务的常识性认识和 积累的经验知识，其本质是一个不断归纳学习的过程。在数据挖掘领域中，人们把数据 分类( d a t ac l a s s i f i c a t i o n ) 定义为一个从现有的带有类别的数据集中寻找同一类别数据 的共同特征，并以此将它们进行区分的过程【”。 数据分类的解决一般分为分类模型的构建和分类模型的使用两个阶段：在模型构建 阶段，为每个类别产生一个相对应数据集的准确描述或规则，其核心内容是分类算法； 在模型使用阶段，利用提取出的类别描述或规则对未知类别的数据进行分类。本文主要 研究分类问题的模型构造阶段。 尽管数据分类在理论和技术方面已经取得了一定的突破，但是它仍然面临很多问题 的挑战，主要包括： 1 、分类算法的准确性和有效性 基于改进蚁群算法的数据分类研究 现代的信息社会的数据存储量往往达到了g b 级，甚至是t b 级。从海量的数据中 抽取分类信息要求所使用的分类算法必须是准确的和有效的。也就是说，在对于海量数 据的分类过程中，分类算法必须能够在可容忍的时间内提取出相对准确的分类信息。具 有指数复杂度的算法在实际应用中是无用的，即使它们能够提取出更加准确的信息。 2 、分类规则的可理解性 分类规则和结果是否能够被人们很好地理解是数据分类所提取出的信息是否有用 的前提。简单明了的分类规则和结果无疑会给人们的判断和决策提供很大的帮助。 解决数据分类的一般步骤如下i l j ： 1 、将现有的已知类别的数据划分为训练数据和测试数据两部分； 2 、通过构造分类算法对训练数据进行学习，最终得到一个符合学习要求的分类模 型，它可以通过分类规则、决策树或者数学公式等形式给出； 3 、使用分类模型对测试数据进行检验，如果符合要求则进行第4 步；否则，转到 第2 步； 4 、应用得到的分类模型对未知类别的新数据进行分类。 其中，第2 步构造分类算法对于分类结果的影响是至关重要的。一个好的分类算法 会使得产生的分类规则更准确地描述训练数据集的特点，并可以被更容易地应用到对未 知数据的预测中去，得到更精确地结果。随着数据分类在人工智能、机器学习和模式识 别等领域的广泛应用，许多分类算法相继产生，其中应用比较广泛、效果较好的几种分 类算法有决策树分类、贝叶斯分类、神经网络分类、蚁群分类等。其中，蚁群算法是受 到自然界中蚂蚁寻找食物行为的启发而被提出的，随后被应用到组合优化问题的解决 中，并取得了很好的效果，从而得到了越来越多的关注。近年来，蚁群算法逐渐被引入 到数据分类的解决中，由于算法本身的潜力，使得它在解决数据分类时相对于传统的分 类算法表现出更好的性能。但是，蚁群算法在数据分类中的应用还处在起步阶段，算法 在很多方面还有待于进一步完善，现有的改进也只是简单的针对问题而进行的，并没有 考虑算法内在的不足，从而使得算法性能的提升非常有限。本文的研究工作正式基于上 述问题而进行的。 在下一节中，本文将着重介绍几种比较经典的分类算法研究进展和优缺点，并在此 基础上分析比较蚁群算法相对于其它分类算法的优势和算法目前存在的不足。 1 2 国内外研究现状 ( 1 ) 决策树分类算法 大连理工大学硕士学位论文 决策树分类算法是最广泛使用的分类算法之- - 拍j 。决策树算法的分类学习过程包 括两个阶段：树构造( t r e eb u i l d i n g ) 和树剪枝( t r e ep r u n i n g ) 【7 l o 树构造阶段。决策树采用自顶向下的递归方式，从根节点开始在每个节点上按照 给定标准选择测试属性，然后按照相应属性的所有可能取值向下建立分枝、划分训练样 本，直到一个节点上的所有样本都被划分到同一个类，或者某一节点中的样本数量低于 给定值时为止。这一阶段关键的操作是在树的节点上选择最佳测试属性，该属性可以将 训练样本进行最好的划分。选择测试属性的标准有信息增益、信息增益比、吉尼指数以 及基于距离的划分等。此外，测试属性的取值可以是连续的，也可以是离散的，而样本 的类属性必须使离散的。 树剪枝阶段。构造过程得到的并不是最简单、紧凑的决策树。因为许多分枝反映 的可能是训练数据中的噪声或孤立点。树剪枝过程试图监测和去掉这种分枝，以便提高 对未知数据集进行分类时的准确性。树剪枝主要有先剪枝、后剪枝和两者相结合的方法。 树剪枝方法的剪枝标准有最小描述长度原则和期望错误率最小原则等。前者对决策树进 行二进位编码，最佳剪枝树就是编码所需二进位最少的树；后者计算某节点上的予树被 剪枝后出现的期望错误率，由此判断是否剪枝 生成一棵决策树是从数据中生成分类模型的一个非常有效的方法，相对于其他分类 方法，决策树算法应用最为广泛，其主要优点包括： 学习过程中不需要了解很多背景知识，只要训练事例能够用属性结论的方式表 达出来，就能用该算法进行学习； 决策树的训练时间相对较少； 决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式； 可以将决策树中到达每个叶节点的路径转换为i f t h e n 形式的分类规则，便于 理解。 尽管决策树分类在实际应用中取得了不错的效果，但是它仍然存在很多的问题： 在构造树的过程中，需要对数据机进行多次的顺序扫描和排序，使得算法的效率 不高，在处理大规模数据的时候的计算时间过长。 算法只适合对于驻留内存的数据集进行处理。当数据规模超出内存所能容纳的范 围时，程序无法运行。 ( 2 ) 贝叶斯分类算法 贝叶斯分类算法是一类利用概率统计知识进行分类的算法【8 】，如n b ( n a i v eb a y e s ) 等。这些算法主要利用贝叶斯定理来预测一个未知类别的样本属于各个类别的可能性， 基于改进蚁群算法的数据分类研究 选择其中可能性最大的一个类别作为该样本的最终类型。例如，考虑根据一个人的饮食 和锻炼的频率来预测他是否有患心脏病的危险。 在描述贝叶斯定理如何应用于分类问题之前，可以先从统计学角度对分类问题加以 形式化。设z 表示属性集，y 表示类变量。如果类变量和属性之间的关系不确定，那么 可以把z 和y 看作随机变量，用p 傩) 以概率的方式描述二者之间的关系。这个条件概 率又称为y 的后验概率，相应地，p 仞称为l ，的先验概率。 在训练阶段，要根据从训练数据中收集的信息，对z 和l ，的每一种组合学习后验概 率。之后，通过找出事后验概率最大的类可以对测试记录进行分类。 由于贝叶斯定理的成立本身需要一个很强的独立性假设前提，而此假设在实际情况 中经常是不成立的，因而造成其分类的准确性下降。为此出现了许多降低独立性假设的 贝叶斯分类算法，如t a n ( t r e ea u g m e n t e db a y e sn e t w o r k ) 等。 ( 3 ) 基于关联规则的分类算法 c b a ( c l a s s i f i c a t i o nb a s e do na s s o c i a t i o n l 是基于关联规则发现方法的分类算法【9 】，它是 数据挖掘中最活跃的研究方法之一，最早是由a g r a w a l 等人提出的l l 。最初提出的动机 是针对购物篮分析问题而提出的，其目的是为了发现交易数据库中不同商品之间的联系 规则，这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货库存以及 货架设计等。该算法分两个步骤构造分类器：第一步，发现所有的右部为类别的类别关 联规则( c l a s s i f i c a t i o na s s o c i a t i o nr u l e s ，c a r ) ：第二步，从已发现的c a r 中选择高优先度 的规则来覆盖训练集。c b a 算法主要是通过发现训练集中的关联规则来构造分类器。 关联规则的发现采用经典算法a p r i o r i ，该算法对于发现隐藏于大量交易记录之中的关联 规则来说是比较有效的。但当利用它发现分类规则时，为了防止漏掉某些规则，最小支 持度经常被设为0 ，此时该算法就发挥不了它的优化作用，结果是产生的频繁集过多， 运行效率很差。c b a 算法的优点是其分类准确度较高，因为它的发现规则相对较全面。 ( 4 ) 神经网络分类算法 神经网络是大量的简单神经元按一定规则连接构成的网络系统。他能够模拟人类大 脑的结构和功能，采用某种学习算法从训练样本中学习，并将获取的知识存储在网络各 单元之间的连接权中。神经网络主要有前向神经网络、后向神经网络和自组织网络。在 数据挖掘领域，主要采用前向神经网络提取分类规则。神经网络算法最早在文献【1 1 】中被 提出，此后又提出许多变形，包括替换的误差函数、网络拓扑的动态调整、学习率和要 素参数的动态调整等。近年来，从神经网络中提取规则受到越来越多的关注。主要有以 下两种倾向：一个是网络结构分解的规则提取；另一个是由神经网络的非线性映射关系 大连理工大学硕士学位论文 提取规则。虽然神经网络分类目前在解决分类问题方面取得了较好的结果，但是仍然存 在较多的不足，主要包括： 网络不适合处理大规模的数据。当数据的规模足够大的时候，采用神经网络解决 分类问题会使得计算时间过长，资源占用过多，导致解决问题的效率低下。 分类过程比较复杂。由于神经网络分类过程中，分类规则隐含在网络权值之中， 需要对输入层和隐含层结点逐步、反复的训练和筛检，直到分类预测精度误差达到一定 的可接受的程度范围。 ( 5 ) 遗传分类算法 遗传分类算法是模拟生物进化过程的全局优化方法【1 2 1 ，将较劣的初始解通过一组遗 传算子( 繁殖即选择、交叉即重组、变异即突变) ，在求解空间按一定的 随机规则迭代搜索，直到求得问题的最优解。遗传算法在数据挖掘领域的主要应用有： 用它和b p 算法结合训练神经网络，然后从网络提取规则；分类系统的设计，如编码方 式、新任分配函数的设计以及遗传算法的改进等。但是遗传算法应用于数据挖掘领域也 存在很多的问题：首先，算法较复杂；另外，算法收敛于局部最小导致得不到全局最优 等难题还未得到很好地解决。 ( 6 ) 基于数据库技术的分类算法 虽然数据挖掘研究的兴起是由数据库领域的研究人员掀起的，然而至今为止提出的 大多数算法则没有利用数据库的相关技术，数据挖掘应用也很难与数据库系统集成，此 问题已成为该领域研究的关键问题之一。在分类算法中，目前主要有m n d 1 3 l 和 g a c r d b 1 4 1 两种。 m n d ( m i n i n gi nd a t a b a s e ) 算法是采用数据库中用户定义的函数( u s e r d e f i n e d f u n c t i o n ，u d n 是发现分类规则的算法。m n d 采用典型的决策树构造方法构建分类器。 其主要区别在于它采用数据库提供的u d f 方法和s q l 语句实现树的构造。简单来说就 是在树的每一层，为每一个属性建立一个维表，存放各属性的每个取值属于各个类别的 个数以及所属的结点编号。根绝这些信息可以为当前结点计算每种分类标准的g i n i i n d e x 值，选出最优的分类标准，然后据此对结点进行分类。上述过程中，对维表的创 建和修改需要进行多次，s o l 实现耗时过多，因此采用u d f 实现。而分类标准的寻找 过程则通过创建若干表和视图，利用连接查询实现。 g a c r d b 算法是一种利用s o l 语句实现的分类算法。它采用一种基于分组计数 的方法统计训练集中各种属性取值组合的类别分布信息，通过最小置信度和最小值尺度 两个阈值找出有意义的分类规则。该算法使用关系数据库系统提供的聚集运算功能，利 用s q l 语句完成主要的计算任务。首先，利用s o l 语句计算利用每个属性进行类别判 基于改进蚁群算法的数据分类研究 定的信息含量，从而选择一个最好的分类属性，并且按照信息含量的大小对属性进行排 序。接着循环地进行属性的选择、候选分类表的生成、剪裁以及分类误差的计算，直到 满足结束条件为止。 基于数据库的分类的缺点有： 算法采用u d f 完成主要的计算任务，而u d f 一般利用高级语言实现，无法使用 数据库系统提供的查询处理机制，无法利用查询优化方法，且u d f 的编写和维护都比 较复杂。 ( 多g a c r d b 中用s q l 语句实现的功能本身是比较简单的操作，但是采用s q l 实 现的方法却显得相当复杂。 m 蚁群分类算法 蚁群算法( a n t c o l o n y o p t i m i z a t i o n ) 1 1 5 , 1 6 l 是由意大利学者d o r i g o m 在1 9 9 1 年提出的 种模拟自然界中蚂蚁集体寻找路径的行为而提出的一种基于种群的启发式仿生进化 算法，目前已被应用到许多问题的解决中并取得了很好的效果【n 1 9 1 。蚁群算法包括两个 基本阶段：适应阶段和协作阶段【捌。在适应阶段，各候选解根据积累的信息不断调整自 身结构：在协作阶段，候选解之间通过信息交流，以期产生性能更好的解，这类似于学 习自动机的学习机制。 p a r e p i n e l l i 等最早将蚁群算法应用于数据挖掘领域，提出了一种求解数据分类的蚁 群算法a n t m i n e r 2 1 1 ，并取得了较好的结果。这是由于蚁群算法具有以下优点： 蚁群算法通过群体间的合作机制来探寻问题的最优解； 通过相对简单的个体( 蚂蚁) 对解空间进行搜索，便于实现； 具有信息正反馈的特点； 算法具有很好的健壮性、鲁棒性和分布式特点。 正是蚁群算法的这些优点使得它在解决大规模的数据分类时的表现优于其它分类 算法，能够更快、更好的提取出分类规则，并且表现出了很大的潜力。 随后，国内外的很多学者在此基础上对算法进行了相应的改进f 2 1 彩l ，但这些改进大 多停留在对于具体数据分类的解决上，并没有对算法的本质和内在的机制进行更深入的 分析。同时，蚁群算法在解决数据挖掘问题方面还处在起步阶段，存在很多问题：算法 对于分类模型的普适性还有待加强；算法的性能还有很大的提升空间等。本文的工作正 是基于蚁群算法在这些方面的缺陷而进行的。 大连理工大学硕士学位论文 1 3 本文的研究思路及主要的工作 根据前面小节的论述，数据分类的核心是分类模型的构造过程，即分类规则的提取 过程。为了提高蚁群算法在模型构造过程中的性能，需要对算法的内在机制进行深入的 了解和分析，在剖析算法本身不足的基础上对算法进行改进。由于蚁群算法最早被用来 解决具有代表性的组合优化问题之一旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ， t s p ) ，并取得了很好的结果，因此本文在蚁群算法对t s p 问题的解决中分析、解决算法 本身的不足。另外，由于t s p 问题与数据分类在解得构造过程中有一定的相似性，所以 利用t s p 问题分析改进的蚁群算法也可以较好地应用到数据分类的解决当中，提取出相 对于改进前的算法更加准确、易理解的分类规则，得到更好的分类结果。本文的研究思 路如图1 1 所示。 本文将会进行以下主要的工作： 1 、数据分类与t s p 问题分析； 2 、对蚁群算法进行分析改进； 3 、对改进后的算法进行试验和结果比较； 4 、将改进后的算法应用于数据分类； 5 、进行应用结果分析。 l 一匝 基于改进蚁群算法的数据分类研究 利用t s p 问题模型对数据分类进行建模 基本蚁群算法及其 改进算法简介 算法内在机制与不足 引入il 利用贡i i 引入 贡献i i 献函数ll 信息段 函数ii 改进p t si i 概念 改进求解结果i l 改进算法效率 图1 1 论文研究思路 f i g 1 1r o a d m a po ft h et h e s i s r e s e a r c h 一8 一 ( 第一章) ( 第二章) ( 第三章) ( 第四章) ( 第五章)l结论与展望 大连理工大学硕士学位论文 1 4 本文的组织结构 本文共分4 个章节。为了使得蚁群算法更好的应用于数据分类，本文将在第二章对 数据分类进行深入分析，并通过与t s p 问题的比较分析来进行模型建立，便于蚁群算法 在数据分类中的应用；在建立模型后，本文第三章将针对算法在模型应用中出现的问题 加以分析、改进，并利用t s p 问题标准数据集进行试验结果比较，从而得出改进算法性 能优越的结论；本文第四章将把改进后的算法应用于数据分类中，同时运用数据分类的 标准数据集对算法性能进行验证；最后将阐述本文的结论和展望。 基于改进蚁群算法的数据分类研究 2 数据分类的分析与建模 2 1 问题分析 2 1 1 问题定义与描述 在数据挖掘中，分类的任务就是确定对象属于哪个预定义的目标判硐。数据分类的 输入数据是记录的集合，其中每条记录也称作数据分类的实例或者样例，用元组国力 来表示。工是属性的集合，而y 是一个特殊的属性，指出实例的类标号( 也称为分类属 性或目标属性) ，以表2 1 所示的数据集合为例 2 6 1 。 表2 1 脊椎动物数据集 t a b 2 1d a t as e to fv e r t e b r a t e 表2 1 所示的样本数据集合将脊椎动物分为以下几类：哺乳类、鸟类、鱼类、爬行 类和两栖类。属性集指明脊椎动物的性质，如体温、繁殖方式、飞行能力等，而类别标 号则表明具有这些性质的脊椎动物所对应的类别。尽管表2 1 中的属性主要是离散的， 但是属性集也可以包含连续特征，如年龄、身高等。同时，类标号却必须是离散属性。 通过以上的描述，可以给分类的定义： 定义2 1 分类( c l a s s i f i c a t i o n ) 分类的任务就是通过学习得到一个目标函数( t a r g e t f u n c t i o n ) f , 把每个属性集z 映射到一个预先定义的类标号y 。 大连理工大学硕士学位论文 其中，目标函数也称分类模型( c l a s s i f i c a t i o nm o d e l ) 。解决数据分类的一般步骤如图 2 1 所示。首先，需要一个训练集( t r a i n i n gs e t ) ，它是由类标号已知的纪录组成。使用训 练集建立分类模型，该模型随后将运用于检验集( t e s ts e t ) ，检验集由类标号未知的记录 组成，如图2 1 所示。 训练集 t i d l 2 3 4 属性1 属性2 属性3类 n o n o n o y e s y e s l a r g e 1 2 5 k n om e d i u ml o o k n os m a l l7 0 k y e s m e d i u m1 2 0 k 1 l n os m a l l5 5 k 1 2y e sm e d i u m8 0 k 1 3y e s l a r g e 1 l o k 1 4n os m a l l6 7 k 厂 1 分类模型l i一 图2 1 分类模型的建立 f i g 2 1c o n s t r u c t i o no fc l a s s i f i c a t i o nm o d e l 2 1 2 分类模型 从图2 1 可以看出，解决数据分类关键是分类模型的建立。实际上，这个过程就是 利用分类算法对分类规则提取的过程。目前普遍采用的方法是i f - t h e n 结构，如下式。 i f 刀删c l a s s ( 2 1 ) 其中i f 部分表示数据记录满足一定的条件，这些条件可以是多个；t h e n 表示满 足这些条件时数据记录的类别。各个条件之间通常用逻辑连接符a n d 来连接起来，表 基于改进蚁群算法的数据分类研究 示一个整体。并且每个条件需要满足： 三元组结构，在本文中 o p e r a t o r 用“= ”表示。例如，图2 1 中的训练集的第一条记录可以用i f - t h e n 规则表示 成： 腰 t h e n ( 类- n o ) ( 2 2 ) 从数据挖掘的角度来说，我们希望i f 部分的条件越少越好，这样能够使得分类的 规则看起来更容易理解，符合可理解性的原则。 2 2 数据分类模型与t s p 模型的关系 从上面的描述可知，分类规则的提取是解决数据分类的前提和关键。规则提取过程 也就是依次进行属性选择的过程，这与解决t s p 问题中的路径构造过程非常的相似，因 此可以利用t s p 优化问题表示分类规则的提取过程。在问题转化的基础上，通过将蚁群 算法应用于解决t s p 问题来深入了解算法内部机制，改进算法本身的不足之处，为更好 地应用于数据分类打下基础。为了更好地说明两类问题的相似性，这里首先对t s p 问题 进行简要地回顾。 2 2 1t s p 问题简介 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 是指一个商人从一个城市集合中的任 意一个城市出发，希望能找到一条最短路径，使得商人能经过每一个城市一次且仅一次， 图2 2 显示了一个t s p 问题的图形表示及它的两种可行路线。其中根据城市之间距离的 定义不同，t s p 问题又可分为非对称t s p 问题( a s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ， a t s p ) 和对称t s p 问题( s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 。前者定义城市a 到城市b 的距离不等同于城市b 到城市a 的距离；后者定义任意两城市问的距离是不 变的。因此，可以给出t s p 问题模型的定义，如下： 定义2 2 有向图g = ( k 彳，d ) ，其中城市集合p ，- 所，巧，碥) ，边集合爿= ( f ，d 陋d y 矿，城市间距离函数d q ，j ) e r ，解空间t l j 。t s p 问题的目的就是我出条闭合路 径t et f ，使得价值函数“幻= e d ( i ，j ) 最小，其中( f ，j ) e t 。 大连理工大学硕士学位论文 图2 2t s p 问题实例及其两种可行解 f i g 2 2i n s t a n c eo f t s pa n di t st w os o l u t i o n s 2 2 2t s p 问题与数据分类 求解t s p 问题的过程是一个路径构造的过程。从解决优化问题的方法论角度来说， 此过程采用了构造一个完整解的方式。在解题过程中，算法在城市中不断选择，最终得 到一条完整的路径。如图2 2 中的实例问题，每一个城市依次被选择了一次，最终构成 一条闭合的路径。 数据分类的核心问题是分类规则的提取，这一过程与t s p 问题中的路径选择过程具 有很大的相似性。正如我们在2 1 2 节讲述的那样，分类规则采用i f - t h e n 结构来进行 表示，其中前提条件球的表现形式为 。假 如将 这一属性值对看作是t s p 问题中的城市的话，那么分类规则提取过 程就转化成了构造一条闭合的规则的过程，即t s p 问题。所以可以说，t s p 问题和数据 分类( 分类规则提取问题) 在本质上是具有相似性的，如图2 3 所示。t s p 问题与数据 分类的相似性如下： 1 、t s p 问题中的城市和数据分类中的属性值对都可以被看作是问题中的一个节点； 2 、两类问题的解决也都是通过节点选择来完成的，即构造不同节点的排列的过程。 这是两类问题本质上的相似点，也是两类问题能利用蚁群算法解决的前提和保证。 基于改进蚁群算法的数据分类研究 t t e r m l = v a l u e l 图2 3 数据分类实例 f i g 2 3i n s t a n c eo f d a t ac l a s s i f i c a t i o n 当然，除了联系之外两者之间也存在一定的差异。t s p 问题与数据分类的差异如下： 1 、t s p 问题的每个节点是一个独立的城市，在节点选择时不需要进行额外的操作， 如图2 2 所示；数据分类的节点是由属性值对构成的，每个属性对应一定的取值或取值 范围，如图2 3 所示。因此在构造数据分类的解时，需要引入额外的对属性取值的操作。 2 、t s p 问题需要把所有的城市依次遍历一次且仅一次，不能忽略任何一个城市； 而数据分类则可以通过后处理过程忽略某一个或几个不重要的属性，从而提取出分类所 需要的规则，如图2 4 所示。 大连理工大学硕士学位论文 t 丁e r m l = v a l u e l t e r m 8 = v a l u e 8 图2 4 忽略属性的规则提取 f i g 2 4e x t r a c t i o no fr u l e sb yi g n o r i n ga t t r i b u t e s 2 3 数据分类模型的建立 由上节的分析可以看出，t s p 问题和数据分类本质上具有一定的相似性。因此，可 以利用t s p 问题的模型建立方法得到数据分类的模型。 数据分类的核心内容是分类规则的提取，也就是式2 1 中的皿部分。这个部分由一 些 属性值对通过逻辑连接符“a n d ”连接构成的。因此，通过把数据分类 转化为t s p 问题，可以得到一条闭合的属性链，即分类规则的礤部分，而分类规则的 t h e n 部分则是这条属性链对应的类别信息。下面给出数据分类的模型定义。 定义2 3 有向图g = l ，其中属性集合r - - 乃，疋，晶) ，相应的属性域集合 皓 n ，玩，k ，属性值集合k = ，k 。) ，分类规则质量q ，解空间v 。数 据分类的目的就是要找出一条闭合的规则r e v ，使得价值函数，( r ) = q ，最大，其中= 嘲 与定义2 2 中的t s p 问题模型进行比较后，不难从数学角度看出二者的联系和区别 与2 2 2 节中的分析是一致的。因此，我们可以在研究如何更好地解决t s p 问题的基础 基于改进蚁群算法的数据分类研究 上来解决数据分类。所以，在下一章中，本文会着重分析蚁群算法在t s p 问题中的应用 和改进，以便为更好地解决数据分类打下良好的基础。 2 4 本章小结 本章首先对数据分类进行了深入的分析，给出了问题的定义、任务描述和分类模型 的建立过程。然后在对t s p 问题和数据分类进行较全面比较的基础上，重点分析了两类 问题的联系与区别，得出了两类问题模型具有本质上的相似性的结论，并建立了数据分 类的数学模型，为t s p 问题的解决方法在数据分类解决中的应用提供了理论支持。 大连理工大学硕士学位论文 3 蚁群算法的改进研究 从第2 章的分析可以看出数据分类与t s p 问题解决过程具有相似性。因此，本章首 先对新兴的群智能算法一蚁群算法在t s p 问题的解决过程进行分析，并在此基础上对 算法进行改进。 上世纪9 0 年代初期，意大利学者m a r c od o r i g o 等最早从自然界中蚂蚁的觅食行为 得到启发，根据蚂蚁的自然特性1 2 7 - 3 0 i 提出了运用蚂蚁能够找到巢穴和食物源之间最短路 径的特性来解决组合优化问题。蚁群算法最早被用来解决组合优化问题中的经典问题一 - t s p 问题，并取得了很好的效果。本章首先对解决t s p 问题的基本蚁群算法及几种改 进算法进行简单回顾，然后分析现有算法的不足，并提出改进策略。最后，通过对标准 t s p 问题的实验结果比较来验证改进后的算法性能的优越性。 3 1 蚁群算法 3 ，1 1 基本蚁群算法 根据仿生学家的长期研究发现，蚂蚁虽然没有视觉，但它们运动时会通过在路径上 释放出一种特殊的分泌物信息素来寻找路径 2 7 1 1 2 9 1 。当它们遇到一个还没有经过的路 口时，就会随机地挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的 路径越长，则释放的信息素量越少。当后续的蚂蚁再次遇到这个路口的时候，它们选择 信息素量相对较大的路径的可能性更大，然后继续在经过的路径上留下信息素。从而使 得信息素含量大的路径上的信息素含量以更大的可能性增加，形成一种正反馈的机制 i n 】。伴随着相对较短的路径上的信息素含量越来越大，其它路径上的信息素会随着时间 的流逝而逐渐消减，最终导致蚂蚁找到最优的路径，如图3 1 所示。图3 1 a 中，蚂蚁对 于没有经过的路径的选择是没有倾向的，因此会以相