基于遗传规划的多类分类技术研究

论文摘要

分类问题尤其是多类分类问题一直是数据挖掘研究的热点问题。在实际应用中，如图像识别，文本分类等等，需要处理的数据都是海量和多类别的。如何解决多类别的分类问题，是近几年研究的重点之一。本文将新的遗传学习算法——遗传规划(Genetic Programming)用于多类分类问题中，对其算法进行了尝试性地改进。遗传规划是一种新型的搜索寻优方法。它仿效生物界中进化和遗传的过程，遵从“优胜劣汰，适者生存”原则，从一组随机生成的初始可行解开始，通过复制、交叉和变异等遗传操作，逐步迭代而逼近问题的最优解。本文阐述了遗传规划算法的原理和进化计算的基本知识；介绍了相关分类技术；分析了遗传规划的特点；研究了运用遗传规划解决分类问题的方法模型；并针对遗传规划在多类分类问题中的技术局限进行了改进。本文主要从三个方面对基于遗传规划的多类分类技术进行改进。首先在基于静态选择边界模型(Static Range Selection，SRS)的基础上进行改进，建立了两种动态分类模型：基于中心的动态边界选择和基于狭槽的动态边界选择，对这两种模型进行了相应的算法设计。第二，将梯度下降搜索算法引入到遗传规划中。遗传规划整体算法仍然运用全局搜索，只是在确定遗传程序数字终端时运用了梯度下降搜索的方法，不影响遗传规划整体的束搜索和遗传操作。第三，遗传程序在进行遗传操作的过程中，会产生很多冗余。本文提出一种在单个程序进化过程中定期清除冗余的方法。该方法既不影响遗传规划的结构和进化过程，又可以提高精度，加速演变。最后，进行了实验设计，通过五个不同难度的图像数据样本集(Shape，Coin)对以上三方面的改进进行验证。实验结果表明，SRS法在较简单的两类分类问题中效果较好，而基于动态的边界选择模型为解决遗传程序的输出转化为类别标定的分类问题，尤其是较复杂的多类分类问题提供了新的解决方法；梯度下降搜索算法提高了群体的进化速度和学习效率；遗传程序进化过程中定期对终端集进行简化，在一定程度上改善了分类性能。本文在遗传规划技术三个方面的改进不同程度地提高了遗传规划的分类性能，但这仅仅是一个初步的探索，需要进一步研究探讨。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 本文研究思路
• 1.4 论文内容安排
• 2 遗传规划的基本理论
• 2.1 进化计算
• 2.1.1 遗传算法
• 2.1.2 进化规划
• 2.1.3 进化策略
• 2.2 遗传规划
• 2.2.1 遗传规划基本原理
• 2.2.2 遗传规划的特点
• 2.2.3 遗传规划的结构
• 2.2.4 个体的描述方法
• 2.2.5 初始群体的生成
• 2.2.6 遗传规划的适应度评价方法
• 2.2.7 遗传算子及遗传操作
• 2.2.8 终止准则与结果判定
• 3 分类技术研究
• 3.1 分类技术
• 3.2 分类方法
• 3.2.1 KNN方法
• 3.2.2 决策树分类法
• 3.2.3 人工神经网络分类
• 3.2.4 支持向量机分类法
• 3.3 基于遗传规划的分类技术
• 3.3.1 基于遗传规划的两类分类过程
• 3.3.2 基于遗传规划的多类分类技术
• 3.3.3 基于静态边界的遗传规划分类模型
• 4 基于遗传规划的多类分类技术改进
• 4.1 基于动态边界的分类模型
• 4.1.1 基于中心的动态边界选择模型
• 4.1.2 基于狭槽的动态边界选择模型
• 4.2 梯度下降法在遗传规划中的使用
• 4.2.1 梯度下降法的基本思路
• 4.2.2 遗传规划中的梯度下降算法
• 4.3 冗余代码的简化
• 4.3.1 遗传规划算法的搜索空间及存在的问题
• 4.3.2 消除冗余的方法
• 4.3.3 简化过程
• 5 基于遗传规划的多类分类技术实验
• 5.1 数据样本
• 5.1.1 计算机产生的基元图像
• 5.1.2 新西兰硬币
• 5.2 实验的建立
• 5.2.1 图像识别的过程
• 5.2.2 终端集的确定
• 5.2.3 函数集的确定和初始群体的生成
• 5.2.4 适应度函数
• 5.2.5 其它参数的设定
• 5.3 动态边界选择的分类模型实验结果与分析
• 5.3.1 计算机生成图形的实验结果与分析
• 5.3.2 新西兰硬币样本的实验结果与分析
• 5.4 遗传规划中引入梯度下降算法的实验结果与讨论
• 5.5 冗余简化的实验结果与分析
• 5.6 本章小结
• 6 结论与展望
• 6.1 本文的主要工作
• 6.2 对未来工作的展望
• 参考文献
• 在读期间发表的学术论文
• 作者简历
• 致谢
• 附录