·866· 智能系统学报 第12卷 习方法和代价敏感学习方法6：数据层面的方法主 思想基于k近邻算法，对每个少数类样本0，从它的 要思想是基于重采样技术也就是对少数类样本的过 k个最近邻中随机选择一个样本a,在o~a之间的 采样和对多数类样本的欠采样。 连线上随机产生合成样本，一般地，取=5。 作为数据层面的处理方法，重采样方法简单 SMOTE过采样方法通过对数据集中每一个少 直观，倍受研究人员青睐7，在过采样研究中，2002 数类样本随机地选取k个最近邻，并在该少数类样 年Chawla提出的SMOTE O(synthetic minority 本与其选取的最近邻之间的连线上随机产生合成样 over-sampling technique)算法是其中的一个经典算 本。在步骤1)中，通过获取的过采样比例以及少数 法，现有很多算法都是在此原型的基础上提出的。 类样本的数量，产生新样本数量：在步骤2)5)中， SMOTE算法在少数类样本与其K个近邻之间的连 循环遍历每一个少数类样本，获取其k近邻，并将 线上产生随机的合成样本，完成对少数类样本的过 其k近邻的索引保存于数组nnarry中，作为合成新 采样，提高了少数类样本数量，使分类器更好地对 样本的参数获取新样本，这里选取最近邻个数k=5, 未知少数类样本进行预测，有效地提高了分类精 例如：已知过采样比例为300%，那么需要从每个少 度。但是，由于SMOTE算法无区分地对所有少数 数类样本的5个最近邻中随机选取3个样本，作为 类样本进行过采样，在少数类极度稀缺时很容易 合成新样本的素材；其中Populate方法详细介绍了 造成过拟合。为了解决这一问题，文献[11]提出了 合成样本的产生过程。在步骤3)中，根据少数类样 基于SMOTE的改进方法(adaptive SMOTE,AS- 本的属性数以及新样本的数量进行遍历，步骤5)用 MOTE)方法川，该方法根据样本集内部实际分布特 于求得样本间的欧式距离：在步骤8)中，根据公式， 性，自适应地调整合成样本产生过程中的近邻选择 得到少数类样本与其近邻之间的合成样本。新生成 策略，避免了原始方法中样本生成的盲目性，进而 的样本使得分类器能够从学习过程中产生更大更抽 一定程度上提高了分类算法的准确率。在文献[12] 象的决策边界，有效地使少数类的决策边界变得更 提出的Borderline-.SMOTE方法中，改变了传统的思 加明显，从而获得更好的分类效果。 路，认为边界样本具有更多的信息，通过查找出的 SMOTE算法 “危险样本”作为种子来产生新的合成样本。在此基 础上，Haibo He等对以上算法进行了改进，根据 SMOTE(T.N.K) 样本的“危险”程度，也就是少数类样本在学习中的 输入少数类样本数量T;过采样百分比%；样本 难易程度，使用加权的方法，构造合成样本的分布 近邻个数k: 输出(NW100)*T个少数类合成样本。 函数，来确定这些样本合成新样本的数目。 1)W=(int)(W/100): 上述文献中所涉及的采样思想大多为基于线性 2)for i=1:T 距离，有一定的局限性，易受数据集中样本分布结 3)计算第i个样本的k个最近邻，其k近邻的 构的影响。本文提出了一种新的非平衡数据集处理 索引保存于nnarry中； 方法一基于密度的重采样算法DS-SMOTE,旨在 4)Populate(N,i,nnarry); 识别任意形状的簇，并且扩大“危险样本的范围，对 5)endfor 簇中的“稀疏样本”进行重采样，达到数据集的平衡。 Populate(W,i,nnarry)方法 在本文实验中，选择了C4.5算法作为基准分类算法， 1)While N~=0 C4.5算法是具有代表性的决策树基准算法，在分类 2)选择1~k之间的随机整数，记为n。随机 数据不平衡的情况下与同类分类器相比具有良好的 选择第i个样本的k近邻中的一个近邻。 分类性能，故选择C4.5算法作为基准分类算法。 3)for attr=1:numattrs 1基于密度的过采样方法 4)(numattrs为样本的属性个数) 5)dif sample[nnarry[nn][attr]]-sample 基于密度的方法能够用于识别任意形状的簇， [i][attr]; 如“$”形以及椭圆形簇。为了更好地对非平衡数 6)(sample[为原始少数类样本集合) 据集的分布进行刻画，结合SMOTE的思想，本节提 7)gap=rand(); 出一种基于密度的过采样方法。 8)synthetic[newinder][attr]sample[i][attr] 1.1 SMOTE算法 gap*dif; SMOTE刀是过采样方法中的经典算法。其主要 9)(newinder为合成样本总量，初始值为O)习方法和代价敏感学习方法[6] ；数据层面的方法主 要思想是基于重采样技术也就是对少数类样本的过 采样和对多数类样本的欠采样。 作为数据层面的处理方法，重采样方法简单、 直观，倍受研究人员青睐[7-9] ，在过采样研究中，2002 年 Chawla 提出的 SMOTE [10] (synthetic minority over-sampling technique) 算法是其中的一个经典算 法，现有很多算法都是在此原型的基础上提出的。 SMOTE 算法在少数类样本与其 K 个近邻之间的连 线上产生随机的合成样本，完成对少数类样本的过 采样，提高了少数类样本数量，使分类器更好地对 未知少数类样本进行预测，有效地提高了分类精 度。但是，由于 SMOTE 算法无区分地对所有少数 类样本进行过采样，在少数类极度稀缺时很容易 造成过拟合。为了解决这一问题，文献[11]提出了 基于 SMOTE 的改进方法 (adaptive SMOTE，AS￾MOTE) 方法[11] ，该方法根据样本集内部实际分布特 性，自适应地调整合成样本产生过程中的近邻选择 策略，避免了原始方法中样本生成的盲目性，进而 一定程度上提高了分类算法的准确率。在文献[12] 提出的 Borderline-SMOTE 方法中，改变了传统的思 路，认为边界样本具有更多的信息，通过查找出的 “危险样本”作为种子来产生新的合成样本。在此基 础上，Haibo He 等 [13]对以上算法进行了改进，根据 样本的“危险”程度，也就是少数类样本在学习中的 难易程度，使用加权的方法，构造合成样本的分布 函数，来确定这些样本合成新样本的数目。 上述文献中所涉及的采样思想大多为基于线性 距离，有一定的局限性，易受数据集中样本分布结 构的影响。本文提出了一种新的非平衡数据集处理 方法——基于密度的重采样算法 DS-SMOTE，旨在 识别任意形状的簇，并且扩大“危险样本”的范围，对 簇中的“稀疏样本”进行重采样，达到数据集的平衡。 在本文实验中，选择了 C4.5 算法作为基准分类算法， C4.5 算法是具有代表性的决策树基准算法，在分类 数据不平衡的情况下与同类分类器相比具有良好的 分类性能，故选择 C4.5 算法作为基准分类算法。 1 基于密度的过采样方法 基于密度的方法能够用于识别任意形状的簇， 如“S”形以及椭圆形簇 [14]。为了更好地对非平衡数 据集的分布进行刻画，结合 SMOTE 的思想，本节提 出一种基于密度的过采样方法。 1.1 SMOTE 算法 SMOTE[7]是过采样方法中的经典算法。其主要 思想基于 k 近邻算法，对每个少数类样本 o，从它的 k 个最近邻中随机选择一个样本 a，在 o～a 之间的 连线上随机产生合成样本，一般地，取 k=5 [15]。 SMOTE 过采样方法通过对数据集中每一个少 数类样本随机地选取 k 个最近邻，并在该少数类样 本与其选取的最近邻之间的连线上随机产生合成样 本。在步骤 1) 中，通过获取的过采样比例以及少数 类样本的数量，产生新样本数量；在步骤 2)~5) 中， 循环遍历每一个少数类样本，获取其 k 近邻，并将 其 k 近邻的索引保存于数组 nnarry 中，作为合成新 样本的参数获取新样本，这里选取最近邻个数 k=5， 例如：已知过采样比例为 300%，那么需要从每个少 数类样本的 5 个最近邻中随机选取 3 个样本，作为 合成新样本的素材；其中 Populate 方法详细介绍了 合成样本的产生过程。在步骤 3) 中，根据少数类样 本的属性数以及新样本的数量进行遍历，步骤 5) 用 于求得样本间的欧式距离；在步骤 8) 中，根据公式， 得到少数类样本与其近邻之间的合成样本。新生成 的样本使得分类器能够从学习过程中产生更大更抽 象的决策边界，有效地使少数类的决策边界变得更 加明显，从而获得更好的分类效果。 SMOTE 算法 SMOTE(T, N, K) 输入 少数类样本数量 T；过采样百分比 N%；样本 近邻个数 k； 输出 (N/100)*T 个少数类合成样本。 1) N=(int)(N/100)； 2) for i=1:T 3) 计算第 i 个样本的 k 个最近邻, 其 k 近邻的 索引保存于 nnarry 中； 4) Populate(N, i, nnarry)； 5) endfor Populate(N, i, nnarry) 方法 1) While N~=0 2) 选择 1～k 之间的随机整数, 记为 nn。随机 选择第 i 个样本的 k 近邻中的一个近邻。 3) for attr=1:numattrs 4) (numattrs 为样本的属性个数) 5) dif = sample[nnarry[nn][attr]] – sample [i][attr]； 6) (sample[][]为原始少数类样本集合) 7) gap=rand()； 8) synthetic[newinder][attr] = sample[i][attr] + gap*dif； 9) (newinder 为合成样本总量, 初始值为 0) ·866· 智 能 系 统 学 报 第 12 卷