¹南京航空航天大学自动化学院，江苏 南京

²南通思振电子科技有限公司，江苏 南通

收稿日期：2023年10月20日；录用日期：2023年11月17日；发布日期：2023年11月24日

摘要

在数据挖掘领域，不平衡数据普遍存在。在许多情况下，这些数据通常具有高维性和类不平衡性。不平衡数据集特征属性分布失衡，会造成分类性能下降，数据的高维性则会导致学习算法非常耗时。针对这一问题，提出了一种基于组合采样和集成学习的特征选择方法。首先使用组合采样方法，处理类不平衡问题，重点合成少数类样本，在保证数据集达到平衡的前提下去除噪声样本，将集成特征选择建模为一个多准则决策过程，使用VIKOR方法得到特征重要性排序，然后在序列前向搜索特征的过程中，使用XGBoost算法的准确率作为评估特征子集优劣的指标，确定最优特征子集。选择AUC、G-mean和F-measure作为评价指标，通过在5组不平衡数据集进行实验，证实了所提算法具有更好的分类效果，且模型的鲁棒性更好。

关键词

不平衡数据分类，组合采样，多准则决策，VIKOR法，前向序列选择

Imbalance-Aware Data Based on Multi-Criteria Decision Making Integrated Feature Selection Algorithm

Gang Wang¹, Liping Ren¹, Li Fang¹, Weilei Xu²

¹College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing Jiangsu

²Nantong Sizhen Electronic Technology Co., Nantong Jiangsu

Received: Oct. 20^th, 2023; accepted: Nov. 17^th, 2023; published: Nov. 24^th, 2023

ABSTRACT

In the field of data mining, unbalanced data are prevalent. In many cases, these data are usually of high dimensionality and class imbalance. An unbalanced distribution of feature attributes in unbalanced datasets can cause degradation of classification performance, while the high dimensionality of the data can lead to very time-consuming learning algorithms. To address this problem, a feature selection method based on combinatorial sampling and integrated learning is proposed. Firstly, we use the combined sampling method to deal with the class imbalance problem, focus on synthesizing a few class samples, and remove the noise samples under the premise of ensuring that the dataset is balanced, model the integrated feature selection as a multi-criteria decision-making process, and use the VIKOR method to get the feature importance ranking, and then in the process of sequential forward searching for the features, we use the accuracy of the XGBoost algorithm as an indicator of the assessment of the feature subset’s The optimal feature subset is determined by using the index of superiority and inferiority. AUC, G-mean, and F-measure are chosen as the evaluation indexes, and the proposed algorithm is confirmed to have a better classification effect and better robustness of the model through the experiments in five unbalanced datasets.

Keywords:Unbalanced Data Classification, Combined Sampling, Multi-Criteria Decision Making, VIKOR Method, Forward Sequence Selection

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

由于大数据时代的到来，各种领域都出现了大量的高维数据 [1] ，但在实际应用中，样本的分布通常是不均匀的。例如，在电信用户丢失数据识别中，丢失用户的比例通常远低于非丢失用户的比例。这种数据集通常被称为不平衡的数据集 [2] 。

高维且不平衡的数据给数据挖掘工作带来了前所未有的挑战。在分类任务中，这些数据包含了不相关特征和冗余特征。这些特征的存在使得学习算法耗费时间，同时也影响了分类性能。传统的分类算法更注重多数类的准确性，并倾向于将样本类别分类为多数类。这样一来，数据集的总体准确率会非常高，但并没有将我们更关注的少数样本进行正确划分。因此，这些传统的算法在处理不平衡的数据时效率非常低。特征选择作为一种降维技术，选择有意义的特征，并从数据集中去除不相关和冗余的特征，对于高维性的不平衡数据集，特征选择有时比分类算法更重要 [3] 。

