分类是机器学习的重要一环，支持向量机、随机森林、K近邻等^[1-2]分类方法广泛应用于人工智能领域。这些经典的数据分类模型往往假定待处理数据具有较为均匀的分布特性，然而，在实际的工程应用中，数据往往会出现一类比另一类多的情况，即分类处理的对象是不均衡数据集^[3]，若不对其进行均衡化处理，那么分类器极有可能忽略少数类数据，导致所获得的分类模型不精确或者分类性能下降^[4-5]。

不均衡数据集在生活生产中十分常见,如何对不均衡数据集的少数类样本进行正确分类是多个领域的重要课题^[6]。比如，在工业过程故障检测与诊断领域^[7]，其模式分类的目标是识别出有故障的少数类样本，而有故障的样本数要远远少于正常(无故障)样本数。对这些极度不均衡的数据进行处理，往往会导致分类器偏向多数类样本，而难以得到较好的模式分类结果。类似的情况还有医疗诊断^[8]、网络入侵监测^[9-10]等领域。并且在实际应用中，少数类样本的误(漏)识别代价往往大于多数类样本的误(漏)识别代价。比如，在癌症筛查和诊断^[11]中，对少数类类别(肿瘤)漏报，极有可能延误病人的最佳治疗时间，为病人生命带来不可估量的危害；在网络入侵监测中，正常访问与入侵行为存在严重的类别不均衡，如果不能有效区分入侵与访问，将严重威胁网络安全。基于这些原因，不均衡数据的处理方法在国内外受到广泛关注^[12]。

现阶段，从数据层面进行考虑和从算法层面进行考虑是不均衡数据集处理方法中的两大主要分支。其中，数据层面的处理方法是基于某种规则，通过删减多数类样本或者增加少数类样本来改善原始数据的不均衡比，使样本尽可能地均衡化，方便进行分类模型的训练；算法层面的处理方法主要包括集成学习^[13]和代价敏感学习^[14-15]方法，这些方法通过修改分类算法在数据集上的偏置，使得分类决策向少数类偏移，从而有效提升分类器在不均衡数据集上的分类精度。

自适应综合过采样算法(adaptive synthetic sampling approach，ADASYN)^[16]是一种有代表性的数据层面处理方法。ADASYN基于少数类样本的概率分布对少数类样本进行自适应插值(过采样)，对少数类样本的扩充，以实现数据集的均衡化处理。该方法通过设定插值公式进行人工生成样本，避免了样本的简单随机复制，有效减弱了模型中可能出现的过拟合现象，同时顾及了样本的分布信息，因而在不均衡数据集处理中获得较好的处理结果。然而，虽然ADASYN在对少数类样本进行插值(过采样)处理时在一定程度上考虑了少数类样本周围多数类样本的分布情况，却没有分析和考虑少数类样本间的关联性，存在少数类样本特征信息利用不充分的问题，导致所获得过采样样本并不一定满足少数类样本的本质分布特性，严重时会降低后续分类模型的性能。

本文针对不均衡数据集中少数类样本难以有效分类，现有过采样方法未能充分利用少数类样本间的特征信息的问题，提出一种融合谱聚类的自适应综合采样方法(spectral clustering-fused adaptive synthetic oversampling approach，SCF-ADASYN)。SCF-ADASYN首先采用谱聚类方法对少数类样本进行分析和处理；根据少数类的分布结构，将其聚成若干个簇；再以少数类样本的聚类簇为单位对少数类进行自适应过采样，得到均衡数据集，以用于后续分类器模型训练。最后，在多个不均衡数据集上进行实验，通过搭配多种经典模式分类方法进行模式分类实验，以验证本文所提方法的有效性和性能优越性。

1 相关工作

本节对ADASYN和谱聚类方法进行简单介绍，概述其算法核心思路及主要流程。

1.1 自适应综合过采样

