针对非平衡多分类问题SVM算法的优化研究与应用

任冷　周维民

摘要：该文针对非平衡数据多分类算法进行研究，传统的分类器在处理非平衡数据多分类时往往直接将二 分 类 问 题 的 算 法 直 接 扩 展 到 多 分 类 问 题 上，忽 视 数 据 之 间 的 关 系 ， 本 文 主 要 基 于 数 据 关 系 对 SVM 算 法 改 进 研 究 ， 提 出 一 种 基 于 空 间 扩 展 的 SVM 算 法 ， 优 化 分 类 器 组 ， 提 高 少 类 样 本 数 据 分 类 精 度。最后通过数据集验证改进后算法的有效性。

关键词：SVM；多分类；数据关系；非平衡样本集；数据挖掘

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）05-0218-03

Abstract： The paper focuses on the issue of unbalanced distribution of data muti-classification algorithm research.The traditional classifier often is directly extended from the two classification algorithm to the multi-classification problems in the treatment of unbalanced data multi-classification， ignoring the relationship between data. So a kind of SVM algorithm based on space extension is put forward based on the data relation，to optimize classifier group， improving the minority sample classification accuracy. At last， specific data is used to demonstrate the effectiveness of the improved algorithm.

Key words： SVM ； multi-classification； data relationship ； unbalanced train sets ； data mining

在互联网技术的推动下，很多行业都变成了“互联网+”的模式，在这种企业概念运营模式下，产生了更多大量的用户数据，它也就推动了数据挖掘技术的快速发展，人们可以利用这种技术来提取对自己有用的信息。但是现实中常常存在分布非平衡的数据，而我们需要的正是少数类样本的数据，所以就需要更精确的分类器。现在非平衡数据的分类问题已经成为数据分类领域的重要研究分支。

在非平衡数据分类问题中，又分为二分类和多分类问题。本文主要是针对多分类问题进行研究的。在这类大问题中最经常用的算法就是支持向量机SVM算法（Support Vector Machine）。

SVM是Vapnik等人提出的通用高效的机器学习方法。最初是为解决二分类问题提出来的，所以是一种典型的二分类算法，在解决小样本二分类问题上有着良好的精度和泛化能力。而对于多分类问题，是以二分类问题为基础，结合分类决策原则，构造分类器，以实现多类分类。而多分类构造方法以一对一方法和一对多方法以及在二者基础上改进得到的有向图无环图方法和二叉树法。经典的一对一方法还存在很多缺点可以改进，而本文主要是利用SVM算法与一对一方法相结合的前提下，提出一种新的SVM多分类算法。这种算法是在SVM的基础上针对一些传统经典的方法提出一个新的角度新的思路进行改进，去解决这个多分类问题，最后利用在数据集上的实验来验证这个新算法的效果，是否在少数类分类的分类效率上有所提高。

1 SMOTE方法

SMOTE是Chawla.N提出的一种过采样方法，它不同于传统的过采样技术，是基于样本简单的复制的。其主要思想是：在一些临近的位置相似的少数类样本中插入新样本，达到改善分类样本不平衡的状况。这种方法对数据样本的预处理有更为明显的效果，由于不是随机的简单复制已有的样本，而是增加不存在的新样本，所以就避免了过度拟合的风险。这种方法所产生的新样本都集中在原始数据所属区域，只是单纯的增加了少类样本的密度，并没有达到向外扩展的要求。

2 SVM算法

支持向量机（Support Vector Machine，SVM）是一类机器学习方法，在统计学学习理论和神经网络技术相结合的基础上，区别于传统方法，将结构风险最小化。SVM算法原理在于找到一个最优超平面，使得边界数据到超平面的垂直距离最大，也就是寻找一个分类面。通过数据集在高维特征空间建立一个线性可分，通过最大化边界距离来区分两类。以上是对于线性可分的情况，而针对线性不可分的问题，SVM通过核函数将低维空间里面的向量转换到高维空间，从而在高维空间中求出最优分类面。

把经典的多分类方法一对一算法与SVM算法相结合构成SVM多分类算法。一对一方法：在K类问题中进行两两组合，使用每两类的训练样本，构建类对间的最优超平面。其中涉及到的决策函数最终都转化为为此规划问题求解，对于这个K类问题，共有K（K-1）/2个不同的决策函数，将K类问题划分为多个两类分类问题进行解决，最终可求得任意类之间的分类界面。归结为一句就是“投票机制”，即多数获胜，每个分类器为它的第一选择类投一票，最终结果就是拥有票数最多的类，就是样本所属的类。

