【机器学习】面向不均衡数据的融合谱聚类的自适应过采样法

第15卷第4期 智能系统学报 Vol.15 No.4 2020年7月 CAAI Transactions on Intelligent Systems Jul.2020 D0:10.11992tis.201909062 面向不均衡数据的融合谱聚类的自适应过采样法 刘金平'，周嘉铭，贺俊宾2，唐朝晖，徐鹏飞'，张国勇 (1.湖南师范大学智能计算与语言信息处理湖南省重点实验室，湖南长沙410081,2.湖南省计量检测研究院， 湖南长沙410014：3.中南大学自动化学院，湖南长沙410082) 摘要：分类是模式识别领域中的研究热点，大多数经典的分类器往往默认数据集是分布均衡的，而现实中的 数据集往往存在类别不均衡问题，即属于正常/多数类别的数据的数量与属于异常少数类数据的数量之间的差 异很大。若不对数据进行处理往往会导致分类器忽略少数类、偏向多数类，使得分类结果恶化。针对数据的不 均衡分布问题，本文提出一种融合谱聚类的综合采样算法。首先采用谱聚类方法对不均衡数据集的少数类样 本的分布信息进行分析，再基于分布信息对少数类样本进行过采样，获得相对均衡的样本，用于分类模型训 练。在多个不均衡数据集上进行了大量实验，结果表明，所提方法能有效解决数据的不均衡问题，使得分类器 对于少数类样本的分类精度得到提升。 关键词：不自适应综合采样法；不均衡数据集；谱聚类；过采样；模式分类；数据分布；有偏分类器：数据预处理 中图分类号：TP391文献标志码：A文章编号：1673-4785(2020)04-0732-08 中文引用格式：刘金平，周嘉铭，贺俊宾，等.面向不均衡数据的融合谱聚类的自适应过采样法J川.智能系统学报，2020， 15(4):732-739. 英文引用格式：LIU Jinping,ZHOU Jiaming,HE Junbin,et al.Spectral clustering-fused adaptive synthetic oversampling ap- proach for imbalanced data processing Jl.CAAI transactions on intelligent systems,2020,15(4):732-739. Spectral clustering-fused adaptive synthetic oversampling approach for imbalanced data processing LIU Jinping',ZHOU Jiaming',HE Junbin,TANG Zhaohui',XU Pengfei',ZHANG Guoyong (1.Hu'nan Provincial Key Laboratory of Intelligent Computing and Language Information Processing,Hu'nan Normal University, Changsha 410081,China;2.Hu'nan Institute of Metrology and Test,Changsha 410014,China;3.School of Automation,Central South University,Changsha 410082.China) Abstract:Classification is a research hotspot in the field of machine learning.Most classic classifiers assume that the distribution of dataset is generally balanced,while the data set in reality often has a problem of class imbalance.Namely. the number of data belonging to the normal/majority category and the amount of anomaly/minority data vary greatly.If the data is not processed,the classifier will ignore the minority and be biased towards the majority,which deteriorates the classification results.Focusing on the problem of data imbalance,this paper proposes a spectral clustering-fused comprehensive sampling algorithm(SCF-ADASYN).First,the spectral clustering method is employed to analyze the distribution information of the minority-type samples in the imbalanced dataset,and the samples of minority class are oversampled to obtain a relatively balanced dataset,used for the classification model training.A large number of experi- ments have been carried out on multiple unbalanced datasets.The results show that the SCF-ADASYN can effectively improve the imbalance on the data set,and the classification accuracies of the testing classifiers on the unbalanced data set can be significantly improved. Keywords:adaptive synthetic sampling approach(ADASYN);imbalanced data set;spectral clustering;oversampling; pattern classification;data distribution;biased classifier;data pre-processing 收稿日期：2019-09-27. 基金项目：国家自然科学基金项目(61971188,61771492)：国家 分类是机器学习的重要一环，支持向量机、 自然科学基金-广东联合基金重点项目(U1701261): 湖南省自然科学基金项日(2018J3349):湖南省研究 随机森林、K近邻等分类方法广泛应用于人工 生科研创新项目(CX20190415). 通信作者：刘金平.E-mail:jp202518@163.com 智能领域。这些经典的数据分类模型往往假定待

DOI: 10.11992/tis.201909062 面向不均衡数据的融合谱聚类的自适应过采样法 刘金平1 ，周嘉铭1 ，贺俊宾1,2，唐朝晖3 ，徐鹏飞1 ，张国勇3 （1. 湖南师范大学 智能计算与语言信息处理湖南省重点实验室，湖南 长沙 410081; 2. 湖南省计量检测研究院， 湖南 长沙 410014; 3. 中南大学 自动化学院，湖南 长沙 410082） 摘 要：分类是模式识别领域中的研究热点，大多数经典的分类器往往默认数据集是分布均衡的，而现实中的 数据集往往存在类别不均衡问题，即属于正常/多数类别的数据的数量与属于异常/少数类数据的数量之间的差 异很大。若不对数据进行处理往往会导致分类器忽略少数类、偏向多数类，使得分类结果恶化。针对数据的不 均衡分布问题，本文提出一种融合谱聚类的综合采样算法。首先采用谱聚类方法对不均衡数据集的少数类样 本的分布信息进行分析，再基于分布信息对少数类样本进行过采样，获得相对均衡的样本，用于分类模型训 练。在多个不均衡数据集上进行了大量实验，结果表明，所提方法能有效解决数据的不均衡问题，使得分类器 对于少数类样本的分类精度得到提升。 关键词：不自适应综合采样法；不均衡数据集；谱聚类；过采样；模式分类；数据分布；有偏分类器；数据预处理 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2020)04−0732−08 中文引用格式：刘金平, 周嘉铭, 贺俊宾, 等. 面向不均衡数据的融合谱聚类的自适应过采样法 [J]. 智能系统学报, 2020, 15(4): 732–739. 英文引用格式：LIU Jinping, ZHOU Jiaming, HE Junbin, et al. Spectral clustering-fused adaptive synthetic oversampling ap￾proach for imbalanced data processing[J]. CAAI transactions on intelligent systems, 2020, 15(4): 732–739. Spectral clustering-fused adaptive synthetic oversampling approach for imbalanced data processing LIU Jinping1 ，ZHOU Jiaming1 ，HE Junbin1,2 ，TANG Zhaohui3 ，XU Pengfei1 ，ZHANG Guoyong3 (1. Hu’nan Provincial Key Laboratory of Intelligent Computing and Language Information Processing, Hu’nan Normal University, Changsha 410081, China; 2. Hu’nan Institute of Metrology and Test, Changsha 410014, China; 3. School of Automation, Central South University, Changsha 410082, China) Abstract: Classification is a research hotspot in the field of machine learning. Most classic classifiers assume that the distribution of dataset is generally balanced, while the data set in reality often has a problem of class imbalance. Namely, the number of data belonging to the normal/majority category and the amount of anomaly/minority data vary greatly. If the data is not processed, the classifier will ignore the minority and be biased towards the majority, which deteriorates the classification results. Focusing on the problem of data imbalance, this paper proposes a spectral clustering-fused comprehensive sampling algorithm (SCF-ADASYN). First, the spectral clustering method is employed to analyze the distribution information of the minority-type samples in the imbalanced dataset, and the samples of minority class are oversampled to obtain a relatively balanced dataset, used for the classification model training. A large number of experi￾ments have been carried out on multiple unbalanced datasets. The results show that the SCF-ADASYN can effectively improve the imbalance on the data set, and the classification accuracies of the testing classifiers on the unbalanced data set can be significantly improved. Keywords: adaptive synthetic sampling approach (ADASYN); imbalanced data set; spectral clustering; oversampling; pattern classification; data distribution; biased classifier; data pre-processing 分类是机器学习的重要一环，支持向量机、 随机森林、K 近邻等[1-2] 分类方法广泛应用于人工 智能领域。这些经典的数据分类模型往往假定待 收稿日期：2019−09−27. 基金项目：国家自然科学基金项目 (61971188，61771492)；国家 自然科学基金−广东联合基金重点项目 (U1701261)； 湖南省自然科学基金项目 (2018JJ3349)；湖南省研究 生科研创新项目 (CX20190415). 通信作者：刘金平. E-mail：ljp202518@163.com. 第 15 卷第 4 期 智 能 系 统 学 报 Vol.15 No.4 2020 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2020

