0 引言

不均衡数据集中，按类样本出现概率的大与小定义多数类与少数类。少数类虽出现概率极小但往往又极其重要。如：通信电话中的骚扰电话、被诊患者中的癌症患者、网络用户行为中的攻击行为、卫星图片中的油井图片等。抽样是使不均衡数据集均衡化的常用方法，增加少数类样本以减少类间偏斜的方法称为over_sampling(向上采样)^[1]。文献[2]提出SMOTE(Synthetic Minority Over-sampling TEchnique)算法，在“近距离少数类样本间仍为同类样本”的假设基础上生成人工少数类样本；文献[3]选用遗传算法优化SMOTE参数，以得到适合应用数据集的取样倍数；文献[4]提出Borderline-SMOTE方法，将人工合成样本限于少数类样本的边界处。减少多数类样本以降低类间偏斜的方法称为under_sampling(向下采样)^[5]。最早由Tomek提出的Tomek links方法按距离寻找分属两类的Tomek links对，并删除其中的多数类样本；H. Alhammady和K. Ramamohanarao提出的EPRC(Emerging Patterns for Rare-class Classification)算法提供三个改进步骤来克服EP算法在少数类分类上的不足^[6]。目前，不少研究将两种抽样相结合^[7-8]，以优势互补。

分析上述两类抽样方法，均以改变样本分布为出发点。文献[9]选用了10种分类方法对13个数据集进行分类性能分析，认为数据集的不均衡不仅体现在样本数量的偏差上，类间重叠亦对分类性能产生影响。文献[10]使用人工数据较系统地分析了类间重叠与类不均衡的关联程度，并有望在实际数据集中进一步作关联分析。文献[11]尝试通过K近邻(K-Nearest Neighbor, KNN)方法来寻找类间重叠区域，距离查找法易受到“维灾”效应影响，且当重叠子域较多时，该方法在有效发现各类边界特征时性能较差。

本文在相关文献的研究^[9-12]基础上，从数据集区域密疏分布特性着手，引入最小超球体进行类描述，界定出密集与稀疏域，按概率定义找出类边界的重叠样本，将样本空间划分为密集、重叠与稀疏三个子域。不同于传统分类方式，本文将各子域隔离参与分类建模，分类模型按序组合构成复合分类器。实验结果比较表明，本文设计的复合分类器的分类性能提升较明显，总体较稳定。

1 样本空间密疏域隔离方法设计

类边界区域中，存在与其他类极为相似的样本，该类样本往往会被误分类，在覆盖稀疏小样本的分类学习中尤其明显，类边界会因此类样本而发生偏移，误分更为严重。

当不同类的样本极其相似时，类重叠就会产生。选用概率法定义类重叠：样本x均以大于0的概率落在至少两个类的界定内，则样本x位于重叠域O。即：x, x∈O, ∃p(C_m|x)＞0且p(C_n|x)＞0。

图 1的(a)和(b)分别表示没有重叠和有重叠的情形。重叠造成两类边界模糊，为分类带来困难。若将类的边界控制在样本密集区，并与稀疏区域相隔离，类重叠可大大降低。

本文引入支持向量数据描述(Support Vector Data Descriptiong, SVDD)^[13]算法，通过计算覆盖给定样本的最小超球体给出类界定。

1.1 SVDD算法描述

给定目标类y_m的数据集S={x_i, i=1, 2, …, n}，定义初始超球体的中心a和半径R，寻找最小超球体就是寻找包含尽可能多的样本在内的最小R，该优化问题表达为：

目标函数：$\phi \left({R, {\tau _i}} \right)={R^2} + C\sum\limits_{i=1}^n {{\tau _i}} $

约束条件：‖x_i-a‖²-R²≤τ_i；τ_i≥0

优化目标：求目标函数的最小值

这里的τ_i为误差，C为误差折中常量。对该二次规划问题采用Lagrange方法求解，可得：

$ \begin{gathered} L\left( {R,\boldsymbol{a},\boldsymbol{\tau} ,\boldsymbol{\mu} ,\boldsymbol{\beta} } \right) = {R^2} + C\left( {\sum\limits_{i = 1}^n {{\tau _i}} } \right) - \sum\limits_{i = 1}^n {{\mu _i}*} \\ \left( {{\tau _i} - {{\left\| {{\boldsymbol{x}_i} - \boldsymbol{a}} \right\|}^2} + {R^2}} \right) - \sum\limits_{i = 1}^n {{\beta _i}{\tau _i}} \\ \end{gathered} $

