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