目前，解决不平衡数据问题的研究主要集中在数据级方法、算法级方法和数据与算法结合方法 [4] 。数据级方法通常被称为外部方法，因为它们通过减少数据集中多数类样本或增加少数类样本来平衡数据。数据级方法主要分为过采样和欠采样。过采样技术增加了少数类的数量，常用的过采样方法有Chawla等 [5] 提出的SMOTE算法，该算法通过寻找样本的近邻集，在样本点与其近邻集随机选择的样本连线上合成新的样本点；Haibo等 [6] 提出了ADASYN算法，根据数据分布自动确定每个少数类样本需要生成的样本数；Fernández-Navarro等 [7] 提出了一种动态过采样方法来平衡数据集。欠采样技术减少了多数类的数量，Yu等 [8] 提出了一种基于蚁群优化思想的启发式欠采样方法来解决类不平衡问题；用于识别边界线和噪声数据的Tomek Link欠采样方法。算法级的方法通常被称为内部方法 [9] ，因为它采用新的分类算法或增强现有算法来解决不平衡数据产生的偏差。代表性的算法有代价敏感学习 [10] 和集成学习 [11] 。混合方法是数据级方法和算法级组合，克服了数据级方法和算法级方法中存在的问题，并实现更好的分类精度，Yong等 [12] 提出了基于k-means聚类和遗传算法的采样方法，以突出不平衡数据集中少数类的性能；Galar等 [13] 提出增强算法和随机欠采样算法相结合的方法。

将特征选择应用到不平衡数据，在近年来已经引起了研究者的关注。根据算法与后续学习算法的结合方式可以将特征选择算法分为过滤式、包裹式和嵌入式 [14] 。针对同一个数据集，不同的特征选择算法会产生不同的最优子集。在这种情况下，特征选择过程被称为不稳定过程。为了提高所选特征子集的稳定性，集成学习近年来得到了发展和广泛的应用。集成学习的思想是多个模型的聚合结果可能会比使用单一模型得到更好的结果。最初的集成方法是在分类模型中引入的，但Saeys等人 [15] 提出了为特征选择方法构建集成框架的想法。

针对不平衡数据，本文提出了一种基于组合采样和集成学习的特征选择方法。使用SMOTE-Tomek组合采样算法处理类不平衡问题后，将集成特征选择建模为一个多准则决策过程，将特征作为可选择的方案，特征选择方法作为选择标准，使用VIKOR方法得到特征重要性排序，然后在序列前向搜索特征的过程中，使用XGBoost算法的准确率作为评估特征子集优劣的指标，确定最优特征子集。每个特征算法可以被认为是局部最优的特征子集，采用集成方法可以提高特征选择算法的鲁棒性和精确性。通过与其他集成算法和基础特征选择算法进行对比实验，验证了本文方法的优越性。

2. 模型介绍

2.1. 组合采样算法

SMOTE-Tomek组合采样算法，充分利用过采样和欠采样两种采样方法的优势。首先，通过SMOTE过采样方法，按设定的采样比例合成少数类样本。随后，将合成的少数类样本进行合并得到总的新增样本集，并将总的新增样本集加到原始数据集中得到最终扩展后的新数据集。最后，在新数据集中计算样本间的距离，如果两个不同类别的样本互为最近邻，则这两个样本构成一个Tomek Link对，在Tomek Link对中的两个样本，要么一个样本使噪声样本，要么两个样本都在类边界附近，因此找出新数据集中存在的Tomek Link对，并删除对中的样本，得到最终的平衡数据集。其中，SMOTE方法对少数类样本的合成流程如下。

(1) 对于少数类中每一个样本x，以欧氏距离为标准计算它到少数类样本集中所有样本的距离，得到其k近邻。

(2) 根据样本不平衡比例设置一个采样比例以确定采样倍率N，对于每一个少数类样本x，从其k近邻中随机选择若干个样本，假设选择的近邻为x_n。

(3) 对于每一个随机选出的近邻x_n，分别与原样本x按照式(1)的方式构建新的样本。

$x_{new}=x+rand\left(0,1\right)\times \left(x_n-x\right)$ (1)

