基于G-Mean加权随机森林算法的不平衡数据处理

Unbalanced Data Processing Based on G-Mean Weighted Random Forest Algorithm

摘要: 分类是机器学习领域的一个热点研究内容，不平衡数据导致在分类时产生了很大困难。企业破产预测可以被归结为一个二分类问题，根据企业的一些特征对企业的状态做出预测，可以帮助企业作出更好的决策以减少企业的损失，但在企业破产数据中，破产企业只占很少的一部分，数据存在严重的不平衡。针对企业破产预测中的不平衡数据，本文提出了一种基于G-mean的加权随机森林算法(BSWRF)。对随机森林采集出来的不平衡子训练集，运用自助采样法进行欠采样，将多数类采样到和少数类一致，形成平衡子训练集，将CART决策树作为基分类器，在每个子训练集上进行训练，同时在包外估计样本上测试，根据G-mean为每棵决策树赋予权重，加权投票得到最终的分类器，提高了分类性能。选择台湾企业破产数据集进行实验，在G-mean、Recall和AUC评价指标上，BSWRF的分类效果都优于随机森林和AdaBoost算法。

Abstract: Classification is a hot research content in the field of machine learning. Unbalanced data leads to great difficulties in classification. According to the data of enterprise bankruptcy, it can be concluded that there is only a part of the prediction of enterprise bankruptcy loss, but there is only a small part of the prediction of enterprise bankruptcy loss according to the data of enterprise bankruptcy. For the unbalanced data in the enterprise bankruptcy forecast, this paper proposes a weighted random forest algorithm (BSWRF) based on G-mean. For the unbalanced sub-training set collected from random forest, the self-help sampling method is used for under sampling. Most classes are sampled to be consistent with a few classes to form a balanced sub-training set. The cart decision tree is used as the base classifier to train on each sub training set. At the same time, it is tested on the Out-of-Bags samples. Each decision tree is given weight according to G-mean, and the final classifier is obtained by weighted voting, which improves the classification performance. The bankruptcy data set of Taiwan companies is selected for the experiment. In G-mean and AUC evaluation indexes, the classification effect of BSWRF is better than random forest and AdaBoost algorithm.

1. 引言

当今社会是一个信息数据快速发展的时代，对得到的数据进行分类是很有必要的，随着机器学习的兴起，已经产生了很多分类模型，这些模型可以分为单一模型、集成模型、混合模型等，这些模型在分类问题中有着很好的效果。但是现实生活中得到的数据很多时候都是不平衡数据集 [1]，很多分类算法在处理不平衡数据集时，模型偏向提高整体精度，导致少数类的分类效果会非常差。比如：信用卡欺诈检测 [2] 中信誉不良的客户很少，大部分客户信誉都是好的；企业破产预测中 [3]，破产的企业占的比例是很小的；癌症基因检测时 [4]，检测出来病人有癌症基因的概率可能仅为百万分之一。这些领域，存在着数据不平衡的问题，对于不平衡问题，人们更加关心少数类的分类结果，因此，对不平衡数据集的研究是非常有意义的。

为了在不平衡数据分类中取得较好的分类效果，国内外学者进行了相关研究，主要的方法有采样法和集成学习的方法。采样法主要有欠采样和过采样。欠采样方法除去样本中的部分多数类，使得多数类和少数类的数目接近时，进行学习。过采样方法增加样本中的部分少数类，当两类数目接近时，进行学习。Prusa等人 [5] 运用随机欠采样来处理不平衡数据集，将随机欠采样应用于情绪分类的不平衡数据中，实验表明，随机欠采样技术显著提高了分类性能。Kang [6] 等人将噪声滤波和欠采样技术结合在一起，该方法过滤出原始少数类中异常的实例，然后使用过滤之后的少数类来训练分类器。Chawla [7] 提出一种过采样的方法，通过“合成”少数类来对少数类进行过采样，并进行实验表明将少数类过采样和多数类欠采样相结合的方法在部分数据集上的分类结果更好。Han [8] 等人提出两种少数类过采样的方法，其方法只针对边界附近的少数样本进行过采样，实验结果表明，其方法比随机过采样方法效果更好。

