基于遗传规划的分类算法研究

摘要

分类问题是机器学习领域最为基础的研究方向。所谓分类问题利用通过训练数据集得到的分类器对新的数据样本进行样本归类的问题。其中，二类分类问题是被研究最为广泛的问题，也是分类问题中最为基础和重要的方向。在二类分类问题中，所有的数据样本将被分类器划分到两个不同的类别。传统的机器学习大多是利用统计知识来设计分类器，从而获得较好的分类效果。在本文中，我们将从优化的角度来谈分类问题。遗传规划(Genetic Programming)作为演化算法(Evolutionary Computation)的分支，其树状结构编码方式与基于决策树的分类器有着紧密联系，此外，遗传规划具有演化算法在解决复杂问题的独特优势。本文将从遗传规划着手，从遗传优化的角度设计和演化分类器，从而获得全局最优分类器。本文的主要研究工作与创新之处包括以下几个方面:
　　 1.遗传规划用于分类问题的个体编码和适应度函数设计。在本文中，我们设计了基于统计的遗传决策树来对分类问题的解进行编码。基于统计的遗传决策树的特点在于能够精细刻画分类平面对样本空间划分情形和数据样本在各个子空间的分布状况。除此之外，利用基于统计的遗传决策树优越的显示特性，我们设计了基于信息熵的适应度函数。新颖的设计使得适应度函数的优化不仅具有和分类问题相一致的目标同时还具有较小的时间复杂度。
　　 2.在分类问题中的遗传规划局部搜索算子设计。局部搜索算子在演化算法中扮演重要的角色，它能够帮助个体解在短时间内能够快速靠近一个局部最优解。一般来讲，搜索算子要结合具体问题的特性来进行设计。本文中，根据基于统计的决策树的分类面对样本空间的划分状况来考虑局部搜索算子的设计，我们设计了基于信息熵增的分割算子。新的局部搜索算子将某些样本子空间的重新划分从而提高了此子空间的信息熵，进而提高了整个决策树的分类性能。
　　 3.多目标遗传规划在分类问题中的研究和应用。对于具有样本偏态分布或者代价敏感的分类问题，我们希望能够找到一组最优的鲁棒解，这组鲁棒解集共同构成ROC的凸包集合。在本文中，这组鲁棒解的寻找问题被我们归约为一个类似多目标优化的问题。则，我们的任务就是最大化召回率(True Positive Rate)和最小化假正率(False Positive Rate)。研究如何将演化多目标技术结合遗传规划来搜索最优的Pareto解集，并将这解集作为近似ROC凸包的集合，这也是本文的创新之处。我们将研究包括当前最先进和流行的演化多目标算法NSGA-Ⅱ，SMS-EMOA，MOEA/D和AG-EMOA等结合遗传规划（多目标遗传规划）来获得这组鲁棒解，从而获得更加通用的问题解集。
　　 4.基于凸包的多目标遗传规划在分类问题中的研究和应用。尽管利用多目标遗传规划获得的Pareto解集能够比较好的近似ROC凸包集合，但存在两个问题是:第一，Pareto解集并不是完全等同于ROC凸包;第二，多目标遗传规划的收敛速度问题。在本文中，我们将从ROC凸包本身出发，利用ROC凸包本身的特性（特别是不同于一般多目标优化技术支配关系的特性）设计了基于凸包的多目标遗传规划分类算法，从而提高最终解集的表现和加快多目标遗传规划的收敛速度，即花费更少的评估次数获得更优的结果。主要的创新点有:设计了基于凸包的多目标排序策略和基于面积贡献的种群选择机制。
　　 本文的研究方式是自下而上和循序渐进的。先从基本的遗传规划引入，探讨如何解决数据分类问题，如何编码和解码。此后，从遗传规划的框架中着手，研究如何快速、有效地利用遗传规划解决数据分类问题。接着，在利用遗传规划能够获得性能不错的单个分类器之后，探讨如何获得一个性能良好的分类器集合来鲁棒地解决分类问题，这是我们更深一层的研究内容。在这里，我们引入最常见的演化多目标优化框架来结合遗传规划，尝试解决ROC凸包最优化问题;之后，我们进一步利用了ROC凸包的特性，设计了专门针对凸包优化的多目标遗传规划，从而更加快速、有效解决此问题。在以上所有的问题中，我们都将通过实际的UCI分类数据集来证实算法的有效性和高效性。

目录

声明

摘要

表格

插图

算法

主要符号对照表

第一章 绪论

1．1 遗传规划简介

1．2 数据挖掘及分类问题概述

1．3 遗传规划在分类问题中的研究

1．3．1 如何利用遗传规划解决分类问题

1．3．2 研究现状和难点

1．4 本论文主要研究内容和创新之处

1．5 本论文的组织结构

第二章 针对分类问题的遗传规划适应度函数设计

2．1 分类问题的评判标准

2．1．1 ROC分析及AUC评判

2．1．2 遗传规划算法在评判标准中的难点

2．2 基于信息熵的适应度函数

2．2．1 研究思路

2．2．2 统计遗传规划决策树

2．2．3 适应度函数设计

2．2．4 基于信息熵的遗传规划算法

2．3 实验设计及分析

2．3．1 数据集描述

2．3．2 对比算法及实验配置

2．3．3 实验结果及结论

2．4 本章小结

第三章 针对分类问题的遗传规划局部搜索算子设计

3．1 遗传规划中的局部搜索算子

3．1．1 局部搜索算子概述

3．1．2 模因演算法

3．1．3 局部搜索算子在遗传规划解决分类问题中的难点

3．2 基于熵增的局部搜索算子设计

3．2．1 研究思路

3．2．2 局部搜索算子设计

3．2．3 模因演遗传规划

3．3 实验设计及分析

3．3．1 数据集

3．3．2 对比算法描述及参数配置

3．3．3 实验结果及结论

3．4 本章小结

第四章 针对分类问题的多目标遗传规划

4．1 多目标遗传规划

4．1．1 演化多目标概述

4．1．2 分类问题中的多目标问题

4．1．3 分类问题中的多目标难点

4．2 基于多目标的遗传规划用于分类问题

4．2．1 研究思路

4．2．2 多目标框架嵌入遗传规划

4．2．3 多目标模因演遗传规划

4．3 实验设计及分析

4．3．1 数据集

4．3．2 对比算法描述

4．3．3 交叉验证和实验配置

4．3．4 实验结果及结论

4．4 本章小结

第五章 针对分类问题的基于凸包的多目标遗传规划

5．1 基于凸包的多目标遗传规划

5．1．1 以往多目标框架的误区

5．2 基于凸包的多目标遗传规划

5．2．1 研究思路

5．2．2 基于凸包的多目标遗传规划算法

5．3 实验设计及分析

5．3．1 数据集

5．3．2 对比算法描述

5．3．3 交叉验证与实验配置

5．3．4 实验结果及结论

5．4 本章小结

第六章 总结与展望

6．1 工作总结

6．2 未来展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果