（计算机应用技术专业论文）基于微粒群算法生成分类规则.pdf

中北大学学位论文 基于微粒群算法生成分类规则 摘要 分类是数据挖掘的一种技术 在商业上已经得到了应用 常见的分类算法有决策树 统计方法 机器学习方法 神经网络方法等 由于进化算法在解决复杂问题时表现出它 的优越性 自遗传算法用于实现数据分类以来 已有很多的进化算法用于数据分类问题 微粒群算法 p a r t i c l es w a r mo p t i m i z a t i o n p s o 作为进化算法的一种 有其自身 的独特性 本文在分析p s o 算法模型 分类模型的基础上 提出了应用p s o 算法实现 数据分类 并通过实验验证了其有效性 首先 设计了p s o 算法实现分类问题的编码 适应度及总体结构 并利用单群体实现了p s o 分类 其次 为了能更好的利用p s o 算 法的特性 提高分类精度 采用多群体p s o 算法生成分类规则 在此方法中 单群体 p s o 算法进化一类规则 c 类问题由c 个群体p s o 算法实现 再次 设计了由实数和二 进制组成的混合编码的表示形式 无关属性单独表示 减少了分类时间 最后 在对遗 传规划 g e n e t i cp r o g r a m m i n g g p 模型分析的基础上 将p s o 算法和g p 相结合 设 计的规则由规则结构和规则的值两部分组成 利用g p 进化规则的结构 p s o 进化规则 的数值 由于p s o 算法后期易于陷入局部最优 为了使p s o 算法更好的解决分类问题 对 p s o 算法进行了改进 提出了具有自适应随机惯性权重的p s o 算法和在p s o 算法中引 入了变异算子 都取得了好的效果 关键词 微粒群算法 分类规则 编码定义 适应度 中北大学学位专a 文 a s t u d yo fe v o l v i n gc l a s s i f i c a t i o nr u l e b a s e do np s o a l g o r i t h m a b s t r a c t t i l ec l a s s i f i c a t i o ni sak i n do ft e c h n o l o g yo fd a t am i n i n ga n dh a sa l r e a d yo b t m n e d a p p l i c a t i o ni nt h et r a d e l h ec o m m o nc l a s s i f i c a t i o na l g o r i t h mh a sd e c i s i o nt r e e s t a t i s t i c a l m e t h o d m a c h i n el e a r n i n g n e u r a ln e t w o r ka n ds oo n s i n c eg e n e t i c c l a s s i f i c a t i o ns y s t e m w a si m p l e m e n t e d m a n ye v o l u t i o na l g o r i t h m sw e r ea p p l i e dt oc l a s s i f i e rb e c a u s et h e ys h o w t h e i ra d v a n t a g ei ns o l v i n gc o m p l e xp r o b l e m s p a r t i c l es w a r mo p t i m i z a t i o n p s o a l g o r i t h mh a si t so w ns p e c i a lc h a r a c t e r sa so n eo f e v o l u t i o na l g o r i t h m s b a s e do na n a l y s i so fp s om o d e la n dc l a s s i f i c a t i o nm o d e l p s o c l a s s i f i c a t i o ns y s t e mw a sp r e s e n t e da n ds h o w e di t se f f i c i e n c yt h r o u g ht h ee x p e r i m e n tr e s u l t s i nt h i sp a p e r f i r s t l y c o d i n g f i t n e s sf u n c t i o na n de n t i r es t r u c t u r eo fp s oi nc l a s s i f i c a t i o n s y s t e mw a sd e f i n e d p s oo fs i n g l ep o p u l a t i o nw a sa p p l i e dt oi m p l e m e n t c l a s s i f i c a t i o ns y s t e m s e c o n d l y m u l t i c a t e g o r yp r o b l e mw a st a k e na sm u l t i t w o c l a s sp r o b l e m an e wa p p r o a c ho f u s i n gm u l t i p a r t i c l e s w a l t l lt oe v o l v em u l t i c l a s s i f i c a t i o nr u l ew a sp r o p o s e di no r d e rt o i m p r o v ea l g o r i t h mp e r f o r m a n c e i nt h i sw a y ap o p u l a t i o ne x p r e s s e d ac a t e g o r ya n d m u l t i c a t e g o r yw a si n d i c a t e db ym u l t i p a r t i c l e s w a r l t t t h e n h y b r i dc o d ec o n s i s t e do fr e a l a n db i n a r yn u m b e rw a sd e s i g n e dt or e p r e s e n t n oc a r e a t t r i b u t e a sar e s u l t i tr e d u c e d c l a s s i f i c a t i o nt i m e f i n a l l y o nt h eb a s i so f a n a l y s i so fp s oa n dg e n e t i cp r o g r a m m i n g g 辫 p s oa n dg pw a sc o m b i n e dt oe v o l v er u l ew h i c hg pw a su s e dt oe v o l v er u l es t r u c t u r em a d p s ow a sa p p l i e dt oe v o l v er u l ev a l u e b e c a u s ep s ot e n d st or u ni n t ol o c a lo p t i m u mi nl a t t e rp e r i o d p s ow a si m p r o v e dt o p r e f e r a b l es o l v ec l a s s i f i c a t i o n p s ow i t ha d a p t i v ea n ds t o c h a s t i ci n e r t i aw e i g h tw a s p r e s e n t e da n dm u t a t i o no p e r a t o rw a si m r o d u c e d t h e y a l lo b t a i nb e t t e re x p e r i m e n tr e s u l t s k e y w o r d s p s o a l g o r i t h m c l a s s i f i c a t i o nr u l e c o d ed e f i n i t i o n f i t n e s s i i 原创性声明 本人郑重声明 所呈交的学位论文 是本人在指导教师的指导下 独 立进行研究所取得的成果 除文中已经注明引用的内容外 本论文不包含 其他个人或集体已经发表或撰写过的科研成果 对本文的研究作出重要贡 献的个人和集体 均已在文中以明确方式标明 本声明的法律责任由本人 承担 论文作者签名 互邕函主日期 坦嶝旦 旦 关于学位论文使用权的说明 本人完全了解中北大学有关保管 使用学位论文的规定 其中包括 学校有权保管 并向有关部门送交学位论文的原件与复印件 学校可 以采用影印 缩印或其它复制手段复制并保存学位论文 学校可允许学 位论文被查阅或借阅 学校可以学术交流为目的 复制赠送和交换学位 论文 学校可以公布学位论文的全部或部分内容 保密学位论文在解密 后遵守此规定 签名 婴9 主 导师签名 日期 型 主兰因塑旦 日期 塑主掏丛鱼 中北大学学位论文 第一章绪论 i i 人类认识世界以来 人类就知道列事物分成不同的类别 以达到了解未知世界的 i 1 呐 在原始的分类学巾 人们的分类是依据经验和专业知识来进行定性分析 很少使 川数学r 目 然而 社会发展到现在 而对着信息爆炸及海量数据 人们迫切需要一些 叫一i 能从数掘中智能地 自动的获得我们所需要的知识 数据挖掘 2 1fd a t a n i n g i m 就是从大量的 不完全的 有噪声的 随机的数 铷h 提取隐含在其中的有用的信息和知识的过程 从某种意义上来说 知识就是分类 吲i 讥d m 作为2 0 盟纪术刚刚兴起的数据智能分析技术 是机器学习 数据库技术和统 节三者扦瞄合的产物 山于其具有广阔的应用前景而备受关注 数据挖掘根据挖掘任 务 i 分为分类发现 数据总结 聚类 关联规则发现 序列模式发现 依赖模型发现 等 本质 i 束叶 数据挖掘的目标就是从实际世界的数据集中发现知识 所以分类做为 数据挖捌 机器学习和模式识别中一个重要的研究领域 对于它的研究就比较重要 1 1 常见的分类算法 分类技术斧统汁分析领域中称为判别分析 比较有名的算法有b a y e s 判别法 距离 l 函数法和k 近邻法及支持向量机等 b a y e s t 3 1 4 1 分类算法是基于贝叶斯定理构造出来的 处删 t r j t d 数掘时 能表现出较高的准确性和运算性能 但事实上 精确估计条件概率 是 引困难 1 7 在人 智能领域 7 7 4 7 l 器学习的角度来看 最常用的是决策树口 算法 决策树是以 羔鬯 熵为基础的一利 决策分类算法 对噪声数据有很好的健壮性且能够学习析取表达 式 优先选择较小的树 是种逼近离散值函数的方法 经常用于数据挖掘 智能决策 锁域 虹年来 波兰数学家p a w l a k 提出了 1 1 t 链集f 6 1 理论 这是一种刘不确定知1 识的分类方 趔 认为知以就是将对象进行分类l i d 能 d 通过数据约简 在保证数据一致的约束下 简f l i e 4 阡i 本数据 最终使用很少的几条逻辑规则就一 1 以描述分类规则 t i i f 十方 型i 他们指出动态范围的选择方法更适合多类问题 m e n d e s 等刚用g p 进化模糊规则 集 0 群f i l e f 1 隶属度函数 p 1 a s a dm u n i 等p 提出单次运行g p 来设计多类问题的分类器的 乃然 赴这种方法中 当g p 进化时 将所有的类采用一种统一的观点 13 本文主要完成的工作 微粒群算法 p a r t i c l es w a r mo p t i m i z a t i o n p s o 3 6 1 3 7 1 是进化算法的一种 与其它 逊化算法有 j 多共刷之处 均使用 群体 概念 表示一组解空间中的个体集合 但是 s o 算法同时呈现出其它进化类算法所不具有的特性 它能给出一组显式的进化方程 表现 li 嗣优良特性 与进化规划剥比 可以看出p s o 算法执行一种有意识的变异 韭化桃划川变异到任何力向 从理论上讲 进化规划有更多的机会在优化点附近开发 而 j 算法 如果 意以 能提供有用的信息则微粒有更多的机会更快地飞到有更好解 洲噩域 与遗传算法对比 k e n n e d y 和s p e a r s l 3 8 埽0 用多峰问题产生器对一个p s o 的二 进 1 豆本和3 种类型的g a s 研究发现 p s 0 基本都能更快地达到全局最优值 基本不受 涮题峰数的影响 受问题维数的影响也很小 山j 二p s 算法的这些特 t 氧 并且由于算法简单 容易实现 在短短几年时间 p s o 算 法得到了很大的发展 并有很多学者对它的应用进行了研究 由于微粒群算法的应用研 究尚处下d j f i i t 段 算法的研究是为 应用 所以本文在拓展微粒群算法的应用方面进 h 盯究 t 要是将微粒群算法应用于数据挖掘中的分类问题 并在应用过程 o x j 微粒 1 7 法 r 某些改进 具体来说 丰要完成以下几个方面的工作 通过剥微粒群算法和分类模型的分析 分类问题采用易于理解的规则表示方法 进行了雕 算法挖掘分类规则的编码设刮和适应度定义以实现分类 2 根扼 分类问题中的多类问题可以看成多个两类问题的思想 没汁使用多个群体 柬 奘蛳分类 每个群体都单独使用微粒群算法进化 类规则 试验结果表明该算法对于 4 中北人学学位沦文 分类问题有更高的预测精度利更快的运行速度 由于惯性权重和全局最好值对算法的性 能影j l i q 较大 提出了具有自适应随机惯性权重的微粒群算法 根据列全局最好值的分析 剥塌f j f tj i h 了变异操作的改进的微粒群算法 t 根据属 k l 与分类相关性与否的分析 设计实数耵l 二进制混合编码麻用于分类系 统 q 存分析分类模 儿遗传规划 微粒群算法的基础上 根掘分类规则的 圭度和结 糊的不确芷性 逸传规划的表示结构利微粒群算法进化的过程 设汁r 瞄遗传规划和微 瓤 辩法州结合生成分类圳则的力法 5 中北大学学位论文 2 1 数据分类 i1 分类问题描述 第二章数据分类和微粒群算法 分类反映同类事务麸同性质的特征型知识和不同事务之问的差异型特征知识 分类 方 7 用于预测数掘对象的离敞类别 分类的目的是能根据已分类的数据构造出一个分类 rl 1 l 1 1 1 候型 驯分荧器 定义1 泼x l x 2 x c 是随机变量 其中x 的域为d o m x 在不失一般 r i 的i j l 提f 设d m c 1 2 目 个分类器就是函数 d o m y 1 d o m x 二 d o m x 斗d o m c 其中 x 则称为该分类器的输入属 制 c 称为类别 c a t e g o y 属性 也称做类标 c l a s s l a b e l 属性 婴构造一个分类器 需要一个训练样本数据集7 1 没丁由m 个儿素组成 每个元素 菪 吲 属性州l 述 在所有属一陆中 有且仪有一个属性为类别属性c 其它属性为输入 属性 输入属性集合即x x i x x 0 其中置具有不同的值域 当一个属性的值 域为连续哦时 咳属性称为连续属性 否则称为离散属性 如果c k c q 那么 7 呲行k 个1 i 同的类别 这样 丁就隐含地确定了一个从 到类别属性c 的映射函数 1 通过刘 进行某种操作 可将陔隐含函数 表示出来 2 分类问题的表示方法 分类模 弘自很多的表示方法 比如决策树 公式 形式文法 形式逻辑表达式 神 经网络 框架和模式 规则等等 假砹数据挖掘用于决策支持系统 但真正最后的决策 尚屉用户 知识发现的结果划用户来说应该是易于理解 表示形式简单 采用规则表不 的分类器就比较好理解 而神弪网络的结果就比较难以理解 本文采用描述型的 h e h 的规则表示方法 6 中 匕大学学位论文 1 3 分类器评价 不同的分类器有不同的特点 分类器评价或比较尺度有三种 1 预测准确度 预 测 j2 1 i c 表示个分炎模型分类的正确率 通常影响一个分类器分类错误的有以下几 1 索 a 川练集的记录数量 股来说 训练集越大 分类器也就越可靠 然而 训 练集越大 构造分类器的叫制也就越长 错误率改善情况随训练集规模的增大而降低 b 特 内数目 过多的属性数日意味着要计算更多的组合 使得构造分类器难度增火 需要的叫州也更长 c 属性中的信息 属性是否跟类信息相关 d 待预测记录的分布 粜待预测记录柬自不同于训练集中记录的分布 那么错误率有可能很高 2 计算的 复杂度 计算的复杂度依赖于具体的史现细节和硬件环境 3 模型描述的简洁度 一 股对f 分类任务来说 模型描述的越简单越容易使人理解 预测的准确度是使用最多的 种比较j t 度 利用训练数据归纳学习获得一个分类器并利用训练数据对所得的分类器准确率进 行 i h 将会得到一个有关陔分类器准确性的过分乐观且具有误差性的评估结果 因为 舣州纳学习都倾向于过分近似所要学习的数掘样本 留展法 h o l d o u t 和交叉验证法是 渺哪0 两种分类器评估方法 衔展浊中 所给定的数据集被随机划分成两个独立的部分 其中记录集中的一部分 作为 j i i 练集 保留剩余的部分用作测试集 通常采用三分之二的数据作为训练数据 其 余的一 分之一用于测试数据集的内容 随机取样是留展法的一种变化 重复利用留展法 世行 m 测准确率估计k 次 最后对这k 次所获得的预测准确率求平均值 以便获得最终 的孙测准确率 虽然这种方法速度快 但由于仅使用2 3 的数据来构造分类器 因此它 没有充分利用所有的数据来进行学习 如果使用所有的数据 那么可能构造出更精确的 分类器 爿 种伟j 釉 模型评估方法是交叉验证法 在k 次交叉验证中 初始数捌集被随机 分为女个巧 不相交的了集5 t s s 每个子集大小基本相同 学习和测试分别进 j a 次 在第 次分类巾 子集s 作为测试集 其他子集合并到一起构成一个大训练数据集 汁 过学j j 获得相 湖q 分类器 如此共进行k 次 整个初始数据集所的分类器的准确率 7 中北大学学位论文 估玑则司用k 次循环l p 所获得的正确分类数之和除以初始数据集的大小来获得 在分 屡交叉验征中 陌所划分的子集层次化以确保每个子集中的各类别分布与初始数据集r l 一 的娄驯分铂基本相同 健f 法交叉验证是k 次迭代交叉验汪的一个特例 设数据集有 个数掘 令足 只保健j 一个数据做为测试 分类的效果一股和数据的特点有关 有的数据噪声大 有的数据分布稀疏 有的属 引u i 关性强 囱 的属性是离散的 有的属性是连续的或者有的是混合的 普遍认为不 泉利 方法能适合卜静种特点的数据 本文主要讨呛连续属4 h 值的数据分类问题 2 2 微粒群算法 e b e l h a r t 和k e n n e d y 通过对h e p p n e r 鸟类模型的研究 认为鸟类寻找栖息地与对一 个特定i t j 题寻找解很类似 并通过修正陔模型 使其具有社会性和智能性 以使微粒能 够降落存最好解处而不降落在其它的解处 提出了微粒群算法 121 微粒群算法的研究背景和现状 微粒叶算法其基本思想是模拟鸟类的群体行为而构建的群体模型 p s o 算法白提出 h 骶受到t 圈际匕相关领域众多学者的关注和研究 目前 其研究现状大致有两个方 面 算法的改进和算法的应用 i 算法的改进 以i e l r e e ds 和e b e r h a r t 提出的p s o 的初始版本为基础 1 9 9 8 年y s h i 与 l i b e rh 刚c f 4 j 首次在进化方程l 中引入了惯性权重 用来改善它的收敛性能 带惯性权 重的p s o 算法被称为标准p s o 算法 虽然p s o 算法与其它进化算法有许多相同之处 但 是很多学揣将进化算法的思想引入p s o 算法中 形成混合微粒群算法 h p s o 用以改 j s u 算法的性能 1 9 9 8 年a n g e l ir i m 4 tj 引入了遗传思想中的选择 杂交机制改进p s o 钾7 曼19 9 9 年p ns u f a n t h a n 4 2 1 提出了基于领域思想的微粒群算法 j k e n n e d y 提出几种 孔取i j 邻或结构h 山于模拟退火算法具有较强的跳出局部最优解的能力 文献将模拟 壁火 翌 想 入到p s o 算法中 将p s o 算法和免疫算法 相结合 改进微粒的多样性 8 中北大学学位论文 1 1f 史f 粳1 i 免 二i 自入局音 最f 7 e 晦n 鸭 算法并不是令局收敛的算法 很多学者纠列收敛性分析对算法进行了很多 的改进研究 卜v a n 1 i o nb e r 9 1 n 提出了具有局部收敛性能的g c p s o g u a r a n t e e d c o 1 v c r g e m ep a r t i c i es w a r mo p t i m i z a t i o n f 4 6 4 6 文献 4 7 g j n 停l e 进化微粒来改善全局搜 索能力 提出了保证全局收敛的随机微粒群算法 p s o 算法与模拟退火相结合 利用 p s 算法的进化公式作为模拟退火新状态产生函数 并通过理论分析汪明了该算法以概 宰川女敛心 崩最优解m i jr ig h t 4 9 1 提出了一种保证种群多样性的微粒群算法等 剥 j 一算法 p 参数的设置也是算法改进的一个方面 c l e r c 提出了收缩因子 5 0 咱自概念 以确 保算浊收敛 为提高p s o 算法对复杂问题全局最优解的探测能力 文献口 引入了一 种 函数扩展技术 能够有效地提高p s o 算法的全局收敛 i 牛i p a s a n g a 等l 5 2 提出了时变加 j 韭表数的 s 算法 这些参数也可以通过模糊系统进行调节 s h i 和e b e r h a r t 提出一个 横 j i 系统来凋节惯性 权重 白适应的变异算法在基本p s o 进化过程中 根据群体适 鹰度 弓差咀及当6 h 最优解的大小来确定当前最优微粒的变异概率 变异操作可增强微粒 群优化算法跳出局部最优解的能力 可避免早熟收敛的问题 2 算法的应用 h o 算法最早应用于人工神经网络的训练问题 不仪应用于演化神经网络的权值 而d 包括网络的结构 p s o 算法演化神经网络最典型的例子是应用p s o 算法分析人的颤 刳 文献f 1 利用p s o 实现了对人工神经网络权值和网络模型结构e j 9 i 化 并将结果应用 于 自然沿言词组 分析方法的设计 同样将p s 0 算法对神经网络进行优化 并利用其 改 1 tj 变 j 器的职能保护机制 已有的研究成果表明p s 0 算法在优化神经网络方面有 7 k 大的潜力 p s o 算法最直接的应用或许是多元函数优化 包括带约束的优化问题 多目标优化 最大最小值问题口1 在函数优化中 如果所讨论的函数受到严重的噪音干扰而呈现非常 1 i 规则的形状 同时所求的不一定是精确的最优值 p s o 算法能达到很好的应用 p s o 辩j 点成功的应用于电力系统 采用二进制和实数混合的p s 0 算法米决定对连续和离散的 j 利 j j 变量的控制策略 在模式分类力词 p s o 算法也有应用 将p s o 算法用于训练模糊前向神经网络进行 模式分类 从而从网络的输出中抽取规则 取的了满意的效果h i wv a nd e rm e r w e 和 9 中北大学学位论文 a i n ir o l i 虮e c l i l t 将微粒群算法应用于数据的聚类 通过与肛均值聚类算法相比 确 更大的潜力 p s o 算法在集成电路改引 系统辨识 状态估计等问题的应用均有报道f 3 6 1 微粒群算法的研究尚处丁初期 算法的应用还比较少 需要拓宽更多的应用领域 算法原理 微粒耕算法作为 利 进化计算 同样沿用进化计算中 群体 和 进化 的概念 同样是依据微粒的个体适应值进行计算 在p s o 算法中 微粒群中的微粒表示问题的 个候选解 是出速度和位置两部分组成的个体 在h 维搜索空间中b 行 该微粒一方 丽 嵝有自我性 即j j i 以根据自我的经验去判断飞行的速度和位置 另一方面同时具有社 会件 j 叮以根掘周围微粒的飞行情况去调整自己的飞行速度和位置 不断的寻找个性和 社会 眺之俐的平衡 发 v 一 x 为微粒i 当前位置 l r v i 为微粒i 的当前速度 进化d 柯中 址录微粒到当前为止的历史最好位置 p l t p p 和所有微粒的全 局最好位置0 段l p p 最初始的p s o 算法的进化力程可描述为 v f 1 v f c 1 p f x f o c p f x o 2 1 21 式表示微粒i 的第j 维的速度变化方程 2 2 式表示位簧变化力程 其中 文 k 筇一 l 为加速常数 通常取值为0 2 u o 1 u o 1 为两个相 互独 硼 j 随机函数 c 川来调节微粒飞向自身方向最好位置方向的步长 c 用来调节 微粒向全局最好位置飞行的步长 为丁改善 21 式的收敛性能 y s h i 与r c e b e r h a r t l 9 9 8 年首次在速度进化方程 卟i i 入惯怛e 权熏 21 成为如下的式子 1 0 中北大学学位论文 v q 1 珊v f c i j p 口 r 一x o c 2 1 j p f 一 f 23 其中 m 称为惯性权重 用来实现全局搜索和局部丌发能力之间的平衡 y s h i 和 l c e h a r 通过试验表明 随代数增加线性减少取值j q 得较好的试验结果 现在 祭术微粒特算法通常足指22 和 23 两式 本文同样如此 抵本微粒群算法的流稃如下 s t e p l 依照仞始化过程 对微粒群算法的随机位置和速度进行初始化 s t e p 2 根据定义的适应值 计算每个微粒的适应值 s t e p 3 对 r 每个微粒 根据微粒的适应值与该微粒历史最好位置的适应值相比较 求微粒的历史最好位置 s t c p 4 陌全局最好位置的适应值与每个微粒的历史最好位置的适应值相比较 求微 粒群的全确最好值 s t e p 5 根据方程进化每个微粒的速度和位置 s t e p 6 判断终止条件是否满足 如果不满足 返回s t e p 2 否则算法结束 22 3 算法参数分析 微粒啊算法体现了信念的社会性和智能性行为 式 23 中 其第一部分为微粒先前 的速度 第j 部分为 认知 部分 考虑微粒自身的经验 表示微粒自身的思考 第三 l 郡分为 社会 部分 表示微粒问的信息共享 每部分都被加权 每部分在e 行中所占 n 勺比例e j d 同 决定了微粒的空间搜索能力 所以在这三部分中的参数的选取对算法的 性能显的很重要 c 反映了微粒飞行过程中所记忆的最好位置对微粒飞行速度的影响 被称为 认知 系数 反映了整个微粒群所记忆的最好位置对微粒飞行速度的影u 向 称为 社会学 习系数 如果选取的值c 相对大 即微粒的认知能力强于社会能力时 将导致微粒在 搜豢区域内较难收敛 反过来 过高的社会能力将导致微粒早熟 所以 对于拧制c 和 c 瞧列算法能有效精确的找到最优解是非常重要的 k c i r e e d y 在 1 1 1 ep m t i c l es w a r m 一文中指出 在算法的执行过程中 微粒晌b l l 中 i b 大学学位论文 仃述度应当受到适当的限制 一方r a ja h 讧 微粒能够飞越局部极值 具有一定的伞局探测 i i l 乃 另 力面又能够使得微粒以 定的速度步长逼近仓局最 u l i 7 弘 p a r a m e t e rs e l e c t i o ni np a n i c l es w a r m o p t i m i z a t i o n j 文中 分析了速度限制和 俐伫f 刊义重对算法性能的影响 并l i 对它们不同的取值做了试验比较 指出算法中的全局 和局硎探索能力的平衡主要通过惯性权重米进行控制 但同时建议t 2j l l 最 人速度限制 o z c a n 与m o h a n 在文r 4 j x 6 0 中分析了p s o 在多维搜索空刚的能力 速度步长与惯性 假重州算法的影啊 文1 一p 认为 惯性权重并不能显著提高算法t i j 性能 当 接近于1 川 实验结果最佳 说明 对算法的有效性司能被算法本身固有的随机性而克服掉 1 2 中北大学学位论文 第三章运用p s o 算法实现分类系统 i 教师和环境提供某概念的一些实例 包括正例和反例 通过归纳推理得出该概念 mr 川殳 瞄进 属于归纳学习 运用遗传算法的学习方法属于归纳学习 学习分为有监督 剌引 督的学习两种 所i 7 1 有峪督的学习 是根据己知的类别学习某科 模式 该模式能 刊术分类n 勺数掘进行预测分类 运用p s o 算法从样例集中挖掘分类模式 需要解决两个方面的问题 是如何表 尔分类器 二是如何评价分类器 这是p s o 算法能否成功运用于分类问题的关键 31 分类空间表示 在p s o 算法 h 微粒代表搜索空间的一个候选解 最优解由微粒的不断进化生成 i 量传学习系统中 规则是由0 和1 组成的定长或不定长的字符串的个体表示的 然而 n 现艾1 i 界的知识学习中 数据柬源既有离散型的 同时有连续型的 t t t i 立l l 说一个人的 i i 或矮 人们通带 的判断是身高处于多少范围内是高 本文主要讨沦这科 连续型属性的 分类问题 根据p s o 算法进化方程可以看出 每个微粒的每维都要与全局最好值进行比 较 所以每个微粒如果与全局最好值具有相同的结构的话 易于实现 对于一个有n 维 输入属性值的分类问题 假设可生成m 条规则 那么就可以考虑采用 一个微粒表示该 条规则的方法 列于浚微粒中的每条规则 输入属性构成了规则的前件 类标表示规则 的结沦 虽然月个属性中的不是每个属性都与结论相关 如果每个微粒选择 个属性中 的某些属性进行进化 那么由于进化方程所限 刺于进化很难实现 所以初始时是由n 个属 p l i i e 右边界值组成 即采用以下的规则形式 矿 l x 1 酣1 a i v x a a i f 工f 1 t f t h e n c k h1 f ml 玉 1 1 1 q 表示属性x 的左右边界值 可以看出 规则由 7 个属性 晌矗右边界的连接组成 这样一个微粒就由m x 2 n 1 维组成 表示埘条规则 每条规 f 7 个输入属一削p i 拘缸右边界和一个输出属性组成 在规则的进化过程中 些属性的 死天性显现出来 在这种方法中 当进化过程中 如果当右边界值大于左边界值时 认 1 3 中北大学学位论文 为酬萌性无关 c f i 当于剥规则进行了泛化 可以看出 生成规则的过程 也是一个属性 选择的j 丑程 当最优规则生成后 由于微粒表示的是规则集 存在冗余规则 则对规则 l 批j 合并 并将无火属性去除 形成最后的规则 32 适应度函数 适麻度函数用于实现刑微粒表示的规则集的优劣评价 因为采用定长的分类规则 所姒 韭化过程中 规模不会发生变化 所以只考虑分类的正确性 为了反映规则分类 数捌i 17 川 率 l u 以从两个疗面米考虑 一是规则覆盖诈例的比例 另 个是能反映规 则覆箍反例的情况 为了得 至 j 9 类的目标 在微粒每次进化时 就要将训练集中的数据 与微粒相比较 统计微粒覆盖正例和反例的情况 由于微粒表示的是多条规则组成的规 则集 所以实质是数掘与微粒中的每个规则进行比较 如果微粒中存在规则的条件与数 拥约输入值满足并且规 i j 的分类与数据的分类情况相一致 则认为分类正确 如果微粒 m 征规 i j 的条件与数据的输入值满足并且规则的分类与数掘的分类情况不一致 则认 为l 幺微粒覆f i i 了一个反例 根据这种思想 定义适应度函数由 i f l f i t 2 两个部分组成 i 1 二2 f 1 规则条f l 与结论都匹配的数据个数 加2 表示规则条件匹配而结论不匹配的数 捌个数 m 何代进化刊 l i t i t 2 赋初始值 0 0 根据适应度函数的定义可求得微粒i 旷j m l i t 2 值 t i t m 2 与记录历史最优位置只的 加l f i t 2 r 比较 如果 f 2 l f i t 且 f i t 2 加2 p p 记录微粒i 的当前值 同理 每个微粒 旧 门 i t 2 p 与全局最优只的 f i t l f i t 2 相比较 修改最的值 3 3 分类系统结构 31 分类系统结构图 黪遗传算法分类系统 j s o 算法实现分类的总体图如图3 i 这个规则分类系统实际上由两个部分组成p o 分类机制与规则评价 剥于微粒 1 4 中北大学学位论文 忏体的评价依赖t u 配规则的解释作用环境后 环境对于信息的反馈 如果规则的 结沦仪汉赴佯例所属的类 那么分类系统是无消息传递的 s t jm u l i s le s p n s e 系 统 阁3 1 分类系统总体图 3 32 泛化方法 g c n e r a l i z a t i o n 和冲突处理 c o n f l i c tr e s l u t i o n 如何对规则进行解释 关键有两个方面 如何进行规则匹配和冲突解决 矗颇 删匹配巾 般用到两种泛化方法 部分匹配 p a r t i a lm a t c h i n g 无关匹配 j d c j d 日 c 1 9 舸j 二 者混合使用 部分越配可能是最早使用的泛化方法 b o o k e r 在他的学位沦文中 针对h 0 0 1 a n d 的 分类系统的问题 提出了部分匹配 他指出 如果群体无一条规则和输入相匹配 那么 就小能给 i a 搜索提供有用的消息 那么算法还原为随机搜索 为了解决这个问题 每 个规则的条件部分与输入比较 记录匹配的位数 相应的每个规则被分配一个匹配分数 琊么何最高分数n q 规则放入到匹配池中 当在规则中设置通配符时 就可以采用无关匹配 在这利l 匹配方法中 当某位的值 为通配符州 则可以不用考虑陔位 可以与输入的任何值匹配 l5 中北大学学位论文 ic o r c o r a n 和is e n 2 7 在文中g a 实现的分类系统中 使用的当 唰 表示该属性 为个关心属性 本章采用这种方法 出于一个微粒表示多个规则 当数据的输入属性的值不仅只满足微粒中一条规则的 条化诈用规则的结论两不相同叫 冲突产生了 解决冲突常用的方法有加权投票法 瞳抒凯孔舰则集一雕门最优规则法等 为了算法简化 本章选择最优规则的方法 根掘规 则的适应度 选择适应度值最高的规则的结论作为数据的分类结果 34 算法实现步骤 j 刈已分类的训练数掘集的分类达到所要求的精度时 或者达到终止代数时 算法 终 h 用微粒群算法实现分类发现机制的基本流程如下 s t e p l 随机产生初始的微粒群 每个微粒由m 2 n 1 个实值组成 表示1 i l 条 规则 每个规则由门个输入属性和一个输出属性组成 s t e p 2 微粒适成度 f i l l f i t 2 赋初值 o 0 s t e p s 求微粒与数据集的匹配情况 修改微粒的适应度 f i t l t i t 2 s t e p 根据 i t l f i t 2 值更新只 只 s t e p 5 根据式 2 2 23 修改微粒的速度和位置 生成新微粒 s t c l 6 判断算法的终止条件是甭满足 如果满足 则执行s t e p 7 否则返回s l e p 2 s t e p 7 刑只表示的棚则集中的冗余规则进行合并操作 测试只中最优规则集的分 类正确率 35 仿真实验 次验数据选用u c 1 6 2 机器学习数据眸提供的i r i s w i n e 和g l a s s 2 三个数据集 运 用保躺法进行算法评估 即每次随机选取其中2 3 的数据作为训练集 其余的1 3 作为 剐试集 川1 于测试分类的证确率 参数c c 分别设为1 8 与18 甜选择从1 0 至0 4 线什减少 群体规模设为1 0 0 每个微粒根据问题的规模设置包含的不同的规则数目 1 6 中北大学学位论文 共统i t o o 次实验的运行结果的平均值 可得以下表3 1 的结果 表3ip s 0 算法分类结果 t a b l e 31r c s u l t so b t a i n e db yp s oa g o r i t h m d a i as e t s f r a i n i n gs e t t e s ts e t 收敛代数 i r l sp l a n t s9 89 6 9 29 9 3 5 5 8 6 w i n e9 96 5 8 6 9 5 7 6 76 4 g l a s s 27 8 6 05 表31 中 因为w in o 勺属性数多于irs 的属性数 所以w i n e 的甲均收敛代数大于 g l a s s 数掘进化非常缓慢 表1 中分类精度是微粒进化到1 0 0 0 0 代的结果 对此 数掘5 ij l l t o 了硼o 代 l0 0 0 0 代和1 5 0 0 0 代的结果可以看出 在1 5 0 0 0 代的时候测试集 一分娄精度足6 27 而在5 0 0 04 m 1 只有5 2 0 4 s 3 6 小结 将隅 j 算法作为优化分类规则的手段 通过对连续属性的左右边界进化学习 得到 比较炯 门效果 蜕明此方法是可行的 但是 在实验过程中 同时发现存在一些问题 分类数据n q 输入属性个数较多时 由于采用的是微粒表示规则集的方法 使得搜索空 州变的非常庞大 进化速度减慢 很难找到优化的分类结果 另外 在进化过程中 如 果微粒中的某个单个规则迅速收敛 使得该微粒具有高的适应度 可能抑制微粒中其它 觇则的进化 而使整个搜索结果陷入了局部收敛 而得不到最优的规则集 所以 如何 j 硼1 陌 算法能更好的提高分类精度是需要进一步研究的问题 1 7 中北大学学位论文 第四章运用多群体p s o 算法生成分类规则 存进化汁算应用于分类系统的两种方法中 p i n 方法是用一个个体表示藜个规则集 每个个体独立进行评价 m i c h i g a n 方法是一 个个体表示 条规则 整个群体之间队作完 成给定的任务 t 1 j 于整个群体之间的互相协作 使得每个个体评价相刈困难 采用将c 一 r q 1 j 题看成c 个两类刚题的思想 利用多群体p s o 算法来实现规则分类 并将结果 1 45i 1 键 果进行了比较 晁示山该方法的有效性 4 1 分类模型 j 义1 分类器 凡 斗h c r 为n 维连续值空间 h c 是对于c c 2 类问题的 炎杯 却i 简化起见 衄2 2 c 剥于任意 月 颅 是h c 中的一个值 疋义2 分类器 r 寸h c r u 为n 维连续值空间 加一 y r y o 1 i 2 一 1 4 m 1 定义1 是埘c 类问题的一个描述 定义2 晓明了可将c 类问题看为c 个两类问题 近过定义2 可以看出 剥 二某个 r h x c 的值为0 或j 即可认为x 数据要么属 一l 衷i 要复 不属于浚类 k i s h o e 等i i 运用g pr 分类系统时将多类问题看成多个两类问题 可以简化问题 色考虑分类叫 只需考虑属于陔类 还是不属于该类 而无需关心其他类的情况 本章 采用将 类问题看作为c 1 个两类问题的方法 来生成所要求的分类器 分类器采用规则的形式 由于是连续属性变量空间分类 所以采用n 个数对 表 jj 圳则的每维特征 这利l 表示方法将分类空间划分成了若干个超矩形空唰 没x r u 如果 v i i i 2 j 则认为 满足规则的条件部分 18 中北大学学位论文 42 具有随机自适应惯性权重的p s o 算法 标准p s o 算法更象微粒的聚类 微粒向当前最好点的方向飞行 导致多样性缺少 五m 随停滞 尤其在进化后期缺乏改进解的能力 针对p s o 算法存在的问题 州p s o t 7 2 迸行了改进 通过剥标准p s o 算法中惯性权重和全局最好值的分析 提出了一种 根据全局最好值的变化而自适应变化的随机惯性权重的方法 41 自适应随机m 的p s o 算法原理 瞰23 式可以看出 影响p s o 算法性能有以下几个因素 历史速度v 及 一1 和b 一一i 取值的大小 下面主要考虑 对算法性能的影响 在方程 23 中 惯性权重 的作用主要表现在两个方面 其一 用来控制历史速 度刺当i i i 速度的影响 其二 用来控制全局搜索和局部开发之mj 的平衡 当 取值较大 川 0 1 1 项的值加大 那么搜索的范围加大 提高了全局搜索i i 0 可增加多样性 而 呶牧小值川一 1 的速度变化范罔减弱 增强局部挖掘最优解的能力 加速收敛 在标准 s o 弹法中 通j 首采用随代数增加线性递减的方式 在这利 取值力法中 存在一螳问 趣c 酋先 如果在运行初期探测到较优点 则希望能迅速收敛于最优点 而 的线性递 减a 戎缓了算法的i 投敛速度 其次 在算法的运行后期 随 的城小 导致令局搜索能力 h 聱 多样性减弱 容易陷入局部最优 为此 采用 0 1 均匀分布的随机惯性权重 7 1 求取代线性递减的方法 使得微粒既能在运行初期有机会获得较小的1 2 值 又能够在 后期有机会得到较大的 值 但是当全局最好值心未发生变化时 希望随机取得的 值 较大 加大搜索力度 但山于均匀分布的随机 在 0 1 之问取值的概率是相同的 职的较小值与较大值的机会是均等的 并不能有更多的机会取得较大的值 如果取得较 小的m 值 则川能陷入局部最优 根据以上对0 9 的分析 均匀分布的随机 取值应该根 抓 是否发 一变化 随机取值的范围 i i 同 分两种情况 当尸 不变时 甜随机取一个 较大的噎 否则甜随机选取的值既可以小 电呵以大 表示如下 1 匈 0 山 a n d q i 屯 e l s e r a n d r 3 其中 j j 7 j 值没置最好小于1 2 1 9 中北大学学位论文 存自适应随机惯性杈重础的p s o 算法中 考虑速度矿的情况 如果出现k 0 那么根据方程 22 x f x 0 一1 微粒未发生变化 陷入停滞 l j f c i 以一正 c 州 一 即少了第