第4期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·733· 处理数据具有较为均匀的分布特性，然而，在实 少数类样本特征信息利用不充分的问题，导致所 际的工程应用中，数据往往会出现一类比另一类 获得过采样样本并不一定满足少数类样本的本质 多的情况，即分类处理的对象是不均衡数据集)， 分布特性，严重时会降低后续分类模型的性能。 若不对其进行均衡化处理，那么分类器极有可能 本文针对不均衡数据集中少数类样本难以有 忽略少数类数据，导致所获得的分类模型不精确 效分类，现有过采样方法未能充分利用少数类样 或者分类性能下降4。 本间的特征信息的问题，提出一种融合谱聚类的 不均衡数据集在生活生产中十分常见，如何 自适应综合采样方法(spectral clustering-fused ad-. 对不均衡数据集的少数类样本进行正确分类是多 aptive synthetic oversampling approach,SCF-ADA- 个领域的重要课题。比如，在工业过程故障检 SYN)。SCF-ADASYN首先采用谱聚类方法对少 测与诊断领域m,其模式分类的目标是识别出有 数类样本进行分析和处理；根据少数类的分布结 故障的少数类样本，而有故障的样本数要远远少 构，将其聚成若干个簇：再以少数类样本的聚类 于正常（无故障）样本数。对这些极度不均衡的 簇为单位对少数类进行自适应过采样，得到均衡 数据进行处理，往往会导致分类器偏向多数类样 数据集，以用于后续分类器模型训练。最后，在 本，而难以得到较好的模式分类结果。类似的情 多个不均衡数据集上进行实验，通过搭配多种经 况还有医疗诊断1、网络入侵监测0等领域。并 典模式分类方法进行模式分类实验，以验证本文 且在实际应用中，少数类样本的误（漏）识别代价 所提方法的有效性和性能优越性。 往往大于多数类样本的误（漏）识别代价。比如， 在癌症筛查和诊断山中，对少数类类别（肿瘤）漏 1相关工作 报，极有可能延误病人的最佳治疗时间，为病人 生命带来不可估量的危害：在网络入侵监测中， 本节对ADASYN和谱聚类方法进行简单介 正常访问与入侵行为存在严重的类别不均衡，如 绍，概述其算法核心思路及主要流程。 果不能有效区分入侵与访问，将严重威胁网络安 1.1自适应综合过采样 全。基于这些原因，不均衡数据的处理方法在国 采样是一种常见的数据集预处理方法，它通 内外受到广泛关注。 过增加少数类样本或减少多数类样本改变其不均 现阶段，从数据层面进行考虑和从算法层面 衡比，从而构造出新的训练数据集，最常见的采 进行考虑是不均衡数据集处理方法中的两大主要 样方法包括过采样和欠采样图方法。 分支。其中，数据层面的处理方法是基于某种规 欠采样是一类通过对部分多数类样本进行删 则，通过删减多数类样本或者增加少数类样本来 减以达到均衡化处理目的的不均衡数据集处理方 改善原始数据的不均衡比，使样本尽可能地均衡 法，例如：压缩最近邻法、随机删除法。研究表 化，方便进行分类模型的训练；算法层面的处理 明，欠采样方法在删除样本时会不可避免地丢失 方法主要包括集成学习1和代价敏感学习41 信息，因此并未被广泛采用。 方法，这些方法通过修改分类算法在数据集上的 与欠采样相比，通过增加少数类样本达到均 偏置，使得分类决策向少数类偏移，从而有效提 衡化目的的过采样应用更为广泛。综合少数类过 升分类器在不均衡数据集上的分类精度。 采样技术(synthetic minority oversampling tech- 自适应综合过采样算法(adaptive synthetic nique,SMOTE)I9是一种应用较为广泛的过采样 sampling approach,.ADASYN)l是一种有代表性 算法。该算法通过线性插值对少数类样本进行过 的数据层面处理方法。ADASYN基于少数类样 采样，插值空间位于原数据空间，因其具有良好 本的概率分布对少数类样本进行自适应插值（过 的分类效果和简单易于实施的优势而被广泛应 采样)，对少数类样本的扩充，以实现数据集的均 用。然而，研究表明，该方法会导致类别重叠的 衡化处理。该方法通过设定插值公式进行人工生 问题（在多数类样本之间线性插值出一个少数类 成样本，避免了样本的简单随机复制，有效减弱 样本而导致类别重叠)。因而，He等6提出了一 了模型中可能出现的过拟合现象，同时顾及了样 种自适应.综合过采样方法(adaptive synthetic 本的分布信息，因而在不均衡数据集处理中获得 sampling approach,ADASYN)通过预先判定少数 较好的处理结果。然而，虽然ADASYN在对少数 类样本周围多数类的分布情况，对于不同的少数 类样本进行插值（过采样）处理时在一定程度上 类样本进行自适应插值。 考虑了少数类样本周围多数类样本的分布情况， ADASYN算法流程如下： 却没有分析和考虑少数类样本间的关联性，存在 不均衡度的计算：d=m,/,式中d∈(0,1]；若

处理数据具有较为均匀的分布特性，然而，在实 际的工程应用中，数据往往会出现一类比另一类 多的情况，即分类处理的对象是不均衡数据集[3] ， 若不对其进行均衡化处理，那么分类器极有可能 忽略少数类数据，导致所获得的分类模型不精确 或者分类性能下降[4-5]。 不均衡数据集在生活生产中十分常见,如何 对不均衡数据集的少数类样本进行正确分类是多 个领域的重要课题[6]。比如，在工业过程故障检 测与诊断领域[7] ，其模式分类的目标是识别出有 故障的少数类样本，而有故障的样本数要远远少 于正常 (无故障) 样本数。对这些极度不均衡的 数据进行处理，往往会导致分类器偏向多数类样 本，而难以得到较好的模式分类结果。类似的情 况还有医疗诊断[8] 、网络入侵监测[9-10] 等领域。并 且在实际应用中，少数类样本的误 (漏) 识别代价 往往大于多数类样本的误 (漏) 识别代价。比如， 在癌症筛查和诊断[11] 中，对少数类类别 (肿瘤) 漏 报，极有可能延误病人的最佳治疗时间，为病人 生命带来不可估量的危害；在网络入侵监测中， 正常访问与入侵行为存在严重的类别不均衡，如 果不能有效区分入侵与访问，将严重威胁网络安 全。基于这些原因，不均衡数据的处理方法在国 内外受到广泛关注[12]。 现阶段，从数据层面进行考虑和从算法层面 进行考虑是不均衡数据集处理方法中的两大主要 分支。其中，数据层面的处理方法是基于某种规 则，通过删减多数类样本或者增加少数类样本来 改善原始数据的不均衡比，使样本尽可能地均衡 化，方便进行分类模型的训练；算法层面的处理 方法主要包括集成学习[13] 和代价敏感学习[14-15] 方法，这些方法通过修改分类算法在数据集上的 偏置，使得分类决策向少数类偏移，从而有效提 升分类器在不均衡数据集上的分类精度。 自适应综合过采样算法 (adaptive synthetic sampling approach，ADASYN)[16] 是一种有代表性 的数据层面处理方法。ADASYN 基于少数类样 本的概率分布对少数类样本进行自适应插值 (过 采样)，对少数类样本的扩充，以实现数据集的均 衡化处理。该方法通过设定插值公式进行人工生 成样本，避免了样本的简单随机复制，有效减弱 了模型中可能出现的过拟合现象，同时顾及了样 本的分布信息，因而在不均衡数据集处理中获得 较好的处理结果。然而，虽然 ADASYN 在对少数 类样本进行插值 (过采样) 处理时在一定程度上 考虑了少数类样本周围多数类样本的分布情况， 却没有分析和考虑少数类样本间的关联性，存在 少数类样本特征信息利用不充分的问题，导致所 获得过采样样本并不一定满足少数类样本的本质 分布特性，严重时会降低后续分类模型的性能。 本文针对不均衡数据集中少数类样本难以有 效分类，现有过采样方法未能充分利用少数类样 本间的特征信息的问题，提出一种融合谱聚类的 自适应综合采样方法 (spectral clustering-fused ad￾aptive synthetic oversampling approach，SCF-ADA￾SYN)。SCF-ADASYN 首先采用谱聚类方法对少 数类样本进行分析和处理；根据少数类的分布结 构，将其聚成若干个簇；再以少数类样本的聚类 簇为单位对少数类进行自适应过采样，得到均衡 数据集，以用于后续分类器模型训练。最后，在 多个不均衡数据集上进行实验，通过搭配多种经 典模式分类方法进行模式分类实验，以验证本文 所提方法的有效性和性能优越性。 1 相关工作 本节对 ADASYN 和谱聚类方法进行简单介 绍，概述其算法核心思路及主要流程。 1.1 自适应综合过采样 采样是一种常见的数据集预处理方法，它通 过增加少数类样本或减少多数类样本改变其不均 衡比，从而构造出新的训练数据集，最常见的采 样方法包括过采样[17] 和欠采样[18] 方法。 欠采样是一类通过对部分多数类样本进行删 减以达到均衡化处理目的的不均衡数据集处理方 法，例如：压缩最近邻法、随机删除法。研究表 明，欠采样方法在删除样本时会不可避免地丢失 信息，因此并未被广泛采用。 与欠采样相比，通过增加少数类样本达到均 衡化目的的过采样应用更为广泛。综合少数类过 采样技术 (synthetic minority oversampling tech￾nique，SMOTE)[19] 是一种应用较为广泛的过采样 算法。该算法通过线性插值对少数类样本进行过 采样，插值空间位于原数据空间，因其具有良好 的分类效果和简单易于实施的优势而被广泛应 用。然而，研究表明，该方法会导致类别重叠的 问题 (在多数类样本之间线性插值出一个少数类 样本而导致类别重叠)。因而，He 等 [16] 提出了一 种自适应综合过采样方法 (adaptive synthetic sampling approach，ADASYN) 通过预先判定少数 类样本周围多数类的分布情况，对于不同的少数 类样本进行自适应插值。 ADASYN 算法流程如下： 不均衡度的计算： d = ms/ml，式中 d ∈ (0,1] ；若 第 4 期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·733·

