基于层次聚类改进SMOTE的过采样方法
来源:用户上传
作者:
摘 要： 针对SMOTE算法在合成少数类新样本时存在的不足，提出了一种基于层次聚类算法改进的SMOTE过采样法H-SMOTE。该算法首先对少数类样本进行层次聚类，其次根据提出的簇密度分布函数，计算各个簇的簇密度，最后在各个簇中利用改进的SMOTE算法进行过采样，提高合成样本的多样性，得到新的平衡数据集。通过对UCI数据集的实验表明，H-SMOTE算法的分类效果得到明显的提升。
关键词： 过采样;少数类;层次聚类;SMOTE
中图分类号： TP301.6 文献标识码： A DOI：10.3969/j.issn.1003-6970.2020.02.044
【Abstract】： For conventional oversampling algorithms， for example， SMOTE， there are several problems such as ignoring within-class imbalances. Based in the comprehensive consideration of within-class imbalance， an oversampling algorithm， which is a hybrid of Aggregation hierarchy clustering and improved SMOTE（H-SMOTE）， is proposed.Firstly， it utilizes the hierarchy clustering to cluster minority class samples. Secondly， according to the proposed cluster density distribution function， the cluster density of each cluster are calculated. Finally， the H-SMOTE algorithm is adopted to oversample on the lines of the location-distant minority class samples in each cluster， the diversity of synthetic samples is improved and a new balanced data set between and within classes is obtained. Experiments on the UCI data sets show that H-SMOTE can effectively improve the classification performance of the classifier for the minority class samples.
【Key words】： Oversampling; Minority class; Aggregation hierarchy clustering; SMOTE
0 引言
不平衡数据集是指数据集中某些类的样本个数明显小于其他类的数据集[1]。在二分类问题中，定义拥有较多样本数量的类别为负类，将样本数量少的类别成为正类[2]。在类不平衡数据集的分类问题中，由于少数类样本的误分代价更大，所以少数类样本比其他类别数据更重要[3]。样本不平衡会带来样本点的空间分布并不能符合真实分布，因此使用SMOTE扩充样本集合时，并不能改变原有样本的分布的外围轮廓特征，这就意味着对分类问题中分类边界的影响比较小。因此，如何有效的解决不平衡数据集的分类问题成为了数据挖掘领域中的重要研究内容。
SMOTE算法[4]是目前常用的过采样方法，可以有效的平衡数据集。但也存在一些问题：该算法无法克服非平衡数据集的数据分布问题，容易产生分布边缘化的问题。由于负类样本的分布决定了其可选择的近邻，如果一个负类样本处在负类样本的边缘，则由这个负类样本和近邻产生的新样本也在边缘，从而无法确定正负类的边界[5]。
对于SMOTE算法存在的问题，Han[6]等人提出了Borderline-SMOTE算法，该算法是对位于分类边界的少数类样本进行过采样，加强对分类边界样本的学习。He[7]等人提出的ADASYN算法根据数据分布自动确定每个少数类样本需要生成新样本的数量，拥有越多多数类邻居的少数类样本生成更多的新样本。相比于SMOTE算法，Borderline- SMOTE和ADASYN算法只對样本的分布进行了细致划分，因此依然存在SMOTE算法出现的问题[8]。
针对以上过采样算法存在的问题，本文提出了H-SMOTE算法。首先，对少数类样本使用层次聚类算法进行聚类;其次，根据本文提出的密度函数计算簇密度;最后，在每个簇中使用改进的 SMOTE 算法（H-SMOTE）进行过采样，得到类间和类内均达到平衡的新数据集，并且合成的少数类样本具有多样性。
1 理论知识
1.1 SMOTE算法
SMOTE算法[4]的基本原理是在近邻少数列样本之间进行线性差值，合成新的少数类样本。具体步骤如下：
（3）将生成的新样本全部加入原始训练数据 中，消除训练数据集的不平衡度。
1.2 层次聚类算法
层次聚类[9]（hierarchical clustering）是一种基于原型的聚类算法，试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可以采用“自顶向下”的分拆策略。层次聚类算法的优势在于，可以通过绘制树状图（dendrogram），帮助我们使用可视化的方式来解释聚类结果。 层次聚类[10]可以分为凝聚（agglomerative）层次聚类和分裂（divsive）层次聚类。分裂层次聚类采用的就是“自顶而下”的思想，先将所有的样本都看作是同一个簇，然后通过迭代将簇划分为更小的簇，直到每个簇中只有一个样本为止。凝聚层次聚类采用的是“自底向上”的思想，先将每一个样本都看成是一个不同的簇，通过重复将最近的一对簇进行合并，直到最后所有的样本都属于同一个簇 为止。
在文本中我们选用的是凝聚层次聚类，在凝聚层次聚类[11]中，判定簇间距离的两个标准方法就是单连接（single linkage）和全连接（complete linkage）。单连接，是计算每一对簇中最相似两个样本的距离，并合并距离最近的两个样本所属簇。全连接，通过比较找到分布于两个簇中最不相似的样本（距离最远），从而来完成簇的合并。
凝聚层次聚类除了通过单连接和全连接来判断两个簇之间的距离之外，还可以通过平均连接（average linkage）和ward连接。使用平均连接时，合并两个簇所有成员间平均距离最小的两个簇。使用ward连接，合并的是使得SSE增量最小的两个簇。
给定要聚类的N的对象以及N*N的距离矩 阵（或者是相似性矩阵）， 层次聚类方法的基本步骤如下：
（1）将每个对象归为一类， 共得到N类，每类仅包含一个对象。类与类之间的距离就是它们所包含的对象之间的距离，这里使用欧氏距离，即
（2）找到最接近的两个类并合并成一类，于是总的类数少了一个。
（3）重新计算新的类与所有旧类之间的距离。
（4）重复第2步和第3步，直到最后合并成一个类为止（此类包含了N个对象）。
2 基于层次聚类改进SMOTE的过采样方法
针对SMOTE等传统过采样算法存在的问题，本文先将SMOTE算法进行改进，并结合层次聚类算法，提出了H-SMOTE过采样算法。
2.1 簇密度分布函数
相比于SMOTE等传统算法，H-SMOTE算法引入簇密度分布函数的定义，因此该算法可以有效解决少数类样本类内不平衡的问题。H-SMOTE 算法在两个相距较远的样本点的连线上不断合成新样本，可以提高合成少数类样本的多样性，为分类器提供更多有效的分类信息。
3 实验设计与结果分析
3.1 数据集
本实验采用UCI数据库中的五个数据集作为实验数据，5个数据集的特征如表1所示：
3.2 评价指标
传统的分类学习方法中，一般采用分类精度作为评价指标，然而对于不平衡数据集，用分类精度来评价分类器的性能是不合理的[13-14]。所以对于不平衡数据集，有新的评价指标，F-value、G-mean等，基本上都是建立在混淆矩阵基础上的。
二分类问题的混淆矩阵如表2所示。其中，TP表示少数类样本判为少数类的数目，TN表示多数类样本判为多数类的数目，FN、FP分别表示判决错误的实际少数类和多数类样本数目。
3.3 实验结果与分析
本文实现了SMOTE、Borderline-SMOTE、ASMOTE、KM-SMOTE、H-SMOTE和SVM算法。将SMOTE、Borderline-SMOTE、ASMOTE、Random- SMOTE算法中的上采样倍数设为同一数值，使用SVM算法[15]進行分类。实验结果如表3、表4所示。
由表3和表4可知，Pima和Ionosphere两个数据集的不平衡程度较高，H-SMOTE和SVM组合算法较其他算法在F-value和G-mean上提升效果明显。主要是数据集不平衡程度较高，存在较多的孤立少数类样本，H-SMOTE算法通过接近度能够选择这些孤立样本，避免孤立点被噪声淹没。Ecoli1和Segment两个数据集的不平衡程度较低，本文改进的算法较其它算法相比，F-value和G-mean也有明显的提升。
以上结果总体来看，本文提出的H-SMOTE过 采样算法可以有效提升分类器对少数类样本的分类 性能。
4 结论
本文针对SMOTE算法合成少数类新样本存在的不足，引入了层次聚类算法，提出一种基于层次聚类改进的SMOTE算法。该算法首先使用层次聚类算法对少数类样本聚类;其次，利用簇密度分布函数计算各个簇的采样权重，最后，使用改进的SMOTE算法合成新的少数类样本。实验结果表明，H-SMOTE算法可以有效地提高分类器的分类性能。
参考文献
Li J， Fong S， Wong R K， et al. Adaptive multi-objective swarm fusion for imbalanced data classification[J]. In-formation Fusion， 2018， 39： 1-24.
Cao Peng， Liu Xiaoli， Zhang Jian， et al. ?2， 1 norm regu-larized multi-kernel based joint nonlinear feature selec- tion and over-sampling for imbalanced data classifica-tion[J]. Neurocomputing， 2017， 234： 38-57.
Bahnsen A C， Aouada D， Stojanovic A， et al. Feature engineering strategies for credit card fraud detection[J]. Expert Systems with Applications An International Jour-nal， 2016， 51（C）： 134-142. Chawlan， V.， Bowyer， K. W. and Hall， L. O. （2002） SMOTE： Synthetie minority over-sampling technique. Journal of Aflificial Intelligence Research， 16（1）， 321- 357.
向鴻鑫， 杨云. 不平衡数据挖掘方法综述[J]. 计算机工程与应用， 2019， 55（4）： 6-21.
Han Hui， Wang Wenyuan， Mao Binghuan. Border-line- SMOTE： A new over-sampling method in imbal-anced data sets learning[C]//International Conference on Intelligent Computing， 2005： 878-887.
He Haibo， Bai Yang， Garcia E A， et al. ADASYN： Adap-tive Synthetic Sampling Approach for Imbalanced Learn-ing[C]// IEEE International Joint Conference on Neural Networks， 2008： 1322-1328.
李军. 不平衡数据学习的研究[D]. 长春： 吉林大学， 2011.
代翔， 黄细凤， 唐瑞， 蒋梦婷， 陈兴蜀， 王海舟， 罗梁. 基于层次聚类的子话题检测算法[J]. 华南理工大学学报（自然科学版）， 2019， 47（08）： 84-95.
王韫烨， 孔珊. 一种基于检测器集层次聚类的免疫否定选择算法[J/OL]. 计算机工程： 1-6[2019-10-23]. http：//kns. cnki.net/kcms/detail/31.1289.TP.20190814.0950.006.html.
钟俊坤. 几种新聚类算法的研究[D]. 西安： 西安电子科技大学， 2014.
王亮， 冶继民. 整合DBSCAN和改进SMOTE的过采样算法[J/OL]. 计算机工程与应用： 1-10[2019-10-23]. http：//kns. cnki.net/kcms/detail/11.2127.TP.20190925.1044.010.html.
Yaxiang G U， Shifei D， 顾亚祥， et al. Advances of Support Vector Machines（SVM）支持向量机研究进展[J]. 计算机科学， 2011， 38（2）： 14-17.
Yang Y， Shan-Ping L I. Instance Importance Based SVM for Solving Imbalanced Data Classification[J]. Pattern Recognition & Artificial Intelligence， 2009.
王和勇， 樊泓坤， 姚正安. SMOTE和Biased-SVM相结合的不平衡数据分类方法[J]. 计算机科学， 2008， 35（5）： 174-176.
转载注明来源:https://www.xzbu.com/8/view-15234674.htm