采样是一种常见的数据集预处理方法，它通过增加少数类样本或减少多数类样本改变其不均衡比，从而构造出新的训练数据集，最常见的采样方法包括过采样^[17]和欠采样^[18]方法。

欠采样是一类通过对部分多数类样本进行删减以达到均衡化处理目的的不均衡数据集处理方法，例如：压缩最近邻法、随机删除法。研究表明，欠采样方法在删除样本时会不可避免地丢失信息，因此并未被广泛采用。

与欠采样相比，通过增加少数类样本达到均衡化目的的过采样应用更为广泛。综合少数类过采样技术(synthetic minority oversampling technique，SMOTE)^[19]是一种应用较为广泛的过采样算法。该算法通过线性插值对少数类样本进行过采样，插值空间位于原数据空间，因其具有良好的分类效果和简单易于实施的优势而被广泛应用。然而，研究表明，该方法会导致类别重叠的问题(在多数类样本之间线性插值出一个少数类样本而导致类别重叠)。因而，He等^[16]提出了一种自适应综合过采样方法(adaptive synthetic sampling approach，ADASYN)通过预先判定少数类样本周围多数类的分布情况，对于不同的少数类样本进行自适应插值。

ADASYN算法流程如下：

不均衡度的计算： $d = {m_s}/{m_l}$ ，式中 $d \in (0,1]$ ；若d<d_th(d_th为设定的不均衡度最大阈值)，则：

1)应合成样本数计算： $G = \beta ({m_l} - {m_s})$ ；其中 $\beta \in [0,1]$ 代表加入合成样本后样本的不均衡度。

2)少数类样本的K近邻查找。找出每个x_i(少数类样本)在n维空间的K近邻，同时计算其比率 ${r_i} = {\Delta _i}/K,i = 1,2,\cdots,m$ ， ${x_i}$ 的K近邻中多数类的数目记作 $\Delta_i $ ；

3)对r进行正则化处理： ${\hat r_i} = {r_i}\Bigg/\displaystyle\sum\limits_{i = 1}^{{m_s}} {{r_i}} $ ， ${r_i}$ $\left( {{\displaystyle\sum {\hat r} _i} = {\rm{1}}} \right)$ 为概率分布；

4)计算每个少数类样本应合成的样本数目。每个少数样本 ${x_i}$ 计算应合成的样本数目为 ${g_i} = G \times {\hat r_i}$ ；

5)对于每个少数类样本x_i生成g_i个新样本，步骤如下：

对1~g_i个新样本执行循环：

①在每个待合成的少数类样本x_i周围k个邻居中选择1个少数类样本x_zi；

②依据式(1)插值：

${s_j} = {x_i} + \lambda \times ({x_{zi}} - {x_i})$

(1)

其中(x_zi−x_i)是n维空间的差异向量，λ∈[0,1]。

ADASYN和传统过采样方法(比如SMOTE)相比，最大优势是能够自适应地决定待合成的少数类样本合成的样本数目，避免了简单的随机复制带来的过拟合问题。

1.2 谱聚类

谱图划分问题衍生出了谱聚类^[20]，它将聚类问题转化为无向图的多路划分问题^[21]。样本点用无向图 $G(V,W)$ 中的顶点来指代，用图中边的权重来指代数据点间的相似性度量，图G中顶点的集合为K，图G中边权重的集合为r。以最优化为准则，在此无向图基础上，相同类别的点相似性较高，不同类别的点相似性较低，流程如图1所示。

由Ng、Jordan和Weiss提出的NJW算法^[21]是一种经典的谱聚类算法，给定一批样本维数为l、样本数量为n的样本集 $s = \{ {s_1},{s_2},\cdots,{s_n}\} \in {\Re ^l}$ ，NJW算法流程如下：

1)构造相似性矩阵 ${{A}} \in {\Re ^{n \times n}}$ ，矩阵中元素 ${{ A}_{ij}} = \exp ( - ||{s_i} - {s_j}||)/2{\sigma ^2}$ ，且当i=j时， ${{{A}}_{ii}} = 0$ ；