·734· 智能系统学报 第15卷 dkd(dh为设定的不均衡度最大阈值)，则： 由Ng、Jordan和Weiss提出的NJW算法2 1)应合成样本数计算：G=Bm-m);其中 是一种经典的谱聚类算法，给定一批样本维数为 Be[0,1]代表加入合成样本后样本的不均衡度。 1、样本数量为n的样本集s={s1,2,…,Sn}∈R,W 2)少数类样本的K近邻查找。找出每个x, 算法流程如下： (少数类样本)在n维空间的K近邻，同时计算其 1)构造相似性矩阵A∈R,矩阵中元素 比率r=△/K,i=1,2,…,m,x的K近邻中多数类的 A=exp(-ls-sD/2r2,且当时，Aa=0; 数目记作△； 2)构造度矩阵D,相似性矩阵A的第1行元 3)对r进行正则化处理：：= (∑= 素值的和是矩阵对角线上的元素D(i,):该矩阵主 对角线外的其他值均为O。由此构造Laplacian矩 为概率分布； 阵L=DAD; 4)计算每个少数类样本应合成的样本数目。每 个少数样本：计算应合成的样本数目为g:=G×: 3)构造矩阵X=[x1,2,…,]∈R:特征值分 5)对于每个少数类样本x,生成8，个新样本， 解L,找出L前k个最大特征值对应的特征向量 步骤如下： x,2,…,x,然后特征向量按列存储； 4)归一化X的行向量得到矩阵Y,Y=X/ 对1~g,个新样本执行循环： 12 ①在每个待合成的少数类样本x周围k个邻 ∑，； 居中选择1个少数类样本x: 5)空间R中的样本为矩阵Y所有行向量（样 ②依据式(1)插值： 本数量为n,样本维数为k),采用c-means进行 si=xi+AX(xi-xi) (1) 聚类； 其中(x-x)是n维空间的差异向量，1∈[0,1]。 6)当且仅当矩阵Y的第i行被划分为第j聚 ADASYN和传统过采样方法（比如SMOTE) 类时，把最初的样本点s:划分为第j聚类。 相比，最大优势是能够自适应地决定待合成的少 数类样本合成的样本数目，避免了简单的随机复 2融合谱聚类的自适应综合采样算法 制带来的过拟合问题。 1.2谱聚类 2.1算法的提出 谱图划分问题衍生出了谱聚类20，它将聚类 ADASYN算法I61在计算插值数目时会计算 问题转化为无向图的多路划分问题四。样本点用 少数类样本周围的多数类样本的分布情况，从而 无向图G(VW中的顶点来指代，用图中边的权重 在分类边界对少数类样本进行自适应采样。然而 来指代数据点间的相似性度量，图G中顶点的集 在少数类样本之间也存在特征信息的关联，如果 合为K,图G中边权重的集合为r。以最优化为 能充分利用少数类样本间的特征关联信息，再以 准则，在此无向图基础上，相同类别的点相似性 此决定插值的数目和范围，将会进一步提高不均 衡数据集的分类精度221。因此，本文在ADA- 较高，不同类别的点相似性较低，流程如图1所示。 SYN算法的研究现状基础上，提出一种融合谱聚 开始 类的自适应综合采样算法(SCF-ADASYN)。 输入待聚类的数据点 2.2算法设计 集和聚类数k 市 SCF-ADASYN的思路为：先依据公式 根据相似性度量构造数据点 d=m/m(m,为多数类样本数，m,为少数类样本 集拉普拉斯矩阵L 数)求出样本的不均衡度d,以此计算所需的总插 选取L的特征值及特征向量. 值数G,再用谱聚类对少数类数据进行分析，得 构造特征向量空间 到k个少数类样本聚类簇，根据每个簇的少数类 使用传统聚类算法对特征向量进 样本数目分配其插值数，最后以簇为单位根据公 行聚类，并对应于原始数据的聚类 式s=:+(x-)×d进行样本插值。SCF-ADA- 输出得到片个簇 SYN算法描述如下。 算法SCF-ADASYN 结束) 输入含有m个样本点{，}，i=1,2,…,m 图1谱聚类算法的一般过程 的训练集A,最大的不均衡容忍度阈值(d),聚类 Fig.1 General process of spectral clustering 簇数目k

d<dth(dth 为设定的不均衡度最大阈值)，则： G = β(ml −ms) β ∈ [0,1] 1 ) 应合成样本数计算： ；其中 代表加入合成样本后样本的不均衡度。 ri = ∆i/K,i = 1,2,··· ,m xi ∆i 2) 少数类样本的 K 近邻查找。找出每个 xi (少数类样本) 在 n 维空间的 K 近邻，同时计算其 比率 ， 的 K 近邻中多数类的 数目记作 ； rˆi = ri /∑ms i=1 ri ri (∑ rˆi = 1 ) 3) 对 r 进行正则化处理： ， 为概率分布； xi gi = G ×rˆi 4) 计算每个少数类样本应合成的样本数目。每 个少数样本 计算应合成的样本数目为 ； 5) 对于每个少数类样本 xi 生成 gi 个新样本， 步骤如下： 对 1~gi 个新样本执行循环： ①在每个待合成的少数类样本 xi 周围 k 个邻 居中选择 1 个少数类样本 xzi； ②依据式 (1) 插值： sj = xi +λ×(xzi − xi) (1) 其中 (xzi−xi ) 是 n 维空间的差异向量，λ∈[0,1]。 ADASYN 和传统过采样方法 (比如 SMOTE) 相比，最大优势是能够自适应地决定待合成的少 数类样本合成的样本数目，避免了简单的随机复 制带来的过拟合问题。 1.2 谱聚类 G(V,W) 谱图划分问题衍生出了谱聚类[20] ，它将聚类 问题转化为无向图的多路划分问题[21]。样本点用 无向图 中的顶点来指代，用图中边的权重 来指代数据点间的相似性度量，图 G 中顶点的集 合为 K，图 G 中边权重的集合为 r。以最优化为 准则，在此无向图基础上，相同类别的点相似性 较高，不同类别的点相似性较低，流程如图 1 所示。 开始 输入待聚类的数据点 集和聚类数 k 根据相似性度量构造数据点 集拉普拉斯矩阵 L 选取 L 的特征值及特征向量， 构造特征向量空间 使用传统聚类算法对特征向量进 行聚类，并对应于原始数据的聚类 结束 输出得到 k 个簇 图 1 谱聚类算法的一般过程 Fig. 1 General process of spectral clustering s = {s1,s2,··· ,sn} ∈ ℜl 由 Ng、Jordan 和 Weiss 提出的 NJW 算法[21] 是一种经典的谱聚类算法，给定一批样本维数为 l、样本数量为 n 的样本集 ，NJW 算法流程如下： A ∈ ℜn×n Ai j = exp(−||si − sj ||)/2σ 2 Aii = 0 1 ) 构造相似性矩阵 ，矩阵中元素 ，且当 i=j 时， ； D(i,i) L = D − 1 2 AD− 1 2 2) 构造度矩阵 D，相似性矩阵 A 的第 i 行元 素值的和是矩阵对角线上的元素 ；该矩阵主 对角线外的其他值均为 0。由此构造 Laplacian 矩 阵 ； X = [x1, x2,··· , xk] ∈ ℜn×k x1, x2,··· , xi 3) 构造矩阵 ：特征值分 解 L，找出 L 前 k 个最大特征值对应的特征向量 ，然后特征向量按列存储； Yi j = Xi j/ (∑ j X 2 i j)1/2 4) 归一化 X 的行向量得到矩阵 Y， ； 5) 空间 ℜ 中的样本为矩阵 Y 所有行向量 (样 本数量为 n，样本维数为 k)，采用 c-means 进行 聚类； si 6) 当且仅当矩阵 Y 的第 i 行被划分为第 j 聚 类时，把最初的样本点 划分为第 j 聚类。 2 融合谱聚类的自适应综合采样算法 2.1 算法的提出 ADASYN 算法[16] 在计算插值数目时会计算 少数类样本周围的多数类样本的分布情况，从而 在分类边界对少数类样本进行自适应采样。然而 在少数类样本之间也存在特征信息的关联，如果 能充分利用少数类样本间的特征关联信息，再以 此决定插值的数目和范围，将会进一步提高不均 衡数据集的分类精度[ 2 2 ]。因此，本文在 ADA￾SYN 算法的研究现状基础上，提出一种融合谱聚 类的自适应综合采样算法 (SCF-ADASYN)。 2.2 算法设计 d = ms/ml sj = xi +(xzi − xi)×λ SCF-ADASY N 的思路为：先依据公式 (ms 为多数类样本数，ml 为少数类样本 数) 求出样本的不均衡度 d，以此计算所需的总插 值数 G，再用谱聚类对少数类数据进行分析，得 到 k 个少数类样本聚类簇，根据每个簇的少数类 样本数目分配其插值数，最后以簇为单位根据公 式 进行样本插值。SCF-ADA￾SYN 算法描述如下。 算法 SCF-ADASYN xi yi 输入 含有 m 个样本点{ , }，i = 1,2,··· ,m 的训练集 A, 最大的不均衡容忍度阈值 (dth)，聚类 簇数目 k。 ·734· 智 能 系 统 学 报 第 15 卷

