深入理解机器学习——类别不平衡学习（Imbalanced Learning）：样本采样技术-[人工采样技术之ADASYN采样法]

分类目录：《深入理解机器学习》总目录

与Borderline-SMOTE算法相类似，ADASYN（Adaptive Synthetic Sampling）算法也是一种改进的SMOTE算法。该算法于2008年提出，其主要思想是充分利用样本的密度分布信息来确定各少数类样本用作主样本的频次，为少数较难学习的类别样本合成更多的训练数据，从而尽可能修正类别不平衡分布所产生的负面影响。

ADASYN算法首先要确定需生成的新少数类样本数，即$N^{+}\times \text{SR}$，然后在原始训练集$S$上找到每个少数类样本$x_i^{+},i=1,2,\cdots ,N^{+}$的$K$近邻，其中，第$i$个少数类样本的多数类近邻数记为$N_i^{\text{major}}$，进而可通过下式确定每个少数类样本各自的比例参数${\Gamma }_i$：
$${\Gamma }_i=\frac{N_i^{\text{major}}}{Z\times K}$$

其中，$Z$为标准化因子，用以保证$\sum {\Gamma }_i=1$。在比例参数确定后，即可通过下式确定每个少数类样本被选作主样本的频次：
$$g_i={\Gamma }_i\times N^{+}\times \text{SR}$$

从上式不难看出，与Borderline-SMOTE算法相似，ADASYN算法更关注那些位于决策边界附近的少数类样本，它们被选作主样本的频次远远高于那些位于少数类决策区域内的样本。当然，这也会进一步放大少数类噪声信息的传播强度，ADASYN算法的具体流程如下：

ADASYN采样法
输入：训练集$S=\{(x_i,y_i),i=1,2,\cdots ,N,y_i\in \{+,-\}\}$；多数类样本数$N^{-}$，少数类样本数$N^{+}$，其中$N^{-}+N^{+}=N$；不平衡比率$\text{IR}=\frac{N^{-}}{N^{+}}$；采样率$\text{SR}$；邻近参数$K$
输出：过采样后的训练集$S=\{(x_i,y_i),i=1,2,\cdots ,N+N^{+}\times \text{SR},y_i\in \{+,-\}\}$
( 1 ) 从训练集$S$中取出全部多数类与少数类样本，组成多数类训练样本集$S^{-}$及少数类训练样本集$S^{+}$
( 2 ) 置新生成样本集$S^{\text{New}}$为空+
( 3 ) for$i=1:N^{+}$
( 4 ) \quad 在$S^{+}$中找到对应样本$x_i$
( 5 ) \quad 在$S$中找到$x_i$的$K$近邻，记录其多数类近邻数为$N^{\text{major}}$
( 6 ) \quad 计算其比例参数：${\Gamma }_i=\frac{N_i^{\text{major}}}{Z\times K}$
( 7 ) \quad 计算其主样本频次：$g_i={\Gamma }_i\times N^{+}\times \text{SR}$
( 8 ) for$i=1:N^{+}$
( 9 ) \quad 在$S^{+}$中随机选出一个主样本$x_i$
(10) \quad for$i=1:g_i$
(11) \qquad 调用SMOTE算法生成主样本$x_i$的新样本$x_i^{\text{new}}$
(12) \qquad 添加$x_i^{\text{new}}$至$S^{\text{New}}$：$S^{\text{New}}=S^{\text{New}}\cup x_i^{\text{new}}$
(13) return 过采样后的训练集$S^{\prime }=S^{-}\cup S^{\text{New}}$