摘 要

基于广义特征值的最接近支持向量机(GEPSVM)和多权向量支持向量机(MVSVM)采用L2-范数度量距离，以至于对野值具敏感性。为了缓解此问题，本文提出了基于L1-范数距离的GEPSVM (L1-GEPSVM)和基于L1-范数距离的MVSVM (L1-MVSVM)。为了求解L1-GEPSVM和L1-MVSVM目标问题，提出了一个迭代凸优化方法。尽管L1-MVSVM性能优势较L1-GEPSVM是明显的，但还有提升的空间，这是由于两个原因。第一，该算法将MVSVM差形式转换为商形式，然后建立L1-范数距离模型。一般来说，平衡目标函数中不同项的贡献往往可以提高其泛化性能。第二，仅仅找的一个投影是不足够的。为此我们提出了基于L1-范数距离的多投影MVSVM（L1-DMVSVM）。为了解L1-DMVSVM问题，本文采用投影梯度上升算法。实验显示了其性能优势。

关键词：L1范式；迭代凸优；多平面支持向量机；多权向量投影

Research on Multiplane Classification Algorithms based on L1-norm Distance Metric

ABSTRACT

GEPSVM and MVSVM use the L2- norm distance metric, which suffer from outliers. To alleviate this problem, this paper develops L1-norm distance based GEPSVM (L1-GEPSVM) and L1-norm distance based MVSVM (L1-MVSVM). To solve the objectives of L1-GEPSVM and L1-MVSVM, an iterative convex optimization algorithm is designed. Although L1-MVSVM outperforms than L1-GEPSVM in the terms of classification performance, it has the large space to improve. There are two reasons for this. First, it converts the original difference formulation in the objective into a quotient problem. Generally speaking, balancing the different terms of the objective in a learning model can improve its generalization ability. Second, only a projection is not enough for classification of data. So , we propose L1-norm distance based muti-projection MVSVM (L1-DMVSVM). Experimental result demonstrates the effective of the algorithm.

Key words：L1-norm; iterative convex optimization; multiplane SVM; multi-weight vector projection

目 录

1 绪论 - 1 -

1.1 传统支持向量机SVM - 1 -

1.2 多平面支持向向量机（GEPSVM） - 1 -

1.3 多权向量投影支持向量机（MVSVM） - 2 -

1.4 本文的组织安排 - 3 -

2 基于L1范数距离度量的特征值型多平面分类器 - 4 -

2.1 相关向量机介绍 - 4 -

2.1.1 支持向量机(SVM ) - 4 -

2.1.2 多平面支持向向量机(GEPSVM) - 5 -

2.1.3 多权向量支持向量机(MVSVM) - 6 -

2.2 基于L1范数距离度量的GEPSVM - 7 -

2.2.1 目标函数 - 8 -

2.2.2 基于迭代凸优化的解 - 8 -

2.3 基于L1范数距离度量的拓展型MVSVM - 11 -

2.4 实验数据分析 - 12 -

3 基于L1范数距离度量的多权向量多投影分类器 - 14 -

3.1 算法设计动机 - 14 -

3.2 基于L1-范数距离的L1-DMVSVM - 14 -

3.3 实验结果分析 - 16 -

3.3.1 实验结果 - 16 -

3.3.2 权向量数目对性能的影响分析 - 17 -

3.3.3 学习率参数分析 - 20 -

3.3.4 正则化参数对性能影响分析 - 23 -

4 创新和缺陷问题的讨论 - 26 -

4.1 基于L1范式距离的多投影机的创新 - 26 -

4.2 缺陷及遇到问题讨论 - 26 -

结 束 - 27 -

致 谢 - 28 -

参考文献 - 30 -

1 绪论

1.1 传统支持向量机SVM