(1)

使用KKT(Karush-Kuhn-Tucker)三等式条件，令式(1)对R、a、τ的偏导数等于零，得到三个式子：$\sum\limits_{i=1}^n {{\mu _i}}=1$, a_i=μ_ix_i, C=μ_i+β_i。式(1)的最小化问题转为求其对偶问题的最大值，进而求得μ_i和R，μ_i非零时对应的样本x_i为目标类y_m的支持向量。判断新样本P是否属目标类y_m，即为计算P到超球体中心a的距离(式(2))是否小于R²：

$ {\left\| {\boldsymbol{P} - \boldsymbol{a}} \right\|^2} = \boldsymbol{P} \bullet \boldsymbol{P} - 2\sum\limits_{i = 1}^n {{\mu _i}{\boldsymbol{x}_i}{p_i}} + \sum\limits_{i,j = 1}^n {{\mu _i}{\mu _j}{\boldsymbol{x}_i}{\boldsymbol{x}_j}} $

(2)

1.2 扩展SVDD以隔离密疏域

隔离样本空间的密疏域，是对数据集中每个样本进行判断，以完成区域归类。需要在SVDD算法基础上加以扩充。对二分类问题，执行SVDD算法将产生两类的边界描述。判断样本P的所属域时，需依次应用各类的界定加以分析。

为便于程序的设计，依据式(2)中关于新样本P的判定规则，引入核函数代替向量内积计算，给出类的判定函数f(X)：

$ \begin{gathered} f\left( \boldsymbol{X} \right) = \operatorname{sgn} \left( {{R^2} - K\left( {\boldsymbol{X},\boldsymbol{X}} \right) + 2\sum\limits_{i = 1}^n {{\mu _i}K\left( {\boldsymbol{X},{\boldsymbol{x}_i}} \right) - } } \right. \\ \left. {\sum\limits_{i,j = 1}^n {{\mu _i}{\mu _j}K\left( {{\boldsymbol{x}_i},{\boldsymbol{x}_j}} \right)} } \right) \\ \end{gathered} $

(3)

显然，f(X)值为+1时，样本X属目标类；值为0时，样本X处于类的边界；值为-1时，样本X为目标类的离群点。判断样本X的具体归属域，需要结合正负类的判断函数加以分析。依据类重叠的定义，样本X同属正负类时，归于重叠域内；均不属任何类时，作为所有类的离群点，归于稀疏域内。该过程表示为：

