李懿恒，杜晨曦，杨燕燕，李翔宇

（北京交通大学软件学院，北京 100044）

0 引言

随着传感器技术、计算机技术、通信技术和数据存储等技术的高速发展，互联网、过程工业、电力系统、轨道交通等应用领域产生并存储了大量数据［1］。这些实际应用中的数据往往具有类别不平衡的特性，即数据集中某一类样本数量要小于其他类别样本数量，易引发学习过程中多数类别样本覆盖少数类别样本的现象，而实际中小类样本往往是关键样本［2］。如在故障诊断中，故障样本通常少于正常运行数据，将“故障”误诊为“正常”使故障系统继续工作，会导致无法预计的后果和损失。因此，如何提高类别不平衡数据中少数类别样本的分类学习精度具有重要意义。

为了提高类别不平衡数据集中少数类别样本的准确率，学者们研究了类别不平衡数据的特征选择问题，其目的在于选择能在多数类别和少数类别之间获得最高区分能力的特征［3-5］。文献［6］通过组合预先分别选择的正特征和负特征，以期改善文本分类中类不平衡数据的分类性能；文献［7］对高维类别不平衡数据中使用的6 个常用filter 方法和3 个使用分类结果矩阵的filter 方法进行了详细比较，该文分析认为特征选择有利于处理大多数高度不平衡的数据集；文献［8］首次对不平衡数据分类问题的重采样法、分类算法和特征选择算法进行了系统比较，并在来自于不同应用的小样本数据集上评估了7 个特征选择度量方法，结果表明，在大多数不平衡应用中，信噪相关系数和滑动阈值特征评估特别适用于特征选择；文献［9］提出了一种基于连续支撑步骤的后向消除方法，其特征贡献度量是基于一个在独立子集上获得的平衡损失函数；文献［10］使用K-means 聚类算法将多数类样例平均分成同尺寸的子集，将其贴上伪标签，并在分割后的数据上执行传统特征选择算法；文献［11］极小化了多数类别样本和少数类别样本之间的重合度，并基于此提出了两个类别不平衡数据的特征选择算法。然而，上述类别不平衡数据特征选择算法旨在改进现有特征选择算法，并未考虑类别不平衡数据中的不一致性问题。

在处理数据不一致等不确定性数据的方法中，粒计算［12］在处理不同类型数据的分析与挖掘方面显示出了独特优势。它通过相似关系对样本空间进行粒化聚类，并对样本标签进行近似，进而刻画了条件特征与标签之间的不一致性［13］。一些学者将粒计算与类别不平衡数据的学习问题结合起来，构建了几个类别不平衡数据的特征选择算法。如，文献［14］将样本的权重引入经典粗糙集模型中，平衡了数据集的类别分布，并构造了一个加权粗糙集模型来处理类别不平衡数据集，进而设计了加权粗糙集模型的特征选择算法和分类器算法；文献［15］通过重构邻域粗糙集下近似算子，提出了基于特征和标记之间依赖关系的在线特征选择框架，旨在处理流特征环境下的类不平衡问题；文献［16］提出了基于邻域粗糙集的类别不平衡数据特征选择算法，该算法通过研究下、上边界域的方式定义了类别不平衡数据集的特征重要性。

数值实验已经表明，上述类别不平衡数据特征选择算法可有效提高少数类别样本的分类精度。然而它们大多是从算法层面进行研究的，并没有对数据进行再平衡化处理。文献［17］指出类别不平衡数据的再平衡化可有效提高判别分析算法的性能；文献［18］也指出数据的再平衡化可有效改进类别不平衡学习问题的性能。因此，将类别不平衡数据再平衡化对于提高少数类别样本的性能具有重要意义，也是本文的一个重要思路。另外，伪标签策略常见于无监督学习和半监督学习，可有效提高类别标签的预测精度［19-20］，因此，本文通过伪标签的策略将类别不平衡数据进行平衡化，进而基于粒计算的思想构建了一种新的类别不平衡数据的特征选择算法。

本文主要工作如下：

