一种改进的少数类样本识别方法

董 璇，蔡立军（西北工业大学 理学院，陕西 西安710129）

非均衡数据集的分类问题是模式识别和机器学习的研究热点。所谓非均衡数据集是指数据集合中，某些类的数据样本较多，而其他类数据样本较少[1]。样本较少的为少数类，样本较多的为多数类。非均衡数据集分类问题可应用于风险管理、网络入侵检测、银行预测、医疗诊断等领域。例如，医生疾病诊断中错将癌症病人诊断为正常人，损失会很大。这种情况下少数类样本却是人们更加关注的。针对该特点，传统的分类算法不再适用，有必要寻求好的分类方法使其在类别不均衡条件下，提高对少数类的识别率。

目前，解决非均衡数据集分类问题主要通过两种途径：算法层面方法和数据层面方法。算法层面方法主要是对已有分类算法进行改进或提出新的算法，如李亚军等[2]提出的改进的Adaboost算法与SVM的组合分类器。数据层面的解决办法有欠抽样方法，随机去掉部分多数类样本使不同类别样本数量均衡，此方法缺点是丢失了多数类的一些重要信息，造成分类性能降低。改进的欠抽样方法有托梅克联系对（Tomek Link）[3]方法、压缩最近邻法（CNN）[4]。简单的过抽样方法随机复制少数类样本的缺点是易导致过学习。Chawla等[5]提出了SMOTE（Synthetic Minority Over-sampling Technique）方法，人工合成少数类样本，但是生成样本范围受到极大限制。本文提出了S-SMO-Boost方法，利用Adaboost提升算法，每次迭代不仅仅增大错分样本权值，还从迭代过程中抽取错分少数类样本，并对该部分样本进行过抽样，过抽样过程采用SMOTE的改进方法——空间插值法，增强对错分少数类样本的训练，以训练出一个强分类器，提高分类性能。

1 分类原理

对于含有两个不同类的数据集(多类可化为两类)S={(X1，y1)，(X2，y2)， … ，(Xm，ym)}，每 个 数 据 元 组 Xi(0≤i≤m)用 n 维属性向量 Xi={xi1，xi2，…，xin}表示，yi∈Y={1，0}为Xi的类标号，即数据元组所属类别。对数据集进行分类即将数据集分为训练集和检验集，分类原理如图1所示。

对于两类非均衡类数据集 S=P∪N，|P|=np，|N|=nN，设 nN=λnp，λ 为非均衡率，λ>1且 λ∈Q+。 图 2为一个非均衡数据集样本分布情况。

训练集为数据集中抽取的样本，由于训练集中两类样本数量同样相差极大，训练分类算法得到的分类器分类结果向多数类偏斜，故对测试集进行分类时，少数类样本识别率较低。本文提出S-SMO-Boost方法。

2 S-SMO-Boost方法

Adaboost是一种流行的提升算法，利用样本的权值来确定训练集的抽样分布。 令 S={(Xj，yj)|j=1，2，…，m}表示包含m个训练样本的集合，初始时所有样本权值均为1/m，根据训练样本的抽样分布来抽取样本，得到新的样本集，由该训练集训练一个分类器，对原数据集样本进行分类。每一轮迭代结束时更新训练样本的权值，增加错误分类样本权值，减少正确分类样本权值。使分类器在随后迭代中关注那些很难分类的样本。算法中基分类器Ci的重要性依赖于它的错误率。组合分类器的最终结果通过取每个基分类器预测的加权平均得到。但是，由于少数类样本与多数类样本数量相差较大，即使增大错分少数类样本的权值，抽取的少数类样本仍然很少。利用S-SMO-Boost方法，在每次迭代中，记录错分少数类样本，利用空间插值法（S-SMOTE）在其周围产生相似的少数类样本，加入训练集中，进入下次迭代，训练分类器，有针对性地加强了对错分少数类样本的训练，提高了少数类样本的识别率。

S-SMO-Boost方法具体算法如下：

输入： 训练集 S={(xj，yj)|j=1，2， …，m}， 其中 yj∈(1，0)，k 表示迭代次数。

