0 引言

不平衡数据集通常指类别间数量相差较大的数据集，称具有少量样本的那些类为小类，而具有大量样本的那些类为大类，传统分类方法追求的是整体识别率，而对小类的识别率一般较低。目前，对于不平衡数据集的分类问题的研究主要分为两大类：一类是改变训练集样本分布，降低不平衡程度；另一类是适当修改现有算法，使之适应不平衡分类问题。

降低不平衡度的方法包括训练集重采样方法和训练集划分方法。SMOTE(Synthetic Minority Over-sampling Technique)算法^[1]是一种简单有效的上采样方法，首先为每个小类样本随机选出几个邻近样本，并在该样本与这些邻近样本的连线上随机取点，生成无重复的新的小类样本。Japkowicz等^[2]的实验研究了不平衡数据对经典算法的影响，包括决策树C4.5、BP(Back Propagation)神经网络和支持向量机(Support Vector Machine, SVM)等，由于支持向量机对分类性能影响较大的是少数的支持向量，因此该方法对数据不平衡度相对不敏感。Chen等^[3]通过修剪大类的支持向量，使支持向量个数平衡，提高稀有类的识别率。Chan等^[4]将大类样本按照合理的类别样本分布比例随机地划分成一系列不相交子集，并分别与小类样本融合，组成一系列平衡的分类子问题，训练成子分类器，最后通过元学习将这些子分类器集成组合分类器。Lu等^[5-6]采用最小最大模块化SVM模型，提出了“部分对部分”任务分解策略，控制每个子问题的规模和平衡度，并根据先验知识和训练集的样本分布，制定有效的分解规则。SMOTEBoost(Synthetic Minority Over-sampling Technique and Boosting)算法^[7]的每次迭代使用SMOTE生成新的样本，不再使用AdaBoost(Adaptive Boosting)集成算法中的权值调整规则，使Boosting算法更专注于小类样本中的难分样本。这些方法虽然能有效地提升小类的识别率，但同时也忽略了很多潜在有用的大类样本信息，造成大类识别率降低。

算法自适应方法包括分类器集成^[8]和代价敏感学习^[9]等。Zhou等^[10]提出了代价敏感神经网络与分类器集成相结合的方法，实验表明，分类器集成对二分类不平衡问题和多分类不平衡问题同样有效。文献[11]提出了AdaBoost.MLR算法解决多类别分类问题，对识别率较低的类别给予较高的错分代价，提高“难分”类别的识别精度，但提升幅度有限。AdaCost^[12]算法在AdaBoost算法^[13]的权值更新规则中引入错分代价因子，提高了小类样本的查全率和查准率。这些方法在模型训练过程中引入了错分代价因子，强迫分类器“关注”错分代价较高的小类样本，能在确保大类样本识别率的前提下，提升小类样本的识别率，但由于类别不平衡性和模型自身的原因，对小类识别率的提升是有限的。

多分类SVM算法^[14]采用一对一、一对其余的方法将二分类SVM扩展到多类别分类问题中，在不平衡数据分类中表现出很好的分类性能。文献[15]采用主动学习方法构造平衡的训练集，并提出了一种基于SVM的主动学习样本选择策略，实验表明，主动学习方法能用较少的样本获得较高的分类性能，但是主动学习需要迭代多次选择最有价值的样本，进行多次模型训练，而SVM的非线性模型优化过程对计算和存储要求太高。AdaC2.M1算法^[16]针对多类别不平衡分类问题，提出了基于代价敏感的AdaBoost集成学习方法，采用遗传算法搜索各个类别的错分代价, 实验表明代价敏感方法很难较好地适用于多类别不平衡分类问题。

研究分析表明，单一地使用重采样方法改变训练集样本分布，虽然能提升小类样本的识别率，但也会大幅度降低大类样本的识别率；单一地使用代价敏感方法虽然保证了大类样本识别率不会降低，但对小类样本的识别率提升是有限的，因此，本文采用主动学习方法，选择最有潜在价值的样本，充分利用稀有的小类样本，降低数据集的不平衡性，并结合代价敏感方法，在多分类AdaBoost算法弱分类器的迭代训练中，对小类样本给予较高的错分代价，对大类样本给予较低的错分代价，动态调整样本权值更新速度，实现主动学习方法、代价敏感方法和多分类AdaBoost方法的融合，在保证大类样本识别率不会降低的前提下，大幅度提高小类样本的识别率。

1 传统多分类AdaBoost算法