支持向量机 (Support Vector Machine，SVM）^[1]是一个有监督性学习模型，通常用来进行模式识别、分类、以及回归分析，是基于模式识别的方法和统计学理论的一种全新的，非常有潜力的分类技术，主要用于模式识别领域。1963年，ATE-T Bell实验室研究小组在Vanpik的领导下，首次提出了支持向量机（SVM）理论方法。这种方法是从样本集中，选择一组样本，对整个样本集的划分可以等同于对这组样本的划分，这组样本子集就被形象地称之为支持向量（SV）。但在当时，SVM在数学上不能明晰地表示，人们对模式识别问题的研究很不完善，因此SVM的研究没有得到进一步的发展与重视。

1971年，Kimeldorf提出了使用线性不等约束重新构造SV的核空间，使一部分线性不可分的问题得到了解决。^[2]

20世纪90年代，一个比较完善的理论体系——统计学习理论（Statistical Learning Theory，SLT）形成了，此时一些新兴的机器学习方法（如神经网络等）的研究遇到了一些重大的困难，比如欠学习与过学习问题、如何确定网络结构的问题、局部极小点问题等，这两方面的因素使得SVM迅速发展和完善，并在很多问题的解决中表现出许多特有优势，而且能够推广应用到函数拟合等其他机器学习问题中，从此迅速发展了起来，目前已经成功地在许多领域里得到了应用。按照求解分类平面数目划分，SVM可分为单平面支持向量机(Single-surface SVM, SSVM)和多平面支持向量机（Multisurface Support Vector Machine, MSVM）。SSVM方法是解一个分类平面分开两类，往往无法较好地求解更复杂的分类问题，如异或问题（Exclusive OR, XOR）^[3]。因此多平面支持向量机是近年发展的一种新型的支持向量机方法。与单平面支持向量机不同，该类算法找多个分类平面，寻找最优拟合平面，这些平面满足每类平面离本类样本尽可能的近，离它类样本尽可能远。理论与实验证明在计算效率和分类性能上，多平面支持向量机一般优于单平面支持向量机

1.2 多平面支持向量机

基于广义特征值的最接近支持向量机(proximal support vector machine via generalized eigenvalues,GEPSVM)^[4]GEPSVM属于多平面支持向量机中的特征值型方法，特征值型方法主要是为了缓解传统支持向量机在大规模分类问题中需要过高的内存及计算代价，同时也避免了传统支持向量机无法可靠地求解如异或等复杂问题。GEPSVM是传统支持向量机的近似方法，考虑两分类问题，GEPSVM求解两个超平面，每个超平面都满足的条件是：离本类样本尽可能近，而离它类样本尽可能远。由于GEPSVM仅需要解特征值问题而非带约束凸规划问题，因此，面对大规模问题，该算法具备计算效率高的优势 (的时间复杂度^[3]，为样本的维度)。GEPSVM是一种两分类的方法，支持向量机是在典型平面平行的约束条件下, 实现最大间隔分类, 需要求解二次规划问题.基于广义特征值的最接近支持向量机，摒弃了SVM 的平行约束最接近支持向量机(proximal SVMs)^[1]大多数均不考虑平行约束, 在距本类样本尽可能近, 距它类样本尽可能远的条件下求解两个原型超平面,其实质是用一个原型超平面去拟合一类样本.由此GEPSVM 的原型超平面可通过广义特征值解析获得, 不需要二次规划, 在计算时间上明显优于SVM ,且分类性能与SVM 相当.然而,GEPSVM 仍存在如下不足:1)仅对两分类问题有效, 无法直接求解多分类问题;因此当面临多类问题时, 常采用一对一或一对多方式构建分类器, 如此不仅繁琐, 而且极易出现类间数据不平衡问题;2)存在正则化因子的选择问题;GEPSVM为避免过拟合, 采用了正则化手段, 从而面临如何选择较为合适的正则化因子的问题.同时正则化因子的选择好坏直接关系到分类性能的优劣;3)求解原型平面的广义特征值问题中所涉及的矩阵一般仅为半正定, 故导致奇异性问题。幸运的是:一方面正则化手段能够克服此问题, 但另一方面使求得的原型超平面可能失去原有的几何意义,即样本到原型超平面距离的含义。通过分析和实验中，已经证明比SVM更好利于减少的时间复杂度问题。^[6]

1.3 多权向量投影支持向量机（MVSVM）

于2010年，Ye等人提出了多权向量投影支持向量机(Multi-Weight Vector Projection Support vector machines, MVSVM)^[7]，不同于SSVM，该类方法为每类寻找一个最优拟合平面，这些平面满足离本类样本尽可能近，而离它类样本尽可能远的约束。该方法不仅保持GEPSVM的优良特性外，还具有其附加的边缘（1）它执行复杂的数据集（2）不是广义特征在GEPSVM问题，MVSVM解决了两个标准特征值问题，以避免奇异矩阵的GEPSVM; （3）它有比SVM和GEPSVM相当或更好的推广能力（4）它是三种算法里最快的。实验中尝试了人工和公共数据集也表明MVSVM的有效性。MVSVM通过求解简单特征值问题，能有效地缓解已有的特征值型多平面分类方法易出现的平面交叉于不同类的样本而导致的错分严重等问题（特别在多分类问题中），并在平衡参数不同的设置下，从理论上讨论了MVSVM的一些等价形式，且分析了不同特征值型多平面方法的时间复杂度。

本文中所涉及的是L2和L1范数，简单理解L2范数，是指向量各元素的平方和然后求平方根，而L1范数是指向量中各个元素绝对值之和。L2范数多平面方法倾向于强调最小化远离本类样本点到平面的L2范数距离,例如GEPSVM度量点到平面的距离用L2范数的平方。自然的，为了获得目标函数的最小值，GEPSVM不得不强调那些偏远于同类的样本的作用。这样说明L2范数易夸大野值的影响。同样的问题也出现在MVSVM中。为了缓解此问题，我们提出基于L1范数距离的GEPSVM和基于L1-范数的MVSVM。L1范数是度量计算本类样本到本类平面的距离的和，从而减少偏离本类样本对性能的影响。

1.4 本文的组织安排

研究内容：