基于核方法的虚拟样本构造

刘鹏飞，何良华

(同济大学 电子与信息工程学院，上海 201804)

基于核方法的虚拟样本构造

刘鹏飞，何良华

(同济大学 电子与信息工程学院，上海 201804)

样本不平衡问题已经成为机器学习领域的研究热门。虚拟样本生成方法是一种重要的解决样本不平衡问题的方法，它通过线性生成少数类样本来实现。在以往的大多数研究工作中，虚拟样本的生成是在原始的特征空间中进行的，样本通常处于线性不可分的状态，将会导致生成的虚拟样本丢失几何特性。因此，文章提出了一种基于核方法的虚拟样本构造方法，虚拟样本在线性可分的核空间中生成。

样本不平衡；支持向量机；虚拟样本；核方法

0 引言

对不平衡样本的学习一直是机器学习领域的热点问题。样本不平衡问题的主要难点在于以往的分类算法大多以样本分布平衡为前提，导致了分类结果往往偏向于多数类样本[1]。

为解决样本不平衡条件下的分类问题，人们提出了很多应对方法。其中，构造虚拟样本作为基于数据层面的一种策略已经成为一种主流的处理方法[2]。构造虚拟样本方法通过生成少数类虚拟样本来平衡样本分布，从而减少因样本分布不平衡带来的影响。CHAWLA N V等人提出了Synthetic Minority Oversampling Technique (SMOTE)[3],利用相邻样本的特征相似性，通过对相邻少数类样本进行插值构造的方法生成虚拟样本。SMOTE在很多领域表现出了出色的性能，很多研究者在SMOTE的基础上提出了改进，如HAN H等人提出了Borderline-SMOTE[4]，只选取分界面边界附近的少数类样本进行SMOTE生成。HE H等人提出了Adaptive synthetic sampling approach for imbalanced learning(ADASYN)[5]，根据不同的分布密度对不同区域的少数类样本生成不同数量的虚拟样本。

然而，如SMOTE等以往的工作，对少数类样本的构造都是在原始的低维空间中进行的。构造少数类样本通常使用线性组合其他的少数类样本进行生成，而低维空间中的样本往往处于线性不可分的状态，这可能导致新生成的虚拟样本丢失该类的几何特性。因此，在线性可分的空间中对样本进行线性生成是一种更加适合的选择，一方面线性可分的条件使得分类学习更加容易，另一方面，线性可分空间保证了新生成的样本的几何分布更加契合原始的样本空间。支持向量机(Support Vector Machine，SVM)[6]算法将线性不可分的样本映射到线性可分的更高维空间中进行分类。因此，本文结合SVM，通过在高维线性可分空间中构造虚拟样本，从而提高分类器在样本不平衡条件下的分类性能。

1 SVM算法

本文期望在一个线性可分的空间中构造虚拟样本，而现实生活中大多数数据都是线性不可分的，因此需要将数据从原始空间映射到线性可分空间中。而SVM正是这种算法，通过核方法将原始空间中样本映射到一个高维空间中，在这个高维空间中样本是线性可分的。下面将介绍所涉及到的SVM相关知识。

1.1 SVM基本公式

当样本处于线性可分的情况时，SVM的决策公式如下：

SVM(x)=sign()+b

(1)

w则通过下式得到:

(2)

其中αi是SVM的对偶目标函数中的拉格朗日乘子：

(3)

从式(2)中可以得知，w仅仅由那些αi>0的项组成。这些αi>0的样本xi对应到SVM中被称为支持向量(SupportVector)，它们对SVM分界面的构建起到了决定性的作用。因此对于样本不平衡的分析问题，更多地关注于作为支持向量的样本。

1.2 SVM中的核函数

当样本处于线性不可分的情况时，SVM首先使用核函数将样本映射到一个高维线性可分的空间，然后再利用上述公式进行分类。

核函数与样本特征之间的关系表达式如下：

F=<φ(xi),φ(xj)>F=K(xi,xj)H

(4)

其中φ是映射函数，它将处于原始特征空间H(Hilbert，希尔伯特空间)的样本映射到高维空间F，在高维空间中样本线性可分程度更大。通过φ，一个低维空间中xi被映射到高维空间中的zi=φ(xi)。同时，在映射之后内积的计算复杂度并没有增加，通过核函数的技巧计算仍然可以在低维空间中进行。

将核函数应用到1.1节中，SVM的决策函数将变为：

SVM(x)=sign(F+b)

(5)

α通过对偶目标函数得到：

(6)

从式(6)中可以得知，求解一个SVM模型只需输入样本两两之间的核函数值。这些两两的核函数值可以用矩阵的形式来表示，并且称之为核矩阵。

2 基于核方法的虚拟样本构造

核方法有效地将低维空间中的线性不可分的样本映射到高维空间中，使得样本线性可分程度大大增加。在线性可分的高维空间中构建决策面更加简单，同时对于样本的线性生成也能保持相关的几何特性，因此本文的虚拟样本构造方法是基于这样的核空间。同时SVM算法作为利用核方法的典型代表，本文选取SVM算法对样本进行分类。

2.1 虚拟样本的表示

在SVM映射后的核空间(即高维空间)中的样本通常形式会比较复杂，甚至在常用的高斯核映射后的样本具体特征都不可知(高斯核将样本映射至无穷维度)，所以构建虚拟样本不能基于具体的单独的样本。

从1.1节中的式(6)得知，求解一个SVM模型只需关注样本两两之间的核函数值。所以对于高维空间中具体的单独样本过于复杂的问题，可以把高维空间中具体的虚拟样本替换为该虚拟样本与其他所有样本的核函数值。

