第6期 王俊红，等：一种基于密度的SMOTE方法研究 ·867· 10)endfor 区域的密度阈值。如果一个对象0的&-邻域密度 11)newindex++; M≥Min Pts,.则o为一个稠密对象，如果一个对象o 12)W=W+1: 的&-邻域密度<Min Pts,.则o为一个稀疏对象。 13)endwhile 个类中的稀疏对象构成此类的种子样本集合(seeds)。 l.2 Borderline-SMOTE算法 根据SMOTE算法思想，DS-SMOTE算法根据 Borderline-SMOTE算法在SMOTE算法的基 式(3)在种子样本与其近邻之间合成新样本： 础上进行了改进I。不同于SMOTE算法，Border- new→o+D(seed,o)Xr (3) line-SMOTE算法避免了在过采样过程中样本选择 式中：o为目标对象，D(seed,o)为种子样本seed,与 的随机性，选择类边界样本，作为种子样本合成新 其近邻样本o之间的欧氏距离，r为随机数，且 样本。在样本空间中，如某一样本周围的邻居样本 r∈(0,1)o 较多，则这个样本较为稠密，就决策树分类算法而 DS-SMOTE算法的核心思想为：在SMOTE算 言，产生的叶子节点一一规则较多，容易产生过拟 法的基础上，在少数类中抽取种子样本集合后对其 合问题，所以不宜在这个样本与其近邻之间添加新 进行过采样。在算法中，我们对少数类中稀疏对象 的样本。Borderline-SMOTE算法尝试着在训练过 进行样本采集得到一个种子样本集合，产生种子集 合的过程主要包括：计算少数类中样本的邻域半 程中尽量地去学习边界特征，认为边界样本在分类 径、计算该类的密度阈值、产生稀疏对象集合作为 中比远离边界的样本更容易被错分，一个类的边界 种子样本集。DS-SMOTE算法产生的合成样本分 样本携带了更多的信息，对分类器分类性能的好坏 布于稀疏对象及其近邻之间，最终得到与多数类样 起到了决定性的作用。因此，在Borderline-SMOTE 本数量相等的少数类样本集合。 算法中，加入了识别边界样本的过程：若一个少数 DS-SMOTE算法 类样本的m近邻中，半数以上为多数类样本，则认 输入训练集T,原始样本集合中多数类S,= 为这个样本为容易被错分的危险样本；否则为安全 {x,2,xmm}、少数类集合S2={y,2,,ymm}、邻 样本。在危险样本与其k近邻之间合成新样本，完 域半径&、密度阈值Min Pts。 成对边界少数类样本的过采样，以此加强少数类的 1)对于少数类集合S2,在整个训练集T中对 决策边界，以获得好的分类结果。 S2中的每一个样本y计算其近邻。若其近邻类别 13基于密度的过采样算法 都为多数类，则认为y,为噪声，且不会出现在下一 设某类的样本集合为S={s,=1,2,,n},其中 步计算中； S,为维数为m的样本向量，样本的维数代表其属性 2)选择少数类集合S,执行=getE(S)得到少 的个数。一个类的对象o的密度是指靠近对象0的 数类邻域半径e 对象数量。 3)求得邻域半径为ε时，每个少数类样本的密度： 定义1参数(>0)为对象o的邻域区域的半 4)for/=1,|minl 径，即o的邻域半径。则一个对象o的&邻域是指 5)令%的&邻域密度=1： 以o为圆心、以ε为半径的空间，定义为 6)forj=1,|minl ={s,2·D(si,o)cos0≤s (1) 7)计算其他少数类样本与样本y的欧式距离D: 式中：D(s,o)为对象o以外的样本S到对象o的距 8)if D<=c 离，采用欧式距离方法计算；0为点o与s连线与 9)y的&-邻域密度+1； 水平轴之间的夹角。 10)endfor 定义2对象0的-邻域的密度是指对象0在 11)endfor &邻域内的对象数量。 12)endfor 定义3一个样本数量为m的类在邻域半径 13)根据式(2)，求得密度阈值Min Pts; 为e时，类中样本的密度阈值Min Pts为类中样本 14)forj=1,|min] i的&邻域密度M,的均值。 15)ify的&邻域密度≤密度阈值 (2) 16)y为稀疏对象，将y,加入种子样本集合： m台 17)endfor 为了确定对象0是否为稀疏点，即对象0的& 18)endfor 邻域是否稀硫，本文中使用参数Min Pts,作为稠密 19)产生种子集合seed;10) endfor 11) newindex++； 12) N=N+1； 13) endwhile 1.2 Borderline-SMOTE 算法 Borderline-SMOTE 算法在 SMOTE 算法的基 础上进行了改进[12]。不同于 SMOTE 算法，Border￾line-SMOTE 算法避免了在过采样过程中样本选择 的随机性，选择类边界样本，作为种子样本合成新 样本。在样本空间中，如某一样本周围的邻居样本 较多，则这个样本较为稠密，就决策树分类算法而 言，产生的叶子节点——规则较多，容易产生过拟 合问题，所以不宜在这个样本与其近邻之间添加新 的样本。Borderline-SMOTE 算法尝试着在训练过 程中尽量地去学习边界特征，认为边界样本在分类 中比远离边界的样本更容易被错分，一个类的边界 样本携带了更多的信息，对分类器分类性能的好坏 起到了决定性的作用。因此，在 Borderline-SMOTE 算法中，加入了识别边界样本的过程：若一个少数 类样本的 m 近邻中，半数以上为多数类样本，则认 为这个样本为容易被错分的危险样本；否则为安全 样本。在危险样本与其 k 近邻之间合成新样本，完 成对边界少数类样本的过采样，以此加强少数类的 决策边界，以获得好的分类结果。 1.3 基于密度的过采样算法 设某类的样本集合为 S={s ··· i , i=1, 2, , n}，其中 si 为维数为 m 的样本向量，样本的维数代表其属性 的个数。一个类的对象 o 的密度是指靠近对象 o 的 对象数量。 定义 1 参数 ε(ε>0) 为对象 o 的邻域区域的半 径，即 o 的邻域半径。则一个对象 o 的 ε-邻域是指 以 o 为圆心、以 ε 为半径的空间，定义为 ψ= {ε, θ|2 · D(si ,o) · cos θ ⩽ ε} (1) 式中：D(si , o) 为对象 o 以外的样本 si 到对象 o 的距 离，采用欧式距离方法计算[16] ；θ 为点 o 与 si 连线与 水平轴之间的夹角。 定义 2 对象 o 的 ε-邻域的密度是指对象 o 在 ε-邻域内的对象数量。 定义 3 一个样本数量为 m 的类在邻域半径 为 ε 时，类中样本的密度阈值 Min Pts 为类中样本 i 的 ε-邻域密度 Mi 的均值。 MinPts = 1 m ∑m i=1 Mi (2) 为了确定对象 o 是否为稀疏点，即对象 o 的 ε- 邻域是否稀疏，本文中使用参数 Min Pts，作为稠密 区域的密度阈值。如果一个对象 o 的 ε-邻域密度 M≥Min Pts，则 o 为一个稠密对象，如果一个对象 o 的 ε-邻域密度 M<Min Pts，则 o 为一个稀疏对象。一 个类中的稀疏对象构成此类的种子样本集合 (seeds)。 根据 SMOTE 算法思想，DS-SMOTE 算法根据 式（3）在种子样本与其近邻之间合成新样本： new ⇒ o+ D(seedi ,o) ×r (3) 式中：o 为目标对象，D(seedi , o) 为种子样本 seedi 与 其近邻样本 o 之间的欧氏距离，r 为随机数，且 r∈(0, 1)。 DS-SMOTE 算法的核心思想为：在 SMOTE 算 法的基础上，在少数类中抽取种子样本集合后对其 进行过采样。在算法中，我们对少数类中稀疏对象 进行样本采集得到一个种子样本集合，产生种子集 合的过程主要包括：计算少数类中样本的邻域半 径、计算该类的密度阈值、产生稀疏对象集合作为 种子样本集。DS-SMOTE 算法产生的合成样本分 布于稀疏对象及其近邻之间，最终得到与多数类样 本数量相等的少数类样本集合。 DS-SMOTE 算法 ··· ··· 输入 训练集 T, 原始样本集合中多数类 S1 = {x1 , x2 , , xmaj}、少数类集合 S2 = {y1 , y2 , , ymin}、邻 域半径 ε、密度阈值 Min Pts。 1) 对于少数类集合 S2 , 在整个训练集 T 中对 S2 中的每一个样本 yi 计算其近邻。若其近邻类别 都为多数类, 则认为 yi 为噪声, 且不会出现在下一 步计算中； 2) 选择少数类集合 S3 , 执行 ε= getE(S3 ) 得到少 数类邻域半径 ε； 3) 求得邻域半径为 ε 时, 每个少数类样本的密度； 4) for j = 1, |min| 5) 令 yi 的 ε-邻域密度=1； 6) for j = 1, |min| 7) 计算其他少数类样本与样本 yi 的欧式距离 D； 8) if D<=ε 9) yi 的 ε-邻域密度+1； 10) endfor 11) endfor 12) endfor 13) 根据式 (2), 求得密度阈值 Min Pts； 14) for j = 1, |min| 15) if yi 的 ε-邻域密度≤密度阈值 16) yi 为稀疏对象, 将 yi 加入种子样本集合； 17) endfor 18) endfor 19) 产生种子集合 seed； 第 6 期 王俊红，等：一种基于密度的 SMOTE 方法研究 ·867·