第4期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·735· 输出过采样后的数据集D。 开始 算法实现的主要步骤如下： 1)不均衡度的计算：d=m,/m,式中de0,1; 输人不平衡数据集 若dkd(d为一预设阈值)，则执行2)： 由多数类少数类比例计算插 2)求出应合成的少数样本数：G=(m-m)B, 值数G 其中B∈[0,1]表示加人合成样本后的不均衡度； 聚 对少数类样本X进行聚类。 3)使用谱聚类方法对少数类样本进行聚类 阶 得到不同的簇 处理，得到k个簇；计算每个少数类样本簇C(每 计算每个簇中样本数的比 个簇的少数类样本数记为n,i=1,2,…,k)之间的 值，确定其插值数g 样本数比值，并由此比值计算出每个簇的插值数 G=m 插 使用插值公式进行插值 值 4)找出每个少数类簇的样本x,在n维空间的 合并多数类与少数类样本 K近邻，计算其比率=△/K,i=1,2,…,m,其中△ 是：的K近邻中多数类的数目，n∈(0,1]： 输出插值完毕的平衡数据集 5)正则化r:= ),n实际上为概率分布； 结束 6)以少数类样本簇为单位插值： 图2融合谱聚类的自适应综合采样算法流程图 对C~C,执行循环： Fig.2 Flowchart of SCF-ADASYN ①对于少数类簇的每个样本点计算需合成的 3.1 数据集 样本数目，g:=×G 表1展示了实验中使用的数据集信息，表中 ②对于每个少数类样本x,生成g,步骤 R为不均衡率，其公式为 如下： 对1g个新样本执行循环： IR= 少数类样本数 多数类样本数 (a)在每个待合成的少数类样本x,周围k个 表1不均衡数据集信息 邻居中选择1个少数类样本x Table 1 List information of imbalanced datasets (b)依据式(2)进行插值： 数据集 样本数属性少数类多数类R S;=&+AX(x4-x) (2) Blood 671 4 219 452 0.4845 式中(x-x)是n维空间的差异向量，1∈[0，]0 Pima 768 8 268 500 0.5350 SCF-ADASYN算法流程如图2所示。由于谱 Abalone 4177 8 为 689 0.0610 聚类使用数据的相似性矩阵的谱执行降维，可以 在小数据集上产生高质量的聚类，适用于少数类 Haberman 306 3 81 225 0.3956 Yeast 1484 707 0.0523 样本聚类分析，因此SCF-ADASYN在自适应样本 插值前利用谱聚类分析少数类样本，SCF-ADA- 数据集Blood中的数据是2007年某地献血情 SYN在聚类阶段将少数类样本分为簇，时间复杂 况统计，分为献血与没献血2类。 度为O(n)；在插值阶段，时间复杂度与聚类簇数 数据集Pima为凤凰城附近的糖尿病呈阳性 正相关，时间复杂度为O(C),其中C是聚类的簇 的患者分类数据集。 数。因此，整个SCF-ADASYN的时间复杂度为On)。 数据集Abalone为鲍鱼数据集，数据集中含 3实验 有4177个样本，本文选择其中的“18”作为少数 类，选择其中的“9”作为多数类。 本文实验包括2个部分：1)验证性实验，在选 数据集Haberman包含病人手术时的多项指 用的不均衡数据集上，对本文提出的SCF-ADA- 标，以此判断病人的状况。 SYN进行有效性验证，对比了其相对于未处理以 数据集Yeast为酵母数据集，本文选择数据 及经ADASYN算法处理的评价结果，分析、讨论 集标签中的CYT和MIT作为多数类，样本数为 本文算法的有效性；：2)在多个常见的不均衡数据 707,选择EXC类别作为少数类，样本数为37。 集上，将本文提出的SCF-ADASYN与SMOTE、 Abalone数据集的不均衡比0.0610，而Haber- ADASYN进行对比，判断本文算法的优劣。 man数据集的不均衡比是0.3956.可以判断出

输出 过采样后的数据集 D。 算法实现的主要步骤如下： 1) 不均衡度的计算： d = ms/ml，式中 d ∈ (0,1] ； 若 d<dth（dth 为一预设阈值），则执行 2）； G = (ml −ms)· β β ∈ [0,1] 2) 求出应合成的少数样本数： ， 其中 表示加入合成样本后的不均衡度； i = 1,2,··· , k Gi = ni ml 3) 使用谱聚类方法对少数类样本进行聚类 处理，得到 k 个簇；计算每个少数类样本簇 Ci (每 个簇的少数类样本数记为 ni , ) 之间的 样本数比值，并由此比值计算出每个簇的插值数 ; ri = ∆i/K,i = 1,2,··· ,m ∆i xi ri ∈ (0,1] 4) 找出每个少数类簇的样本 xi 在 n 维空间的 K 近邻，计算其比率 ，其中 是 的 K 近邻中多数类的数目， ； rˆi = ri /∑ms i=1 5) 正则化 r： ri，ri 实际上为概率分布； 6) 以少数类样本簇为单位插值： 对 C1~Ck 执行循环： gi =rˆi ×Gi ①对于少数类簇的每个样本点计算需合成的 样本数目， ； ②对于每个少数类样 本 x i 生 成 g i 步 骤 如下： 对 1~gi 个新样本执行循环： (a) 在每个待合成的少数类样本 xi 周围 k 个 邻居中选择 1 个少数类样本 xzi； (b) 依据式 (2) 进行插值： sj = xi +λ×(xzi − xi) (2) 式中 (xzi −xi ) 是 n 维空间的差异向量，λ∈[0,1]。 SCF-ADASYN 算法流程如图 2 所示。由于谱 聚类使用数据的相似性矩阵的谱执行降维，可以 在小数据集上产生高质量的聚类，适用于少数类 样本聚类分析，因此 SCF-ADASYN 在自适应样本 插值前利用谱聚类分析少数类样本，SCF-ADA￾SYN 在聚类阶段将少数类样本分为簇，时间复杂 度为 O(n 3 )；在插值阶段，时间复杂度与聚类簇数 正相关，时间复杂度为 O(Cn)，其中 C 是聚类的簇 数。因此，整个 SCF-ADASYN 的时间复杂度为 O(n 3 )。 3 实验 本文实验包括 2 个部分：1）验证性实验，在选 用的不均衡数据集上，对本文提出的 SCF-ADA￾SYN 进行有效性验证，对比了其相对于未处理以 及经 ADASYN 算法处理的评价结果，分析、讨论 本文算法的有效性；2）在多个常见的不均衡数据 集上，将本文提出的 SCF-ADASYN 与 SMOTE、 ADASYN 进行对比，判断本文算法的优劣。 开始 输入不平衡数据集 由多数类少数类比例计算插 值数 G 计算每个簇中样本数的比 值，确定其插值数 g 使用插值公式进行插值 合并多数类与少数类样本 输出插值完毕的平衡数据集 结束 聚 类 阶 段 插 值 阶 段 对少数类样本 X 进行聚类， 得到不同的簇 图 2 融合谱聚类的自适应综合采样算法流程图 Fig. 2 Flowchart of SCF-ADASYN 3.1 数据集 表 1 展示了实验中使用的数据集信息，表中 IR 为不均衡率，其公式为 IR = 少数类样本数 多数类样本数 表 1 不均衡数据集信息 Table 1 List information of imbalanced datasets 数据集 样本数 属性 少数类 多数类 IR Blood 671 4 219 452 0.484 5 Pima 768 8 268 500 0.535 0 Abalone 4177 8 42 689 0.061 0 Haberman 306 3 81 225 0.395 6 Yeast 1484 8 37 707 0.052 3 数据集 Blood 中的数据是 2007 年某地献血情 况统计，分为献血与没献血 2 类。 数据集 Pima 为凤凰城附近的糖尿病呈阳性 的患者分类数据集。 数据集 Abalone 为鲍鱼数据集，数据集中含 有 4 177 个样本，本文选择其中的“18”作为少数 类，选择其中的“9”作为多数类。 数据集 Haberman 包含病人手术时的多项指 标，以此判断病人的状况。 数据集 Yeast 为酵母数据集，本文选择数据 集标签中的 CYT 和 MIT 作为多数类，样本数为 707，选择 EXC 类别作为少数类，样本数为 37。 Abalone 数据集的不均衡比 0.061 0，而 Haber￾man 数据集的不均衡比是 0.395 6，可以判断出 第 4 期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·735·