通过插入给定两个高维空间中样本的中值来代表一个虚拟样本的生成：

(7)

z*表示由已知高维空间中的样本z1和z2生成的虚拟样本，要知道在高维空间中这些样本都是不可知的，因此本文使用z*与所有其他样本的核函数值(也即高维空间中的内积)来表示虚拟样本：

Kz*,x=

(8)

2.2 虚拟样本的构造

2.1节中已经将虚拟样本的表示转换成了虚拟样本与其他样本之间的核函数值，因此虚拟样本的构造问题也就转换成了如何求解它们的核函数值。

利用内积空间中线性性质，可以将式(8)计算如下：

(9)

(10)

生成一个样本时，核矩阵从N阶矩阵KM1扩展到N+1阶矩阵KM2。

2.3 构造源的选取

插值生成虚拟样本所需要的两个样本称为构造源，生成不同的虚拟样本需要不同的构造源，本节主要讨论对于构造源的选取。

图1 SVM中不同样本分布示意图

图1中为SVM分类后不同类别的样本分布示意，图中有两类样本，中间实线表示SVM分类决策面，实线两旁的虚线代表两类样本的支撑界面。对于单独的一类样本来说，分类后的样本点可以分为三类：第一类介于支撑界面内侧，对应到式(5)中该类样本点的αi=0，这类样本点对于SVM分界面的构建没有任何影响，甚至对该类样本进行增减后都不会影响SVM分界面；第二类处于支撑界面上，其0<αi

对这三类样本点都进行了相应的虚拟样本的构造，得到的结论为：只有选取αi=C的第三类样本作为构造源生成后才会改变SVM分界面。

3 实验结果

本节将从两个实验来验证本文所提出方法的有效性。实验将使用本方法后的分类结果与原始的SVM分类结果进行对比。实验1使用人造数据集作为数据，实验2使用UCI真实数据集。

3.1 人造数据集

为了验证提出方法的有效性，实验将在人造数据集上对比原始SVM分类结果与构造虚拟样本后的分类结果。构造虚拟样本时，样本生成数量为多数类样本与少数类样本数量的差值，构造源选取αi=C的样本，同时，生成方式为随机生成。

实验使用的数据集由两个高斯分布构成，分别代表两类样本的分布，以其中一类为少数类样本，另一类为多数类样本。不同不平衡率的数据集是以少数类为基数，按照比例增加多数类样本形成的。图2为训练样本的分布，图3为不同不平衡率情况下SVM与本文方法的对比。图3横轴表示不平衡率，纵轴表示性能指标，其中f代表F-value指标，g代表G-mean指标，这两个指标都能比较好地考量不平衡条件下地分类性能。

图2 人造数据集样本分布

图3 不同不平衡率下SVM与本文方法对比

从图3中可以看到随着不平衡率的上升，SVM在F-value和G-mean下的性能显著下降，而本文的方法在1～8的不平衡率下性能只有轻微下降，并且高于SVM。

3.2 UCI数据集

本节实验采用UCI中部分数据集作为真实数据集，每个数据集的详细信息如表1所示。Np、Nn分别代表少数类样本和多数类样本的数量，n代表样本的特征数，IR表示数据集的不平衡率。

表1 UCI数据集信息

实验结果见表2和图4。表2中列出了SVM与本文方法的F-value和G-mean值，而图4对比了它们的性能。从图4可以看出，本文方法相比于SVM在F-value和G-mean两个指标下都有明显的提升。

表2 UCI数据集上性能对比

4 结论

本文提出了一种新的在核空间中构造虚拟样本的方法来解决样本不平衡问题。在SVM的理论中分析了构造

图4 UCI数据集上分类结果对比

虚拟样本的原理，同时在试验中对所提出的方法的有效性进行了验证。在具有不同不平衡率的人造数据集以及现实生活中的真实数据集中，基于核方法的虚拟样本构造方法的表现均优于原始的SVM。

[1] BORDES A, ERTEKIN S, WESTON J, et al. Fast kernel classifiers with online and active learning[J]. Journal of Machine Learning Research, 2012, 6(6):1579-1619.

[2] HE H, BAI Y, GARCIA E A, et al. ADASYN: adaptive synthetic sampling approach for imbalanced learning[C]. 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence). IEEE, 2008: 1322-1328. [3] CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2011, 16(1):321-357.

[4] HAN H, WANG W Y, MAO B H. Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning[C].International Conference on Intelligent Computing, Springer Berlin Heidelberg, 2005: 878-887.

[5] HE H, GARCIA E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge & Data Engineering, 2009, 21(9):1263-1284.

[6] VAPNIK V. The nature of statistical learning theory[M]. Springer Science & Business Media, 2013.

Synthetic sample construction based on kernel method

Liu Pengfei，He Lianghua

(College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

Learning from imbalanced data is a popular problem in machine learning. Synthetic over-sampling method is one of important approaches by generating linear synthetic minority class samples. While in most previous works, synthetic samples are generated in original feature space where samples are linear non-separable, which leads to the loss of geometrical relation between samples. Therefore, in this paper, a new oversampling method called kernel-based oversampling method is proposed, samples are generated in kernel space where samples in this space are linear separable.

imbalanced data; support vector machine; synthetic sample; kernel method

TP181

A

10.19358/j.issn.1674- 7720.2017.03.016

刘鹏飞，何良华.基于核方法的虚拟样本构造[J].微型机与应用，2017,36(3)：52-54,58.

2016-10-15)

刘鹏飞(1991-)，男，通信作者，硕士研究生，主要研究方向：认知与智能信息处理。E-mail:1433239@tongji.edu.cn。

何良华(1977-)，男，博士，教授，主要研究方向：认知与智能信息处理。