SMOTE-Tomek组合采样算法的优势在于：充分考虑了经过SMOTE过采样后新数据集可能出现噪声样本和边界样本的问题，通过寻找Tomek Link对的方式继续处理新的数据集，消除数据集中存在的噪点和边界问题，得到更高质量的数据集，提高训练模型的精确度，达到更好分类测试数据的目的。

2.2. 多准则决策与VIKOR算法

多准则决策(Multiple Criteria Group Decision Making, MCDM)是指一群决策者，按各自的偏好对备选目标进行评价，从中寻求最满意的目标。目前，多准则决策分析方法主要用于解决选择、排序、有序分类、描述问题。

常用的多准则决策方法有TOPSIS和VIKOR方法，TOPSIS通过构造多属性问题的理想解和负理想解，以方案靠近理想解和远离负理想解两个基准作为方案排序的准则，来选择最满意方案。VIKOR决策方法是一种折衷排序方法，通过最大化群效用和最小化个体遗憾值对有限决策方案进行折衷排序。与TOPSIS相比，VIKOR方法既有前者的正负理想值概念，还具备妥协个体和群体利益的折衷解，更适合解决存在利益冲突和测度单位不同的多准则决策问题。本文采用VIKOR方法作为解决方法。

VIKOR方法确定好各指标的权值以及决策矩阵 $X\in R^{m\times n}$ ，其中m表示备选方案的数量，n表示准则的数量。第一步，根据规划后的决策矩阵确定各准则的正理想解 $r_j^{+}$ 和负理想解 $r_j^{-}$ ：

$r_j^{+}=\left\{\max \left(x_{ij}\right)|i=1,2,\cdots ,m;j=1,2,\cdots ,n\right\}$ (2)

$r_j^{-}=\left\{\min \left(x_{ij}\right)|i=1,2,\cdots ,m;j=1,2,\cdots ,n\right\}$ (3)

第二步，计算各方案到正理想解和负理想解的距离比值：

$S_i={\displaystyle \sum w_j}\left(\frac{r_j^{+}-x_{ij}}{r_j^{+}-r_j^{-}}\right),R_i=\underset{j}{\max }\left\{w_j\left(\frac{r_j^{+}-x_{ij}}{r_j^{+}-r_j^{-}}\right)\right\}$ (4)

其中，w_j是第j个指标的权重。

第三步，计算各个方案产生的利益比率值Q，以便对备选方案进行排序：

$S^{+}=\underset{i}{\max }{S}_i,S^{-}=\underset{i}{\min }{S}_i$ (5)

$R^{+}=\underset{i}{\max }{R}_i,R^{-}=\underset{i}{\min }{R}_i$ (6)

$Q_i=v\frac{S_i-S^{-}}{S^{+}-S^{-}}+\left(1-v\right)\frac{R_i-R^{-}}{R^{+}-R^{-}}$ (7)

v为多准则决策的决策机制系数，v值体现了准则的重要程度或决策者的偏好。v > 0.5时，表示根据大多数人的意见，属于风险偏好型；v = 0.5时，兼顾大多数群体利益和少数反对意见，属于风险中性型；v < 0.5时，根据少数人所持的反对意见，属于风险厌恶型。一般取v = 0.5。

第四步，根据Q_i值对被评价对象进行排序。Q_i值越小，第i个被评价对象排序越靠前。

3. 基于多准则决策的不平衡数据集成特征选择算法

集成特征选择是借鉴了集成学习的思想，通过结合多个单一特征选择模型的输出得到最终的特征子集。各种研究表明，采用集成方法不仅可以避免关键信息的丢失，还可以提高特征选择算法的鲁棒性以及分类精度。根据所使用的基选择器是否为同一种类型可将集成特征选择方法分为同构集成特征选择方法和异构集成特征选择方法。同构集成特征选择方法利用数据的多样性，数据被均匀地划分为K份，对每一份数据都采用同一种特征选择方法进行特征选择，最后，将每一份数据特征选择后的特征合并为新的特征集合。异构集成方法利用了特征选择方法的多样性，采用了不同的特征选择方法对相同的数据进行处理。集成特征选择方法的关键是如何结合部分特征选择结果来获得最终特征子集的输出，主要的方法有集成特征子集和集成特征排序。集成特征子集最典型的方法是计算特征子集的交集或并集，如果一个特征被所有选择选择方法选择，那么它必定是一个高度相关的特征，但极端情况下可能会出现空集。每个特征采用不同的特征选择方法会得到不同的排名，集成特征排名的最简单的方法是通过计算每个特征排名的中位数或平均值得到最终的排名。

