1. 引言
随着大数据技术的发展,数据的体量在飞速地增长。如何在海量的数据中精准、高效地挖掘有价值的信息是非常重要的。由于数据的多样性和复杂性,会出现许多不平衡数据,即在统计样本或数据集中不同类别的样本数量存在严重的不均衡情况。在二分类数据中,一种类别的样本数量远远大于其他类别的样本数量一般称为“多数类”,而其他类别则称为“少数类”。在实际应用中普遍存在不平衡数据分类问题,如:信贷评估[1]、医疗诊断[2]、诈骗检测[3]等。
目前对不平衡数据进行分类的处理包括两个层面:算法层面和数据层面[4]。算法上主要是通过发掘或改进算法使其对不平衡数据分类有效;数据上主要是在具体分类前对数据进行预处理使数据达到相对平衡,主要有对少数类进行过抽样、对多数类进行欠抽样,以及过、欠结合的混合抽样。本文主要关注欠抽样算法。
欠抽样是通过剔除部分多数类样本来保持数据平衡的。文献[5]提出,利用欠抽样算法对数据进行预处理是比利用过抽样算法效果要好。文献[6]提出了随机欠抽样方法,可随机地减少多数类样本来缩小少数类与多数类的样本差,进而得到与少数类样本数量相同的多数类样本达到样本相对平衡。文献[7]提出了基于聚类的欠抽样,使每一簇原始数据被其相应的聚类质心来代替从而减少多数类中数据点数使之与少数类数据点数达到相同。文献[8]提出了一种基于聚类分布K-means欠抽样算法,依据聚类分布和从多数类聚类到少数类聚类中心的距离来选择样本,保持原始分布的同时提高边界样本的采样率。这些方法旨在对原始不平衡数据进行预处理使样本类别更加均衡,从而提高模型的性能和泛化能力。但现实任务中数据大都呈现非线性、非正态的分布特点,传统的方法在处理不平衡数据的非线性问题时仍有不足。
1992年核函数成功应用到了SVM中,核函数的重要性被人们所了解。1998年,B. Schokopf等人[9]基于核函数与主成分分析的有机结合,提出核主成分分析(KPCA)。核主成分分析能够捕捉到数据中的非线性结构,并将其转化为线性可分的形式,从而更好地实现数据的降维和特征提取等工作。在诸如模式识别、图像处理和数据挖掘等领域[10]-[15],核主成分分析已被广泛应用,并在处理复杂数据集和提高分类性能方面发挥了重要作用。
基于不平衡数据的非线性问题,本文从数据层面出发提出一种基于KPCA的欠抽样算法。将原始数据在非线性核函数映射的作用下变成高维空间中线性可分的数据,通过计算核矩阵并求解其特征值和相应的特征向量以及核主成分,进而将高维空间中的数据在核主成分上进行投影得出样本的综合评分,最后按照评分对多数类样本进行排名并删除排名靠前且相似度高的多数类样本从而达到欠抽样的目的,余下的多数类样本与少数类样本相组合可达到相对平衡的状态进而最大化的降低非平衡数据集的不平衡率。
2. 理论知识
2.1. 核函数
核方法的基本原理[14]为:当需要处理的变量为非线性时,引入核函数,它是一个非线性变换,用来将原始空间R中的线性不可分问题转化为高维特征空间H中的线性可分问题。图1展示了数据从输入空间映射到高维特征空间的过程。
Figure 1. Nonlinear mapping
图1. 非线性映射
核函数定义[14]:假设存在映射
,能将二元函数
,映射到特征空间H中,并且满足
,称K是核函数。常见的核函数包括多项式核函数、高斯径向核函数、多层感知机核函数等。
在本文的实际应用中采用了以下三种核函数,具体形式如下:
1) 多项式核函数
(1)
其中
,d是整数,均为自定义参数。当参数d较小时,此函数的外推能力较强,但随着d的增大,外推能力则逐渐变弱。
2) 高斯径向核函数
(2)
其中
是自定义的高斯核函数的带宽参数。它决定了高斯分布的标准差,即控制了核函数的平滑程度和波动范围。
3) 多层感知机核函数
(3)
其中b,c是自定义参数。
2.2. 核主成分分析原理
核主成分分析的核心思想[16] [17]是将核函数与主成分分析相结合,在非线性变换函数
的作用下将原始空间R中数据映射到特征空间H,即R中的样本点
转变为H中的样本点
,并在H中进行主成分分析。
实现过程为:若样本集合中有n个样本点,用两者的内积
表示R中的两个数据
和
在H空间的距离。假设H空间中的样本
已经中心化,即
(4)
则在H空间中进行主成分分析,通过计算协方差矩阵
(5)
求得满足
的特征值
以及相应的特征向量
。
由于
[17],则存在一组参数
使
(6)
故
就等价于
。
通过定义
的核矩阵K [17],
,上述
等价为
对核矩阵K进行特征分解得到其特征值
(
),
为相应特征向量。则
在H空间向量
上的投影为:
(7)
此外,当假设
不成立时,只需将矩阵K调整为
(8)
其中
。
3. 基于KPCA欠抽样的不平衡数据分类算法
本文采用基于KPCA的欠抽样算法对不平衡数据进行预处理,以便可以初步帮助解决传统方法不善于解决现实任务中的非线性问题。经此算法预处理后的数据最大可能达到多数类与少数类相对平衡的状态。基于KPCA欠抽样算法的实现步骤如下:
1) 建立初始样本矩阵
设有m个待评价样本,n个属性特征。假设第i个样本在第j个属性下的取值为
,建立初始矩阵S为:
初始样本矩阵归一化处理:
上述式子中:
(9)
2) 依据数据特点选取核函数及核参数[18]
选择与样本数据特点贴切的核函数并设置相对最优的参数值将R空间数据映射到H空间中,可得到核矩阵K,其中
,
和
代表矩阵
的第i行和j列所对应的数。
3) 中心化核矩阵
中心化后的核矩阵记为
,其中元素表达式为
,
为核矩阵中所有元素是均值。
4) 求解特征值和特征向量
对中心化的核矩阵
利用
进行特征分解,得到核矩阵
的特征值
和相应的特征向量
。
5) 确定特征空间的维数t
t满足下式的最小值
(10)
6) 计算样本点X的主成分
计算投影:
(11)
其中,
为特征向量
的第j个元素,
为数据点X的第k个主成分。
7) 计算样本主成分因子得分
其中,
,
将原始样本数据点投影到主成分上,得到相应的投影坐标值即为样本主成分因子得分。
表示为对于第i个样本数据点在第j个主成分上的因子得分。
8) 最终得出每个样本的得分
样本得分为主成分因子得分的线性组合,
,其中,
是主成分因子得分,
是每个主成分的权重系数,用来表达主成分在样本的综合得分中的贡献程度。
9) 根据每个样本评分
对样本进行降序排列并删除前r个多样本数据来达成欠抽样的目的。其中,r为多数类与少数类个数差。
算法流程图如图2所示:
Figure 2. Flow chart based on KPCA under-sampling algorithm
图2. 基于KPCA欠抽样算法流程图
4. 实验结果与分析
4.1. 实验数据
本文为验证基于KPCA欠抽样算法在不平衡数据集上的分类效果,使用UCI数据库中9组数据集进行实验,这9组数据集的不平衡度呈递增形式且范围由1.79%~33.74%,实验数据集信息如表1。此外部分数据是多分类数据集,本实验运用一种应用广泛的转化方法[19]将多分类数据集中的某些类别合并使之成为二分类数据集。例如一个7分类数据集steel-plates,steel-plates_0表示将数据集中标签为0的样本看作少数类,那么多数类则是由标签1到6这六类样本合并而成。
Table 1. Experimental datasets description
表1. 实验数据集描述
编号 |
数据集 |
样本总数 |
属性 |
多数类样本数 |
少数类样本数 |
不平衡度/% |
1 |
Ionosphere |
351 |
34 |
225 |
126 |
1.79 |
2 |
QSAR |
1055 |
41 |
699 |
356 |
1.96 |
3 |
German Credit |
1000 |
24 |
700 |
300 |
2.33 |
4 |
Wall-following_1 |
5456 |
24 |
4630 |
826 |
5.61 |
5 |
Steel-plates_1 |
1941 |
27 |
1751 |
190 |
9.22 |
6 |
Steel-plates_0 |
1941 |
27 |
1783 |
158 |
11.28 |
7 |
Wall-following_3 |
5456 |
24 |
5128 |
328 |
15.63 |
8 |
Thyroid_1 |
3772 |
21 |
3581 |
191 |
18.74 |
9 |
Ozone |
2536 |
72 |
2463 |
73 |
33.74 |
4.2. 实验设计
本文采用五折交叉验证方法进行实验,即将每个数据集划分为5份,选取4份作为训练集,1份作为测试集,每个数据集重复实验5次,实验5次并以平均值作为最终的评价结果。分类器采用线性回归模型中的Logistic Regression模型。本文实验包括3种情况,具体如下:
1) 原始数据不进行欠抽样预处理,仅使用Logistic Regression分类器模型对不平衡数据集进行分类。
2) 采用随机欠抽样算法对原始数据进行预处理,再利用Logistic Regression分类器模型对预处理后的不平衡数据集进行分类。
3) 采用本文提出的基于KPCA的欠抽样方法对不平衡数据集进行预处理,再利用Logistic Regression分类器模型对预处理后的不平衡数据集进行分类。
4.3. 评价指标
本文采用基于混淆矩阵分析的方法来对不平衡数据集分类器性能进行评价。此方法在当少数类样本远小于多数类样本时,可以适当减少分类器把所有的样本都分类为多数类。因此,本文采用准确率(Accuracy)、F1-measure和AUC值作为评价指标测试3种实验情况的分类结果。
Table 2. Confusion matrix
表2. 混淆矩阵
|
预测值 |
计数 |
Positive |
Negative |
真实值 |
Positive |
TP |
FN |
P |
(True positive) |
(False Negative) |
Negative |
FP |
TN |
N |
(False Positive) |
(True Negative) |
由表2可看出数据的预测值与真实值的组合有四种:分别为:预测和真实同为正例、预测和真实同为负例、预测为正例真实为负例、预测为负例真实为正例。TP、TN、FP、FN分别表示其对应样本个数,有
样本总数。
1) Accuracy:所有结果中,预测正确的结果所占的比例,计算公式为:
(12)
2) F1-measure:综合了查准率(Precision)和召回率(Recall),是他们的调和平均,用来反应模型的稳健性,计算公式为:
(13)
3) AUC:AUC [20] (Area Under Curve)是ROC曲线下的面积,用来衡量算法的性能。
ROC曲线是受试者特征曲线(Receiver Operating Characteristic Curve)是一种用于反映诊断检查方法敏感性和特异性特征的曲线图。ROC曲线的纵轴是真正例率(Ture Positive Rate,简称TPR)公式为:
(14)
横轴是假正例率(False Positive Rate,简称FPR)公式为:
(15)
4.4. 结果分析
实验分析了三种情况的Accuracy、F1-measure、AUC。表3列出了三种算法在各个数据集下的评价指标值,其中原数据不进行预处理直接分类的方法缩写为DTC;随机欠抽样缩写为RUS;加黑数字为同组最大值。
由表3可以看出基于KPCA的欠抽样方法与其他算法相比,整体来看在绝大多数数据集上都表现的不错。在AUC值指标方面:相比其他方法本文方法体现出其稳定的优势,在各个数据集中都有不同的提升。在指标Accuracy和F1-measure值上:本文方法在大部分数据集上表现依旧不错,但在极个别数据集上表现略微不足。
为了更好的观察对比表3中的三种方法在这9组数据集上三种指标上的表现,下面采用3个柱状图形式直观的展示3个评分的对比结果。
Table 3. Classification of Accuracy, F1-measure and AUC of different classification algorithms on unbalanced datasets
表3. 不同分类算法在不平衡数据集上的Accuracy、F1-measure值、AUC值对比
DataSet |
Accuracy |
F1-measure |
AUC |
DTC |
RUS |
KPCA |
DTC |
RUS |
KPCA |
DTC |
RUS |
KPCA |
Ionosphere |
0.8592 |
0.8553 |
0.8868 |
0.8958 |
0.8608 |
0.9118 |
0.8945 |
0.8968 |
0.9446 |
QSAR |
0.8107 |
0.7804 |
0.8364 |
0.6591 |
0.7707 |
0.8548 |
0.8931 |
0.8632 |
0.8987 |
German Credit |
0.7600 |
0.7611 |
0.7667 |
0.5200 |
0.7485 |
0.7879 |
0.8130 |
0.8359 |
0.8430 |
Wall-following_1 |
0.8638 |
0.8327 |
0.8617 |
0.3890 |
0.8421 |
0.8431 |
0.8681 |
0.8848 |
0.8879 |
Steel-plates_1 |
0.8823 |
0.8684 |
0.8947 |
0.8167 |
0.8673 |
0.900 |
0.9449 |
0.9458 |
0.9495 |
Steel-plates_0 |
0.9451 |
0.7895 |
0.8438 |
0.9713 |
0.7872 |
0.8333 |
0.9317 |
0.8754 |
0.9326 |
Wall-following_3 |
0.9224 |
0.9087 |
0.9316 |
0.4800 |
0.9062 |
0.9384 |
0.9565 |
0.9589 |
0.9643 |
Thyroid_1 |
0.6468 |
0.6522 |
0.6609 |
0.6593 |
0.6721 |
0.6777 |
0.7158 |
0.7112 |
0.7264 |
Ozone |
0.8630 |
0.8636 |
0.8636 |
0.8523 |
0.8421 |
0.8636 |
0.8920 |
0.9146 |
0.9250 |
Figure 3. Accuracy comparison of the three algorithms
图3. 三种算法的Accuracy对比
图3给出了三种方法的Accuracy的对比结果,可以看出本文算法在其中6组数据集中相对其他两种算法均有小提升,但在Wall-following_1和Steel-plates_0数据集中,本文算法的表现力不如DTC方法且略有降低。但由图3知在Wall-following_1数据中虽然其Accuracy略有下降但与F1-measure的进步相比,Accuracy下降的不明显。而在Steel-plates_0数据集中图3和图4结果表明本文算法与原始数据直接进行分类的方法相比在利用KPCA进行预处理时对于特征的提取时可能导致了一些关键信息丢失,减低了多数类的分类准确率以及召回率使得模型整体Accuracy与F1-measure值均比不进行预处理直接分类的方法略低一些。
Figure 4. F1-measure comparison of the three algorithms
图4. 三种算法的F1-measure对比
Figure 5. AUC comparison of the three algorithms
图5. 三种算法的AUC值对比
图4给出了三种算法在F1-measure上的对比结果,可以看出除了上述提到的第六个数据集外,与其他两种方法相比,基于KPCA欠抽样算法在各个数据集上均有所提高。尤其在第2、3、4以及第7个数据集上相对于其他两种方法表现优秀,相对于最低评分平均提升了68%。因此,在F1-measure方面有显著进步,进而进一步验证了本文方法的有效性。
图5给出了三种方法的AUC值对比结果,清楚的观察到相对于其他两种方法,本文方法在这9组数据集上的表现一贯优秀,在每个数据集上均有不同程度的提升。其稳定性可以得出此方法在处理不平衡数据集时能力更强,具有一定的鲁棒性。同时也验证了此方法有效性和稳定性。
5. 结论
本文通过对传统的欠抽样算法不擅长处理的不平衡数据具有的非线性问题进行研究:提出一种基于KPCA的欠抽样算法,根据得到的样本评分进行剔除评分较高的多数类样本,使不平衡数据集的不平衡率尽可能的降低。在此基础上,将9组不同非平衡率的数据集进行欠抽样处理后,采用Logistic Regression分类器模对预处理后的不平衡数据集进行分类预测。实验结果显示,与现有的欠抽样方法相比,本文方法在Accuracy、F1-measure值和AUC值三个方面都有显著提升。然而,在某些数据集中,本文方法在特征提取阶段可能会导致多数类样本的关键信息被删除,从而降低了分类器的整体分类准确度。因此,解决这一问题将成为下一步研究的重点。
基金项目
本文得到了国家自然科学基金项目(32070669)和唐山市人才资助项目(16013601)的支持。
NOTES
*通讯作者。