AdaBoost算法是目前应用最广泛的机器学习方法之一，基本思想是将若干个弱分类器按照某种规则组合起来，集成为一个分类能力很强的强分类器，最初应用于二分类问题，多类别分类问题是二分类问题的扩展。假设训练样本集X={(x₁, y₁), (x₂, y₂), …, (x_m, y_m)}，其中y_i∈{1, 2, …, K}。对于样本x_i，若l=y_i，则Y_i(l)=1, 否则Y_i(l)=－1。集成学习算法通常指通过某种方式得到T个弱分类器h_t(x):X×Y→R，弱分类器权重α_t，然后进行组合得到强分类器，即

$ f(x) = \sum\limits_{t = 1}^T {{\alpha _t}{h_t}(x)} $

(1)

多分类AdaBoost算法如下。

输入：训练样本集X={(x₁, Y₁), …, (x_m, Y_m)}，样本权重D，弱分类器h(x):X×Y→R，迭代次数T。

初始化：D₁(i, l)=1/(mK)，其中i=1, 2, …, m，l=1, 2, …, K。

For t=1, 2, …, T：

1) 根据样本分布D_t，训练弱分类器h_t(x):X×Y→R；

2) 计算弱分类器权重α_t；

3) 更新权重$ {D_{t + 1}}(i, l) = [{D_t}(i, l){\rm{exp}}(-{\alpha _t}{Y_i}(l){h_t}({x_i}, l))]/{Z_t} $，其中$ {Z_t} = \sum\limits_{i, l} {{D_t}(i, l){\rm{exp}}(-{\alpha _t}{Y_i}(l){h_t}({x_i}, l))} $；

输出：强分类器$ f(x, l) = {\rm{sign}}(\sum\limits_{t = 1}^T {{\alpha _t}{h_t}(x, l)} ) $。

AdaBoost算法中T个不同的弱分类器是通过改变数据分布来实现的，样本权重更新是根据弱分类器对样本的分类情况来确定的，具体来说，如果弱分类器对某个样本的某个标签分类正确，则对应的权重减少，如果分类错误，则对应权重增加，权重减少与增加的速度只与弱分类器有关，每次权重改变的速度是一样的。

2 主动学习不平衡多分类方法

在传统的主动学习任务中，往往选择对分类器最有价值的样本加入训练集参与训练，以更新分类器，但在不平衡多分类问题中，如果仍采用传统的样本选择方法，可能会导致训练集中大类的样本一直更新，而小类的样本一直得不到更新，即分类器的更新存在不平衡性。针对这个问题，本文提出一种新的基于不确定性动态间隔的样本选择策略，从原始训练集中挑选那些更有意义的样本，选择数量最小但信息量最大的子集作为最终训练集，降低类别之间数据的不平衡性。

2.1 主动学习多分类AdaBoost算法

设有标注样本集为X={(x₁, y₁), (x₂, y₂), …, (x_m, y_m)}，首先抽取部分最有价值的样本作为初始训练集，且类别之间样本均衡。设L^k、U^k分别为第k次学习时的训练集和非训练集，满足X=L^k∪U^k。用多分类AdaBoost算法对L^k样本集进行训练，得到强分类器，并对样本集U^k进行预测，按照某种样本选择策略选择最有价值的样本加入到L^k+1中，重复上述过程直到满足停止条件。

2.1.1 样本选择策略

本文采用基于Margin策略的不确定性来选择待标注的样本，如式(2) 所示：

${x^ * } = \mathop {\arg \min }\limits_x ({\beta _x}(f(x, {l_1}) - f(x, {l_2})))$

(2)

其中：l₁和l₂分别是最具有最大和第二大值的置信度输出值，即当前分类模型最确定的两个类别，二者的差值越小说明模型对样本的不确定性越大，则对样本进行标注获得的信息量越多；β_x为数据平衡控制因子，目的是保证类别之间的数据平衡性。

2.1.2 基于主动学习的训练集选择方法

输入：有标注样本集X={(x₁, y₁), (x₂, y₂), …, (x_m, y_m)}，其中y_i∈{1, 2, …, K}，初始训练集L¹，非训练集U¹=X－L¹。

For k=1, 2, …, iter

1) 在训练集L^k上训练多分类AdaBoost分类器f；

2) 统计训练集L^k中各类别包含样本个数，记包含样本数最少的类别为c₁，包含样本数最大的类别为c₂；

3) 用分类器f对非训练集U^k中样本预测，如果分类模型满足停止条件，循环终止；

4) 如果c₂/c₁>thresh，且非训练集U^k中样本x对应的类别为c₁，则令β_x=ε；否则β_x=1；对每个样本计算β_x(f(x, l₁)－f(x, l₂))，l₁和l₂分别是最具有最大和第二大值的置信度输出值，选择最小的N个样本，记为S；