本文的算法基于多准则决策方法构建的，将集成特征选择过程建模为一个多准则决策问题，采用VIKOR方法对特征进行排序，即将数据集中的特征作为备选方案，特征选择方法作为标准，在图1中给出了具体流程。使用SMOTE-Tomek组合采样算法平衡数据，对平衡后的数据集用多种过滤式特征选择方法进行特征选择，根据每个特征选择方法得到特征权重构建决策矩阵，采用VIKOR方法得到最终的特征重要性排序，然后在序列前向搜索特征的过程中，使用XGBoost算法的准确率作为评估特征子集优劣的指标，确定最终的最优特征子集。

图1. 本文特征选择方法流程图

对不平衡数据集采用SMOTE-Tomek组合采样方法做平衡化处理，对处理后的数据集采用不同特征选择算法计算特征权重，根据特征权重构建决策矩阵，因为不同特征选择算法得到的特征权重量纲不同，所以采用极差法对决策矩阵进行归一化处理，为了得到更加公正的结果，为每个特征选择算法的重要性赋以相同的权重，对决策矩阵采用VIKOR方法，根据VIKOR索引(Q)对特征进行升序排序，Q值越小，特征越重要。然后引入包裹式思想，采用XGBoost的分类精度作为序列前向搜索策略的评价函数，初始特征集合为空集，从特征排序集合中选择重要性得分最高的特征放入初始集合中并计算XGBoost的分类精度，接下来将排名第二的特征放入选特征集合并计算XGBoost的分类精度，每次从余下的特征集合中选择一个特征，将其放入已选特征集合中并计算其分类精度直至遍历整个特征空间，通过对每组特征集合对应的分类精度进行比较，得到最终的最优特征子集。

通过一个示例展示本文所提算法的步骤。例如，有一个7个特征的数据集，采用4个特征选择算法，每个特征选择算法都会得到一个特征权重向量，基于此构造决策矩阵如下：

$R=\left[\begin{array}{cccc}0.9377& 0.2664& 1.7410& 212.5192\\ 0.4702& 0.1088& 1.7753& 25.9614\\ 0.2262& 0.0356& 1.7066& 4.1388\\ 0.7552& 0.1396& 1.7897& 36.2948\\ 0.6832& 0.0681& 1.7897& 19.4997\\ 0.6652& 0.1301& 1.7897& 28.4255\\ 0.8359& 0.2535& 1.7897& 219.3343\end{array}\right]$ (8)

其中，行数为特征个数，列数为使用特征选择算法的个数，每一列表示一个特征选择算法得到的特征权重向量，特征权重越大，特征重要性越高。

为了消除不同量纲带来的不可公度性，采用极差法对决策矩阵进行规范化，规范化后的矩阵如下：

$E=\left[\begin{array}{cccc}0& 0& 0.5869& 0.0316\\ 0.6569& 0.6826& 0.1738& 0.8986\\ 1& 1& 1& 1\\ 0.2564& 0.5492& 0& 0.8506\\ 0.3576& 0.8593& 0& 0.9286\\ 0.3829& 0.5902& 0& 0.8871\\ 0.1431& 0.9558& 0& 0\end{array}\right]$ (9)

根据式(2)、(3)得到正理想解 $r_j^{+}$ 和负理想解 $r_j^{-}$ ：

$r_j^{+}=\left[1,1,1,1\right],r_j^{-}=\left[0,0,0,0\right]$ (10)

MCDM函数需要标准的权重，所以我们为每个特征选择方法设置相等的权重(1/n)，n为采用特征选择算法的个数，这里 $w=\left[0.25,0.25,0.25,0.25\right]$ 。