集成学习通过构建多个基学习器，进行适当的组合形成性能好的强分类器。集成学习由于生成方式的不同，可以分为Bagging和Boosting两大类。Bagging的代表算法是随机森林算法 [9]，Boosting的代表算法是AdaBoost算法 [10]。Breiman [9] 提出随机森林算法，并将其应用于分类问题。Wang等人 [11] 将过采样技术结合到Bagging模型中，并将其扩展到求解多分类问题上，提出一种集成模型分类方法SMOTEBAGGING。任才溶 [12] 等人利用K-means算法对原始气象数据聚类，结合欠采样方法构建基于随机森林的预测模型，并将其应用于气象数据。Galar [13] 等人综述了处理不平衡数据集方法的研究现状，并通过实验得出随机欠采样技术和集成方法结合的分类效果很好。在这些方法中主要存在两个方面的问题，在数据处理中运用采样技术，会导致部分有用信息被覆盖掉，在随机森林中，随机抽取的样本以及特征会导致不同的基分类器的分类性能不相同，每个基分类器赋予相同的权重会降低模型的效率，从而影响模型整体的分类性能。

本文针对企业破产预测中的不平衡数据进行研究，将破产预测归结为一个分类问题，根据企业的一些特征来判断企业的状态，本文提出基于G-mean的加权随机森林算法来对企业是否会破产做出分类。首先对随机森林中随机抽取出来的子训练集进行欠采样，使每一个子训练集变成平衡样本集，在每一个平衡样本集上用决策树训练一个基分类器，然后在包外样本上进行测试，得出包外样本上的G-mean，将G-mean通过一个变换，作为每一个基分类器的权重，得到最终的分类模型，这种方法能够降低效果差的基分类器的决策能力，提高投票的公平性，从而提升模型性能。

2. 相关知识

2.1. 自助采样法

给定一个包含n个样本的数据集D，每次从D中抽取一个样本放入 $D^{\prime }$，然后将这个样本再放入D中，重复n次这样的操作，就得到了一个包含 $n$ 个样本的数据集 $D^{\prime }$，因为是有放回的，D中的有一部分样本不会出现在 $D^{\prime }$ 中，可以通过下式计D中的样本不会出现在 $D^{\prime }$ 中的概率：

$\underset{n\to \infty }{\lim }{\left(1-\frac{1}{n}\right)}^n=\frac{1}{\text{e}}\approx 0.368$ (1)

上式表明，通过自助采样，数据集D中约有36.8%的样本不会出现在数据集 $D^{\prime }$ 中，用 $\tilde{D}$ 表示这部分样本，在实际操作中，可以利用 $\tilde{D}$ 来验证模型，这种测试也成为“包外估计”。

2.2. 随机森林

随机森林是Bagging一种代表算法，随机森林以决策树为基分类器来构建模型，给定一个包含n个样本的数据集，通过自助采样法可以得到N个包含n个样本的子训练集，随机森林算法在每一个子训练集上训练出一个基决策树。并且随机森林算法在训练基分类器之前，加入了一个特征随机选择的步骤，假设决策树划分时，针对决策树的每个节点，有f个特征，先从这f个特征中随机选择k个特征作为一个子集，再从这个子集中选择一个最优特征来划分，参数k控制了随机性的引入成度。一般情况，k的推荐值为 $k={\log }_{2}f$。对每一个基决策树的结果进行投票，选择数量最多的结果作为类别预测。最终的投票结果由下式表示：

$H\left(x\right)=\arg \underset{y\in Y}{\max }{\displaystyle {\sum }_{n=1}^{N}I\left(h_n\left(x\right)=y\right)}$ (2)

