2017, Vol. 15
在很多分类问题中，数据集往往是很不平衡的，一些类的样本数目远远高于其他类，这就形成了不平衡学习问题。许多传统的机器学习和数据挖掘算法假设目标类具有相似的先验概率，但是许多现实应用都严重违背了这种假设，如网络入侵检测、欺诈检测、文本分类、风险管理和医学诊断等。从现实应用的角度看，不平衡问题主要体现在两个方面：数据本身的不平衡和外部因素导致的不平衡[1]。
类别不平衡严重影响分类器的预测性能。传统的机器学习方法没有考虑到类别不平衡的问题，易于产生偏向并忽略少数类样本，导致少数类样本被错分[1]。例如，在一个多数类和少数类比例为99的问题中，学习算法为了最小化错误率可能将所有的样本都预测为多数类，这种情况下少数类都被错分。此外，类别不平衡也与代价敏感学习紧密相关。对于一些问题，错分少数类的代价往往高于错分多数类。
目前，不平衡学习的研究已经取得了相当大的进展[2]。目前的解决方法大致可分为3类：基于采样的方法[3]、基于学习的方法(如敏感学习[4])和结合采样和学习的方法[5]。在上述3种方法中，基于采样的方法是最基本的策略，如下采样[2]和上采样[6]。采样方法通过改变样本的数量和分布来平衡不同类的样本，这种方法对于不平衡学习问题往往有较好的效果。上采样对于不平衡学习问题是一种较有效的方法。这种方法利用原始的少数类样本来合成新的少数类样本，从而增加少数类样本数目，平衡样本分布。但是上采样方法的主要问题有两个：一方面，上采样扩大了训练集，导致训练和预测的耗时增加；另一方面，上采样仅仅是复制原始少数类样本，这导致了某些样本的重复，可能会出现过拟合的问题。
本文使用上采样方法解决类别不平衡的二分类问题。目前，很多上采样方法已经被提出，如随机上采样(random over-sample，ROS)、合成少数类上采样技术(synthetic minority over-sampling，SMOTE)[6]、自适应合成采样(adaptive synthetic sampling，ADASYN)[7]和严格合成少数类上采样技术(critical SMOTE，CSMOTE)[5]。本文提出一种基于高斯混合模型的上采样方法来生成新的少数类样本。高斯模型被广泛用于分类或表示数据。因此，本文使用高斯模型来模拟少数类样本的分布，在此基础上合成新的少数类样本。
1 方法 1.1 高斯混合模型高斯混合模型(gaussian mixture model, GMM)是单高斯模型的延伸，能够较好地描述数据的密度分布。GMM假设所有的数据点都是由有限个高斯分布生成的，通常作为概率分布的参数模型使用。对于基于GMM的分类系统，模型训练的主要目的就是估计参数使得高斯混合分布能够较好地匹配训练集中特征向量的分布。GMM的参数主要是在先验模型的基础上使用最大期望算法(expectation maximization，EM)进行估计[8]。GMM可以认为是M个单一高斯概率密度函数的加权平均，其概率密度分布函数为
| $ p\left( x \right) = \sum\limits_{i = 1}^M {{{\rm{\pi }}_i}} N\left( {x|{\mu _i}, {\Sigma _i}} \right). $ |
式中：x为服从高斯混合分布的随机变量；M为高斯分量的数目；πi为第i个高斯分量的权重；N(x|μi, Σi)为第i个高斯分量的概率密度函数；μi、Σi分别为第i个高斯分量的均值和方差。
1.2 主成分分析和核主成分分析主成分分析(principal component analysis，PCA)是常用的线性降维方法，能够有效地从高维数据中提取重要信息[9]。PCA通过线性投影将高维数据映射到低维空间中表示，并期望在所投影的维度上的数据方差最大。PCA追求在降维后最大化保持数据的内在信息，通过在投影方向上的数据方差衡量该方向的重要性。PCA最初被用来分析多元数据，但现在已经被广泛应用到其他方面，如去噪信号、盲源分离和数据压缩等。
核主成分分析(kernel principal component analysis，KPCA)[10]是主成分分析的非线性扩展。PCA从高维空间到低维空间的映射是线性的，对于非线性映射往往无能为力。KPCA通过使用核技巧来实现非线性的降维，被广泛使用于多种领域，如去噪、压缩和结构预测等。
1.3 支持向量机支持向量机(support vector machine，SVM)已被广泛用于多种领域[11]。本文选择使用支持向量机作为基本的学习模型来评估所提出方法的有效性。下面简单介绍支持向量机的基本思想。
给定样本集{(xi, yi)}i=1N，其中xi∈Rd, y∈{+1, －1}，它们分别是第i个样本的特征向量和相对应的标签，而+1和-1分别代表正类和负类的标签。
SVM寻找满足分类要求并拥有最大间隔的划分超平面，即寻找最小化
| $ {y_i}{\cdot}\left ( {{\mathit{\boldsymbol{w}}^{\rm{T}}} \cdot {x_i} + b} \right) \ge 1, i = 1, 2, ..., N. $ |
式中：w为超平面的法向量，‖w‖2是w的欧几里得范数。
本文使用LIBSVM[12]工具构建模型，并选择被广泛使用的高斯核函数K(xi, yi)=e－‖xj－xi‖2/2σ2作为核函数。本文采用LIBSVM软件中基于交叉验证的网格搜索策略优化正则参数和核参数。LIBSVM的最新下载地址为https://www.csie.ntu.edu.tw/~cjlin/libsvm/。
1.4 Tomek links如果两个属于不同类别的样本点都是彼此的最近邻，那么他们就构成了一个Tomek link[13]。记点对(xi, xj)的距离为d(xi, xj), 其中xi∈Smin, xj∈Smax。如果不存在点xk使得d(xi, xk) < d(xi, xj)或d(xj, xk) < d(xi, xj)，那么点对(xi, xj)就是一个Tomek link。如果点对属于Tomek link，则该点对属于噪声或边界点。因此，本文利用Tomek links方法来清洗采样后类间的数据交叠，建立类簇分布良好的训练集，以此提高分类性能。
1.5 提出的方法上采样方法的关键问题是如何生成有效的新的样本。高斯混合模型基于多变量正态分布，假设数据集是多个混合在一起的多元高斯分布，从而用极大似然估计的思想来将数据聚类，达到描述数据分布的目的。尽管高斯混合模型常用于聚类，但其有效地描述了数据的密度分布。此外，在实际应用中高斯混合模型的使用十分广泛，高斯分布很常见，很少出现不符合其假设的应用场景。因此，本文利用该思想，单独对少数类的样本进行聚类，从而得到少数类样本的数据分布。在此基础上，利用得到的模型随机生成新的少数类样本，达到采样的目的。
在整个采样算法中有两个需要注意的问题。首先，在利用高斯混合模型对少数类样本的分布进行模拟之前，需要对样本数据有一定的了解。虽然高斯混合模型并不假设数据集到底是由多少个多元高斯分布叠加而成的，但是如果能够知道这个信息，算法能够更快速准确地学习到数据的结构。总之，能够利用的信息越多，算法的效果就会越好。因此，在使用高斯混合模型对少数类样本进行模拟前应充分了解数据的特性。其次是采样比例的问题。本文采样并不需要达到绝对的平衡。对于不平衡比例较大的数据集，如果采样比例过大，同样会造成分类器性能的降低。因此，对于不同类别比例的数据集，需要采样的数目也不一样。在本文中，使用增长比例来衡量采样的数目。记原始数据集多数类样本与少数类样本的比例为u，上采样后多数类样本与少数类样本的比例为v，则增长比例为
记训练集为S=Smin∪Smax，其中，Smin、Smax分别为少数类的样本集和多数类的样本集。本文提出的方法主要是通过上采样合成新的少数类样本来获得一个相对平衡的训练集，记为Snew。记α为采样系数，控制生成样本的数目。β为置信度，决定生成样本是否可信。
本文提出方法的主要流程如下。
步骤1 利用高斯混合模型对少数类样本Smin进行建模，得到模型Gmodel。生成的模型用于接下来合成样本。
Gmodel←Model(Smin).
步骤2 记少数类样本的数目为Nmin，利用高斯混合模型随机生成新的少数类样本，记采样得到的样本集为
Ssample←Sample(Gmodel, α·Nmin).
步骤3 经过上述的采样本文得到了新的少数类样本，但由于上采样经常会引入数据交叠的问题，因此必须对训练集进行清洗。本文选择Tomek links技术进行清洗，去除由采样引入的数据交叠为
Snew←Tomeklinks(S, Ssample).
1.6 评价指标在处理类别不平衡问题时，衡量性能的指标也有所不同。本文中，使用查准率(precision)、查全率(recall)、F-Measure和G-mean来综合衡量分类器的性能，定义如下：
| $ \begin{array}{l} {\rm{Precision = }}\frac{{{\rm{TP}}}}{{{\rm{TP}}{\rm{ + FP }}}},\\ {\rm{Recall = }}\frac{{{\rm{TP}}}}{{{\rm{TP + FN}}}}{\rm{, }}\\ {{F}}-{\rm{Measure = }}\frac{{{\rm{(1 + }}{\beta ^{\rm{2}}}{\rm{){\cdot}Recall{\cdot}Precision}}}}{{{\beta ^{\rm{2}}}{\rm{{\cdot}Recall + Precision}}}}{\rm{, }}\\ G-{\rm{mean = }}\sqrt {\frac{{{\rm{TP}}}}{{{\rm{TP + FN}}}}{\rm{ \times }}\frac{{{\rm{TN}}}}{{{\rm{TN + FP}}}}} {\rm{.}} \end{array} $ |
式中：β为衡量查准率对查全率相对重要性的系数，通常为1；TP(true positive)、FP(false positive)、TN(true negative)和FN(false negative)分别为正确预测为正类的数目、错误预测为正类的数目、正确预测为负类的数目和错误预测为负类的个数，其性能可用混淆矩阵(confusion matrix)来表示，如图 1所示。
|
图 1 混淆矩阵 Figure 1 Confusiton matrix |
但是上述指标都是基于阈值的，选取不同的阈值可以得到不同的结果。因此本文还使用了另外一种评价指标AUC(area under roc curve)，即ROC(receiver operating characteristic)曲线下的面积。与上述4种指标不同，AUC是与阈值无关的且与分类器的性能成正比，因此本文选择AUC来衡量分类器的总体预测性能。
2 结果与分析 2.1 采样前后特征值比较为了进一步了解本文使用的采样方法，采用KPCA方法对采样前后的数据进行主成分分析。为了更好地展现实验结果，本文使用二维数据进行实验。在该实验中，使用了banana数据集、同心圆数据集和3个高斯分布构成的数据集进行实验。本文分别对采样前后的数据进行KPCA主成分分解，并根据不同的主成分画出等高线图。
在banana数据集上的结果如图 2所示，可以发现在图 1中采样前第1个主成分很好地将数据分成了两部分，第2个主成分将数据分成3部分，而第3个和第4个主成分分别将数据分成:4部分和5部分，与采样后的情况基本一致。对于特征值而言，采样前后基本不变，尤其是第1个主成分，仅仅相差0.02%。
|
图 2 banana数据集采样前后主成分对比 Figure 2 Comparisons of principal components on before-sampling and after-samping banana dataset |
在同心圆数据集上的实验结果如图 3所示。本文发现在同心圆上的结果不同于banana数据集，在采样前后主成分对数据的划分不是完全相同。第1个主成分在采样前后都将数据划分成了两部分，并且特征值也比较接近，两部分的中心分布也比较相似。而在第2个和第3个在采样前将数据分别划分为2部分和3部分，但是在采样后分别将数据划分为3部分和2部分。由此可以发现采样改变了数据的分布，但是特征值还是比较接近的。第4个主成分在采样前后都将数据划分成了4部分，各部分中心的分布也比较相似，特征值变化也不是很大。总体而言，采样前、后有的分布还是比较类似的，没有发生比较大的变化。
|
图 3 同心圆数据集采样前后主成分对比 Figure 3 Comparisons of principal components on before-sampling and after-samping circle datasets |
在3个高斯分布合成的数据集上的实验结果如图 4所示。本文可以很明显地发现在4个主成分上采样前后的分布基本相同，第1个和第2个主成分都将数据很好地划分成了3部分，并且特征值也很相近。而第3个和第4个主成分都将数据划分成了4部分，但是中心位置的分布略有不同。但是就采样前后的比较而言，两个主成分的结果基本相同。
|
图 4 3个高斯分布合成的数据集采样前后主成分对比 Figure 4 Comparisons of principal components on before-sampling and after-samping gaussian datasets |
为了验证本文所提出的方法，使用UCI(university of california, irvine)机器学习库中的一些不平衡数据集来进行实验[5]，数据集及其特性见表 1。
|
表 1 数据集描述 Table 1 Summary description of datasets |
本文将比较几种针对不平衡数据集的方法在上述数据集上的性能，包括SVM方法、CSMOTE方法、随机下采样集成方法(RUSBoost)[14]、HardEnsemble(HE_S)[5]方法及所提出的GOS方法。RUSBoost结合采样和boosting集成方法，是SMOTEBoost[15]的变种方法。SMOTEBoost利用SMOTE合成少数类样本，而RUSBoost则使用了随机下采样来实现样本的平衡。HardEnsemble方法结合了上采样和下采样的方法来减少不同采样带来的负面影响，从而提高分类的性能。
首先，本文考察AUC指标，其结果见表 2。在Yeast1458vs7数据集上，GOS的AUC值高于其他4种方法，但在Yeast1vs7数据集上，GOS的AUC值远远低于其他方法。在其他3种数据集中，GOS的AUC值略优由于CSMOTE，但稍稍低于SVM和HE_S方法。而从多数类和少数类的比例角度来看，GOS方法在比例较低和较高的情况下的AUC值往往较高，而在比例值为14.30的Yeast1vs7数据集上的表现较差。
|
|
表 2 SVM、CSMOTE、RUSBoost和HE_S方法在AUC值上的比较 Table 2 AUC comparisons between SVM, CSMOTE, RUSBoost and HE_S for serveral datasets |
而不同方法在几种数据集上的F-Measure值和G-mean值的比较结果见表 3、4。本文发现GOS方法的F-Measure值优于其他4种方法，尤其在Yeast1vs7数据集上，其结果远远高于其他4种方法。在几种数据集上，GOS方法的F-Measure值最少比其他方法高1%。而对于G-mean值而言，GOS方法在Ecoli3和Yeast1458vs7数据集上高于其他方法，在Yeast1vs7数据集上仅仅低于CSMOTE方法。而在Ecoli数据集中，GOS方法的G-mean值低于RUSBoost和HE_S方法。总体而言，GOS在不同平衡比例的数据集上的F-Measure值有很好的表现，高于其他4种方法，并且在AUC值和G-mean值上也有不俗的表现。而从多数类和少数类的比例角度来看，GOS方法在不同比例数据上都有较好的表现，尤其在比例较高的情况下，该方法的F-Measure值和G-mean值远远高于其他方法。
|
|
表 3 SVM、CSMOTE、RUSBoost和HE_S方法在F-Measure值上的比较 Table 3 F-Measure comparisons between SVM, CSMOTE, RUSBoost and HE_S for serveral datasets |
|
|
表 4 SVM、CSMOTE、RUSBoost和HE_S方法在G-mean值上的比较 Table 4 G-mean comparisons between SVM, CSMOTE, RUSBoost and HE_S for serveral datasets |
本文中，对一个新的上采样方法进行了研究，该方法基于高斯混合模型合成新的少数类样本，在此基础上使用Tomek links技术对新生成的样本进行筛选，最终得到相对平衡的训练集样本。在UCI不平衡数据集上对GOS方法进行实验，并和其他预测方法相比较。实验结果表明, 该方法有助于缓解类不平衡，并提升分类的准确性。
| [1] |
CHAWLA N V, JAPKOWICZ N, KOTCZ A. Editorial: special issue on learning from imbalanced data sets[J]. ACM Sigkdd Explorations Newsletter, 2004, 6(1): 1–6.
DOI:10.1145/1007730.1007733( 0)
|
| [2] |
HE Haibo, GARCIA E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Enginee-ring, 2009, 21(9): 1263–1284.
DOI:10.1109/TKDE.2008.239(0)
|
| [3] |
ESTABROOKS A, JO T, JAPKOWICZ N. A multiple resampling method for learning from Imbalanced data sets[J]. Computational Intelligence, 2004, 20(1): 18–36.
DOI:10.1111/j.0824-7935.2004.t01-1-00228.x(0)
|
| [4] |
ZHOU Zhihua, LIU Xuying. On multi-class cost-sensitive learning[J]. Computational Intelligence, 2010, 26(3): 232–257.
DOI:10.1111/j.1467-8640.2010.00358.x(0)
|
| [5] |
NANNI L, FANTOZZI C, LAZZARINI N. Coupling diffe-rent methods for overcoming the class imbalance problem[J]. Neurocomputing, 2015, 158: 48–61.
DOI:10.1016/j.neucom.2015.01.068(0)
|
| [6] |
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(1): 321–357.
DOI:10.1613/jair.953(0)
|
| [7] |
HE Haibo, BAI Yang, GARCIA E A, et al. ADASYN: Adaptive synthetic sampling approach for imbalanced learning[C]//Proceedings of the 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence). HongKang: IEEE, 2008:1322-1328. DOI: 10.1109/IJCNN.2008.4633969.
(0)
|
| [8] |
ULUKAYA S, ERDEM C E. Gaussian mixture model based estimation of the neutral face shape for emotion recognition[J]. Digital Signal Processing, 2014, 32: 11–23.
DOI:10.1016/j.dsp.2014.05.013(0)
|
| [9] |
周志华. 机器学习[M]. 北京: 清华大学出版社, 2016: 229-232.
ZHOU Zhihua. Machine learning[M]. Beijing: Tsinghua University Press, 2016: 229-232. ( 0)
|
| [10] |
LI Junbao, GAO Huijun. Sparse data-dependent kernel principal component analysis based on least squares support vector machine for feature extraction and recognition[J]. Neural Computing and Applications, 2012, 21(8): 1971–1980.
DOI:10.1007/s00521-011-0600-z(0)
|
| [11] |
DIOSAN L, ROGOZAN A, PECUCHET J P. Improving classification performance of support vector machine by genetically optimising kernel shape and hyper-parameters[J]. Applied Intelligence, 2012, 36(2): 280–294.
DOI:10.1007/s10489-010-0260-1(0)
|
| [12] |
CHANG C C, LIN C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2011, 2(3): 27.
DOI:10.1145/1961189.1961199(0)
|
| [13] |
ZHANG Jing, CAO Peng, GROSS D P, et al. On the application of multi-class classification in physical therapy recommendation[J]. Health Information Science and Systems, 2013, 1(1): 15.
DOI:10.1186/2047-2501-1-15(0)
|
| [14] |
SEIFFERT C, KHOSHGOFTAAR T M, HULSE J V, et al. RUSBoost: A hybrid approach to alleviating class imbalance[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2010, 40(1): 185–197.
DOI:10.1109/TSMCA.2009.2029559(0)
|
| [15] |
CHAWLA N V, LAZAREVIC A, HALL L O, et al. SMOTEBoost: Improving prediction of the minority class in boosting[C]//European Conference on Principles of Data Mining and Knowledge Discovery. Berlin: Springer, 2003:107-119. DOI: 10.1007/978-3-540-39804-2_12.
(0)
|