1）重新定义了样本的一致度，研究了该一致度的单调性，从而设计了一种贪婪前向搜索的特征选择算法。

2）通过学习算法学习类别不平衡数据集的伪标签，用以平衡类别不平衡数据的样本类别分布。

3）将所学样本的伪标签融入一致性的测度中，构造了伪标签一致度的概念，用于评估类别不平衡数据集的特征，研究了伪标签一致度的单调特性。

4）通过保持类别不平衡数据的伪标签一致度，构造了基于伪标签一致度的类别不平衡数据的特征选择算法PLCFS（Pseudo-Label Consistency based Feature Selection），数值实验也表明了该算法的有效性。

1 基于一致性测度的特征选择算法

对于监督分类任务而言，每个数据集可表示为一个决策表(U，A∪D)，其中：U为数据集中所有样本的集合；A是数据集中描述样本的所有特征构成的集合；D={d}用于确定数据中样本的标签或者类别。对于每个样本x∈U，a(x)是样本x关于特征a∈A的取值，d(x)是样本x的标签。

对于∀B⊆A，定义特征子集B的等价关系RB={(x，y)：a(x)=a(y)，∀a∈B}。RB可将样本集合U划分为等价类的集合U/RB={[x]B：x∈U}，其中[x]B={y∈U：(x，y)∈RB}是由RB确定的等价类。

样本x∈U的广义决策［21-22］定义为：

d([x]B)={d(y)：y∈[x]B}。

若|d([x]B)|=1，则样本x关于特征子集B是一致的，即[x]B中所有样本具有相同标签；若|d([x]B)|>1，则样本x关于B是不一致的，即[x]B中有样本的标签不同。根据广义决策，本文给出样本一致度的概念。

定义1设(U，A∪D)是决策表，样本x∈U关于B⊆A的一致度定义为：

一致度的概念刻画了样本关于特征子集的一致性。为了刻画数据集中所有样本关于特征子集的一致度，本文引入了数据集一致度的概念。

定义2设(U，A∪D)是决策表，U关于特征子集B⊆A的一致度定义为：

样本集合U关于B的一致度consB(U)反映了特征子集与决策标签之间的一致性。

定理1设(U，A∪D) 是决策表，B⊆C⊆A，则对于∀x∈U，有consB(x)≤consC(x)。

证明 由广义决策的定义以及定义1，易证该定理成立。

定理1 表明样本关于特征子集的一致度是单调递增的，即随着特征的增加，数据中每个样本的一致度增大。

推 论1设(U，A∪D)是决策表，B⊆C⊆A，则consB(U)≤consC(U)。

证明 有定理1 和定义2，可证该推论成立。

推论1 表明数据集的一致度关于特征子集单调递增，即随着特征的增多，数据集的一致度增大。

定理2设(U，A∪D)是决策表，若对于P⊆A，有consP(U)=consA(U)，则对∀B⊇P且B⊆A，有consB(U)=consA(U)。

证明 由推理1 易证该定理成立。

该定理表明若P能保持数据集的一致度，则任意包含P的特征子集仍能保持数据集的一致度，因此，本文总能找到一个极小特征子集，使其能保持数据集的一致度，这一极小特征子集就是数据集的最优特征子集，其具体定义如下。

定义3设(U，A∪D)是决策表，特征子集P⊆A是一个最优特征子集，如果它满足下列条件：

1）consP(U)=consA(U)；

2）∀a∈P，consP-{a}(U)≠consA(U)。

在定义3 中，条件1）表明P能保持数据集的一致度；条件2）表明P是保持数据集一致度不变的极小特征子集，即从P中去掉任何一个特征都不能保持数据集的一致度。

通过前向搜索的方式，在每次迭代时添加使一致度增加最大的特征，直至一致度保持不变，从而获得数据集的最优特征子集。该特征选择算法的具体过程如下。

算法1 的时间复杂度为O(|U|2|A|)，空间复杂度为O(|U|2)。然而，该算法的前提假设是数据中样本类别分布是均衡的。当处理类别不平衡数据时，尽管数据集的整体分类精度有所改善，但却忽略少数类别样本的分类精度。鉴于此，本文提出了基于伪标签的类别不平衡数据特征选择算法。