(1)初始化权值 w={wj=1/m|j=1，2，…，m}。

(2)for i=1 to k do

(3)根据 w，通过对 S进行抽样（有放回），产生训练集 Si。用Si训练基分类器 Ci，用 Ci对原训练集S中所有样本分类。

(5)if εi>0.5， 重 设 样 本 权 值 ，w={wj=1/m|j=1，2，…，m}，返回步骤(4)。

end if

(6)对于 xj，if yj=1，而 Ci(xj)=0，则记录 xj。

(7)对其利用空间插值方法，产生虚拟样本 syn′i∈Pcreat。

(10)将 Pcreat归入训练集 S。

(11)end for

上述算法中，步骤(6)～(7)对迭代过程中错分的少数类利用空间插值法进行过抽样，在其邻域空间内产生类似有效少数类样本；步骤（10）将虚拟样本加入训练集，同样加大了少数类被抽到的概率，加强了对易错分少数类样本的训练，降低了数据集的非均衡程度，有效提高了非均衡数据集的分类性能，其有效性将在实验中得到验证。

3 空间插值方法

SMOTE方法是一种过抽样方法，该方法在少数类p与其同类k（k=5）近邻p′之间的连线上人工合成少数类样 本 pnew=p+random(0，1)×(p′-p)，其 中 random（0，1）是介于0与1之间的随机数。根据需要循环以上过程生成更多新的虚拟样本，避免了过度拟合问题。

其缺点是：(1)没有针对性，对于分类正确的少数类样本，同样产生虚拟样本，增加了分类成本；(2)生成样本仅介于少数类样本之间的连线上，限制了生成范围，不符合真实数据分布情况，有一定局限性。

空间插值法S-SMOTE(Space Synthetic Minority Oversampling Technique)对SMOTE方法中少数类样本的生成范围进行了改进。设数据集中少数类样本集为P={(p1，1)，(p2，1)， … ，(pi，1)}(0≤i≤np)，pi为 P 中 样 本 元组；多数类样本集为 N={(n1，0)，(n2，0)，…，(nj，0)}（0≤j≤nN），1 和 0 分别为少数类和多数类标号。nN=λ np(λ>1且 λ∈Q+)。

空间插值法的基本思想如下：

(1)对少数类样本 pi，利用欧式空间距离公式求其 k（k=5）近邻。

(2)利用该少数类及其k近邻构造超几何体（三维空间中为四面体），在该超几何体内随机插值，产生虚拟少数类样本，相比SMOTE方法，生成样本范围变大。对于存在多数类近邻的少数类，更容易被错分，故在分类过程中贡献较大，因此构造部分边界虚拟少数类样本。图3表示利用空间插值法在超几何体内随机产生虚拟少数类样本。

产生虚拟样本具体步骤：

(1)求少数类样本 pi的 k近邻，设 k1为其 k近邻中多数类样本个数。

(2)若k1=0，则从 k近邻中随机取 4个设为pi1、pi2、pi3、pi4构成一个四面体，如图4(左)所示。据式(1)～式(3)构造四 面体 内部样 本，syn′inew=(syni1，syni2，… ，synin)∈Pcreat

其中，r1，r2，r3∈(0，1)。

(3)若k1=1，则将该多数类样本看作噪声去除，从剩余近邻中选取3个与pi构成超几何体产生虚拟样本sy∈Pcreat。

(4)若 2≤k1≤4，则从其 k近邻中随机选取 3个与 pi构成超几何体，pi为顶点，如图 4（右）所示，sy=pi+r3×(bi-pi)∈Pcreat，集中于pi为顶点等比缩小的几何体内。

(5)若 k1=5，则该少数类被认为是噪声，不再产生虚拟样本。

(6)记录|Pcreat|，循环此过程直至产生所需虚拟样本数量。