根据式(4)计算各方案的群体效益值S_i和个体遗憾值R_i：

$S_i=\left[0.1546,0.60291,1.0,0.4140,0.5364,0.4651,0.0497\right]$ (11)

$R_i=\left[0.1467,0.2246,0.25,0.2126,0.2321,0.2218,0.03577\right]$ (12)

为了兼顾大多数群体利益和少数反对意见v取0.5，根据式(7)计算各个方案产生的利益比率值Q_i，以便对备选方案进行排序：

$Q_i=\left[0.3141,\mathrm{0.73191.0},0.6045,0.7144,0.65268,0.0\right]$ (13)

其中i为特征数。

最后，根据特征在Q_i中的值按升序进行特征重要性排序，即 $f_7>f_1>f_4>f_6>f_5>f_2>f_3$ 。

4. 实验结果与分析

本文采用ReliefF [16] [17] 、MIC [18] 、mRMR [19] 、fisher-score [18] 这四种过滤式特征选择算法构建基于VIKOR的集成特征选择模型，通过组合采样和集成特征选择算法，有针对性的解决不平衡数据种存在的高维性和类不平衡性问题，得到更好地分类效果。为了验证所提方法的性能，将本文的算法与其他特征选择算法比较。

4.1. 数据集

本文实验采用的是NASA Metrics Data Program (MDP)数据库中的数据集，MDP数据库是由美国国家航空航天局提供的用于软件研究的开放数据库，数据集基本信息如表1所示，其中不平衡度由多数类个数除以少数类个数得到。

表1. 数据集的基本信息

4.2. 评价指标

由于不平衡数据集的类不平衡性，准确率这一指标没有意义。例如，样本数为100的数据集中，有99个好的产品和1个坏的产品，通过简单地预测好的产品，会获得99%的准确率，然而我们真正关心的坏的产品却被忽略了。所以，本文采用AUC、F-measure和G-mean作为评价指标，本文定义少数类为正类，多数类为负类，利用混淆矩阵表示分类结果，如表2所示。

表2. 混淆矩阵

精确率(Precision)，是指所有预测为正类样本中，正确预测为正类的样本所占的比率。计算公式如式(14)所示：

$\text{Precision}=\frac{\text{TP}}{\text{TP}+\text{FP}}$ (14)

召回率(Recall)，是指所有实际为正类的样本中，正确预测为正类的样本所占的比率。计算公式如式(15)所示：

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

特异度( )是指所有负类样本中，被正确预测为负类的样本所占的比率。计算公式如式(16)所示：

$\text{Specificity}=\frac{\text{TN}}{\text{TN}+\text{TP}}$ (16)

F-值(F-measure)是精确率和召回率的调和平均数。因为精确率和召回率是反比关系，所以采取折中的指标来评价。计算公式如式(17)所示：

$\text{F-measure}=\frac{2\times \text{Precision}\times \text{Recall}}{\text{Precision}+\text{Recall}}$ (17)

F-mean是召回率与特异度的综合指标，可用来评价处理不平衡数据的模型的表现情况，计算公式为：

$\text{G-mean}=\sqrt{\text{recall}\ast \text{specificity}}$ (18)

AUC (Area Under the Curve)指的是ROC曲线下方面积。ROC曲线(receiver operating characteristic

curve)，全称为受试者工作特征曲线。它以假正率 $\frac{\text{FP}}{\text{TN}+\text{FP}}$ 为横坐标，假正率 $\frac{\text{TP}}{\text{TP}+\text{FN}}$ 为横坐标绘制的曲

线。

对于一个数据集，其预测结果对应ROC曲线上的一个点。通过调整阈值，可得到一条经过(0, 0)和(1, 1)的曲线，曲线下方的面积即为AUC的值。AUC的取值范围为0~1，当AUC为0.5时，跟随机猜测的一样，代表模型无意义，小于0.5则表示还不如随机猜测的结果。AUC值越大，说明该模型的性能越好。因此，越靠近坐标系的左上角，表示模型的性能越好。