2 本文算法

将伪标签策略融入一致性测度中，本文提出了融合伪标签策略的类别不平衡数据特征选择算法——PLCFS。首先，引入了伪标签策略用于平衡数据的类别标签；接着，将伪标签引入一致性测度的计算公式中，构造了一种新的一致性测度，用于度量不平衡数据集的一致性；最后，通过保持新的一致性测度不变，设计了类别不平衡数据的特征选择算法。

假设通过学习算法，如聚类算法、主动学习、K最近邻（K-Nearest Neighbor，KNN）算法，可学得类别不平衡数据的新标签，该标签为一种伪标签，它使得不平衡数据集的样本标签平衡化。对任意样本x∈U，本文将通过某一学习算法所学的伪标签记作PL(x)。

由于样本的伪标签可使类别不平衡数据达到平衡，故原有一致度的概念就不适用了。因此，本文需要给出新的一致度概念，在此之前，通过考虑类别不平衡数据集中每个样本的伪标签，本文引入了样本的伪标签广义决策的概念。

定义4设(U，A∪D)是决策表，PL(x)是通过学习算法学到的x∈U伪标签。样本x∈U的伪标签广义决策定义为dPL([x]B)={d(y)：y∈[x]B，PL(x)=PL(y)}。

样本的伪标签广义决策同时考虑了具有相同特征描述和相同伪标签的样本。利用伪标签广义决策，本文给出了类别不平衡数据集的伪标签一致度的概念，具体定义如下。

定义5设(U，A∪D)是决策表，PL(x)是通过学习算法学到的x∈U伪标签。样本x相较于特征子集B⊆A的伪标签一致度定义为：

样本的伪标签一致度度量了该样本关于特征子集、真实标签和伪标签之间的一致性。

定义6设(U，A∪D)是决策表，PL(x)是通过学习算法学到的x∈U伪标签。样本x相较于特征子集B⊆A的伪标签一致度定义为：

伪标签一致度反映了不平衡数据的特征所导出的样本分布、真实标签的样本分布和伪标签的样本分布之间的一致性。

定理3设(U，A∪D)是决策表，B⊆C⊆A，PL(x)是通过学习算法学到的x∈U伪标签，则对于∀x∈U，有。

定理3 表明，不平衡数据中每个样本的伪标签一致度关于特征子集单调递增。

推论2设(U，A∪D)是决策表，B⊆C⊆A，则。

证明 由定理3 和定义6，可证该推论成立。

推论2 表明，类别不平衡数据集的一致度随特征子集单调递增，即随着特征的增多，其一致度单调增加。

定理4设(U，A∪D)是决策表，B⊆C⊆A，PL(x)是通过学习算法学到的x∈U伪标签，若对于P⊆A，有，则对∀B⊇P且B⊆A，有。

证明 证明过程类似与定理2。

定理4 表明，对于类别不平衡数据集而言，若P可保持样本的伪标签一致度，则在后续增加特征的过程中，数据集的伪标签一致度仍能被保持，因此，本文总能找到类别不平衡数据集的一个极小特征子集，使其能保持伪标签一致度。

定理5 表明，若一个特征的加入不增加某一样本的伪标签一致度，则后续增加特征的过程中，该特征依然不增加这一样本的伪标签一致度。

推论3设(U，A∪D)是决策表，PL(x)是通过学习算法学到的x∈U伪标签，B1⊆A，a∉B1，若，则对于∀B2⊇B1，有。

证明 由定义6 和定理5，可证该定理成立。

推论3 表明，在特征选择的过程中，若一个特征的加入不增加数据集的伪标签一致度，则在后续特征选择的过程中该特征依然不增加数据集的伪标签一致度。基于此定理，本文可以在特征选择的过程中，删去这种特征，从而有效减少特征空间的搜索范围，进而提高特征选择的计算效率。

利用前向搜索的方式，本文设计了如下类别不平衡数据集的特征选择算法。

