不平衡数据是指数据集不同类间的数据分布不均衡,其中某一类或多类的样本数量远远超过其他类[1]。例如,在网络安全中,异常行为通常只占一小部分,而大多数行为都是正常的。一般来说,相较于大类中的样本,小类中的样本可能携带罕见但更有用的信息[2]。然而,一些基础分类模型,如支持向量机(SVM)分类器[3],致力于最大限度提高整体分类精度,大多数小类样本被分配到大类,因此对不平衡数据分类的性能较差[4]。
近年来,不平衡数据分类问题备受关注,研究成果丰硕,大致可以分为3类:采样方法[5]、代价敏感学习方法[6]和集成学习方法[7]。采样方法侧重于对不平衡数据进行预处理,使类间数据达到均衡,然后就可以用基础分类模型分类。代价敏感的学习方法是对小类样本分配较高权重,这样可以减小对其分类的错误率。集成学习方法结合了不同子集训练的多个分类模型,相互间提供了互补性信息,解决了单一分类模型对不平衡数据分类性能较差的问题。
虽然以上的不平衡数据分类方法在一些场景中具有一定的有效性,但是这些方法只考虑全局最优,并不一定适合每个测试数据。例如,位于不同类别重叠区域的数据就难以准确划分,这些数据分布的特殊性导致其类别存在一定的不确定性[8],因此容易被错误分类。
针对上述问题,提出了一种复合可靠性分析下的不平衡数据证据分类方法。首先,为了评估分类模型的整体性能,本文设计了一种全局可靠性评估策略,在对大类多次降采样的基础上,分别训练多个分类模型,通过计算采样前后数据分布的差异性来评估不同分类模型的全局可靠性。其次,为了提升分类模型对每个测试数据的局部分类性能,本文设计了一种局部可靠性评估策略,通过评估分类模型对测试数据邻域分类结果的性能来量化该测试数据被正确分类的可靠性,这样能够使分类模型对每个测试数据实现局部最优。最后,在证据推理框架下[9],结合全局可靠性因子和局部可靠性因子对不同分类模型的结果做折扣融合并决策分析。
采样方法侧重于对输入数据进行预处理,以解决不平衡的问题,大致可以分为过采样和降采样两种方法。过采样方法[10-11]致力于生成数据来增加小类中的样本数量。例如,随机过采样方法(random over-sampling approach, ROS)[10]通过随机抽样的方式选取少量数据,然后将所选样本添加到原始小类中。降采样方法[12-13]致力于去除一部分样本来减少大类样本的数量。例如,随机欠采样方法(random undersampling approach, RUS)[12]随机选取一些与小类样本数量相同的大类样本,去掉其他样本,可能会丢失一些重要信息。
与采样方法不同,集成学习方法是将多个互补分类器组合在一起,以提高分类模型的整体性能。EasyensEmble是Liu等[14]提出的一种带双层结构的集成学习算法,先将大类进行欠采样,采样出多个子集分别与小类结合成多个子训练集,再以AdaBoost算法对每个子训练集进行训练从而生成基础分类模型。
假设测试集X={x1,x2,…,xH}在辨识框架Ω={ωmin,ωmaj}下被训练集Y={y1,y2,…,yG}训练得到的模型分类,Ymaj、Ymin分别表示数据量多的大类样本集合和数据量少的小类样本集合。
为了均衡数据的不同类别,本文使用一种多重降采样方法对Ymaj的数据降采样,从而得到T个子集值计算如下:
T=[IR];
(1)
(2)
式中:IR为可用于测量不平衡数据不平衡程度的不平衡比率;|· |表示势,用于统计集合中元素数量;[·]为四舍五入符号。
每个子集的样本数与Ymin的样本数相同,并与Ymaj组合生成新的训练子集{Y1,Y2,…,YT}。每个训练子集训练一个基本分类模型可用于对待测样本xi分类,定义为
(3)
式中:Γt(·)表示基础分类模型;Yt表示第t个训练子集;表示xi的分类结果。
由于分类任务的一个基本假设是训练数据和测试数据独立同分布,而对不平衡的训练数据多次降采样后得到多个训练子集的数据分布与原始分布不可避免地会存在一定的偏差,且不同的训练子集相对应的分布偏差也不同,因此由这些训练子集训练得到的分类模型也有不同的全局可靠性。本文利用最大均值差异MMD来计算采样前后数据分布差异性,从而评估不同训练模型得到的分类结果的可靠性。Yt训练模型得到分类结果的全局可靠性αit定义为
(4)
(5)
式中:N为Ymaj中训练样本数量;M为训练子集的样本数量;φ(·)表示一个映射函数,通常为高斯核函数,主要是将Ymaj和
映射到同一空间,然后计算两个数据分布间的差异性。
可以看出,训练子集与原始数据分布间的差异性越大,对应分类结果的全局可靠性αit越小。
全局可靠性反映的是分类模型的全局最优化性能,但是由于不同模型对于特定测试样本的分类结果不同,因此还需要评估模型对每个测试样本的局部性能,这将在下一节中详细介绍。
如图1所示,一个两类的不平衡数据,每个样本有两维属性,对应于x轴坐标和y轴坐标。Ymin和Ymaj的训练样本分别用正方形和圆形标记。两个测试样本(x1、x2)用五角星标记,并假设它们属于大类。从大类中采样两个子集和
每个子集样本数量与小类相同。将它们与Ymin相结合,生成平衡的训练集,从而分别训练得到不同的分类器Γ1和Γ2。可以看出,
对应的分类器Γ2可以正确地将样本x2分配给大类,但是该样本可能会被
对应的Γ1错误分类。尽管Γ1可能比Γ2有更优的全局分类性能,但可能不适合某些样本(例如x2)的正确分类。
图1 不同分类模型的可靠性示意图
Figure 1 Illustration of the reliability of different classifiers
由于测试样本与其近邻具有相似的空间结构和数据分布,因此它们的分类结果也是相似的。本文通过评估不同分类模型对待测样本近邻的分类性能来量化模型对该样本分类的局部可靠性。基于上述分析,假设样本xi在训练集Y中的K个近邻为{y1,y2,…,yK},分类模型Γt分类xi得到的分类结果的局部可靠性βit定义为
(6)
(7)
式中:为近邻yk的分类结果中数据类ωc的概率值;向量Lk=[lk(ωmin),lk(ωmaj)]表示yk的类别标签。
可以看出,分类模型Γt分类xi近邻的分类性能越好,其分类xi得到分类结果的局部可靠性也就越大。
至此,样本xi分类结果的全局可靠性以及局部可靠性都已计算得到,在下一节中会详细介绍如果有效地利用这些可靠性因子并融合多个分类结果。
样本xi有T个分类结果在证据推理[9](Dempster-Shafer, DS)框架下每个分类结果都可以看作是一个证据源,每个证据源都有一个全局可靠性和局部可靠性。为了全面评估不同分类结果的可靠性,本文定义了一种复合可靠性因子γit:
(8)
式中:αit和βit分别为xi第t个分类结果的全局可靠性和局部可靠性。
在获得复合可靠性因子后,用折扣融合方法将xi的T个分类结果进行折扣融合,被折扣的分类结果定义如下:
(9)
式中:表示基本信任值,类似于概率框架下的分类概率,它表示待测数据属于某一类别的置信度;Ω表示全集,也被称为完全未知类。
通过折扣融合可以将xi分类结果的部分概率值分配给完全未知类来表征数据类别的不确定性。复合可靠性因子越高,说明该分类结果越可靠,不确定性越小,被折扣掉的信息也就越少。经过折扣后的证据之间的冲突程度变小,在这种情况下就可以用基础的DS融合规则[15]结合多个折扣后的结果:
(10)
经DS融合后的结果mi中还包含有完全未知类的基本信任值,为了便于决策,本文将mi转换成pignistic概率[16]BetP(·)进行最终决策,定义如下:
(11)
式中:|Ω|为Ω中元素的数量。最后,测试样本xi可以分配到概率最大的类别。
本文所提出算法的计算步骤如下。
输入:测试集X={x1,x2,…,xH}、训练集Y={y1,y2,…,yG}、辨识框架Ω={ωmin,ωmaj}、小类样本集合Ymin和大类样本集合Ymaj;
输出:测试集类别。
① for t =1 to T
对训练集的大类数据Ymaj降采样;
用Ymaj训练分类模型测试样本分类;
依据式(4)、(5)计算分类的全局可靠性;
② endfor
③ for i = 1 to H
样本xi在训练集中搜索近邻并分类;
④ for t = 1 to T
分类模型Γt对xi的近邻分类;
依据近邻分类结果计算局部可靠性;
根据式(8)计算复合可靠性因子;
折扣分类结果
⑤ endfor
根据式(10)融合多个分类结果;
根据式(11)做最终决策;
⑥ endfor
将本文方法与其他几种相关的典型方法进行比较。本文中的所有实验都是在配备英特尔酷睿i7-9750H芯片和16 G运行内存的计算机上进行。主要用两个常用的不平衡分类指标FM和GM评价不同方法的性能。FM和GM的值越高,该方法的性能就越好。
使用KEEL库和UCI数据库的12个不平衡数据集来测试和评估不同方法的性能。每个数据集使用五折交叉验证进行实验,能有效避免偶然性对结果的影响。这些数据集的基本信息如表1所示,包括数据集、数据库、样本数量、属性个数和不平衡比例IR。
表1 不平衡数据集基本信息
Table 1 Basic information of imbalanced datasets
数据集数据库样本数量属性个数IRcaesarianUCI8051.35 ecoli2KEEL33675.46 fertility_DiagnosisUCI10097.33 glass1KEEL21491.82 glass0123vs456KEEL21493.20 LymphographyUCI142181.33 new-thyroid1KEEL21555.14 new-thyroid2KEEL21555.14 shuttle-2vs5KEEL3 316966.17 vehicle0KEEL846183.25 vowel0KEEL988139.98 page-blocks0KEEL5 472108.79
采用一些典型的不平衡数据分类方法做对比实验。ROS和SMOTE是最具有代表性的过采样方法,被用来生成数据集来增加小类样本的数量,然后利用平衡训练集对基本分类模型训练。RUS和CBU是欠采样方法,采用随机策略和聚类方法从大类样本中抽取一些样本来平衡数据集。RUSBOOST和EasyEnsemble是集成学习方法,对原始数据集进行多次采样,并训练不同的分类器做出决策。此外,EATWSVM[17]在TWSVM公式中引入了内核增强,从而对不平衡数据进行分类。
实验中将本文方法与其他对比方法相比较。不同方法分类结果的FM值和GM值分别见表2和表3,其中最后一行分别代表不同方法在不同数据集上得到的FM和GM的平均值。从实验结果可以看出,在大多数情况下,本文方法性能比其他不平衡数据分类方法更好;从平均值来看,本文方法的整体性能要明显优于其他方法,FM和GM值相较于其他最优的不平衡数据分类方法分别高出8.1%和4.99%。此外,不同方法在分类部分数据的ROC曲线和PR曲线如图2和图3所示。结果表明,本文方法的ROC曲线[18]和P-R曲线下方面积要大于其他方法,这进一步证实本文方法在分类不平衡数据的有效性。分析原因是本文方法在处理数据不均衡问题时不仅能够评估不同分类模型的全局性能而且量化了这些模型对每个测试样本的局部分类性能,从而提升了模型的分类性能,并在一定程度上避免了错误分类的风险。因此,本文方法相较于其他方法获得了较好的分类性能。
表2 不同方法分类不同数据集的FM值
Table 2 FM values of different datasets classified by various methods
数据集FM/%ROSRUSSMOTECBURUSBOOSTEasyEnsembleEATWSVM本文方法caesarian61.2159.5065.8564.3562.0861.3555.7167.23ecoli271.9270.7570.9271.9071.9371.2359.6473.09fertility_Diagnosis24.1329.9128.1625.0224.6820.1925.0035.00glass158.5857.3655.6154.4755.8755.3041.7662.39glass0123vs45683.9885.7682.9886.1583.2084.6460.7286.16Lymphography77.9280.0579.8279.9677.3079.9263.5082.13new-thyroid197.1396.1797.3393.6791.5797.3371.64100.00new-thyroid297.1395.1498.6790.1488.3096.0070.05100.00shuttle-2vs593.6175.6093.6172.3483.6478.3093.0298.00vehicle091.6492.4591.9189.0677.9493.4883.1594.49vowel080.1173.0781.7470.8775.8771.0164.8282.69page-blocks022.8722.5918.3831.5466.0026.6446.8480.96FM平均值71.6969.8672.0869.1271.5369.6261.3280.18
表3 不同方法分类不同数据集的GM值
Table 3 GM values of different datasets classified by various methods
数据集GM/%ROSRUSSMOTECBURUSBOOSTEasyEnsembleEATWSVM本文方法caesarian60.6058.9763.7263.8560.6759.7552.2866.31ecoli290.5889.7790.2190.1588.1689.9879.8990.93fertility_Diagnosis58.1662.4661.1656.5256.6150.3245.0763.72glass161.2657.6254.0852.3464.9255.6451.3663.71glass0123vs45690.9691.2690.0190.7791.2391.2870.6191.94Lymphography80.1682.3281.8082.0780.1582.1367.8283.58new-thyroid198.2599.1699.4498.5994.7399.4477.44100.00new-thyroid298.2498.8799.7297.7493.8999.1676.07100.00shuttle-2vs596.6999.4996.6999.3999.6999.5797.7699.97vehicle094.9196.6495.9795.0287.2296.6790.6497.68vowel095.5095.7196.7594.4386.1994.8670.4197.80page-blocks050.2646.0238.2148.8583.5143.7057.3691.20GM平均值81.29 81.52 80.65 80.81 82.25 80.21 69.74 87.24
图2 不同方法分类不同数据集的ROC曲线
Figure 2 ROC curves of different methods in classifying various datasets
图3 不同方法分类不同数据集的P-R曲线
Figure 3 P-R curves of different methods in classifying various datasets
K值是影响本文方法性能的关键参数,K表示本文方法在评估模型局部可靠性时所需要找的近邻个数。图4所示为K值变化对本文方法在不同不平衡数据分类中性能的影响。其中横坐标为K的值,取值为3~15。实验结果表明,随着K的增加,本文方法在不同不平衡数据上分类性能的变化较小,这表明本文方法对K值具有一定的鲁棒性。在实际应用中推荐K∈[3,15]作为该参数的取值范围,默认值为7。
图4 本文方法在K取不同值时的分类结果
Figure 4 Classification results of the proposed method with different K
(1)提出了一种复合可靠性分析下的不平衡数据证据分类方法,该方法通过评估分类模型的全局可靠性和局部可靠性来提升模型对不平衡数据的分类性能。
(2)实验用公开的不平衡数据集验证了本文算法的有效性,FM值和GM值相较于其他不平衡数据分类方法分别高出8.1%和4.99%。
(3)在未来的研究中,将尝试利用集成学习的思想结合不同采样方法的优势,研究更高性能的不平衡数据分类方法。
[1] 李艳霞, 柴毅, 胡友强, 等. 不平衡数据分类方法综述[J]. 控制与决策, 2019, 34(4): 673-688.
LI Y X, CHAI Y, HU Y Q, et al. Review of imbalanced data classification methods[J]. Control and Decision, 2019, 34(4): 673-688.
[2] 胡峰, 王蕾, 周耀. 基于三支决策的不平衡数据过采样方法[J]. 电子学报, 2018, 46(1): 135-144.
HU F, WANG L, ZHOU Y. An oversampling method for imbalance data based on three-way decision model[J]. Acta Electronica Sinica, 2018, 46(1): 135-144.
[3] 张震, 张英杰. 基于支持向量机与Hamming距离的虹膜识别方法[J]. 郑州大学学报(工学版), 2015, 36(3): 25-29.
ZHANG Z, ZHANG Y J. Iris recognition method based on support vector machine and Hamming distance[J]. Journal of Zhengzhou University (Engineering Science), 2015, 36(3): 25-29.
[4] 韩敏, 朱新荣. 不平衡数据分类的混合算法[J]. 控制理论与应用, 2011, 28(10): 1485-1489.
HAN M, ZHU X R. Hybrid algorithm for classification of unbalanced datasets[J]. Control Theory &Applications, 2011, 28(10): 1485-1489.
[5] 刘定祥, 乔少杰, 张永清, 等. 不平衡分类的数据采样方法综述[J]. 重庆理工大学学报(自然科学), 2019, 33(7): 102-112.
LIU D X, QIAO S J, ZHANG Y Q, et al. A survey on data sampling methods in imbalance classification[J]. Journal of Chongqing University of Technology (Natural Science), 2019, 33(7): 102-112.
[6] 孙艳歌, 邵罕, 杨艳聪. 基于代价敏感不平衡数据流分类算法[J]. 信阳师范学院学报(自然科学版), 2019, 32(4): 670-674.
SUN Y G, SHAO H, YANG Y C. Classification for imbalanced data streams based on cost-sensitive[J]. Journal of Xinyang Normal University (Natural Science Edition), 2019, 32(4): 670-674.
[7] 王乐, 韩萌, 李小娟, 等. 不平衡数据集分类方法综述[J]. 计算机工程与应用, 2021, 57(22): 42-52.
WANG L, HAN M, LI X J, et al. Review of classification methods for unbalanced data sets[J]. Computer Engineering and Applications, 2021, 57(22): 42-52.
[8] ZHANG Z W, TIAN H P, YAN L Z, et al. Learning a credal classifier with optimized and adaptive multiestimation for missing data imputation[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(7): 4092-4104.
[9] SHAFER G. A mathematical theory of evidence[M]. Princeton: Princeton University Press, 1976.
[10] HE H B, GARCIA E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9): 1263-1284.
[11] CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2002, 16: 321-357.
[12] GUO H X, LI Y J, SHANG J, et al. Learning from class-imbalanced data: review of methods and applications[J]. Expert Systems With Applications, 2017, 73: 220-239.
[13] LIN W C, TSAI C F, HU Y H, et al. Clustering-based undersampling in class-imbalanced data[J]. Information Sciences, 2017, 409-410: 17-26.
[14] LIU X Y, WU J X, ZHOU Z H. Exploratory undersampling for class-imbalance learning[J]. IEEE Transactions on Systems, Man, and Cybernetics Part B, Cybernetics: a Publication of the IEEE Systems, Man, and Cybernetics Society, 2009, 39(2): 539-550.
[15] CHALLA S, KOKS D. Bayesian and Dempster-Shafer fusion[J]. Sādhanā, 2004, 29: 145-174.
[16] SMETS P. Decision making in the TBM: the necessity of the pignistic transformation[J]. International Journal of Approximate Reasoning, 2005, 38(2): 133-147.
[17] JIMENEZ-CASTAO C, ALVAREZ-MEZA A, OROZCO-GUTIERREZ A. Enhanced automatic twin support vector machine for imbalanced data classification[J]. Pattern Recognition, 2020, 107: 107442.
[18] 逯鹏, 李奇航, 尚莉伽, 等. 基于优化极限学习机的CVD预测模型研究[J]. 郑州大学学报(工学版), 2019, 40(2): 1-5.
LU P, LI Q H, SHANG L J, et al. A CVD prediction model based on optimized extreme learning machine[J]. Journal of Zhengzhou University (Engineering Science), 2019, 40(2): 1-5.