·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 卷