基于谱聚类的不平衡数据欠采样方法研究*

杨晓月

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

在机器学习和数据挖掘领域中，分类问题是其中一个比较重要的研究方向。传统的分类方法有K近邻、支持向量机、决策树、贝叶斯网络、神经网络等［1～3］，这些方法为数据挖掘技术提供了丰富的理论和技术基础。但是在实际生活中，由于数据的真实性问题会导致传统的分类方法失效，数据样本的不平衡就是其中一个亟待解决的问题。

不平衡问题普遍存在于很多领域，例如：在医学检测［4］领域，检测诊断病人是否患癌症，患者属于少数类，若将患癌症的患者误诊断为健康，那么会使患者错过最佳的治疗时间；在互联网入侵检测［5］领域，入侵的样本数远少于正常访问的样本数，若将网络入侵判别为正常访问，那么会导致系统受到外界侵害；故障诊断［6］领域，机器故障属于少数类，若将故障诊断为正常，可能会带来不必要的损失等。在这些应用中，数据集中某个类别的样本数可能会远多于其他类别，其中真正有价值的信息集中在那一小部分数据，仅占全部数据的一小部分。在这种情况下，传统的分类方法通常会倾向于将测试样本判别为多类，对少类的识别率很低，这导致得到的分类器在少类上的分类效果很差，对少类的错分代价是非常大的［7］。

总而言之，传统分类算法并不适合直接用于对不平衡数据进行分类，研究如何让分类算法更加关注少类样本，提升少数类的分类准确率，对于不平衡数据在实际生产生活中的应用具有重要科学意义。

2 基于谱聚类的欠采样方法

目前处理不平衡问题的方法主要分为两类，一类是在数据层面上，通过欠采样（under-sampling）或过采样（over-sampling）的方法平衡类别分布，欠采样方法可以提升模型对少类样本的分类性能，但是这种方法会造成多类样本数据的信息丢失，而使得模型无法充分利用已有的信息［8］。传统的过采样方法可以生成少类样本的数据，但是只是基于当前少数类蕴含的信息，缺乏数据多样性，一定程度上会造成过拟合。另一类是在算法层面上，修改已有的分类算法或者提出新的算法。集成学习［9］、代价敏感学习［10］、单类学习［11］等，是处理不平衡数据集的常见算法。其中，集成学习通过集成多个分类器，来避免单个分类器对不平衡数据分类预测造成的偏差。代价敏感学习是在算法迭代过程中，设置少数类被错分时具有较高的代价损失，通常与集成学习算法组合使用。

随机欠采样方法是欠采样中常用的方法之一，它通过随机地删除多类样本来降低数据集的不平衡程度，但是这种方法可能会丢失有价值的信息。本文针对这一问题，提出一种基于谱聚类［12］的欠采样方法，先对多类数据进行谱聚类，得到聚类簇，再根据聚类簇按比例进行欠采样，可以有效去除多数类的冗余数据，根据聚类簇中的样本数据到少类样本数据的平均距离来选择样本，能够有选择地去除部分多数类的边界数据，但是能够保留重要边界信息，不会对数据的总体分布造成影响，这样便于后续的分类工作。

2.1 谱聚类算法

聚类算法直观上就是根据样本数据的相似性，将其划分成不同的组，使得在相同组内的数据是相似的，不同组之间的数据具有较低的相似性。一些经典的聚类算法，如K-means算法、EM算法（Ex⁃pectation Maximization Algorithm）等，都只适用于聚类球状形的数据集，不能推广到任意的形状，当数据集不为凸时，算法会陷入局部最优［13］。谱聚类算法在最近几年开始变得受欢迎起来，主要是因为算法实现比较简单，可以对任意形状的样本空间进行聚类，并且收敛于全局最优解，不易陷入局部最优，聚类效果常优于经典的聚类算法。

谱聚类是从图论中演化出的一种算法，其思想源于图论中的谱图理论，是将聚类问题转化成一个无向图的最优划分问题。标准化谱聚类的算法步骤如下：

输入：数据集S=(x1，x2，…xn)和聚类簇的数目k；

输出：聚类簇A1，A2，…，AK。

1）使用式（1）计算n*n的相似度矩阵W，即为Sij组成的相似度矩阵；

2）使用式（2）计算度矩阵D，即为W的每行元素之和，由di组成的n*n对角矩阵；