·736· 智能系统学报 第15卷 Abalone要更加不均衡，选用不同不均衡度的数据 通过G-mean的数值来判断分类器的效果， 集，能直观比较不同不均衡情况下本文方法效果。 G-mean数值越大说明召回率和查准率越高，效果 本实验将在这5个数据集上对SMOTE算 越好。 法、ADASYN算法以及本文的SCF-ADASYN算 F值计算公式为 法进行测试。将3种方法处理过的数据集通过支 Precision x Recallx(1+B2) F-measure 持向量机(support vector machine,SVM)2、随机森 Precision+82 x Recall 林(random forest,.RF)2、K最近邻算法(k-nearest F-measure计算公式中包含了查准率和召回 neighbor,KNN)2等分类器进行分类，按4：1的比 率，在实验室中多取B=1。当查准率和召回率同 率将数据集随机分为训练集和测试集，并运行 时上升时，F-measure才会提升。因此，本文用F- 5次取平均值作为结果，比较分析本文方法的优劣。 measure衡量对于不均衡数据的分类性能。 本文的实验环境为 因为能独立于数据集的类分布，ROC曲线对 1)处理器型号：Inter(R)I5-8300HCPU@ 数据集的不均衡性有很好的鲁棒性，本文使用曲 2.30GHz: 线下面积AUC来代替ROC曲线作为不均衡数据 2)运行内存：8GB: 评价方法，值越大代表分类器的性能表现越优秀。 3)实现语言：Python3.7; 3.3实验结果及分析 4)操作系统：Linux(Ubuntu1:8.04)。 1)验证性实验 3.2评价指标 本文验证性实验选用Pima数据集进行实 对于少数类数据的分类评价在不均衡数据分 验。Pima数据集为印第安人糖尿病数据集，其中 类评价中十分重要261。本文用F-measure、G- 少数类样本268例，多数类样本500例。比较未 mean以及AUC2m来衡量分类结果。 进行均衡化处理、采用ADASYN处理、SMOTE 分类结束后，结果分为4种情况：预测正例、 处理以及SCF-ADASYN算法处理后的Pima数据 预测负例以及真实正例、真实负例，如表2所示。 集，在多个分类器下的分类表现。 表2混淆矩阵 由表3实验结果可知，经SCF-ADASYN算法 Table 2 Confusion matrix 处理后，F-measure,G-mean以及AUC相较于未经 总样本数 采样处理显著提高，说明经本文算法处理后分类 预测正例 预测负例 器整体的分类性能以及对少数类样本的分类精度 真实正例 TP FN 都显著提高。也就是说，本文提出的SCF-ADA- 真实负例 FP TN SYN算法能有效地处理数据类不均衡的问题，从 将表2中的TP、FP、TN、FN按照模型的评价 而提高分类器的性能。 需求进行组合就构成了常用的评价标准。本文使 表3验证性实验结果 用的评价标准包括查准率、召回率、G-mean、F值 Table 3 Experimental results of validation experiments 以及AUC。 分类器 数据层方法 AUC F值 G-mean 查准率(Precision)为 SCF-ADASYN 0.8005 0.7821 0.8004 Precision TP/(FP+TP) ADASYN 0.7817 0.7613 0.7808 该指标表示正确分类的多数类样本与分为多 RF SMOTE 0.7881 0.7412 0.7743 数类的所有样本比值。 召回率(Recall)表示被正确分类的少数类样 未处理 0.70600.7254 0.7265 本与实际少数类样本的比值，其计算公式为 SCF-ADASYN 0.7446 0.7762 0.7393 Recall TP/(TP+FN) ADASYN 0.7481 0.7609 0.7470 G-mean为查准率和召回率乘积的平方根，它 KNN SMOTE 0.7231 0.7123 0.7763 反映出分类器对于多数类和少数类分类的整体能 未处理 0.70540.69510.7155 力。因此，采用G-mean准则来评价不均衡数据 SCF-ADASYN 0.9181 0.82830.8252 集总体分类性能十分合理。 总体性能指标G-mean的计算公式为 ADASYN 0.7793 0.7860 0.7788 SVM SMOTE 0.79560.77530.7414 TP.TN G-mean (TP+FN)·(TN+FP) 未处理 0.70520.6686 0.6565

Abalone 要更加不均衡，选用不同不均衡度的数据 集，能直观比较不同不均衡情况下本文方法效果。 本实验将在这 5 个数据集上对 SMOTE 算 法、ADASYN 算法以及本文的 SCF-ADASYN 算 法进行测试。将 3 种方法处理过的数据集通过支 持向量机 (support vector machine, SVM)[23] 、随机森 林 (random forest, RF)[24] 、K 最近邻算法 (k-nearest neighbor, KNN)[25] 等分类器进行分类，按 4∶1 的比 率将数据集随机分为训练集和测试集，并运行 5 次取平均值作为结果，比较分析本文方法的优劣。 本文的实验环境为 1) 处理器型号： Inter(R)I5-8300H CPU@ 2.30 GHz; 2) 运行内存：8 GB; 3) 实现语言：Python 3.7; 4) 操作系统：Linux(Ubuntu18.04)。 3.2 评价指标 对于少数类数据的分类评价在不均衡数据分 类评价中十分重要[ 2 6 ]。本文用 F-measure、G￾mean 以及 AUC[27] 来衡量分类结果。 分类结束后，结果分为 4 种情况：预测正例、 预测负例以及真实正例、真实负例，如表 2 所示。 表 2 混淆矩阵 Table 2 Confusion matrix 总样本数 预测正例 预测负例 真实正例 TP FN 真实负例 FP TN 将表 2 中的 TP、FP、TN、FN 按照模型的评价 需求进行组合就构成了常用的评价标准。本文使 用的评价标准包括查准率、召回率、G-mean、F 值 以及 AUC。 查准率 (Precision) 为 Precision = TP/(FP+TP) 该指标表示正确分类的多数类样本与分为多 数类的所有样本比值。 召回率 (Recall) 表示被正确分类的少数类样 本与实际少数类样本的比值，其计算公式为 Recall = TP/(TP+FN) G-mean 为查准率和召回率乘积的平方根，它 反映出分类器对于多数类和少数类分类的整体能 力。因此，采用 G-mean 准则来评价不均衡数据 集总体分类性能十分合理。 总体性能指标 G-mean 的计算公式为 G-mean = √ TP·TN (TP+FN)·(TN+FP) 通过 G-mean 的数值来判断分类器的效果， G-mean 数值越大说明召回率和查准率越高，效果 越好。 F 值计算公式为 F-measure = Precision×Recall× ( 1+β 2 ) Precision+β 2 ×Recall β = 1 F-measure 计算公式中包含了查准率和召回 率，在实验室中多取 。当查准率和召回率同 时上升时，F-measure 才会提升。因此，本文用 F￾measure 衡量对于不均衡数据的分类性能。 因为能独立于数据集的类分布，ROC 曲线对 数据集的不均衡性有很好的鲁棒性，本文使用曲 线下面积 AUC 来代替 ROC 曲线作为不均衡数据 评价方法,值越大代表分类器的性能表现越优秀。 3.3 实验结果及分析 1) 验证性实验 本文验证性实验选用 Pima 数据集进行实 验。Pima 数据集为印第安人糖尿病数据集，其中 少数类样本 268 例，多数类样本 500 例。比较未 进行均衡化处理、采用 ADASYN 处理、SMOTE 处理以及 SCF-ADASYN 算法处理后的 Pima 数据 集，在多个分类器下的分类表现。 由表 3 实验结果可知，经 SCF-ADASYN 算法 处理后，F-measure，G-mean 以及 AUC 相较于未经 采样处理显著提高，说明经本文算法处理后分类 器整体的分类性能以及对少数类样本的分类精度 都显著提高。也就是说，本文提出的 SCF-ADA￾SYN 算法能有效地处理数据类不均衡的问题，从 而提高分类器的性能。 表 3 验证性实验结果 Table 3 Experimental results of validation experiments 分类器 数据层方法 AUC F值 G-mean RF SCF-ADASYN 0.800 5 0.782 1 0.800 4 ADASYN 0.781 7 0.761 3 0.780 8 SMOTE 0.788 1 0.741 2 0.774 3 未处理 0.706 0 0.725 4 0.726 5 KNN SCF-ADASYN 0.744 6 0.776 2 0.739 3 ADASYN 0.748 1 0.760 9 0.747 0 SMOTE 0.723 1 0.712 3 0.776 3 未处理 0.705 4 0.695 1 0.715 5 SVM SCF-ADASYN 0.918 1 0.828 3 0.825 2 ADASYN 0.779 3 0.786 0 0.778 8 SMOTE 0.795 6 0.775 3 0.741 4 未处理 0.705 2 0.668 6 0.656 5 ·736· 智 能 系 统 学 报 第 15 卷