2)构造度矩阵D，相似性矩阵A的第i行元素值的和是矩阵对角线上的元素 ${{D}}(i,i)$ ；该矩阵主对角线外的其他值均为0。由此构造Laplacian矩阵 ${{L}} = {{{D}}{^{{\rm{ - }}\frac{{\rm{1}}}{{\rm{2}}}}}}{{A}}{{{D}}{^{{\rm{ - }}\frac{{\rm{1}}}{{\rm{2}}}}}}$ ；

3)构造矩阵 ${{X}} = [{x_1},{x_2},\cdots,{x_k}] \in {\Re ^{n \times k}}$ ：特征值分解L，找出L前k个最大特征值对应的特征向量 ${x_1},{x_2},\cdots,{x_i}$ ，然后特征向量按列存储；

4)归一化X的行向量得到矩阵Y， ${{{Y}}_{ij}} = {{{X}}_{ij}}/ {\Bigg(\displaystyle\sum\nolimits_j {{{X}}_{ij}^2} \Bigg)^{1/2}}$ ；

5)空间 $\Re $ 中的样本为矩阵Y所有行向量(样本数量为n，样本维数为k)，采用c-means进行聚类；

6)当且仅当矩阵Y的第i行被划分为第j聚类时，把最初的样本点 ${s_i}$ 划分为第j聚类。

2 融合谱聚类的自适应综合采样算法 2.1 算法的提出

ADASYN算法^[16]在计算插值数目时会计算少数类样本周围的多数类样本的分布情况，从而在分类边界对少数类样本进行自适应采样。然而在少数类样本之间也存在特征信息的关联，如果能充分利用少数类样本间的特征关联信息，再以此决定插值的数目和范围，将会进一步提高不均衡数据集的分类精度^[22]。因此，本文在ADASYN算法的研究现状基础上，提出一种融合谱聚类的自适应综合采样算法(SCF-ADASYN)。

2.2 算法设计

SCF-ADASYN的思路为：先依据公式 $d = {m_s}/{m_l}$ (m_s为多数类样本数，m_l为少数类样本数)求出样本的不均衡度d，以此计算所需的总插值数G，再用谱聚类对少数类数据进行分析，得到k个少数类样本聚类簇，根据每个簇的少数类样本数目分配其插值数，最后以簇为单位根据公式 ${s_j} = {x_i} + ({x_{zi}} - {x_i}) \times \lambda $ 进行样本插值。SCF-ADASYN算法描述如下。

算法　SCF-ADASYN

输入　含有m个样本点{ ${x_i}$ , ${y_i}$ }， $i=1,2, \cdots, m$ 的训练集A, 最大的不均衡容忍度阈值(d_th)，聚类簇数目k。

输出　过采样后的数据集D。

算法实现的主要步骤如下：

1) 不均衡度的计算： $d = {m_s}/{m_l}$ ，式中 $d \in (0,1]$ ；若d<d_th（d_th为一预设阈值），则执行2）；

2) 求出应合成的少数样本数： $G = ({m_l} - {m_s}) \cdot \beta $ ，其中 $\;\beta \in [0,1]$ 表示加入合成样本后的不均衡度；

3) 使用谱聚类方法对少数类样本进行聚类处理，得到k个簇；计算每个少数类样本簇C_i(每个簇的少数类样本数记为n_i, $i=1, 2, \cdots, k$ )之间的样本数比值，并由此比值计算出每个簇的插值数 ${G_i} = \dfrac{{{n_i}}}{{{m_l}}}$ ;

4) 找出每个少数类簇的样本x_i在n维空间的K近邻，计算其比率 ${r_i} = {\Delta _i}/K,i = 1,2,\cdots,m$ ，其中 ${\Delta _i}$ 是 ${x_i}$ 的K近邻中多数类的数目， ${r_i} \in (0,1]$ ；