其中， $h_n\left(x\right)$ 是第n棵决策树的输出， $I(\cdot )$ 是一个示性函数，当决策树分类正确时，输出为1，分类错误时，输出为0。

2.3. AdaBoost

AdaBoost算法是Boosting算法的代表算法，通过改变训练数据的概率分布，在不同的数据上训练出一系列基分类器。下面叙述AdaBoost算法。

输入：训练数据集 $D=\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_N,y_N\right)\right\}$，其中 $x_i\in X\subset R^n$，标记 $y_i\in Y=\left\{-1,+1\right\}$，基分类器。

1) 对训练数据集初始化权重分布： $W_1=\left(w_{11},w_{12},\cdots ,w_{1N}\right),w_{1i}=\frac{1}{N},i=1,2,\cdots ,N$ ；

2) 对 $m=1,2,\cdots ,M$，使用 $W_m$ 对训练数据集进行学习，得到基分类器 $G_m\left(x\right)$ ；

3) 计算每一个 $G_m\left(x\right)$ 在训练集上的分类误差率如下：

$e_m\left(x\right)={\displaystyle \underset{i=1}{\overset{N}{\sum }}P\left(G_m\left(x_i\right)\ne y_i\right)}={\displaystyle \underset{i=1}{\overset{N}{\sum }}w{}_{mi}I\left(G_m\left(x_i\right)\ne y_i\right)}$ (3)

4) 计算 $G_m\left(x\right)$ 系数 ${\alpha }_m$

${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$ (4)

5) 更新训练数据集上面的权重分布：

$W_{m+1}=\left(w_{m+1,1},\cdots ,w_{m+1,i},\cdots ,w_{m+1,N}\right)$ (5)

$w_{m+1,i}=\frac{w_{mi}}{Z{}_m}=\exp \left(-{\alpha }_m{y}_i{G}_m\left(x\right)\right),i=1,2,\cdots ,N$ (6)

其中 $Z_m$ 是规范化因子，可以使 $W_{m+1}$ 变成一个概率分布。 $Z_m$ 表达式如下：

$Z_m={\displaystyle \underset{i=1}{\overset{N}{\sum }}{w}_{mi}\exp \left(-{\alpha }_m{y}_i{G}_m\left(x_i\right)\right)}$ (7)

6) 将基分类器进行线性组合：

$f\left(x\right)={\displaystyle \underset{m=1}{\overset{M}{\sum }}{\alpha }_m{G}_m\left(x\right)}$ (8)

输出：最终分类器 $G\left(x\right)$ ：

$G\left(x\right)=sign\left(f\left(x\right)\right)=sign\left({\displaystyle \underset{m=1}{\overset{M}{\sum }}{\alpha }_m{G}_m\left(x\right)}\right)$ (9)

3. 基于G-Mean加权随机森林算法

基于G-mean加权随机森林算法，首先在数据采样层面，针对训练集中采样出来的N个子训练集，此时的子训练集是不平衡数据集，先进行欠采样，将每个子训练集中的多数类采样到和少数类一致，得到N个平衡子训练集，在每个子训练集上训练一个决策树，并且在包外估计样本上测试每个决策树的性能，计算出包外估计样本上的G-mean，将G-mean做一个变换，作为每个决策树的权重，用来加权投票得到最终的分类器。BSWRF的功能框架如图1所示，BSWRF算法的具体步骤如下：

1) 给定一个原始的不平衡数据集D，将数据集划分为训练集和测试集。

2) 在训练集上进行Bootstrap sampling得到N个子训练集，此时的子训练集都是不平衡数据集，未被采集到的样本会形成包外估计样本，即每个子训练集会对应一个OOB (Out-of-Bag)测试集。

3) 在N个子训练集上进行欠采样来平衡数据集，对多数类样本使用随机不放回采样，将多数类采样到和少数类数目相同。得到N个平衡的子训练集。