第4期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·737· 将本文方法与SMOTE进行比较，3项指标均 算法，这是由于谱聚类在样本数量较少、样本属 有提升，说明本文提出的SCF-ADASYN能够有效 性较大的数据集上聚类效果更好，能更好地细化 提升预处理后分类器的分类精度，相较于SMOTE 出少数类样本之间的特征属性，在这种情况下 具有更好的性能表现。 插值得到的均衡数据集少数类样本的分类精度 而经过SCF-ADASYN处理后，模型的AUC、 更高。 G-mean以及F-measure值相较于搭配ADASYN 表5为SMOTE算法、ADASYN算法以及 的模型分别提高了7.19%、4.67%以及4.08%，说 SCF-ADASYN算法在5个数据集上搭配不同分 明SCF-ADASYN算法相比于ADASYN算法对分 类器的G-mean值。 类的优化程度更高。 表53种采样方法在不同分类器中的G-mean 2)对比性实验 Table 5 G-mean of three comparative sampling methods 表4为SMOTE算法，ADASYN算法以及 数据集 方法 SVM RF KNN SCF-ADASYN算法在5个数据集上搭配不同分 SMOTE 0.69330.7000 0.7409 类器的F-measure值。 Blood ADASYN 0.66080.6776 0.7032 表43种采样方法在不同分类器中的F-measure SCF-ADASYN 0.695 8 0.73880.7413 Table 4 F-measure of three comparative sampling methods SMOTE 0.83100.76950.7929 数据集 方法 SVM RF KNN Pima ADASYN 0.77880.78080.7470 SMOTE 0.7322 0.69860.7354 SCF-ADASYN 0.8152 0.8004 0.7393 Blood ADASYN 0.67760.67540.7287 SMOTE 0.62120.6054 0.6232 SCF-ADASYN 0.700 8 0.73910.7345 Abalone ADASYN 0.63230.6332 0.6474 SMOTE 0.8493 0.7540 0.8075 SCF-ADASYN 0.643 2 0.62650.6513 Pima ADASYN 0.7860 0.7613 0.7609 SMOTE 0.71130.73620.7159 SCF-ADASYN 0.818 1 0.78210.7762 Haberman ADASYN 0.67610.72770.7013 SMOTE 0.39150.38560.3971 SCF-ADASYN0.70590.74380.7127 Abalone ADASYN 0.40250.39460.3715 SMOTE 0.70210.7123 0.6954 SCF-ADASYN0.41210.40650.4042 Yeast ADASYN 0.71640.7033 0.7145 SMOTE 0.76190.7333 0.6913 SCF-ADASYN0.72320.72630.7232 Haberman ADASYN 0.6666 0.7191 0.7021 SCF-ADASYN 0.6966 0.7333 0.6904 G-mean为多数类样本分类查准率和少数列 SMOTE 0.8012 0.80350.7923 样本召回率乘积的平方根，G-mean提升意味着两 Yeast ADASYN 0.7963 0.80110.7352 者同时提升，因此本文整体的分类性能用它来 衡量。 SCF-ADASYN0.80620.81240.8215 如表5所示，经SCF-ADASYN算法处理后， F-measure作为召回率和查准率两者的组合， 分类器的G-mean有不同程度的提高。其中，在 相同的多数类样本查准率下，其数值升高，说明 Abalone数据集上，如果采用RF作为模型分类 在分类过程中对于少数类样本的分类能力得到 器，基于本文所提出的SCF-ADASYN进行不均衡 提高。 数据集处理，其模型分类的G-mean要比采用 从表4可以看出，对比SVM、RF以及KNN ADASYN算法高3.2%，比SMOTE算法高1.9%。 对5个数据集进行模式分类，SCF-ADASYN的F- 这些结果表明，本文算法与SMOTE以及ADA- measure值基本高于ADASYN算法，其中在 SYN算法相比，分类效果有较大的提高，能够显 blood数据集上，使用RF作为分类器的分类性能 著提高不同类别的分类精度，具有良好的适应性。 指标F-measure提高了9.43%，这说明经本文方法 表6为SMOTE算法、ADASYN算法以及 处理后，在少数类的分类精度上要优于ADA- SCF-ADASYN算法在5个数据集上搭配不同分 SYN算法。在Blood、Haberman以及Yeast数据 类器的AUC值，AUC值大意味着整体分类效果 集上，本文方法的F-measure值要高于两个经典 优秀

将本文方法与 SMOTE 进行比较，3 项指标均 有提升，说明本文提出的 SCF-ADASYN 能够有效 提升预处理后分类器的分类精度，相较于 SMOTE 具有更好的性能表现。 而经过 SCF-ADASYN 处理后，模型的 AUC、 G-mean 以及 F-measure 值相较于搭配 ADASYN 的模型分别提高了 7.19%、4.67% 以及 4.08%，说 明 SCF-ADASYN 算法相比于 ADASYN 算法对分 类的优化程度更高。 2) 对比性实验 表 4 为 SMOTE 算法，ADASYN 算法以及 SCF-ADASYN 算法在 5 个数据集上搭配不同分 类器的 F-measure 值。 表 4 3 种采样方法在不同分类器中的 F-measure Table 4 F-measure of three comparative sampling methods 数据集 方法 SVM RF KNN Blood SMOTE 0.732 2 0.698 6 0.735 4 ADASYN 0.677 6 0.675 4 0.728 7 SCF-ADASYN 0.700 8 0.739 1 0.734 5 Pima SMOTE 0.849 3 0.754 0 0.807 5 ADASYN 0.786 0 0.761 3 0.760 9 SCF-ADASYN 0.818 1 0.782 1 0.776 2 Abalone SMOTE 0.391 5 0.385 6 0.397 1 ADASYN 0.402 5 0.394 6 0.371 5 SCF-ADASYN 0.412 1 0.406 5 0.404 2 Haberman SMOTE 0.761 9 0.733 3 0.691 3 ADASYN 0.666 6 0.719 1 0.702 1 SCF-ADASYN 0.696 6 0.733 3 0.690 4 Yeast SMOTE 0.801 2 0.803 5 0.792 3 ADASYN 0.796 3 0.801 1 0.735 2 SCF-ADASYN 0.806 2 0.812 4 0.821 5 F-measure 作为召回率和查准率两者的组合， 相同的多数类样本查准率下，其数值升高，说明 在分类过程中对于少数类样本的分类能力得到 提高。 从表 4 可以看出，对比 SVM、RF 以及 KNN 对 5 个数据集进行模式分类，SCF-ADASYN 的 F￾measur e 值基本高 于 ADASYN 算法，其中 在 blood 数据集上，使用 RF 作为分类器的分类性能 指标 F-measure 提高了 9.43%，这说明经本文方法 处理后，在少数类的分类精度上要优于 ADA￾SYN 算法。在 Blood、Haberman 以及 Yeast 数据 集上，本文方法的 F-measure 值要高于两个经典 算法，这是由于谱聚类在样本数量较少、样本属 性较大的数据集上聚类效果更好，能更好地细化 出少数类样本之间的特征属性，在这种情况下 插值得到的均衡数据集少数类样本的分类精度 更高。 表 5 为 SMOTE 算法、ADASYN 算法以及 SCF-ADASYN 算法在 5 个数据集上搭配不同分 类器的 G-mean 值。 表 5 3 种采样方法在不同分类器中的 G-mean Table 5 G-mean of three comparative sampling methods 数据集 方法 SVM RF KNN Blood SMOTE 0.693 3 0.700 0 0.740 9 ADASYN 0.660 8 0.677 6 0.703 2 SCF-ADASYN 0.695 8 0.738 8 0.741 3 Pima SMOTE 0.831 0 0.769 5 0.792 9 ADASYN 0.778 8 0.780 8 0.747 0 SCF-ADASYN 0.815 2 0.800 4 0.739 3 Abalone SMOTE 0.621 2 0.605 4 0.623 2 ADASYN 0.632 3 0.633 2 0.647 4 SCF-ADASYN 0.643 2 0.626 5 0.651 3 Haberman SMOTE 0.711 3 0.736 2 0.715 9 ADASYN 0.676 1 0.727 7 0.701 3 SCF-ADASYN 0.705 9 0.743 8 0.712 7 Yeast SMOTE 0.702 1 0.712 3 0.695 4 ADASYN 0.716 4 0.703 3 0.714 5 SCF-ADASYN 0.723 2 0.726 3 0.723 2 G-mean 为多数类样本分类查准率和少数列 样本召回率乘积的平方根，G-mean 提升意味着两 者同时提升，因此本文整体的分类性能用它来 衡量。 如表 5 所示，经 SCF-ADASYN 算法处理后， 分类器的 G-mean 有不同程度的提高。其中，在 Abalone 数据集上，如果采用 RF 作为模型分类 器，基于本文所提出的 SCF-ADASYN 进行不均衡 数据集处理，其模型分类的 G-mean 要比采用 ADASYN 算法高 3.2%，比 SMOTE 算法高 1.9%。 这些结果表明，本文算法与 SMOTE 以及 ADA￾SYN 算法相比，分类效果有较大的提高，能够显 著提高不同类别的分类精度，具有良好的适应性。 表 6 为 SMOTE 算法、ADASYN 算法以及 SCF-ADASYN 算法在 5 个数据集上搭配不同分 类器的 AUC 值，AUC 值大意味着整体分类效果 优秀。 第 4 期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·737·