步骤(2)中，少数类pi的k近邻均为少数类，构造超几何体 G1(如图3所示)，G1内随机虚拟样本以该少数类样本及其k近邻为近邻，则根据K-NN算法思想，近邻多为少数类的样本属于少数类的概率很大，故可归入少数类样本集 S中。步骤（3）、（4）中，k近邻中存在多数类样本时，当产生的虚拟样本靠近多数类时，根据最近邻思想，则其可能属于多数类，故构造超几何体 G2、G3(如图3所示)，将生成样本范围控制在以pi为顶点的等比缩小的几何体内，使生成样本更靠近少数类样本，提高了生成样本的质量，避免噪声产生。所以空间插值的方法能生成有效的虚拟少数类样本。

4 实验结果及其分析

4.1 数据集

实 验 采 用 Haberma、Pima Indians、Wisconsin-breastcancer、Machine 4个公开数据集，它们均选自 UCI机器学习数据库[6]。4个数据集除Machine外均为两类非均衡数据集，对 Machine数据集选取类标为“3”的一类作为少数类，将其余类别合并为多数类。表1为4个数据集的基本信息。

表1 数据集描述

4.2 实验结果

仿真实验在CPU双核2.80 GHz、内存2 GB的PC机上进行，将S-SMO-Boost方法分别与单独使用S-SMOTE、SMOTE、J48方法进行比较，均以 J48为基分类器，并采用十折交叉验证法。其中，S-SMOTE方法处理数据时，循环其构造样本的过程直至|Pcreat|=nN-nP=(λ-1)nP。 则Pcreat、P与剩余多数类样本集合并为均衡数据集训练分类器。

分类性能评价准则采用几何均值G-mean值与少数类的F-value值：

其中，TP与TN分别表示正确分类的少数类与多数类数量，FP与FN分别表示错分为少数类与多数类的样本数量。G-mean值中 TP/(TP+TN)指少数类精确度，TN/(TN+FP)指多数类精确度，只有两者的值都大时，几何均值才会大，因此几何均值能合理地评价非均衡数据集的整体分类性能。F-value值中 Recall=TP/(TP+FN)与Precision=TP/(TP+FP)分别表示少数类查全率和查准率，两者值都大时F-value值才会大，因此F-value值能正确反映少数类的分类性能。

图5表示分别用四种方法对4个数据集分类时得到的少数类F-value值。同种方法得到的F-value值点用线连起可清晰显示，利用S-SMO-Boost方法得到的F-value值相比其他方法均有一定程度的提高。

表2对不同方法，分别比较了4个数据集的G-mean值，由实验结果可知，直接用J48进行分类得到的值最小，因为数据集严重不均衡。相比SMOTE方法，SSMOTE在少数类邻域空间内插值产生有效虚拟样本，并加强靠近边界少数类样本的训练，故分类性能相对较好。S-SMO-Boost将空间插值法融入提升算法，在迭代过程中利用错分样本产生虚拟样本，增强对错分少数类样本的训练，且增大错分样本的权值，加大迭代中作训练集的概率，并将弱分类器组合成强分类器。由表2知，用S-SMO-Boost方法得到的G-mean值最大，提高了非均衡数据集的整体分类性能。

表2 数据集G-mean值比较

为了解决非均衡数据集中少数类识别率较低的问题，本文提出了S-SMO-Boost方法，利用空间插值方法，产生有效虚拟样本，并将其与提升算法融合，加强对错分少数类样本的训练。经实验验证，该方法提高了少数类识别率和数据集整体分类性能。

[1]WEISS G.Mining with rarity：an unifying framework[J].Sigkdd Explorations，2004，6(7)：7-19.

[2]李亚军，刘晓霞，陈平.改进的AdaBoost算法与SVM的组合分类器[J].计算机工程与应用，2008，44(32)：140-142.

[3]TOMEK I.Two modi-cations of CNN[J].IEEE Transactions on Systems Man and Communications，1976，SMC-6：769-772.

[4]MANNILA，LIU，MOTODA.Adavances in instance selection for instance-based leaning algorithms[J].Data Mining and Knowledge Discovery，2002(6)：153-172.

[5]CHAWLA N，BOWYER K，HALL L，et al.SMOTE：synthetic minority over-sampling echnique[J].Journal of Artificial Intelligence Research，2002(16)：321-357.

[6]BLAKE C，MERZ C.UCI repository of machine learning databases[DB/OL].1998.http：//archive.ics.uci.edu/ml/.