3）计算拉普拉斯矩阵Lrsym=D-1/2LD-1/2=D-1/2(D-W)D-1/2；

4）计算Lrsym的特征值，将特征值从小到大排序，取前k个特征值，并计算前k个特征值对应的特征向量μ1，μ2，…，μk；

5）将上面的k个列向量组成矩阵U={μ1，μ2，…，μk}，U∈Rn*k；

6）令yi∈Rk是U的第i行的向量，其中i=1，2，…，n，再将yi∈Rk依次单位化，使得|yi|=1；

7）使 用k-means算 法 将 新 样 本 点Y={y1，y2，…，yn}聚类成簇A1，A2，…，AK；

8）输出A1，A2，…，AK。

2.2 支持向量机

支持向量机（Support Vector Machine）［14］是一种经典的分类算法，常用于二分类问题。支持向量机可以分为线性和非线性两大类。其主要思想是在空间中找到一个能够将所有数据划分开的超平面，并且让数据集中所有样本到这个超平面的距离最短，离超平面较近的样本之间能有更大的间距，也就是寻求可以更好隔离两个类别的超平面。当训练样本线性可分时，使用硬间隔最大化（hard mar⁃gin maximization）训练得到线性分类器；当训练样本近似线性可分时，使用软间隔最大化（soft mar⁃gin maximization）训练得到线性分类器；当训练样本不可分时，使用核技巧（kernel trick）和软间隔最大化训练非线性的分类器。

以二分类为例，设给定训练样本集{(x1，y1)，…，(xn，yn)}，i=1，2，…，n，其中xi表示样本的数据特征，yi∈{+1，-1}表示样本的类别标签。选取适当的核函数K和惩罚参数C。

1）构造最优化问题：

其中，ξi为松弛变量，表示允许样本可以错分的程度，C为惩罚项，即对错分样本的惩罚程度，拉格朗日函数为：