算法2 的时间复杂度为O(|U|2|A|)，空间复杂度为O(|U|2)。它通过保持类别不平衡数据集的伪标签一致度不变的方式计算了一个最优特征子集。

3 实验与结果分析

3.1 实验数据

为验证算法的有效性，本文选取了10 个公开数据集（http：//archive.ics.uci.edu/ml/datasets.php）进行实验，详细情况见表1，其中：高维数据集arrythmia 的特征个数高达279，数据集segmentation 具有2 308 个样本，实验所使用的数据具有高维或大规模特征；数据集的不平衡率最小为1.25，最大为19.2；I是样本数，F是特征数量，IR（Imbalanced Ratio）是数据集的不平衡率，P是正类样本所占比例，N是负类样本所占比例。

表1 实验数据集Tab.1 Experimental datasets

3.2 评价指标

传统的性能评价指标有接受者操作特征曲线下方的面积（Area Under Curve，AUC）、查准率、查全率等，但在高维不平衡数据的分类学习中，若采用传统性能评价指标，则会对小类样本的分类造成误判，但算法仍能保持较高的精度，这显然是不合理的。因此，实验采用F1-Score 和G-mean 作为分类器对类别不平衡数据进行分类的性能度量指标。

在处理多分类问题时，仍然需要对样本进行正反类的划分。通过对样本的正反类划分，可以得到多个二分类混淆矩阵。首先，对各个混淆矩阵的对应元素进行平均，得到真正例（True Positive，TP）、假正例（False Positive，FP）、真反例（True Negative，TN）和假反例（False Negative，FN）的平均值；然后基于平均值，求得查准率P=，查全率R=和micro‑F1=。

另一个是先求出各混淆矩阵的查准率P=和查全率R=，再计算平均值Pˉ和Rˉ，用平均值计算macro‑F1=。

3.3 实验设置

为验证算法2 的性能，实验将算法应用于10 个数据集进行特征提取，然后用支持向量机（Support Vector Machine，SVM）、KNN、随机森林（Random Forest，RF）、逻辑回归（Logistic Regression，LR）、决策树（Decision Tree，DT）共五个传统分类器，分别对原始数据和特征提取后的数据进行分类，比较其F1-Score 和G-mean 值。本实验在操作系统为Windows 10，CPU 主频为2.60 GHz，内存为8 GB 的计算机上完成，编程语言为Python3.8。

为了检验算法2 的有效性，对所选数据集采用k折交叉验证。由于D3、D5 的不平衡度较大，因此采用2 折交叉验证，其他数据集采用5 折交叉验证。同时，用最大相关最小冗余（max-Relevancy and Min-Redundancy，mRMR）算法［23］、特征权重算法Relief［24］以及本文算法1（CFS）作为对比算法，尽管mRMR 和Relief 提出时间较早，却具有较好的性能，并已被学者们广泛应用和研究。在确定mRMR 参数时，以SVM 为基分类器，对数据集的样本进行遍历，选取分类性能最好的特征数作为mRMR 算法的参数。

3.4 实验分析

3.4.1 算法参数k分析

本实验采用k-means 聚类算法对类别不平衡数据贴上伪标签，将样本进行了k个划分，为了分析k对分类结果的影响，选择k分别为2、3、4、5、6、7、8、9，分析不同取值的k对micro-F1 值、macro-F1 值和G-mean 值的影响，结果如图1～3所示。

从图1 可看出，随着k值的变化，算法2 在不同分类器上的micro-F1 值也是改变的。有些数据集上的micro-F1 值随k值波动较大，如数据集D1、D3、D10，这说明k值的选取对算法2 的性能影响较大；而有些数据集上的micro-F1 值随k值改变而平稳变化，如数据集D5 和D9，这说明在这些数据集上k值的选取对算法2 的性能影响较小。此外，从图1 也可看出，不同类别不平衡数据集有不同分类器的micro-F1 值，如对于数据集D4，SVM 分类器普遍有较好的分类性能；对于数据集D6，KNN 分类器具有较好的分类性能；对于数据集D9，SVM 分类器和逻辑回归具有相当的分类性能。