$ \left\{ \begin{gathered} {f_ + }\left( \boldsymbol{X} \right) \geqslant 0且{f_ - }\left( \boldsymbol{X} \right) \geqslant 0,\;\;\;\;\boldsymbol{X}位于类重叠域 \hfill \\ {f_ + }\left( \boldsymbol{X} \right) = 1且{f_ - }\left( \boldsymbol{X} \right) = - 1,\;\;\boldsymbol{X}位于稀疏域 \hfill \\ 其他情形,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\boldsymbol{X}位于密集域 \hfill \\ \end{gathered} \right. $

该方法极易推广至多分类问题中：当样本X使得两个类或以上的判定函数大于等于0时，即位于相应类的重叠域内；若被所有分类器排外，则被认定为离群点；否则位于密集域内。

2 子域去噪处理方法设计

重叠域内样本，常处类分布的边界，因与他类样本较相似，易导致分类决策出错，应有选择地去除掉对分类无益的样本^[14]。稀疏域样本因距离各类的球体中心较远而被排外，存在对类信息表达极为关键的样本，如：网络攻击中新生攻击方法等，同样也有干扰数据需要去除。

对分类有益的样本应当提取出来参与分类过程，本文选用K邻近算法的样本相似度判断方法，结合不同域的具体去噪要求，设置出判定参数；通过计算样本邻近集，作样本有效性判定，最终提取有效样本集。

KNN方法基于邻近性假设，认为测试样本与邻近训练样本属同类。邻近样本依据样本相似性分析进行搜索。设样本维数为N，类标y∈{+1, -1}，常用向量欧氏距离$dist\left({{\boldsymbol{x}_m}, {\boldsymbol{x}_n}} \right)=\sqrt {\sum\limits_{i=1}^N {{{\left({{x_{mi}}-{x_{ni}}} \right)}^2}} } $作x_m与x_n的相似判断。KNN的分类过程：搜索测试样本x_t的K个最相似样本，组成最近邻域集K(x_t)={(x_a, y_a), (x_b, y_b), …, (x_k, y_k)}，集合内所有样本参与表决，取票数最多的y作为x_t的类标，表示为：

$ y = \operatorname{sgn} \left( {\sum\limits_{\left( {{\boldsymbol{x}_i},{\boldsymbol{y}_i}} \right) \in K\left( {{\boldsymbol{x}_t}} \right)} {{\boldsymbol{y}_i}} } \right) $

(4)

2.1 不同密疏情形的近邻分析

按欧氏距离表示样本的相似度，图 2所示的样本分布中，负类样本A的邻近样本均属正类，可视为噪声数据去除掉，否则易造成过度拟合；负类样本B的邻近样本中，多数为同类样本，可视为类边界数据予以保留。

考虑样本域的密疏程度，如图 3所示的样本域。K近邻产生的两个区域明显不同，稀疏域中，近邻样本间的相似度远远低于密集域的，若简单按图 2分析的情况进行处理，显然不合理。

针对稀疏域，结合抽样率与样本密度反比关系^[15-16]，样本应尽可能多地保留。本文引入相似度参数α(表达稀疏程度)，当样本与近邻域样本相似度均值低于α时，样本得以保留。

2.2 稀疏域去噪处理方法设计

定义相似度参数α及有效性判定参数β_K(K的非负函数)。对给定样本(x_s, y_s)，搜索K个最相似样本，组成K(x_s)集，并存储相似度信息。式(4)求得y值与y_s一致时，样本(x_s, y_s)视为有效数据得以保留；否则，计算K个相似度均值几何平均值(Geometric Mean, G-M)，低于α时，保留样本。不低于α时，再应用条件$abs\left({\sum\limits_{\left({{x_i}, {y_i}} \right) \in K\left({{x_s}} \right)} {{y_i}} } \right) \leqslant {\beta _k}$进行判断，条件成立时，样本保留，否则视为噪声数据丢弃。

2.3 重叠域去噪处理方法设计

依据重叠域的判定条件，重叠域数据较密集，主要处理噪声数据，过程较稀疏域简单。沿用有效性判定参数β_K，判断步骤中除去相似度比较即可。

2.4 分类学习有效样本子集

两域处理后保留下的样本组成新样本子集(记为OP)，样本分布不均衡，总体较为稀疏，选用空间向量方法不易表达类信息。从特征角度出发考虑分类，选用决策树方法对该子集进行学习，获取分类器f_OP(X)。

3 复合分类模型设计流程

基于上文所述，扩展SVDD隔离出样本密疏域，且生成正负类的分类器f₊(X)和f_-(X)；使用相似度参数α及有效性判定参数β_K，清理重叠域与稀疏域的噪声数据，生成有效样本子集，学习产生分类器f_OP(X)。具体流程设计如下所述：

1) 分类器学习过程流程设计。

输入：样本集S={(x₁, y₁), …, (x_i, y_i, ), …}，S=S₊∪S_-

n记为样本数目，N记为样本维数，K为KNN参数K，β_K为有效性判定参数。

定义：O为重叠存储域，P为稀疏存储域，α为相似度参数，dist为样本相似度信息存储。