其中，αi和τi是拉格朗日算子，0≤αi≤C(i=1，2，代入化简后得到目标函数：

2）选择α*，满足0≤αi≤C(i=1，2，…，n)，计算：

3）构造决策函数为

2.3 SCUnder算法

SCUnder算法的主要思想是基于谱聚类算法对多类数据进行聚类，得到聚类簇，根据每一个聚类簇中的样本数目、聚类内两两数据之间的平均距离，以及该聚类中的样本数据到少类样本数据的平均距离，来确定每个聚类簇中选择的样本数和选择什么样的多类数据，进而对多数类进行欠采样，以达到多类数据与少类数据相对平衡的状态，有效去除多类样本的冗余数据，降低源数据集的不平衡程度。

记原始数据集为S=S+∪S-，其中S+和S-分别表示少类样本数据和多类样本数据，minorN为少类样本数目，majorN为多类样本数目，计算样本之间的距离均为欧式距离。算法的主要步骤如下。

1）设置聚类数目clusterN=(minorN/majorN)*minorN；

2）利用上述谱聚类算法对多类样本数据进行聚类，生成聚类簇A1，A2，…，AK，k=clusterN；

3）计算第i个聚类簇中的样本数counti，计算第i个聚类簇中两两样本之间距离的平均值Wdisti，由此计算第i个聚类簇的密集程度：

并将其归一化：

4）计算第i个聚类簇中的样本到少类样本数据的平均距离AI_disti，并将其归一化：

5）取每个聚类簇的密集程度Densityi和到少类样本数据的平均距离SI_disti的加权和，作为每个聚类簇的采样比例ratioi，α是一个加权系数，即

6）计算每个聚类簇的采样数目SCsizei，即

7）对多类样本进行欠采样，先计算聚类簇Ai中每个样本到少类的平均距离ddistj，j∈Ai，i=1，2，…，k，按从小到大的顺序进行排序，选取前SCsizei个样本数据，组合成采样后的多类样本数据集Snew；

8）输出欠采样后组合的新训练集S'=S+∪

Snew。

3 实验结果与分析

3.1 性能评估指标

在类别不平衡数据分类问题中，需要采用适用于不平数据分类器的评估指标。通常采用基于混淆矩阵的评价方法，Precision（准确率/查准率）、Re⁃call（召回率/查全率）、F-measure以及G-mean，用以评估分类器性能。对于二分类问题，将少类样本数据记为正类（Positive），多类样本数据记为负类（Negative）。表示分类结果的混淆矩阵如表1所示。

表1 混淆矩阵

其中，TP、FN分别表示正类数据被正确分类的数目、正类数据被错分为负类的数目，FP、TN分别表示负类数据被错分为正类的数目、负类样本被正确分类的数目。根据混淆矩阵，有以下几种性能评估指标。

查准率表示被正确分类的正类数目占被分为正类的全部数目的比例。

查全率表示被正确分类的正类数目占实际全部正类数目的比例。

F-measure表示查准率和查全率的组合均值，β是表示两者相对重要性的参数，通常取β=1。

AUC（area under the ROC curve）也是一个有效的不平衡数据分类性能评价指标，即ROC［15］（re⁃ceiver operating characteristic curve）曲线下方的面积。

为了能更好地评价算法性能，本文采用F-measure和AUC两个评估指标对分类结果进行评价。

3.2 实验数据集

本文从KEEL不平衡数据库［16］中选取了9组基准数据集对算法进行验证，数据集的基本信息由表2所示。

表2 实验数据集的基本信息

3.3 实验结果与分析

为了验证本文提出的基于谱聚类的欠采样方法的有效性，也为了方便与其他采样方法进行对比实验，实验选择SVM作为分类器。与本文提出的SCUnder算法进行对比的方法有基于随机欠采样的支持向量机（简称RU_SVM）、基于代价敏感的支持向量机（简称WS_SVM）、基于单边选择欠采样的支持向量机（简称OSS_SVM）、基于Smote过采样的支持向量机（简称Smote_SVM）。本文的实验采用5折交叉验证的方式，重复进行10次实验，计算10次实验评价指标的平均值，作为最终的实验结果。

其中，分类器SVM统一采用高斯核函数，惩罚因子C设置为50，核函数宽度σ的值设置为5。实验采用python中scikit-learn库中的支持向量机SVC分类算法。本文提出的基于谱聚类的算法实验采用scikit-learn库中的谱聚类SpectralClustering算法，相似度矩阵使用高斯核函数，核函数参数gamma经过交叉验证进行调参，选择最合适的值。SCUnder算法中的加权系数α同样采用交叉验证的方式选择最优解。

下面是上述方法对比的实验结果，表3和表4分别列出了不同算法在各数据集上F-measure和AUC的值，其中性能最好的结果用加粗的方式表示，并以图1和图2的形式进行直观展示。

图1 欠采样方法F-measure值对比图

图2 欠采样方法AUC值对比图

表3 SCUnder算法和其他方法的F-measure性能对比

表4 SCUnder算法和其他方法的AUC性能对比

从表3可以看出，基于谱聚类的欠采样方法在大部分数据集上的分类效果要优于其他方法，SCUnder算法在6组数据集上F-measure值最大，尤其是在glass2、haberman和yeast1数据集上，F-mea⁃sure值明显优于其他方法。相比较于RU_SVM和WS_SVM这两种方法，SCUnder_SVM的F-measure值在所有实验的数据集上的表现均高于这两种方法，这是因为基于谱聚类的欠采样方法通过聚类后按比例进行采样，可以有效去除多数类的冗余数据，而且能够有选择地去除部分不重要的多数类边界数据。从表4可以看出，SCUnder算法在3组数据集上AUC的值最大，在其他数据集上的AUC值虽然不是最高的，但与每组的最优结果相差不大，能够保持平均水平。对于不平衡比例较大的数据集，如glass2数据集，SCUnder算法的表现都优于其他算法，从某种程度上可以看出，本文提出的基于谱聚类的欠采样方法可以适用于各种不平衡度的数据集。总体而言，SCUnder算法能够有效提高少类样本的分类性能。

4 结语

欠采样方法是不平衡数据分类问题中常用的方法之一，从数据层面出发，针对欠采样方法中存在的多类样本数据信息丢失的问题，本文提出一种基于谱聚类的欠采样方法，先对多类样本数据进行谱聚类，得到聚类簇，通过聚类簇确定多类样本的空间分布，根据每个聚类簇的密集程度以及到少类样本的平均距离，来确定采样数目以及选取什么样的多类样本，这样按比例进行的欠采样可以有效去除多数类的冗余数据，并去除部分不重要的边界数据，但是能够保留重要边界信息。通过在9组不同数据集上的对比实验，可以看出基于谱聚类的欠采样方法在一定程度上能够提高少类样本的分类性能，能有效处理不平衡数据的分类问题。