在不平衡数据分类中, 由于训练集中小类样本数量极少, 不能有效地获得足够多的小类样本规则, 导致传统分类器进行分类时, 整体准确率较低, 尤其难以保证小类样本的分类性能, 不平衡数据分类是数据挖掘领域的难点问题之一[1-2]。另一方面, 在实际的应用中, 例如医疗诊断中[3], 如果将一个病人诊断为正常人, 将耽误及时治疗。又如在电信领域中[4], 若将一个欺诈电话预测为正常电话, 有可能造成巨大的经济损失。所以正确分类小类样本具有重要意义, 加之此类应用非常广泛, 不平衡数据分类问题也是数据挖掘领域的热点问题之一[5-7]。
为了提高小类样本的分类准确率, 许多研究者进行了大量的研究[8-10]。其中, 过抽样技术是提高小类样本分类准确率的有效方法之一。另外, 聚类也是数据挖掘的关键技术之一, 目前有许多方法以及应用方面的研究[11-15]。聚类的主要任务是把训练集中的样本聚成多个簇, 使得相似的样本位于相同的簇中, 不相似的样本位于不同的簇中。在过抽样技术中, 对训练集聚类后, 如果合成的新样本与目标样本位于同一簇内, 则保证了新样本与目标样本的簇内样本尽量相似, 将使得新样本的位置更加合理, 并能尽量减少边界因添加新样本而造成的复杂化。
因此, 本研究提出一种基于聚类的过抽样算法ClusteredSMOTE_Boost, 通过聚类整个训练集和聚类所有的目标样本来确定目标样本的合成个数及其K近邻的选取, 尽量使得新样本的位置更加合理。在10个数据集上进行试验, 并将三种过抽样对比算法SMOTE[16]、ADASYN[17]、BorderlineSMOTE[18]与Boosting技术结合分别记为SMOTE_Boost[19]、ADASYN_Boost与BorderlineSMOTE_Boost。本研究ClusteredSMOTE_Boost算法, 与这三种集成算法进行试验对比, 试验结果表明本研究算法在四种评价度量上均取得较好的试验结果。
1 过抽样技术分析对于不平衡数据的分类研究, 主要有基于算法层面与基于数据层面两种方法。在算法层面上, 提出针对不平衡数据特点的新算法以适应数据的不平衡。在数据层面上, 对训练数据预处理以达到训练数据中各类数据的分布尽量平衡, 其主要手段有欠抽样技术、过抽样技术以及两者的结合。过抽样技术是一种通过添加小类样本的手段达到训练集平衡的技术, 其研究难点是合理确定合成新样本的位置。如果新样本添加的位置不够合理, 则不但造成边界复杂, 而且也容易添加许多无意义且具有干扰作用的新样本, 造成小类的分类性能不高。在添加样本过程中, 影响合成样本位置的因素包括:目标样本的选择, 目标样本合成的个数和目标样本K近邻的选取。以下就这三个方面讨论几种不同的过抽样算法。
(1) 目标样本的选择。SMOTE和Safe level SMOTE[20]将所有小类样本作为目标样本参与合成, 因此这两种算法既合成小类的边界样本又合成小类的内部样本。而BorderlineSMOTE与ADASYN算法将小类的边界样本作为目标样本, 因此只对小类的边界样本参与合成。(2)目标样本权重及合成个数的确定。在SMOTE、Safe level SMOTE和BorderlineSMOTE三个算法中, 每个目标样本的权重相同, 因此每个目标样本合成的个数相同。而在ADASYN算法中, 根据每个目标样本的近邻中大类样本的个数确定其密度, 并根据密度确定权重, 权重越大生成的新样本个数越多。因此, 在此算法中, 越靠近大类的目标样本合成越多的新样本。(3)目标样本的K近邻选取。四种算法均在所有小类样本范围内选取K个近邻, 并从中任选一个与目标样本参与合成。
从上述三个方面可以看出, 过抽样技术容易因添加新样本而造成边界复杂, 且许多新样本不一定是有效的。本研究基于聚类的过抽样算法ClusteredSMOTE_Boost, 在合成样本的三个方面均有创新, 尽量合成较少的边界样本, 且使更多的合成样本的位置合理, 试验结果表明了本研究算法的有效性与可行性。
2 ClusteredSMOTE_Boost算法为了使合成的小类样本更加合理, 本研究提出了基于聚类的过抽样算法ClusteredSMOTE_Boost。首先, 过滤训练集噪声样本, 将其余所有小类样本作为目标样本。其次, 聚类整个训练集, 确定每个簇的合成个数, 从而确定每个目标样本权重及合成个数。最后, 聚类所有的目标样本, 选取目标样本簇内的K个近邻, 任选其中一个近邻样本与目标样本合成新样本, 尽量使新样本与目标样本位于同一簇内。
本研究所有训练集的属性均为连续型数据, 并采用欧几里得距离公式进行距离计算。设训练集中小类样本占总体样本的比例为P, 小类样本整体合成的倍数为β, 训练集聚类后形成簇的个数为n, 第i个簇中目标样本个数为mi, 第i个簇需合成的总个数为Gi。为了使合成新样本后训练集中两类样本的数量大致平衡, 对β设置如下:当P ∈ (0, 0.1], β=7; P ∈ (0.1, 0.2], β=4; P ∈ (0.2, 0.3], β=2; P ∈ (0.3, 0.4], β=1。则第i个簇合成的样本个数Gi=mi×β。目标样本权重不同则合成个数不同, 由每个目标样本的权重及目标样本所在簇需要合成的总个数Gi确定每个目标样本的合成个数。
2.1 目标样本权重及合成个数的确定对训练集聚类, 聚类后簇的特点如下:(1)簇中均是大类样本; (2)簇中均是小类样本; (3)簇中既有大类样本又有小类样本。如果簇中均是大类样本, 则该簇内不合成新样本。如果簇中只有小类样本, 则将簇中所有小类样本作为目标样本参与合成新样本, 并利用目标样本与该簇中心点的距离确定目标样本的权重及合成个数。如果目标样本与中心点的距离越小, 则权重越大, 合成个数越多。如果簇中既有大类样本又有小类样本, 则簇中的所有小类样本作为目标样本参与合成新样本, 但此时目标样本权重的确定方法不同, 本研究先选取目标样本所在簇的K1个小类近邻和K2个大类近邻, 分别计算目标样本与K1个小类近邻的总距离和K2个大类近邻的总距离, 根据两者的比值确定目标样本的权重及合成个数。比值越大, 则目标样本越靠近大类样本边界, 权重越大, 合成个数越多。下面就簇中只有小类样本及簇中既有大类样本又有小类样本的两种情况, 详述目标样本的权重及合成个数的计算。
首先, 对簇中只有小类样本的情况, 确定每个目标样本的权重及合成个数。设当前选中的簇为第i个簇, 簇中第k个目标样本为Xk, 确定Xk的权重与合成个数。
设Xk所在簇的中心点为Yi, Xk与Yi的距离为dk, 样本Xk的权重为Wk, Xk需要合成新样本的个数为gk。按照欧几里得距离公式计算Xk与Yi的距离dk, 权重Wk与合成个数gk计算公式为
| $ {W_k} = \left( {1/{d_k}} \right)/\sum\limits_{k = 1}^{{m_i}} {\left( {1/{d_k}} \right)}, \;\;\;\;{g_k} = {W_k} \times {G_i}, $ |
其中, mi为第i个簇中的目标样本个数。
其次, 对簇中既有小类样本又有大类样本的情况, 确定每个目标样本的权重及合成个数。同样设当前选中的簇为第i个簇, 簇中第k个目标样本为Xk, 确定Xk的权重与合成个数。分别选取Xk的K1个小类样本近邻和K2个大类样本近邻, 设Xk到K1个小类样本近邻的总距离之和为Dk1, Xk到K2个大类样本近邻的总距离之和为Dk2, Xk的权重为Wk。Dk1和Dk2同样按照欧几里得公式计算, 权重Wk与合成个数gk的计算公式为
| $ {W_k} = \left( {{D_k}_1/{D_k}_2} \right)/\sum\limits_{k = 1}^{{m_i}} {\left( {{D_k}_1/{D_k}_2} \right)}, \;\;\;\;{g_k} = {W_k} \times {G_i}。$ |
为了使合成的新样本与目标样本在一个簇内, 合成的新样本更加有意义, 且不造成训练集的两类边界复杂化, ClusteredSMOTE_Boost算法在目标样本的K近邻选取上与其他算法不同。其方法是聚类训练集中所有的目标样本, 形成若干个目标样本的簇, 对各簇中的每个目标样本, 在其所在的簇内选取K个近邻, 并从中任意选取一个近邻样本, 采用与SMOTE算法中同样的合成方法, 将所选的近邻样本与目标样本合成新样本。
ClusteredSMOTE_Boost算法将上述的过抽样方法与Boosting技术结合, 采用C4.5算法建立若干个弱分类器, 集成多个弱分类器形成强分类器后进行分类。定义N表示抽取率, 每次根据抽取率N选取样本进行过抽样并建立弱分类器。其具体步骤如下:
(1) 对原始训练集所有数据的权重初始化;
(2) 根据权重的排序从原始数据集中选择抽取率N的样本, 组成子训练集;
(3) 对步骤(2)中的子训练集采用ClusteredSMOTE_Boost算法合成新样本, 形成新的训练集;
(4) 采用C4.5算法在新训练集上建立弱分类器;
(5) 对原始训练集进行分类, 根据分类结果更新训练集中所有数据的权重;
(6) 重复步骤(2)、(3)、(4)、(5), 建立多个弱分类器;
(7) 将多个弱分类器集成形成一个强分类器。
3 试验设计与分析本研究在10个UCI数据集上, 利用weka平台进行试验, 本研究算法ClusteredSMOTE_Boost与其他三种算法SMOTE_Boost、ADASYN_Boost、BorderlineSMOTE_Boost进行试验对比, 所有算法均采用了Boosting分类技术, 并使用不平衡数据分类的常用评价度量评价本研究算法在小类分类性能上的优势。
3.1 评价度量本研究采用四种评价度量OA(整体准确率)、F-measure、G-mean和AUC (ROC曲线下方的面积)作为算法评价的指标。分类器的混淆矩阵中, 正类代表数据集中的小类, 负类代表数据集中的大类。TP为被预测为正类的正类样本个数, TN为被预测为负类的负类样本个数, FP为被预测为正类的负类样本个数, FN为被预测为负类的正类样本个数。各评价度量的计算公式为:
| $ \begin{array}{l} {\rm{OA}} = \left( {{\rm{TP}} + {\rm{TN}}} \right)/\left( {{\rm{TP}} + {\rm{TN}} + {\rm{FP}} + {\rm{FN}}} \right), \\ {\rm{recall}} = {\rm{TP}}/\left( {{\rm{TP}} + {\rm{FN}}} \right), \\ {\rm{precision}} = {\rm{TP}}/\left( {{\rm{TP}} + {\rm{FP}}} \right), \\ {\rm{F}} - {\rm{measure}} = \frac{{2*{\rm{recall}}*{\rm{precision}}}}{{{\rm{recall}} + {\rm{precision}}}}, \\ {\rm{G}} - {\rm{mean}} = \sqrt {\frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FN}}}}*\frac{{{\rm{TN}}}}{{{\rm{TN}} + {\rm{FP}}}}} 。\end{array} $ |
表 1为各算法所选取的10个连续型的UCI数据集, 表 1中显示了每个数据集所包含的样本总个数、小类样本个数、属性个数以及各数据集中两类样本各占总体样本的比例。各算法仅处理数据集为两类的情况, 对于多类的数据集将其转化为两类问题进行。
|
表 1 UCI数据集 Table 1 Datasets of UCI |
试验中, 近邻选取的个数均设为5, 聚类中簇的个数设为6, 弱分类器为C4.5, 弱分类器个数设为10, 每一次从原始数据集中抽取80%的样本进行过抽样并建立弱分类器。表 2~5均是采用十折交叉法在各数据集各度量上得到的试验结果, 表中加粗的数据表示同个数据集下分类性能最佳的结果。
|
|
表 2 4种算法的OA值对比 Table 2 OA comparison of four algorithms |
|
|
表 3 4种算法的F-measure值对比 Table 3 F-measure comparison of four algorithms |
|
|
表 4 4种算法的G-mean值对比 Table 4 G-mean comparison of four algorithms |
|
|
表 5 4种算法的AUC值对比 Table 5 AUC comparison of four algorithms |
试验中的3个过抽样对比方法分别为SMOTE、ADASYN和BorderlineSMOTE, 其中SMOTE方法对每个小类样本进行合成新样本, 并与其K近邻中任选一个样本采用“线性插值”的方法合成新样本。ADASYN方法对每个小类样本根据其近邻中大类样本的个数进行排序, 使近邻中大类越多的小类样本合成的新样本数目越多。BorderlineSMOTE方法把小类样本区域分为3个子区域:噪声区域、边界区域和内部区域, 仅采用边界区域的小类样本参与合成新样本, 并且每个参与合成的小类样本合成的新样本个数相同。
表 2为各算法在10个数据集整体准确率OA度量上的试验结果。由表 2可以看出, ClusteredSMOTE_Boost算法在所有数据集取得一致好的试验结果, 并且在10个数据集的平均值上高出其他算法超过1%。表 3为各算法在10个数据集F-measure度量上的试验结果。由表 3可以看出, ClusteredSMOTE_Boost算法在8个数据集上取得比其他算法均有优势的试验结果, 并且在10个数据集的平均值上高出其他算法几乎2%。表 4为各算法在10个数据集G-mean度量上的试验结果, 由表 4可以看出, ClusteredSMOTE_Boost算法在6个数据集均比其他算法占优势, 且在10个数据集的平均值有明显的优势。表 5为各算法在10个数据集AUC度量上的试验结果, 由表 5可以看出, ClusteredSMOTE_Boost算法在7个数据集以及在10个数据集的平均值均有优势。由各表的试验结果可以得出, ClusteredSMOTE_Boost算法不仅整体准确率高, 而且小类的分类性能也比其他三种算法具有明显的优势。
4 结语在合成新样本的过程中, 如果目标样本的权重以及目标样本的近邻的确定方法不当, 容易造成新样本位置不够合理, 导致新样本意义不大, 甚至使新训练集两类的边界更加复杂。本研究提出基于聚类的过抽样算法ClusteredSMOTE_Boost, 聚类训练集确定目标样本的类型。如果目标样本不是小类的边界样本, 则根据目标样本与所在簇的中心点的距离确定其权重和合成个数, 尽量在各簇的中心合成较多的新样本。如果目标样本是小类的边界样本, 则根据目标样本与大类的距离确定其权重和合成个数, 尽量使越靠近大类边界的目标样本合成更多的新样本。同时, 聚类所有的目标样本, 在目标样本所在簇内选取近邻, 并与目标样本合成新样本, 以尽量保证合成的新样本与目标样本位于同一个簇内, 减少训练集两类边界因添加新样本而造成的复杂化。试验结果表明ClusteredSMOTE_Boost算法的过抽样技术对提高小类分类性能是有效的。
| [1] | WANG S, YAO X. Multi-class imbalance problems: analysis and potential solutions[J]. IEEE Transactions on Systems Man & Cybernetics: Part B, 2012, 42(4): 1119-1130 |
| [2] | HE H, GARCIA E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge & Data Engineering, 2009, 21(9): 1263-1284 |
| [3] | KUMAR M, BHUTANI K, AGGARWAL S. Hybrid model for medical diagnosis using neutrosophic cognitive maps with genetic algorithms[C]//IEEE International Conference on Fuzzy Systems. Istanbul, Turkey: IEEE, 2015: 1-7. |
| [4] | SRIVASTAVA A, KUNDU A, SURAL S, et al. Credit card fraud detection using hidden Markov model[J]. IEEE Transactions on Dependable & Secure Computing, 2008, 5(1): 37-48 |
| [5] | LI J, FONG S, MOHAMMED S, et al. Improving the classification performance of biological imbalanced datasets by swarm optimization algorithms[J]. Journal of Supercomputing, 2016, 72(10): 3708-3728 DOI:10.1007/s11227-015-1541-6 |
| [6] |
杨明, 尹军梅, 吉根林. 不平衡数据分类方法综述[J].
南京师范大学学报(工程技术版), 2008, 8(4): 7-12 YANG Ming, YIN Junmei, JI Genlin. Classification methods on imbalanced data: a survey[J]. Journal of Nanjing Normal University(Engineering and Technology Edition), 2008, 8(4): 7-12 |
| [7] | SUN Z, SONG Q, ZHU X, et al. A novel ensemble method for classifying imbalanced data[J]. Pattern Recognition, 2015, 48(5): 1623-1637 DOI:10.1016/j.patcog.2014.11.014 |
| [8] | SAEZ J A, LUENGO J, STEFANWSKI J, et al. SMOTE—IPF: addressing the noisy and borderline examples problem in imbalanced classification by a re-sampling method with filtering[J]. Information Sciences, 2015, 291(5): 184-203 |
| [9] | RAMENTOL E, CABALLERO Y, BELLO R, et al. SMOTE-RSB*: a hybrid preprocessing approach based on oversampling and under sampling for high imbalanced data-sets using SMOTE and rough sets theory[J]. Knowledge & Information Systems, 2012, 33(2): 245-265 |
| [10] | BARUA S, ISLAM M M, YAO X, et al. MWMOTE: majority weighted minority over sampling technique for imbalanced data set learning[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(2): 405-425 |
| [11] | BORAL A, CYGAN M, KOCIUMAKA T, et al. A fast branching algorithm for cluster vertex deletion[J]. Theory of Computing Systems, 2016, 58(2): 357-376 DOI:10.1007/s00224-015-9631-7 |
| [12] | FOMIN S, GRIGORIEV D, KOSHEVOY G. Subtraction-free complexity, cluster transformations, and spanning trees[J]. Foundations of Computational Mathematics, 2016, 16(1): 1-31 DOI:10.1007/s10208-014-9231-y |
| [13] | DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1979, 1(2): 224 |
| [14] | ZENG H J, HE Q C, CHEN Z, et al. Learning to cluster web search results[C]//International ACM SIGIR Conference on Research and Development in Information Retrieval. Sheffield, UK: ACM, 2004: 210-217. |
| [15] |
胡小生, 张润晶, 钟勇. 一种基于聚类提升的不平衡数据分类算法[J].
集成技术, 2014(2): 35-41 HU Xiaosheng, ZHANG Runjing, ZHONG Yong. A clustering-based enhanced classification algorithm for imbalanced data[J]. Journal of Integration Technology, 2014(2): 35-41 |
| [16] | CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2011, 16(1): 321-357 |
| [17] | HE H, BAI Y, GARCIA E A, et al. ADASYN: adaptive synthetic sampling approach for imbalanced learning[C]//IEEE International Joint Conference on Neural Networks. Hoboken, USA: IEEE, 2008: 1322-1328. |
| [18] | HAN H, WANG W Y, MAO B H. Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning[J]. Lecture Notes in Computer Science, 2005, 3644(5): 878-887 |
| [19] | CHAWLA N V, LAZAREVIC A, HALL L O, et al. SMOTEBoost: improving prediction of the minority class in boosting[J]. Lecture Notes in Computer Science, 2003, 2838: 107-119 DOI:10.1007/b13634 |
| [20] | BUNKHUMPORNPAT C, SINAPIROMSARAN K, LURSINSAP C. Safe-Level-SMOTE: safe-level-synthetic minority over-sampling technique for handling the class imbalanced problem[C]//Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Berlin, Germany: Springer, 2009: 475-482. |