·738· 智能系统学报 第15卷 表63种采样方法在不同分类器中的AUC 参考文献： Table 6 AUC of three sampling methods 数据集 方法 KNN RF SVM [1]LESSMANN S,BAESENS B.SEOW H V.et al.Bench- marking state-of-the-art classification algorithms for credit SCF-ADASYN0.53640.53140.5314 scoring:An update of research[J].European journal of op- Abalone ADASYN 0.50360.5146 0.5213 erational research,2015,247(1):124-36. SMOTE 0.51640.52140.5124 [2]LIU J.HE J,ZHANG W,et al.TCvBsISM:Texture classi- SCF-ADASYN 0.801 4 0.8123 0.8014 fication via B-splines-based image statistical modeling[J]. IEEE access,2018,6(1):76-93. Yeast ADASYN 0.75450.7956 0.7914 [3]翟云，杨炳儒，曲武.不平衡类数据挖掘研究综述).计 SMOTE 0.78820.7923 0.7852 算机科学，2010,37(10)：27-32 SCF-ADASYN0.73400.73940.6998 ZHAI Yun,YANG Bingru,QU Wu.Survey of mining im- balanced datasets[J].Computer science,2010,37(10): Blood ADASYN 0.7094 0.67860.6736 27-32. SMOTE 0.7414 0.7031 0.6976 [4]LIN W C,TSAI C F,HU Y H,et al.Clustering-based un- SCF-ADASYN0.72250.74370.7075 dersampling in class-imbalanced data[J].Information sci- ences.2017,172):409-410. Haberman ADASYN 0.7048 0.7278 0.6809 [5]HE H,GARCIA E A.Learning from imbalanced data[J]. SMOTE 0.71910.73910.7135 IEEE transactions on knowledge data engineering,2009. SCF-ADASYN 0.744 6 0.80050.8154 21(9):1263-84. Pima ADASYN 0.7481 0.78170.7793 [6]LIU J.TANG Z,ZHANG J,et al.Visual perception-based statistical modeling of complex grain image for product SMOTE 0.79880.76950.8322 quality monitoring and supervision on assembly produc- 由表6可以看出，使用SVM、RF以及KNN tion line[J].Plos one,2016,11(3):1-25. [7]刘天羽，李国正，尤鸣宇.不均衡故障诊断数据上的特征 对5个数据集进行分类，本文方法的AUC值基本 高于SMOTE算法和ADASYN算法，说明经本文 选择).小型微型计算机系统，2009,30(5：924-927 LIU Tianyu,LI Guozheng,YOU Mingyu.Feature selec- 方法处理后，模型对于不均衡数据的分类能力有 tion on unbalanced fault diagnosis data[J].Journal of 效提升。 Chinese computer systems,2009,30(5):924-927. 上述实验表明，经本文提出的SCF-ADA- [8]YUAN X,XIE L,ABOUELENIEN M.A regularized en- SYN方法处理后，各分类器在各不均衡数据集上 semble framework of deep learning for cancer detection 的模式分类性能显著提升，表明SCF-ADASYN方 from multi-class,imbalanced training data[J].Pattern re- 法能够有效地处理数据不均衡的问题。 c0 gnition,2018,77(1):160-72. [9]LIU J,HE J,ZHANG W,et al.ANID-SEoKELM:adapt- 4结束语 ive network intrusion detection based on selective en- 针对不均衡数据中少数类样本难以分类的问 semble of kernel ELMs with random features[J].Know- 题，本文提出了一种融合谱聚类的自适应综合采 ledge-based systems,2019,177(1):104-16. 样方法。该方法利用谱聚类将少数类样本按照特 [10]刘金平，张五霞，唐朝晖，等.基于模糊粗糙集属性约简 与GMM-LDA最优聚类簇特征学习的自适应网络入侵 征信息分成若干个簇，有效获取少数类样本的空 检测.控制与决策，2019,34(2)：243-251 间结构，在获得少数类样本空间结构的基础上， 再以所获得的聚类簇为单位，对少数类样本进行 LIU Jinping,ZHANG Wuxia,TANG Zhaohui,et al.Ad- aptive network intrusion detection based on fuzzy rough 自适应插值，以此解决数据集的不均衡问题。验 set-based attribute reduction and GMM-LDA-based op- 证性和对比性实验结果表明，不均衡数据集在经 timal cluster feature learning[J].Control and decision. 本文算法处理后，在传统分类器上均有更好的少 2019,34(2):243-251 数类分类精度。本文方法融合的谱聚类在处理样 [11]FOTOUHI S,ASADI S,KATTAN M W.A comprehens- 本数目较少的数据集时有较好的效果，而当样本 ive data level analysis for cancer diagnosis on imbal- 数目较大时效果下降，怎样能在大样本数据集上 anced data[J].Journal of biomedical informatics,2018, 取得更好的效果是进一步研究的方向。 90(1:1-29

表 6 3 种采样方法在不同分类器中的 AUC Table 6 AUC of three sampling methods 数据集 方法 KNN RF SVM Abalone SCF-ADASYN 0.536 4 0.531 4 0.531 4 ADASYN 0.503 6 0.514 6 0.521 3 SMOTE 0.516 4 0.521 4 0.512 4 Yeast SCF-ADASYN 0.801 4 0.812 3 0.801 4 ADASYN 0.754 5 0.795 6 0.791 4 SMOTE 0.788 2 0.792 3 0.785 2 Blood SCF-ADASYN 0.734 0 0.739 4 0.699 8 ADASYN 0.709 4 0.678 6 0.673 6 SMOTE 0.741 4 0.703 1 0.697 6 Haberman SCF-ADASYN 0.722 5 0.743 7 0.707 5 ADASYN 0.704 8 0.727 8 0.680 9 SMOTE 0.719 1 0.739 1 0.713 5 Pima SCF-ADASYN 0.744 6 0.800 5 0.815 4 ADASYN 0.748 1 0.781 7 0.779 3 SMOTE 0.798 8 0.769 5 0.832 2 由表 6 可以看出，使用 SVM、RF 以及 KNN 对 5 个数据集进行分类，本文方法的 AUC 值基本 高于 SMOTE 算法和 ADASYN 算法，说明经本文 方法处理后，模型对于不均衡数据的分类能力有 效提升。 上述实验表明，经本文提出的 SCF-ADA￾SYN 方法处理后，各分类器在各不均衡数据集上 的模式分类性能显著提升，表明 SCF-ADASYN 方 法能够有效地处理数据不均衡的问题。 4 结束语 针对不均衡数据中少数类样本难以分类的问 题，本文提出了一种融合谱聚类的自适应综合采 样方法。该方法利用谱聚类将少数类样本按照特 征信息分成若干个簇，有效获取少数类样本的空 间结构，在获得少数类样本空间结构的基础上， 再以所获得的聚类簇为单位，对少数类样本进行 自适应插值，以此解决数据集的不均衡问题。验 证性和对比性实验结果表明，不均衡数据集在经 本文算法处理后，在传统分类器上均有更好的少 数类分类精度。本文方法融合的谱聚类在处理样 本数目较少的数据集时有较好的效果，而当样本 数目较大时效果下降，怎样能在大样本数据集上 取得更好的效果是进一步研究的方向。 参考文献： LESSMANN S, BAESENS B, SEOW H V, et al. Bench￾marking state-of-the-art classification algorithms for credit scoring: An update of research[J]. European journal of op￾erational research, 2015, 247(1): 124–36. [1] LIU J, HE J, ZHANG W, et al. TCvBsISM: Texture classi￾fication via B-splines-based image statistical modeling[J]. IEEE access, 2018, 6(1): 76–93. [2] 翟云, 杨炳儒, 曲武. 不平衡类数据挖掘研究综述 [J]. 计 算机科学, 2010, 37(10): 27–32. ZHAI Yun, YANG Bingru, QU Wu. Survey of mining im￾balanced datasets[J]. Computer science, 2010, 37(10): 27–32. [3] LIN W C, TSAI C F, HU Y H, et al. Clustering-based un￾dersampling in class-imbalanced data[J]. Information sci￾ences, 2017, 17(2): 409–410. [4] HE H, GARCIA E A. Learning from imbalanced data[J]. IEEE transactions on knowledge & data engineering, 2009, 21(9): 1263–84. [5] LIU J, TANG Z, ZHANG J, et al. Visual perception-based statistical modeling of complex grain image for product quality monitoring and supervision on assembly produc￾tion line[J]. Plos one, 2016, 11(3): 1–25. [6] 刘天羽, 李国正, 尤鸣宇. 不均衡故障诊断数据上的特征 选择 [J]. 小型微型计算机系统, 2009, 30(5): 924–927. LIU Tianyu, LI Guozheng, YOU Mingyu. Feature selec￾tion on unbalanced fault diagnosis data[J]. Journal of Chinese computer systems, 2009, 30(5): 924–927. [7] YUAN X, XIE L, ABOUELENIEN M. A regularized en￾semble framework of deep learning for cancer detection from multi-class, imbalanced training data[J]. Pattern re￾cognition, 2018, 77(1): 160–72. [8] LIU J, HE J, ZHANG W, et al. ANID-SEoKELM: adapt￾ive network intrusion detection based on selective en￾semble of kernel ELMs with random features[J]. Know￾ledge-based systems, 2019, 177(1): 104–16. [9] 刘金平, 张五霞, 唐朝晖, 等. 基于模糊粗糙集属性约简 与 GMM-LDA 最优聚类簇特征学习的自适应网络入侵 检测 [J]. 控制与决策, 2019, 34(2): 243–251. LIU Jinping, ZHANG Wuxia, TANG Zhaohui, et al. Ad￾aptive network intrusion detection based on fuzzy rough set-based attribute reduction and GMM-LDA-based op￾timal cluster feature learning[J]. Control and decision, 2019, 34(2): 243–251. [10] FOTOUHI S, ASADI S, KATTAN M W. A comprehens￾ive data level analysis for cancer diagnosis on imbal￾anced data[J]. Journal of biomedical informatics, 2018, 90(1): 1–29. [11] ·738· 智 能 系 统 学 报 第 15 卷

第4期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·739· [12]ZHOU P,HU X,LI P,et al.Online feature selecton for ics-based adaptive synthetic sampling approach[J/OL]. high dimensional class-imbalanced data[J].Knowledge- Control and decision:https://doi.org/10.13195/j.kzyjc.2019. based systems,2017,136(15:187-199 1672. [13]QIAN Y,LIANG Y,LI M,et al.A resampling ensemble [23]CHAUHAN V K.DAHIYA K.SHARMA A.Problem- algorithm for classification of imbalance problems[J]. formulations and solvers in linear SVM:a review[J.Arti- Neurocomputing,2014,143(2):57-67. ficial intelligence review,2018.6(1):1-53. [14]LIU M.XU C,LUO Y,et al.Cost-sensitive feature selec- [24]PAUL A,MUKHERJEE D P,DAS P,et al.Improved tion by optimizing F-Measures[J].IEEE transactions on random forest for classification[J].IEEE transactionson image processing,2018,27(3):1323-35. image processing,2018,27(8):4012-24. [15]吴雨茜，王俊丽，杨丽，等.代价敏感深度学习方法研究 [25]ZHANG S,DENG Z,CHENG D,et al.Efficient KNN 综述.计算机科学，2019,46(5少：8-19. classification algorithm for big data[J].Neurocomputing, WU Yuqian,WANG Junli,YANG Li,et al.Survey on 2016,195(26):143-8. cost-sensitive deep learning methods[J].Computer sci- [26]林智勇，郝志峰，杨晓伟.若干评价准则对不平衡数据 ence,2019,46(5):8-19. 学习的影响凹.华南理工大学学报（自然科学版），2010 [16]HE H,BAI Y,GARCIA E A,et al.ADASYN:Adaptive 38(4):147-155. synthetic sampling approach for imbalanced learning[Cl// LIN Zhiyong,HAO Zhifeng,YANG Xiaowei.The influ- Neural Networks.Hong Kong,China,2008,3641-46 ence of several evaluation criteria on unbalanced data [17]AHMAD J,JAVED F,HAYAT M.Intelligent computa- learning[J].Journal of South China University of Techno- tional model for classification of sub-Golgi protein using logy (natural science edition),2010,38(4):147-155. oversampling and fisher feature selection methods[J.Ar- [27]THARWAT A.Classification assessment methods[J].Ap- tificial intelligence in medicine,2017,78(1):14-16. plied computing and informatics,2018,12(1):1-13. [18]LIN WC,TSAI C F,HU Y H,et al.Clustering-based un- 作者简介： dersampling in class-imbalanced data[J].Information sci- 刘金平，副教授，博士，主要研究 ences,2017,17(2):409-410. 方向为智能信息处理。 [19]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 [20们]蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述[.计算机科 学，2008(7)：14-18. 周嘉铭，硕士研究生，主要研究方 CAI Xiaoyan,DAI Guanzhong,YANG Libin.Survey on 向为数据挖掘、模式识别。 spectral clustering algorithms[J].Computer science, 2008(7:14-18. [21]NG A Y,JORDAN M I.WEISS Y.On spectral cluster- ing:Analysis and an algorithm[C]//Proceedings of the Advances in Neural Information Processing Systems. Berkeley,USA,2002:26-34. 贺俊宾，硕士研究生，主要研究方 [22]刘金平，周嘉铭，刘先锋，等.基于聚类簇结构特性的自 向为模式识别、计算机视觉。 适应综合采样法在入侵检测中的应用J/OL].控制与 决策：https://doi..org/10.1n3195j.kzyjc.2019.1672. LIU Jinping,ZHOU Jiaming,LIU Xianfeng,et al.To- ward intrusion detection via cluster-structure characterist-

ZHOU P, HU X, LI P, et al. Online feature selecton for high dimensional class-imbalanced data[J]. Knowledge￾based systems, 2017, 136(15): 187–199. [12] QIAN Y, LIANG Y, LI M, et al. A resampling ensemble algorithm for classification of imbalance problems[J]. Neurocomputing, 2014, 143(2): 57–67. [13] LIU M, XU C, LUO Y, et al. Cost-sensitive feature selec￾tion by optimizing F-Measures[J]. IEEE transactions on image processing, 2018, 27(3): 1323–35. [14] 吴雨茜, 王俊丽, 杨丽, 等. 代价敏感深度学习方法研究 综述 [J]. 计算机科学, 2019, 46(5): 8–19. WU Yuqian, WANG Junli, YANG Li, et al. Survey on cost-sensitive deep learning methods[J]. Computer sci￾ence, 2019, 46(5): 8–19. [15] HE H, BAI Y, GARCIA E A, et al. ADASYN: Adaptive synthetic sampling approach for imbalanced learning[C]// Neural Networks. Hong Kong, China, 2008, 3641−46 [16] AHMAD J, JAVED F, HAYAT M. Intelligent computa￾tional model for classification of sub-Golgi protein using oversampling and fisher feature selection methods[J]. Ar￾tificial intelligence in medicine, 2017, 78(1): 14–16. [17] LIN W C, TSAI C F, HU Y H, et al. Clustering-based un￾dersampling in class-imbalanced data[J]. Information sci￾ences, 2017, 17(2): 409–410. [18] 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. [19] 蔡晓妍, 戴冠中, 杨黎斌. 谱聚类算法综述 [J]. 计算机科 学, 2008(7): 14–18. CAI Xiaoyan, DAI Guanzhong, YANG Libin. Survey on spectral clustering algorithms[J]. Computer science, 2008(7): 14–18. [20] NG A Y, JORDAN M I, WEISS Y. On spectral cluster￾ing: Analysis and an algorithm[C]//Proceedings of the Advances in Neural Information Processing Systems. Berkeley, USA, 2002: 26−34. [21] 刘金平, 周嘉铭, 刘先锋, 等. 基于聚类簇结构特性的自 适应综合采样法在入侵检测中的应用 [J/OL]. 控制与 决策: https://doi.org/10.1n3195/j.kzyjc.2019.1672. LIU Jinping, ZHOU Jiaming, LIU Xianfeng, et al.To￾ward intrusion detection via cluster-structure characterist- [22] ics-based adaptive synthetic sampling approach[J/OL]. Control and decision: https://doi.org/10.13195/j.kzyjc.2019. 1672. CHAUHAN V K, DAHIYA K, SHARMA A. Problem￾formulations and solvers in linear SVM: a review[J]. Arti￾ficial intelligence review, 2018, 6(1): 1–53. [23] PAUL A, MUKHERJEE D P, DAS P, et al. Improved random forest for classification[J]. IEEE transactionson image processing, 2018, 27(8): 4012–24. [24] ZHANG S, DENG Z, CHENG D, et al. Efficient KNN classification algorithm for big data[J]. Neurocomputing, 2016, 195(26): 143–8. [25] 林智勇, 郝志峰, 杨晓伟. 若干评价准则对不平衡数据 学习的影响 [J]. 华南理工大学学报(自然科学版), 2010, 38(4): 147–155. LIN Zhiyong, HAO Zhifeng, YANG Xiaowei. The influ￾ence of several evaluation criteria on unbalanced data learning[J]. Journal of South China University of Techno￾logy (natural science edition), 2010, 38(4): 147–155. [26] THARWAT A. Classification assessment methods[J]. Ap￾plied computing and informatics, 2018, 12(1): 1–13. [27] 作者简介： 刘金平，副教授，博士，主要研究 方向为智能信息处理。 周嘉铭，硕士研究生，主要研究方 向为数据挖掘、模式识别。 贺俊宾，硕士研究生，主要研究方 向为模式识别、计算机视觉。 第 4 期 刘金平，等：面向不均衡数据的融合谱聚类的自适应过采样法 ·739·