数学规划在数据挖掘和机器学习中的应用

摘要

本文从机器学习领域中的两类分类问题出发，对于线性可分和线性不可分的情况分别给出了直观的几何解释，并根据几何解释和数学规划中的对偶理论，给出了线性分类器的数学规划表述。对于线性可分离情况，求两个样本集合的最大间隔等价于求包含各自数据点的凸包的最小距离，并借助简约凸包的概念，将这一结论推广到线性不可分离的情况。借助“最大间隔分类器“的理念，引入了“支持向量机”的概念，并在下文中对支持向量机以及它和数学规划之间的关系进行了较详细的阐述。 支持向量机(Support Vector Machine，简称SVM)是在九十年代初期由Vapnik及其合作者引入到机器学习领域中来的，之后受到了广泛地关注，在数据分类、回归、奇异点分析、聚类问题、主成分分析等方面得到了应用，在近几年得到了广泛地发展，现已成为机器学习和数据挖掘领域的标准工具。支持向量机是机器学习领域中若干标准技术的集大成者。它集成了最大超平面、Mercer核、凸二次规划、稀疏解和松弛变量等多项技术，在若干挑战性的应用中，获得了目前为止最好的性能。它在泛化性能和误差估计等方面得到了统计学习理论强有力地支持，这是先前的传统统计方法和人工神经网络等所不可企及的。在介绍了SVM的同时渗透着核方法的理念，并突出强调核方法在SVM中的奠基性作用。核方法的引入，将SVM的理念拓展到非线性分类器的领域当中，即只需通过一次映射，将样本空间映射到一个特征空间，使得在特征空间中可以将问题视为一个新的寻求线性分类器的过程，而映射是通过选择合适的核函数来实现。接下来，做为两类分类问题的简单扩展，较为简单地介绍了一下用SVM解决多类分类问题的方法和思路。 阐述了数学规划和最优化理论在数据挖掘和机器学习中的两个经典问题中的应用：特征选取和聚类。文中把特征选取和聚类都表述成了一个数学规划问题，以便借助最优化领域中的成熟的算法使这两个问题得以较好地解决(目前在线性规划和二次规划中都有很好的算法)。对于前者，将特征选取和分类两个任务同时进行，得到的分类器很好地兼顾了特征选取，使得分类器有较好的泛化能力。将其表述成一个数学规划问题，但是在未经处理的时候，该非线性问题最多只能转化一个非线性整数规划问题，这在实际中是难以处理的，通过一些近似或者精确地转化步骤，最终可以得到一个近似最优解，且最终问题是线性规划问题。目前，线性规划以其成熟的理论体系和算法(单纯形法和内点法)备受青睐，它求解准确，算法稳健，在大规模问题上表现出了良好的可扩展性(Scalability)，近些年也涌现出了很多性能优异的线性规划求解软件。该章最后，通过修改前述两类分类问题的支持向量机中的相关度量，将问题转化为求解两个线性规划问题，并通过初步的理论分析，可以看出在规模较大的问题上，这两个线性规划问题得到最优解可以为原问题提供良好的近似解，从实际工程应用的角度来看，这也是一种较好的思路。最后，给出了总结和一点展望。

目录

文摘

第一章引言

第二章最优化理论

2.1数学规划问题的表述

2.2约束最优化问题的最优性条件

2.3最优化问题的对偶理论

第三章支持向量机的数学规划表示

3.1线性分类

3.1.1线性可分离情况

3.1.2线性不可分离情况

3.2非线性分类器及其核函数

3.3多类分类问题

第四章数学规划在数学挖掘问题中的一些应用

4.1特征选取问题

4.2聚类问题

4.3在L1和L∞范数下的两类分类问题

4.3.1 L1范数

4.3.2 L∞范数

第五章总结和说明

附录

参考文献

致谢