图1 不同k值下的micro-F1值Fig.1 micro-F1 values under different k values

从图2 可看出，随着k值的变化，算法2 在不同分类器上的macro-F1 值也是改变的。有些数据集上的macro-F1 值随k值波动较大，如数据集D1、D2、D3、D9、D10，这说明k值的选取对算法2 的性能影响较大；而有些数据集上的macro-F1 值随k值改变而平稳变化，如数据集D5，D7 和D8，这说明在这些数据集上k值的选取对算法2 的性能影响较小。此外，从图2 也可看出，不同类别不平衡数据集有不同分类器的macro-F1 值，如对于D4 和D8，SVM 分类器普遍有较好的分类性能；对于D6 而言，KNN 分类器具有较好的分类性能；对于数据集D5，随机森林具有较好的分类性能。

图2 不同k值下的macro-F1值Fig.2 macro-F1 values under different k values

从图3 可以看出，随着k值的变化，算法2 在不同分类器上的G-mean 值也在改变。有些数据集上的G-mean 值随k波动较大，如数据集D1、D2、D3、D6、D10，这说明k值的选取对算法2 的性能影响较大。而有些数据集上的G-mean 值随k值的变化而平稳改变，如数据集D5 和D9，这说明在这些数据集上k值的选择对算法2 的性能影响较小。此外，从图3也可看出，不同类别不平衡数据集有不同分类器的G-mean值，如对于数据集D4，SVM 分类器普遍有较好的分类性能；对于数据集D6，KNN 分类器具有较好的分类性能。

图3 不同k值下的G-mean值Fig.3 G-mean values under different k values

综上所述，聚类个数k影响着类别不平衡数据集的分类精度，并不能得出一个好的选择或者取值范围。

3.4.2 与传统特征选择算法对比

表2 给出了各算法在各数据集上选择出的特征数。从表2 可以看出，算法mRMR 和Relief 均在4 个数据集上选择最少特征，算法PLCFS 在3 个数据集上选择最少特征，而算法CFS 仅在1 个数据集上选择最少特征。算法mRMR 和Relief 在更多数据集上选择最少特征，是因为算法mRMR 的特征个数由分类器决定，在预选的特征基础上加入了相应的分类器，最终所选特征个数为最优分类精度对应的特征子集；而算法Relief 的特征个数由迭代次数和分类性能决定，它先根据迭代个数预选一些特征，再利用相应的分类器选择最优分类精度所对应的特征子集。算法PLCFS 通过保持伪标签一致度选择特征，无需借助于分类器，若借助分类器选择特征，PLCFS 也有望选择较少的特征个数，这将在后续研究中融合分类器再设计一个新的不平衡数据特征选择算法。与算法CFS 相比，PLCFS 所选特征个数明显较少，这表明改进CFS 来处理类别不平衡数据集是有必要的。总体来看，与先进算法mRMR 和Relief 相比，所提算法PLCFS 在去除类别不平衡数据集的冗余特征方面具有一定效果。

表2 四种算法在10个数据集上选择的特征数Tab.2 Numbers of features selected by four algorithms on 10 datasets

表3～7 给出了不同分类器在经过特征选择的数据集上的micro-F1 值、nacro-F1 值、G-mean 值。从表3～7 的整体结果来看：算法mRMR 具有最优分类性能，是由于其借助于分类器，所选的特征具有最高的分类精度；PLCFS 算法的性能仅次于mRMR 的性能，这说明PLCFS 在不借助于任何分类器的前提下，所选特征可在一定程度上改善类别不平衡数据集的分类性能；算法Relief 的性能较算法mRMR 和PLCFS 逊色，这说明算法Relief 删去的一些特征可能对提高分类性能是有益的，尽管该算法所选特征的个数在一些数据集上比算法PLCFS 和mRMR 少；算法PLCFS 的性能明显优于CFS，这说明CFS 不适合处理类别不平衡数据集，CFS 的改进算法PLCFS 在一定程度上提高了类别不平衡数据集的分类性能。

