摘 要

支持向量机自上世纪九十年代提出以来，在机器学习和人工智能领域获得广泛关注，并成功运用于文档分类、生物特征识别、语音识别、自然语言处理等许多方面。然而，因其需要求解二次规划，在大样本的环境下，由于训练时间过长，其应用范围受到了一定的限制。近年来，为解决这一问题，人们提出了很多近似的方法，平面型学习机就是其中之一。

平面型学习机采用平面拟合样本方式进行分类器设计，较为著名的如基于广义特征值得最近支持向量机GEPSVM（Proximal Support Vector Machine via Generalized Eigenvalues）、孪生支持向量机TWSVM（Twin Support Vector Machine）等。GEPSVM是一种新的两分类方法，通过求解广义特征值来获得两个彼此不平行的拟合超平面。由于平面的无限扩展性，使得该方法在分类过程中所使用的分类规则产生错分的现象。在此背景下，本文提出一种局部化的分类规则，用以克服平面因无限扩展而产生的错分问题。具体操作如下：（1）按GEPSVM训练分类器，或者两个拟合平面；（2）在拟合平面上求解两个平面凸壳；（3）根据待识样本到两个平面凸壳的距离实现样本归类。在人工数据和国际标准数据上面实验，验证以上方法的有效性。

关键词：支持向量机；广义特征值；局部化；分类；凸壳；

Abstract

Recently, the Generalized eigenvector Machine via Generalized eigenvector Machine (SVM) is a new classification method with similar performance to SVM. By solving Generalized Eigenvalues, two hyperplanes fitting two classes of samples are obtained. The (TWSVM) classifier can be avoided by introducing techniques recently used by support vector machines. In this way, we develop a simpler non-parallel plane proximal classifier and accelerate its training by reducing the significant computational burden of TWSVM. The formula of the non-parallel plane proximal classifier for binary data classification is equivalent to two identical mean square error optimization problems which lead to the solution of two small linear equations in the input space. The calculation shows that the Matlab implementation of the non-parallel plane near-end classifier can be trained with data sets of 3 million points, 10 of which are less than 3 seconds. The synthesis and the calculation results of several reference sets show the advantages of the proposed classifier in computing time and test accuracy. In this paper, the test samples are classified into the nearest hyperplane class. However, this rule can lead to poor classification results in some cases. In this regard, based on GEPSVM, the category of samples is determined by looking for a local convex region containing the projection of all training samples on the hyperplane. This local method not only has better classification performance than GEPSVM, but also derives a new simple and easy nucleation algorithm for convex hull on hyperplane. Finally, the validation is obtained on the manual and UCI data sets.

Key words: Closest to support vector machine; Generalized eigenvalue problem; Convex hull. Localization; classification

目 录

1 绪论………………………………………………………………………………………5

1.1研究意义………………………………………………………………5

1.2国内外研究进展…………………………………………………………………………5

本文主要内容…………………………………………………5

2 SVM简介………………………………………………………………………………6

2.1 支持向量机SVM……………………………………………………………………6

2.2 GEPSVM基本原理…………………………………………………6

2.3 GEPSVM数学模型…………………………………………………………………………7

3 局部化的GEPSVM………………………………………………………………………………8

3.1 基于GEPSVM的二分类……………………………………………………………………8

3.2 GEPSVM的不足…………………………………………………9

3.3局部化的LGEPSVM (Localized GEPSVM)………………………………………………………10

3.3.1 最小凸壳顶点集的计算………………………………………………………11

3.3.2 测试点在凸壳内外的判断准则算………………………………………………………12

3.3.2.1 凸壳顶点不共线的情况………………………………………………………13

3.3.2.2 凸壳顶点共线的情况………………………………………………………13

3.4测试点到凸壳的距离计算方法……………………………………………………………………13

4 实验结果……………………………………………………………………………………15

4.1 凸壳算法……………………………..................………………………………………15

4.2 分类能力测试…………………………............…………………………………………16

4.2.1 线性核…………………….............…………………………………16

4.2.2 高斯核……………………............…………………………………16

4.3 测试时间比较……………………………………………………………………17

5结论…………………….………………………………………………………………18

6致谢………………………….……………………………………………………………20

7参考文献…………………………..………………………………………………………21

第一章 绪论

1.1 研究意义

对于平面型学习机而言， 采用全局的分类规划，由于采用了平面拟合样本，所导出的分类平面在交叉处容易造成错分现象。为解决这一局限，本文提出一种局部化的分类方法，主要通过凸壳来进行设计，并将该方法应用到多分类任务中，与其他方法相比，该分类方法可以有效解决XOR问题，并对同类的其他诸多算法问题，都有着借鉴价值。

1.2国内外研究进展

平面分类器来自最接近的支持向量机（SVM近端，PSVM）以及其流行的版本 - PSVM经由广义特征值最接近向量机（GEPSVM）。PSVM首先诞生于2001年的SIGKDD，知识发现与数据挖掘专委会。由Fung和Mangasarian提出。其可以拟合两种类型的样品，再分别通过2个超平面彼此平行，求解二次规划，并获得最优的分类面。在SVM优化问题的不等式约束和1-范数度量误差由等式约束替换时，问题可以通过线性方程来解决（时间复杂度为O（N ³）），将问题归于线性方程的求解，并且SVM的时间复杂度是O（n³）。 (n为样本的数量）。

而从06到07年,在人工智能和机器学习两个领域的顶级期刊TPAMI上，两篇关于MATLAB向量机算法的文章被相继发表（《广义特征值支持向量机》、《孪生支持向量机》两文），这一事件意味着SVM的算法思想的改变，从平行平面，变为非平行平面，而基于非平行平面的SVM算法，已然成为了近年来该领域的热门话题。