5) 正则化r： ${\hat r_i} = {r_i}\Bigg/\displaystyle\sum\limits_{i = 1}^{{m_s}} {{r_i}} $ ， ${r_i}$ 实际上为概率分布；

6) 以少数类样本簇为单位插值：

对C₁~C_k执行循环：

①对于少数类簇的每个样本点计算需合成的样本数目， ${g_i} = {\hat r_i} \times {{{G}}_{{i}}}$ ；

②对于每个少数类样本x_i生成g_i步骤如下：

对1~g_i个新样本执行循环：

(a) 在每个待合成的少数类样本x_i周围k个邻居中选择1个少数类样本x_zi；

(b) 依据式(2)进行插值：

${s_j} = {x_i} + \lambda \times ({x_{zi}} - {x_i})$

(2)

式中(x_zi −x_i)是n维空间的差异向量，λ∈[0,1]。

SCF-ADASYN算法流程如图2所示。由于谱聚类使用数据的相似性矩阵的谱执行降维，可以在小数据集上产生高质量的聚类，适用于少数类样本聚类分析，因此SCF-ADASYN在自适应样本插值前利用谱聚类分析少数类样本，SCF-ADASYN在聚类阶段将少数类样本分为簇，时间复杂度为O(n³)；在插值阶段，时间复杂度与聚类簇数正相关，时间复杂度为O(Cn)，其中C是聚类的簇数。因此，整个SCF-ADASYN的时间复杂度为O(n³)。

3 实验

本文实验包括2个部分：1）验证性实验，在选用的不均衡数据集上，对本文提出的SCF-ADASYN进行有效性验证，对比了其相对于未处理以及经ADASYN算法处理的评价结果，分析、讨论本文算法的有效性；2）在多个常见的不均衡数据集上，将本文提出的SCF-ADASYN与SMOTE、ADASYN进行对比，判断本文算法的优劣。

3.1 数据集

表1展示了实验中使用的数据集信息，表中IR为不均衡率，其公式为

$ {\rm{IR}} = \frac{{\text{少数类样本数}}}{{\text{多数类样本数}}} $

数据集Blood中的数据是2007年某地献血情况统计，分为献血与没献血2类。

数据集Pima为凤凰城附近的糖尿病呈阳性的患者分类数据集。

数据集Abalone为鲍鱼数据集，数据集中含有4 177个样本，本文选择其中的“18”作为少数类，选择其中的“9”作为多数类。

数据集Haberman包含病人手术时的多项指标，以此判断病人的状况。

数据集Yeast为酵母数据集，本文选择数据集标签中的CYT和MIT作为多数类，样本数为707，选择EXC类别作为少数类，样本数为37。

Abalone数据集的不均衡比0.061 0，而Haberman数据集的不均衡比是0.395 6，可以判断出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 评价指标

对于少数类数据的分类评价在不均衡数据分类评价中十分重要^[26]。本文用F-measure、G-mean以及AUC^[27]来衡量分类结果。

分类结束后，结果分为4种情况：预测正例、预测负例以及真实正例、真实负例，如表2所示。

将表2中的TP、FP、TN、FN按照模型的评价需求进行组合就构成了常用的评价标准。本文使用的评价标准包括查准率、召回率、G-mean、F值以及AUC。

查准率(Precision)为

${\rm{Precision}} = {\rm{TP}}/({\rm{FP}} + {\rm{TP}})$

该指标表示正确分类的多数类样本与分为多数类的所有样本比值。

召回率(Recall)表示被正确分类的少数类样本与实际少数类样本的比值，其计算公式为

${\rm{Recall}} = {\rm{TP}}/({\rm{TP}} + {\rm{FN}})$

G-mean为查准率和召回率乘积的平方根，它反映出分类器对于多数类和少数类分类的整体能力。因此，采用G-mean准则来评价不均衡数据集总体分类性能十分合理。

总体性能指标G-mean的计算公式为