3 算法的改进思想

本文主要是面向非平衡训练样本进行分类器的设计，分类器的设计将通过几个指标并且与几个经典算法进行仿真结果的比较来区分分类器的优劣。

非平衡数据的分类问题不同于平衡数据问题，因为在后者中会更多的注重多数类样本，而忽视少数类样本，很可能会被覆盖掉。所以对于一些算法可能总体分类精度很高，可是少数类分类的精度却不能达到满意的效果。在SVM分类过程中，影响分类准确率的最重要因素是分类界面的选择也就是支持向量的选取。SVM算法是解决二分类问题的经典算法，虽然多分类问题是基于二分类的，但是不能直接套用。考虑到多分类问题应该提出对应的解决方案。

本文中正对非平衡多分类问题提出的算法是将SVM算法与多分类构造方法即一对一方法相结合进行研究改进的。一对一方法存在的明显的缺点有二：一是非平衡问题，解决这个问题就要降低数据分布的不平衡度。那么在数据预处理过程成采用smote算法来解决这个问题。二是多分类问题用SVM算法涉及到多个分类界面的问题，如果直接套用二分类的方法那么会出现数据冗余，分类界面杂乱交错，支持向量分布密集难以达到分类的效果。为解决这个问题，考虑出现这个问题的原因就是缺乏重视数据内部之间的关系，所以本文针对这个角度提出一个新的SVM多分类算法，就是基于数据关系的SVM多分类算法。

本文采用基于数据关系SVM的多分类方法是将SVM分类原理上与数据本身的内在关系相结合，提出将支持向量机（Support Vector Machine， SVM）算法与空间扩展的思想相结合的新的学习算法，称为NSVM算法。NSVM方法在多维欧式空间中通过空间扩展的方法对少类数据进行上釆样，以减少非平衡分布的影响，同时结合按照欧式空间内少类数据样本的边界阈值对多类数据样本进行约减的方法，已达到优化分类器的目的，然后再由SVM 一对一方法训练出分类器，最终得到较为高效的分类器组合。

3.1 改进算法的步骤

5 结束语

本文根据数据之间的空 间 关 系 提 出 了 一种空间扩展的SVM分类算法，通过这种 欧 式 空 间 内 的 空 间 关 系 扩 展 少 类 数 据 的 方 法，解 决 了 少 数 类的数据的分布不平衡的问题，减少了被多类覆盖的风险，增加了少类的分类效率。与传统的方法相比，本文提出的这种新的SVM算法在处 理 少 类 分 类 要 求 要 的 问 题 中 更 有 效 果。本文对此进行了验证，说明了这种新算法的有效性，也为非平衡多分类问题提出了一个新的视角，可以研究应用的到实际的问题中。

参考文献：

[1] 许晓峰，海量数据关键分类挖掘算法.复旦大学硕士论文[D]：上海：计算机科学技术学院，2010.

[2] Maciejewski T， Stefanowski J. Local neighbourhood extension of SMOTE for mining imbalanced data .Computational Intelligence and Data Mining （CIDM）， 2011 IEEE Symposium on Paris，2011.

[3] Knerr U.H.. Pairwise classification and support vector machines[M].MA： MIT Press， 1999， 255-268.

[4] 孙涛，吴海峰.SMOTE算法在不平衡数据中的应用[J].北京生物工程，2012，5（32）：14-16.

[5] 陈中杰，蒋刚.基于SVM一对一多分类算法的二次细分法研究[J].传感器与微系统，2013，32（4）：7-8.

[6] 韩敏，朱新荣.不平衡数据分类的混合算法[J].控制理论与应用，2011，28（10）：1485-1489.

[7] 梁志.基于数据关系的SVM多分类方法研究.山西大学硕士论文[D].山西.计算机与信息学院，2013.

[8]He H.B.， Garcia E.A. Learning from imbalanced data[J]. IEEE Transaction Knowledge and Data Engineering，2009， 21（9）：1263-1284.

[9]Xue Zhenxia， Liu Sanyang， Liu Wanli. Unbalanced squares support vector machines[J]. System Simulation .2009（21）.

[10] Y. Tang， Y. Q. Zhang， N. Chawla， and S. Krasser， "SVMs modeling for highly imbalanced classification，" Systems， Man， and Cybernetics， Part B： Cybernetics， IEEE Transactions on， vol. 39， pp. 281 -288，2009.