4) 在N个平衡子训练集上进行训练，得到N个决策树分类器 $\left\{h_1\left(x\right),h_2\left(x\right),\cdots ,h_N\left(x\right)\right\}$。

5) 将每个决策树在其对应的OOB测试集上进行性能测试，得到每个OOB测试集上的G-mean，G-mean的计算如下：

$G_n=\sqrt{\frac{TP}{TP+FN}\times \frac{TN}{TN+FP}}$ (10)

6) G-mean的大小由TP和TN来共同决定，只有多数类和少数类同时分类准确率高，G-mean才会较大，根据G-mean来为每个决策树赋予不同的权重，为能够同时分出多数类和少数类的决策树分类器赋予较大的权重，权重的大小计算如下：

$w_n=\lg \frac{G_n}{1-G_n}$ (11)

7) 通过加权投票，得到最终的分类器，表示如下：

$\begin{array}{c}H\left(x\right)=\arg \underset{y\in Y}{\max }\left\{{\displaystyle {\sum }_{n=1}^{N}I\left(h_n\left(x\right)=y\right)}\ast w_n\right\}\\ =\arg \underset{y\in Y}{\max }\left\{{\displaystyle {\sum }_{n=1}^{N}I\left(h_n\left(x\right)=y\right)}\ast \lg \frac{G_n}{1-G_n}\right\}\end{array}$ (12)

8) 将最终得到的分类器 $H\left(x\right)$ 用于测试集上去测试分类效果。

Figure 1. Functional block diagram

图1. 功能框架

4. 实验结果与分析

4.1. 数据集

数据集选择台湾企业破产预测的数据集，该数据集是一个不平衡数据集，数据集中多数类样本和少数类样本的不平衡率比例达到了29.995，数据集的信息如表1所示。

Table 1. Sample data set

表1. 样本数据集

4.2. 评价指标

在不平衡数据集的分类中，使用分类准确率这个评价指标没办法有效地评估模型的效果，因为它考虑的是总体的分类情况，并且认为少数类样本和多数类样本的重要程度是一样的，这明显是不符合实际的，在实际中，对于不平衡数据集的分类，人们更关心少数类的分类准确率。因此本文采用AUC值、召回率(Recall)和G-mean来评价模型分类效果。用混淆矩阵来更好的描述这些指标，混淆矩阵如表2所示：

Table 2. Confusion matrix

表2. 混淆矩阵

其中，P表示少数类样本，N表示多数类样本，TP表示将少数类预测为少数类，FN表示少数类预测为多数类，FP表示将多数类预测为少数类，TN表示将多数类预测为多数类。基于混淆矩阵，各评价指标如下：

$\text{TPR}=\frac{TP}{TP+FN},\text{FPR}=\frac{FP}{FP+TN}$ (13)

$\text{G-mean}=\sqrt{\frac{TP}{TP+FN}\times \frac{TN}{TN+FP}}$ (14)

$\text{Recall}=\frac{TP}{TP+FN}$ (15)

G-mean用来表示多数类和少数类精度的几何平均，可以同时反映出少数类和多数类的分类情况。ROC (Receiver Operating Characteristic Curve)曲线是由FPR和TPR为横纵坐标画的曲线，AUC值是ROC曲线下方的面积，在样本不平衡的情况下，AUC依然可以对分类器做出合理的解释，ROC曲线越靠近左上角越好，对应的AUC面积越大越好。Recall值反应少数类中有多少被预测正确，Recall值越大越好。

4.3. 实验结果与分析

首先将数据集中的多数类样本和少数类样本随机打乱之后，取70%作为训练集，30%作为测试集，在训练集上训练分类模型，然后在测试集上验证模型性能。为了验证BSWRF算法的有效性，选取了两种经典的集成分类算法随机森林算法和AdaBoost算法进行对比。在构建模型时，统一使用50棵决策树作为基分类器，计算模型在测试集上的G-mean值、Recall值和AUC值，来比较三种模型的分类效果。

