Random Undersampling(随机下采样) 或 原型选择(Prototype Selection)
定义
从多数类
S
m
a
j
S_{maj}
Smaj中随机选择一些样本组成样本集E。然后将样本集E从
S
m
a
j
S_{maj}
Smaj中移除。新的数据集
S
n
e
w
−
m
a
j
=
S
m
a
j
−
E
S_{n e w-m a j}=S_{m a j}-E
Snew−maj=Smaj−E
1.把数据划分为两部分，分别是多数类样本
S
m
a
j
S_{maj}
Smaj和少数类样本
S
m
i
n
S_{min}
Smin
2.从多数类
S
m
a
j
S_{maj}
Smaj中有放回的随机采样n次，每次选取与少数类数目相近的样本个数即
∣
S
i
m
a
j
∣
=
∣
S
m
i
n
∣
|S_{imaj}|=|S_{min}|
∣Simaj∣=∣Smin∣，可得到n个样本集合，记作
{
S
1
m
a
j
,
S
2
m
a
j
,
…
,
S
n
m
a
j
}
\left\{S_{1 m a j}, S_{2 m a j}, \ldots, S_{n m a j}\right\}
{S1maj,S2maj,…,Snmaj}
3.将每一个多数类样本的子集
S
i
m
a
j
S_{imaj}
Simaj与少数类样本
S
m
i
n
S_{min}
Smin合并后训练出Adaboost分类器
H
i
H_i
Hi，阈值设置为
θ
i
\theta_i
θi，可得到n个模型，即
H
i
(
x
)
=
sgn
(
∑
j
=
1
s
i
α
i
j
h
i
,
j
(
x
)
−
θ
i
)
H_{i}(x)=\operatorname{sgn}\left(\sum\limits_{j=1}^{s_{i}} \alpha_{i j} h_{i, j}(x)-\theta_{i}\right)
Hi(x)=sgn(j=1∑siαijhi,j(x)−θi)
4.将这些模型组合形成一个集成学习系统，最终的模型结果是这n个模型的投票值。此处采用加权多数表决的方法，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率小的弱分类器的权值，使其在表决中起较小的作用，即最终分类器为
H
(
x
)
=
sgn
(
∑
i
=
1
n
∑
j
=
1
s
i
α
i
j
h
i
j
(
x
)
−
∑
i
=
1
n
θ
i
)
H(x)=\operatorname{sgn}\left(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{s_{i}} \alpha_{i j} h_{i j}(x)-\sum\limits_{i=1}^{n} \theta_{i}\right)
H(x)=sgn(i=1∑nj=1∑siαijhij(x)−i=1∑nθi)
输入：一个包含少数类阳性样本P和多数类阴性样本集N的训练集D，定义T是从N中抽取的子集个数，
s
i
s_i
si是训练Adaboost基分类器
H
i
H_i
Hi时的循环次数
输出：一个组合分类器H(x)
1.
f
=
(
∣
P
∣
∣
N
∣
)
(
T
−
1
)
f=\sqrt[(\mathrm{T}-1)]{\left(\frac{|\mathrm{P}|}{|\mathrm{N}|}\right)}
f=(T−1)(∣N∣∣P∣)，
f
f
f是每一层级的分类器
H
i
H_i
Hi该达到的假阳性率(False Positive Rate)，即把多数类样本误分为少数类的错误率
for i = 1 to T:
从多数类N中随机抽取一个样本子集
N
i
N_i
Ni，使得
∣
N
i
∣
=
∣
P
∣
|N_i| = |P|
∣Ni∣=∣P∣
使用少数类样本集P和样本子集
N
i
N_i
Ni训练一个Adaboost分类器
H
i
H_i
Hi(
H
i
H_i
Hi由
s
i
s_i
si个基分类器
h
i
,
j
h_{i,j}
hi,j及其权重
α
i
,
j
\alpha_{i,j}
αi,j构成，
θ
i
\theta_i
θi是
H
i
H_i
Hi的调节参数)
H
i
(
x
)
=
sgn
(
∑
j
=
1
s
i
α
i
,
j
h
i
,
j
(
x
)
−
θ
i
)
\mathrm{H}_{\mathrm{i}}(x)=\operatorname{sgn}\left(\sum_{j=1}^{s_{i}} \alpha_{i, j} h_{i, j}(x)-\theta_{i}\right)
Hi(x)=sgn(∑j=1siαi,jhi,j(x)−θi)
调节阈值
θ
i
\theta_i
θi令
H
i
H_i
Hi的FP率为
f
f
f
移除多数类样本集N中所有被
H
i
H_i
Hi正确分类的样本
输出一个集成分类器
H
(
x
)
=
sgn
(
∑
i
=
1
T
∑
j
=
1
s
l
α
i
,
j
h
i
,
j
(
x
)
−
∑
i
=
1
T
θ
i
)
\mathrm{H}(\mathrm{x})=\operatorname{sgn}\left(\sum\limits_{i=1}^{T} \sum\limits_{j=1}^{s_{l}} \alpha_{i, j} h_{i, j}(x)-\sum\limits_{i=1}^{T} \theta_{i}\right)
H(x)=sgn(i=1∑Tj=1∑slαi,jhi,j(x)−i=1∑Tθi)
给定一个样本对
(
x
i
,
x
j
)
(x_i, x_j)
(xi,xj)，其中
x
i
∈
S
m
a
j
,
x
j
∈
S
min
x_{i} \in S_{m a j}, x_{j} \in S_{\min }
xi∈Smaj,xj∈Smin，记
d
(
x
i
,
x
j
)
d(x_i, x_j)
d(xi,xj)是样本
x
i
x_i
xi和样本
x
j
x_j
xj之间的距离，如果不存在任何样本
x
k
x_k
xk，使得
d
(
x
i
,
x
k
)
<
d
(
x
i
,
x
j
)
d\left(x_{i}, x_{k}\right)<d\left(x_{i}, x_{j}\right)
d(xi,xk)<d(xi,xj)，那么样本对
(
x
i
,
x
j
)
(x_i, x_j)
(xi,xj)即称为Tomek Links。即Tomek links为相反类最近邻样本之间的一对连接