表3 十个数据集在SVM分类器上的指标得分Tab.3 Index scores of 10 datasets under SVM classifier

综上所述，mRMR 通过借助于分类器选择具有较高分类精度的特征，从而在几个比较算法中具有最佳性能和最少所选特征个数。本文算法PLCFS 的性能仅次于mRMR，该算法无需借助任何分类器，仅通过保持伪标签一致度来选择特征，若在该算法基础上加入分类器，有望进一步提高类别不平衡数据的分类性能。

表4 十个数据集在KNN分类器上的指标得分Tab.4 Index scores of 10 datasets under KNN classifier

3.4.3 统计性检验

为更好地比较各算法所选特征对分类性能的影响，实验采用非参数统计Friedman 检验对上述实验结果进行统计性检验。Friedman 检验使用不同算法在数据集上的排序对算法性能进行比较分析，定义如下：

其中：N为实验所用数据集的个数；k为所比较算法的个数；rj表示第j个算法性能的平均序值。服从自由度为k-1 的χ2分布，τF服从自由度为k-1 和(k-1)(N-1)的F分布。若“所有算法性能相同”这个假设被拒绝，则说明算法性能显著不同，这时需要进行后续检验来进一步区分各算法。实验采用Nemenyi 检验。Nemenyi 检验可计算出平均序值差别的临界值域CD=，qα是Tukey 分布的临界值。

为更好地比较实验所对比的四个算法在不同分类器上的测试性能，本实验独立进行了3 次Friedman 检验。Friedman 检验的空假设为所有特征选择算法在不同分类器上的性能相同。设置信水平为α=0.05，置信度为95%。实验部分比较了4 个算法在10 个数据集上的测试性能，因此τF的自由度为4 -1=3 和(4-1)(10-1)=27。当α=0.05，F(3，27)=3.56。根据Friedman 检验，CFS、PLCFS、mRMR、Relief 对应的τF值分别为0.46、0.87、0.56，均小于3.56，因此无法拒绝零假设。由Nemenyi 检验，得CD=1.48。

统计检验的实验结果如图4 所示，其中，纵轴表示各个算法，横轴表示平均序值，以原点为中心的横线但表示临界值域的大小。通过图4 所示，本文算法PLCFS 的性能与当下流行的几个特征选择算法Relief、mRMR 和CFS 相比，统计上并没有太大差异。

表5 十个数据集在RF分类器上的指标得分Tab.5 Index scores of 10 datasets under RF classifier

表6 十个数据集在DT分类器上的指标得分Tab.6 Index scores of 10 datasets under DT classifier

表7 十个数据集在LR分类器上的指标得分Tab.7 Index scores of 10 datasets under LR classifier

图4 不同分类器上的Friedman检验结果Fig.4 Friedman test results under different classifiers

4 结语

本文通过融合伪标签策略和一致性测度，提出了一种新的类别不平衡数据集的特征选择算法。首先，重新给出了样本一致度的概念，研究了一致度的单调性，从而构造了基于一致度的特征选择算法；其次，通过学习算法学习了类别不平衡数据集的伪标签，引入了伪标签策略，从而使得类别不平衡数据集的样本标签分布平衡化；接着，将伪标签策略融入一致度的概念中，构造了伪标签一致度的概念，研究伪标签一致度的性质，构造了基于伪标签一致度的类别不平衡特征选择算法；最后通过实验验证了算法的有效性。

本文仅仅是在离散型数据集上进行了研究，因此未来将拓展本文的研究范围到更复杂的数据类型，如数值型数据、文本数据、视频数据、多模态数据等。本文的数值实验的规模不够大，尽管维数最高达279 个特征，但缺乏上千上万的超高维特征，因此，在未来的研究工作中将致力于超高维类别不平衡数据的处理问题。进一步，本文的两个算法无需借助任何分类器就能选择一个最优特征子集，在未来的研究工作中，可以借助分类器设计一个新的伪标签一致度的类别不平衡数据的处理算法。