5) 更新L^k+1=L^k∪S，U^k+1=U^k\S;

End

输出：训练集L。

2.2 基于代价敏感的不平衡多分类AdaBoost算法

分类算法总是希望平均错分代价最小，即希望式(3) 最小：

$ {\varepsilon _c} = \sum\limits_{i = 1}^m {(\sum\limits_{l = 1}^K {cost(i, l)\delta (H({x_i}) = l)} )} $

(3)

对于δ(π)函数，当π为真时，δ(π)为1；否则为0。在多分类AdaBoost算法中引入动态代价调整函数，可以得到代价敏感多分类AdaBoost算法。

2.2.1 改进算法流程

输入：训练样本集L={(x₁, y₁), (x₂, y₂), …, (x_n, y_n)}，样本权重D，代价调整函数cost，弱分类器h(x):X×Y→R，迭代次数T，错分代价因子c。

初始化：D₁(i, l)=1/(nK)，cost₁(i, l)=1，其中i=1, 2, …, n，l=1, 2, …, K；

For t=1, 2, …, T

1) 根据样本分布D_t，训练弱分类器h_t(x):X×Y→R；

2) 计算权值调整函数cost_t：若训练集L为平衡数据集，则对样本x_i，类别l，令cost_t(i, l)=1；若训练集L为不平衡数据集，对样本x_i，类别l，若x_i为小类样本，且l=y_i，则令cost_t(i, l)=c>1，否则cost_t(i, l)=1；

3) 计算弱分类器权重α_t；

4) 对于样本x_i，若l=y_i，则Y_i(l)=1, 否则Y_i(l)=－1；

5) 更新权重：$ {D_{t + 1}}(i, l) = [{D_t}(i, l){\rm{exp}}(-{\alpha _t}\ {cost_t}(i, l){Y_i}(l){h_t}({x_i}, l))]/{Z_t} $，其中$ {Z_t} = \sum\limits_{i, l} {{D_t}(i, l){\rm{exp}}(-{\alpha _t} {cost_t}(i, l){Y_i}(l){h_t}({x_i}, l))} $；

End

输出：强分类器$ f(x) = \mathop {\arg \max }\limits_l \{ \sum\limits_{t = 1}^T {{\alpha _t}{h_t}(x, l)} \} $。

2.2.2 如何选择α_t

由于$ {Z_t} = \sum\limits_{i, l} {{D_t}(i, l)\exp (-{\alpha _t}{u_t}({x_i}, l))} \le \frac{{1 + {r_t}}}{2}{{\rm{e}}^{-{\alpha _t}}} + \frac{{1-{r_t}}}{2}{{\rm{e}}^{{\alpha _t}}} $，其中$ {u_t}({x_i}, l) =-\ {cost_t}(i, l){Y_i}(l){h_t}({x_i}, l) $，${r_t} = \sum\limits_{i, l} {{D_t}(i}, l){u_t}({x_i}, l)$。根据文献[13]中α_t的选择方法，可令${\alpha _t} = \frac{1}{2}\ln (\frac{{1 + {r_t}}}{{1 - {r_t}}})$，此时${Z_t} \le \sqrt {1 - r_t^2} \le 1$。所以在选择弱分类器时，可以选择能使得${r_t} = \sum\limits_i {{D_t}(i}, l){u_t}({x_i})$最大的若分离器h_t，随着弱分类器个数的增加，训练误差会逐渐趋向于0。

3 实验与分析 3.1 评价指标

实验采用G-mean和查准率作为性能衡量标准，令n_i表示属于类别C_i的样本总数, cm(i, j)表示类别为C_i的样本被判断为类别C_j的个数, 则类别C_i的查准率可定义为R_i=cm(i, i)/n_i，G-mean定义为$ G-mean = {\left( {\prod\limits_{i = 1}^K {{R_i}} } \right)^{\frac{1}{K}}} $。

3.2 实验数据集

本文实验使用数据包括TTE测量数据集和4个UCI(University of California Irvine)数据集，其中TTE数据集来源于华西医院，34个属性，共有2214个心脏疾病病例，包括感染性心内膜炎(Infective Endocarditis, IE)58例，冠心病(Coronary Artery Disease, CAD)169例，先心病(Congenital Heart Disease, CHD)733例，瓣膜病(Valvular Heart Disease, VHD)1177例，每个病例只患有一种疾病，最大不平衡度为20.3。详细的数据集信息如表 1所示。

3.3 在TTE数据集上的实验结果与分析 3.3.1 基于主动学习的训练集选择

实验过程中，训练集和测试集比例按照6:4划分，然后在训练集上采用基于不确定性动态间隔的样本选择策略选择新的训练集。