4.3. SMOTE-Tomek算法数据不平衡处理

为了验证组合采样方法的有效性，将原始数据经SMOTE、ADASYN、SMOTE-Tomek进行处理，分别使用随机森林分类算法对平衡后的数据集进行训练和实验。具体实验结果如下。

表3. 不同采样算法实验结果

由表3可以看出，经SMOTE-Tomek组合采样方法处理后的数据，在三个评价指标上的评分基本高于采用其它采样方法处理数据的评分。对比未经处理的原始数据，经过SMOTE-Tomek组合采样方法处理后的数据，AUC值提高了16%，F1-measure值提高了13%，G-mean提高了18%。充分说明了对不平衡数据进行平衡处理的重要性。并且对比其他采样方法，SMOTE-Tomek组合采样方法在各方面的表现都是最好的。

4.4. 与基础特征选择方法比较

4.3节验证了SMOTE-Tomek组合采样方法的有效性，现进一步验证本文所提集成特征选择方法对分类模型的提升。在采用组合采样方法平衡数据集后，将本文提出的基于多准则决策的集成特征选择算法与经典的ReliefF、MIC、mRMR、fisher-score算法进行对比。实验使用随机森林分类算法对经过特征选择处理后的数据集进行训练和测试。具体实验结果如下。

表4. 与基础特征选择方法对比结果

由表4可以看出，本文算法在五个数据集的三个评价指标中评分都是最高的，其中在AUC和G-mean指标上的均值都超过了0.8，说明集成特征选择方法得到的特征子集具有比单一特征选择方法更好的性能，解决了单一特征选择方法在面对复杂多样数据时的局限性。

图2. 与基础特征选择方法对比

从图2则更直观地看出，本文算法明显优于ReliefF方法、MIC方法、mRMR方法和fisher-score方法，原因在于本文方法综合考虑了特征选择方法的优劣。在四种单一特征选择算法中，mRMR方法算法表现较差，在G-mean均值上，ReliefF方法、MIC方法、mRMR方法和fisher-score方法的结果较为接近。

4.5. 与集成特征选择方法比较

将本文方法与目前较新的集成特征选择算法进行比较，包括E-max [20] 、E-mean [20] 、HFS。实验结果如表5所示。

表5. 与集成特征选择方法对比结果

由表5可以看出，本文提出的基于多准则决策的集成特征选择方法，在五个数据集的三个评价指标的得分大多都高于其他集成特征选择方法。虽然在CM1和MW1数据集中，本文算法在F1-measure这一个值上略低于HFS算法，但是综合其他两个指标依然可以说明本文算法在CM1和MW1数据集上具有很好的分类性能。可视化图如图3所示。

图3. 与集成特征选择方法对比

5. 结论

针对不平衡数据的高维性和不平衡性，本文通过SMOTE-Tomek算法解决类不平衡性，其次通过将特征选择建模成一个多准则决策过程解决高维性，在该方法中，根据多种特征选择方法获得特征权重并构建决策矩阵后，将该数据作为决策数据应用到VIKOR方法中，得到特征重要性排序，并在此基础上引入包裹式思想，找到最优特征子集。选择AUC、F-measure和G-mean作为评价指标，在NASA MDP数据集上与单一特征选择方法和其他集成特征选择方法进行对比，实验表明本文所提方法可以明显提高少数样本的分类指标值，模型的鲁棒性更好。

基金项目

国家重点研发计划项目(2020YFB1710502)。

江苏省重点研发计划(社会发展)——城市轨道交通设施的监控、巡检和应灾综合系统科技示范。

文章引用

王 刚,任丽萍,方 力,徐维磊. 基于多准则决策的不平衡感知数据集成特征选择算法
Imbalance-Aware Data Based on Multi-Criteria Decision Making Integrated Feature Selection Algorithm[J]. 传感器技术与应用, 2023, 11(06): 538-549. https://doi.org/10.12677/JSTA.2023.116061

参考文献