处理：//SVDD数据分布描述过程

     f₊(X)=SVDD(S₊)

     f_-(X)=SVDD(S_-)

     //重叠域与稀疏域发现过程

     for i=1, 2, …, n

       if(f₊(x_i)≥0 & & f_-(x_i)≥0)

         O.add(x_i, y_i)

       else if(f₊(x_i)=-1 & & f_-(x_i)=-1)

         P.add(x_i, y_i)

     //P中有效样本提取过程，m记为P中样本数

     for j=1, 2, …, m-1

       for k=j+1, 2, …, m

         $dist\left({{\boldsymbol{x}_j}, {\boldsymbol{x}_k}} \right)=\sqrt {\sum\limits_{i=1}^N {{{\left({{x_{ji}}-{x_{ki}}} \right)}^2}} } $

     $\alpha=avg\left({\sum\limits_{j, k} {dist\left({{\boldsymbol{x}_j}, {\boldsymbol{x}_k}} \right)} } \right)$

     for j=1, 2, …, m-1

       计算x_j的邻近集K(x_j)

       $y=\operatorname{sgn} \left({\sum\limits_{\left({{\boldsymbol{x}_j}, {y_j}} \right) \in K\left({{\boldsymbol{x}_j}} \right)} {{y_j}} } \right)$

       if(y==y_j)

         continue;

       else if$\left({\sqrt {\prod\limits_{\left({{\boldsymbol{x}_i}, {y_i}} \right) \in K\left({{\boldsymbol{x}_j}} \right)} {dist\left({{\boldsymbol{x}_j}, {\boldsymbol{x}_i}} \right)} } \geqslant \alpha } \right)$

         continue;

       else if$\left({{abs}\left({\sum\limits_{\left({{\boldsymbol{x}_i}, {y_i}} \right) \in K\left({{X_j}} \right)} {{y_i}} } \right) \leqslant {\beta _k}} \right)$

         continue;

       else P.delete(x_j, y_j)

     //O中有效样本处理过程略

     //O与P合并，样本子集OP训练过程

     f_OP(X)=DecisionTree(OP)

输出：三个分类器f₊(X)、f_-(X)、 f_OP(X)。

2) 测试样本预测过程。

三个分类器组合产生复合分类模型，按序依次使用，被f₊(X)排外的样本，交给f_-(X)，依旧排外时，由f_OP(X)进行分类，可得最终类标。

对测试样本x_t：

if(f₊(x_t)==1)         y_t=1

else if(f_-(x_t)==1)    y_t=-1

else                  y_t=f_OP(x_t)

输出：y_t

4 实验设计及结果分析

实验数据的有效选取与实验方案的有效组织可直观了然地呈现研究内容的实际效果。实验选取了Machine Learning Repository的4个二分类数据集，从KDD Cup99_10%数据集中选出U2R类样本与normal类样本，记为KDD99。各数据集的样本分布见表 1。

4.1 重叠与稀疏域样本信息及去噪信息

选用扩展SVDD对数据集进行区域划分时，SVDD核函数K(u, v)选用径向基函数(Radial Basis Function, RBF)形式exp(-gamma*u-v²), gamma=1/num_attribute, nu取默认值0.5，程序终止允许误差设为0.001。产生的重叠域样本及稀疏域样本信息见表 2所列。

两域样本在去噪处理时，程序参数K=5, β_K=int(k/2)+1, α在程序运行过程中加以确定。去除的噪声信息见表 2，给出了每个数据集的相关域的样本总数及正负样本比例。

在本文实验选用的算法参数条件下，产生了各个数据集的相关域信息：部分数据集不存在重叠域，但所有数据集均有不同程度的稀疏域；同时产生出正负类的分类器f₊(X)和f_-(X)。两域去噪处理后，选用C4.5算法进行分类学习，产生出分类器：f_OP(X)。为后续便于表示，将复合分类器记为CCRD。

4.2 复合分类器的分类性能分析比较

对分类结果，按TP、FN依此统计正类样本的正确分类数和错误分类数；按FP、TN统计负类样本的错误分类数和正确分类数。实验中，所有分类器均采用十折交叉验证方式，统计结果取十次结果的均值。选用F₊与F_-两个性能指标评价分类器对正类与负类的总体分类性能，取值越大，表明分类效果越好。具体公式计算如下所述，P代表某类的分类正确率，R代表某类的分类召回率，F代表相应类的P与R的调和平均值。

P₊=TP/(TP+FP)

P_-=TN/(TN+FN)

R₊=TP/(TP+FN)

R_-=TN/(TN+FP)

F₊=(2*P₊*R₊)/(P₊+R₊)

F_-=(2*P_-*R_-)/(P_-+R_-)

1) 与单个分类算法的性能比较。