从表3中可以看出本文提出的BSWRF与其他两种算法的对比效果，在对不平衡数据的处理上，性能有了进一步提升。BSWRF算法与随机森林算法相对比，G-mean提升了83.8%，BSWRF算法与AdaBoost算法相比，G-mean提高了61.7%。在AUC评价指标上，BSWRF与另外两种算法的效果比较接近，但还是优于另外两种算法，BSWRF算法比随机森林算法相比提高了4.42%，BSWRF算法比AdaBoost算法提高了1.1%。在Recall指标中，随机森林和AdaBoost算法的结果为0.341和0.494，表明对少数类的预测准确率并不高，BSWRF算法的Recall值达到了0.897，表明BSWRF算法可以对少数类做出较好的预测，整体来说，BSWRF相比于另外两种算法，在不平衡数据集上展示出了更好的分类性能。

Table 3. Performance comparison of three models

表3. 三种模型性能对比

图2中绘制了3种算法的ROC曲线图，图中的蓝色曲线代表AdaBoost算法，绿色曲线代表随机森林算法，红色曲线代表本文所提出的BSWRF算法，从图2中，可以明显看出红色曲线更加靠近左上角，包围的右下角面积更大，绿色曲线所包围的右下角面积最小，从ROC曲线中，可以直观地看出，本文所提出的BSWRF算法在处理不平衡数据集上效果更好。

Figure 2. ROC curves of three models

图2. 三种模型的ROC曲线图

本文还运用ENN (Edited Nearest Neighbors)算法对数据进行清洗，剔除异常点之后，再运用BSWRF算法对数据进行分类。ENN算法的原理是针对多数类中的每一个样本，如果其K个临近点中，有超过一半的点不属于多数类，则该样本就会被视为异常点，然后剔除掉。用ENN算法进行数据清洗之后的结果如表4所示：

Table 4. Sample data set after ENN algorithm cleaning

表4. ENN算法清洗之后的样本数据集

表4展示了运用ENN算法进行数据清洗之后的数据集，在对多数类样本进行异常值剔除之后，多数类样本的数量减少，不平衡率由原始数据集种的29.995降低至28.486。下面在这个数据集上运用BSWRF算法和另外两种对比算法进行分类。分类结果如表5所示：

Table 5. Performance comparison of three models

表5. 三种模型性能对比

表5是通过ENN算法进行数据清洗之后，3种模型的分类效果，从表5中可以看出，进行数据清洗之后，无论是从G-mean，还是AUC评价指标上来说，BSWRF算法的分类效果依然是最好的。并且将表5和表3进行对比，发现经过数据清洗之后，3种模型上的分类效果都有所提升。3种模型在AUC评价指标上都有小幅度的提升，在G-mean和Recall评价指标上，由于随机森林算法和AdaBoost算法本身分类效果较差，所以有较大提升，BSWRF算法有小幅度提升。总之，在经过ENN算法之后，不平衡数据集上的整体分类效果有所提升，并且BSWRF算法依然展现出最好的分类效果。

5. 总结

本文提出了一种基于G-mean的加权随机森林算法，在随机森林采样出来的不平衡子集上运用欠采样方法，进行数据集平衡，得到平衡的训练子集，有效地解决了不平衡数据集中少数类样本信息难以学习的问题，并且在得到的平衡子训练集上进行学习，得到基决策树，然后在包外样本上对基决策树的性能进行评估，计算出G-mean值，并且根据G-mean来为每个基决策树赋予权重，得到基于G-mean的加权随机森林。并且在台湾破产企业数据集上进行了实验，与随机森林算法和AdaBoost算法进行对比，表明本文所提出的BSWRF算法在处理不平衡数据集问题上更有效。此外，本文算法还存在改进的空间，未来可以针对不平衡数据集的边界样本进行研究，提出针对边界数据的解决方法。

基金项目

国家自然科学基金(61901294)；山西省应用基础研究计划资助项目(201901D211105)。

NOTES

^*通讯作者。