初始训练集L¹的选择：在全部训练集上训练多分类AdaBoost分类器f，然后调用分类器f对训练集中全部样本进行预测，对每个样本计算f(x, l₁)－f(x, l₂)，其中l₁和l₂分别是最具有最大和第二大值的置信度输出值，对每个类别选择f(x, l₁)－f(x, l₂)值最小的10个样本，共得到40个样本作为初始训练集；

训练集选择过程：按照2.1.2节的训练集选择方法，结合数据集实际情况，每次迭代选择4个最有价值的样本加入训练集，令ε=0.005，控制训练集平衡度，一定程度上保证每次迭代都能选择到小类样本加入训练集。训练集选择前后及测试集样本个数如表 2所示。

3.3.2 错分代价因子c的调节

本文采用2.2.1节中描述的改进算法，选择每个类别的查准率作为评价指标来验证改进算法对各个类别的性能影响。在对参数c的最优选择实验时，错分代价调整因子c值在[1, 30]区间内以步长1变化，找出较小的最合适的c值范围，然后在小范围内以0.1步长变化，寻找最合适的c值。以下仅列出c=22, 23, 24, 25, 26时的实验结果，具体如表 3所示，可知最可能的c在区间[23, 24]内。

3.3.3 与其他算法的对比实验结果

在对参数c的最优选择实验时，错分代价调整因子c值在[23, 24]区间内以步长0.1变化，寻找最合适的参数c。通过实验可知，当c=23.8时，总体识别率最高可达88.34%，VHD识别率为92.62%，CHD识别率为85.76%，IE识别率为76.85%，CAD识别率为80.14%。

在最优参数下，将本文算法与SMOTEBoost、AdaBoost.MLR、多分类SVM和ML-KNN(Multi-Label K-Nearest Neighbor)^[17]进行比较，每个类别的详细识别率和总体分类识别率如表 4所示。

从表 4可以看出，ML-KNN算法和AdaBoost.MLR算法对IE和CAD的识别率很低，这是因为这两种算法的分类性能跟训练集有关；由于SVM模型只与少数支持向量有关，分类性能较好一些，但对CAD的识别率较低，对IE的识别率仅稍好于随机猜测；SMOTEBoost算法虽然能提升小类样本识别率，但其他类别的样本识别率也会很大幅度地降低。本文算法相较于多分类SVM，心脏病总体识别率提升了5.9%，G-mean指标提升了18.2%，VHD识别率提升了0.8%，IE(小类)识别率提升了12.7%，CAD(小类)识别率提升了79.73%；相较于SMOTEBoost，总体识别率提升了6.11%，G-mean指标提升了0.64%，VHD识别率提升了11.07%，CHD识别率提升了3.69%。

3.4 在UCI数据集上的实验结果与分析

实验过程中，分别对4个UCI数据集按照6:4划分训练集和测试集，首先按照2.1.2节中的样本选择方法，产生新的训练集，然后在新的训练集上采取和3.3.2节类似的步骤，寻找最佳错分代价因子c。对于每个数据集，选择前后训练集的样本个数和最佳参数c值如表 5所示。

只有当各个类别的查准率都很高时G-mean才会高，因此实验采用G-mean指标对本文算法和ML-KNN、多分类SVM、SMOTEBoost、AdaBoost.MLR算法进行对比，各算法的G-mean值如表 6所示。

从表 6可以看出有些数据集的G-mean值为0，这是由于小类样本的查准率为0造成的，这也说明小类样本的分类性能影响算法的整体性能。

本文算法在TTE、abalone和ecoli数据集上取得最高的G-mean值；相较于多分类SVM算法，TTE数据集上的G-mean值提升了18.2%，相较于SMOTEBoost算法，G-mean值提升了0.64%。

4 结语

本文针对多类别不平衡分类中小类样本识别率低问题，采用主动学习思想，选择少量的最有价值的样本作为训练集，并将不平衡分类问题转化为代价敏感分类问题。在多分类AdaBoost算法弱分类器的迭代训练时，对小类样本给予较高的错分代价，在可行的代价选择空间内，寻找能使得分类性能最优的错分代价调整因子，调整样本权重更新速度，对多分类AdaBoost算法进行改进。在心脏病TTE测量数据集上的实验结果表明，该方法对小类样本识别率有较大幅度的提升，还能保证其他类别的识别率不会大幅降低，综合提升了分类器的性能。综合UCI数据集上的实验结果表明，本文算法在TTE、abalone和ecoli数据集上的G-mean值最高，而且训练集只需要少量的有价值的样本，模型训练效率高、速度快、识别率高，性能更优。