本文设计的分类算法是三类算法的扩展与组合，在同一数据集上，依次单个应用三类算法(支持向量机(Support Vector Machine, SVM)、KNN(K=5)、C4.5)和本文算法CCRD。实验分类学习产生的统计结果见表 3。

同一数据集的比较中，CCRD算法的TP值为最大，对正类样本的正确分类数最多；TP与TN存在互约关系，CCRD的TN值虽非最大，但与最大值较为接近。CCRD算法修正了SVM在Haberman_sur上的“正类全部错判”，同时对负类仍有很好的分类效果。从实验结果得出：CCRD算法作为三类算法的扩展与组合，总体分类效果得到了较大提升，分类性能要优于单个算法的性能。

2) 与单个分类算法在SMOTE集下的分类性能比较。

SMOTE算法通过生成少数类样本来降低类间不均衡性，是从改变样本分布角度来研究不均衡问题的。本文所提方法则充分分析了数据集分布子域特点，并依据该特点选用合理算法进行分类学习。与SMOTE相比，是同一问题的不同角度的设计。因此，设计实验比较SMOTE集上的相近算法与本文算法的性能。

在同一数据集上，应用SMOTE(倍数为2)进行预处理，并依次单个应用三类算法(SVM、KNN(K=5)、C4.5)进行分类学习，统计结果见表 4。

SMOTE算法对正类样本进行翻倍扩充，负类样本数保持不变。结合表 3，各数据集上，CCRD算法在TN上均为最大值，正类无法直观作比较，图 4~8使用F₊与F_-两个指标，较为直观地体现了各个数据集上算法间的性能值。

3) 与代价敏感MetaCost算法的分类性能比较。

代价敏感是不均衡样本中用到的另一种方法，本文选用MetaCost算法在原始数据集上进行分类学习。基分类算法依次为SVM、KNN、C4.5，代价矩阵按样本数反比给定。实验结果见表 5。

Breast-cancer集上，MetaCost算法(基于SVM)TP值较CCRD大1，而TN值低44；KDD99集上，MetaCost(基于C4.5)与CCRD的TP值相同，但TN值低25；其他数据集上，CCRD的TP为最大，虽存在部分TN值略低的情形，但相应的TP值提升比例更高。从本实验结果得出，针对给定代价矩阵的MetaCost算法，CCRD的分类性能较优。

将同一数据集的各算法结果按F₊与F_-两个指标进行对比，见图 4~8。SM(S)、SM(K)、SM(C)与MC(S)、MC(K)、MC(C)分别代表基于SVM、KNN、C4.5的SMOTE算法和MetaCost算法。

图 4~8的结果比较中，本文方法CCRD的F₊与F_-在Haberman_sur数据集上(图 5)提升明显；在Breast-cancer(图 4)、Ionoshpere(图 6)、Pima_diabetes(图 7)上，F_-提升较明显，F₊未明显下降。KDD99数据集(图 8)样本量大，TP与TN的提升在F₊与F_-上带来的变化幅度较小。CCRD在与单个算法和MetaCost比较中，F₊与F_-均为最大；与SMOTE算法比较，F₊降低约0.092 5%，F_-相应提升约0.294 2%。实验结果表明：不同算法在不同数据集应用中的性能表现存在差异，CCRD的总体性能较稳定，在提升正类分类性能的同时，未对负类分类造成明显影响。

5 结语

数据集的不均衡对分类算法性能影响较大，其不均衡性不仅体现在样本数量悬殊上，也体现在样本分布的密疏不均与类重叠上。本文从数据样本分布的密疏程度出发，进行样本区域分隔，根据不同域的分布特点，针对性选用不同分类方法进行学习，多个分类模型按序组合成复合分类器。从多组数据集的不同算法性能对比分析中得出，本文所用分类器在给定的评价性能指标中，总体提升明显，且受数据集特性影响较小，总体性能较稳定。

本文所提方法中，扩展SVDD进行区域划分时，实验选择了一种核函数，样本去噪时的近邻集计算是按固定K值进行的，并据此给出定值β_K。方法实现中涉及的相关参数等在今后研究中，尝试以优值选取方式进一步分析给定，以将本文方法推广至多分类问题和大数据集的有效应用中。