$ {\rm{G {\text{-}} mean}} = \sqrt {\frac{{{\rm{TP}} \cdot {\rm{TN}}}}{{({\rm{TP}} + {\rm{FN}}) \cdot ({\rm{TN}} + {\rm{FP}})}}}$

通过G-mean的数值来判断分类器的效果，G-mean数值越大说明召回率和查准率越高，效果越好。

F值计算公式为

$ {\rm{F}} {\text{-}} {\rm{measure}} = \frac{{{\rm{Precision}} \times {\rm{Recall}} \times \left( {1 + {\beta ^2}} \right)}}{{{\rm{Precision + }}{\beta ^2} \times {\rm{Recall}}}} $

F-measure计算公式中包含了查准率和召回率，在实验室中多取 $\;\beta = 1$ 。当查准率和召回率同时上升时，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-ADASYN算法能有效地处理数据类不均衡的问题，从而提高分类器的性能。

将本文方法与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值。

F-measure作为召回率和查准率两者的组合，相同的多数类样本查准率下，其数值升高，说明在分类过程中对于少数类样本的分类能力得到提高。

从表4可以看出，对比SVM、RF以及KNN对5个数据集进行模式分类，SCF-ADASYN的F-measure值基本高于ADASYN算法，其中在blood数据集上，使用RF作为分类器的分类性能指标F-measure提高了9.43%，这说明经本文方法处理后，在少数类的分类精度上要优于ADASYN算法。在Blood、Haberman以及Yeast数据集上，本文方法的F-measure值要高于两个经典算法，这是由于谱聚类在样本数量较少、样本属性较大的数据集上聚类效果更好，能更好地细化出少数类样本之间的特征属性，在这种情况下插值得到的均衡数据集少数类样本的分类精度更高。

表5为SMOTE算法、ADASYN算法以及SCF-ADASYN算法在5个数据集上搭配不同分类器的G-mean值。

G-mean为多数类样本分类查准率和少数列样本召回率乘积的平方根，G-mean提升意味着两者同时提升，因此本文整体的分类性能用它来衡量。

如表5所示，经SCF-ADASYN算法处理后，分类器的G-mean有不同程度的提高。其中，在Abalone数据集上，如果采用RF作为模型分类器，基于本文所提出的SCF-ADASYN进行不均衡数据集处理，其模型分类的G-mean要比采用ADASYN算法高3.2%，比SMOTE算法高1.9%。这些结果表明，本文算法与SMOTE以及ADASYN算法相比，分类效果有较大的提高，能够显著提高不同类别的分类精度，具有良好的适应性。

表6为SMOTE算法、ADASYN算法以及SCF-ADASYN算法在5个数据集上搭配不同分类器的AUC值，AUC值大意味着整体分类效果优秀。

由表6可以看出，使用SVM、RF以及KNN对5个数据集进行分类，本文方法的AUC值基本高于SMOTE算法和ADASYN算法，说明经本文方法处理后，模型对于不均衡数据的分类能力有效提升。

上述实验表明，经本文提出的SCF-ADASYN方法处理后，各分类器在各不均衡数据集上的模式分类性能显著提升，表明SCF-ADASYN方法能够有效地处理数据不均衡的问题。

4 结束语

针对不均衡数据中少数类样本难以分类的问题，本文提出了一种融合谱聚类的自适应综合采样方法。该方法利用谱聚类将少数类样本按照特征信息分成若干个簇，有效获取少数类样本的空间结构，在获得少数类样本空间结构的基础上，再以所获得的聚类簇为单位，对少数类样本进行自适应插值，以此解决数据集的不均衡问题。验证性和对比性实验结果表明，不均衡数据集在经本文算法处理后，在传统分类器上均有更好的少数类分类精度。本文方法融合的谱聚类在处理样本数目较少的数据集时有较好的效果，而当样本数目较大时效果下降，怎样能在大样本数据集上取得更好的效果是进一步研究的方向。