2020-09-26
《模式识别》第四版(希腊)西奥多里蒂斯第二章习题2.34题解
证明： 设
ω
1
\omega_{1}
ω1和
ω
2
\omega_{2}
ω2的条件概率密度函数如图所示, 它们的中心分别为
(
∓
a
,
0
)
(\mp a,0)
(∓a,0), 半径都是
r
r
r, 并且
2
a
>
4
r
2a > 4r
2a>4r, 即
a
>
2
r
a > 2r
a>2r.
设
x
1
\boldsymbol{x}_{1}
x1,
x
2
\boldsymbol{x}_{2}
x2, …,
x
N
\boldsymbol{x}_{N}
xN为训练样本,
x
\boldsymbol{x}
x是待分类的数据, 不妨设训练样本是独立的, 并且待分类点
x
\boldsymbol{x}
x与训练样本是独立的. 由于
x
\boldsymbol{x}
x或者属于
ω
1
\omega_{1}
ω1, 或者属于
ω
2
\omega_{2}
ω2, 所以可以认为先验概率
P
{
ω
1
}
=
P
{
ω
2
}
=
1
/
2
P\{\omega_{1}\}=P\{\omega_{2}\}=1/2
P{ω1}=P{ω2}=1/2. 用
e
N
N
e_{\mathrm{NN}}
eNN和
e
k
N
N
e_{k\mathrm{NN}}
ekNN分别表示NN分类器和
k
k
kNN分类器的误判概率. 先计算
e
N
N
e_{\mathrm{NN}}
eNN. 设
x
′
\boldsymbol{x}'
x′是待分类数据
x
\boldsymbol{x}
x的最近邻点. 那么
e
N
N
=
P
{
x
∈
ω
1
,
x
′
∈
ω
2
}
+
P
{
x
∈
ω
2
,
x
′
∈
ω
1
}
=
P
{
x
∈
ω
1
}
P
{
x
′
∈
ω
2
∣
x
∈
ω
1
}
+
P
{
x
∈
ω
2
}
P
{
x
′
∈
ω
1
∣
x
∈
ω
2
}
=
1
2
P
{
x
′
∈
ω
2
∣
x
∈
ω
1
}
+
1
2
P
{
x
′
∈
ω
1
∣
x
∈
ω
2
}
\begin{array}{rl} e_{\mathrm{NN}}&=P\{\boldsymbol{x}\in\omega_{1},\boldsymbol{x}'\in\omega_{2}\}+P\{\boldsymbol{x}\in\omega_{2},\boldsymbol{x}'\in\omega_{1}\}\\ &=P\{\boldsymbol{x}\in\omega_{1}\}P\{\boldsymbol{x}'\in\omega_{2}|\boldsymbol{x}\in\omega_{1}\}\\ &\hspace{4mm}+P\{\boldsymbol{x}\in\omega_{2}\}P\{\boldsymbol{x}'\in\omega_{1}|\boldsymbol{x}\in\omega_{2}\}\\ &=\frac{1}{2}P\{\boldsymbol{x}'\in\omega_{2}|\boldsymbol{x}\in\omega_{1}\}+\frac{1}{2}P\{\boldsymbol{x}'\in\omega_{1}|\boldsymbol{x}\in\omega_{2}\} \end{array}
eNN=P{x∈ω1,x′∈ω2}+P{x∈ω2,x′∈ω1}=P{x∈ω1}P{x′∈ω2∣x∈ω1}+P{x∈ω2}P{x′∈ω1∣x∈ω2}=21P{x′∈ω2∣x∈ω1}+21P{x′∈ω1∣x∈ω2}
由于
a
>
2
r
a>2r
a>2r, 给定
x
∈
ω
1
\boldsymbol{x}\in\omega_{1}
x∈ω1, 如果
x
′
∈
ω
2
\boldsymbol{x}'\in\omega_{2}
x′∈ω2, 则
∥
x
−
x
′
∥
>
2
r
\|\boldsymbol{x}-\boldsymbol{x}'\|>2r
∥x−x′∥>2r. 因此, 给定
x
∈
ω
1
\boldsymbol{x}\in\omega_{1}
x∈ω1, 当
x
′
∈
ω
2
\boldsymbol{x}'\in\omega_{2}
x′∈ω2时, 所有训练样本都属于
ω
2
\omega_{2}
ω2. 若不然, 存在训练样本
x
i
\boldsymbol{x}_{i}
xi,
x
i
≠
x
′
\boldsymbol{x}_{i}\neq\boldsymbol{x}'
xi=x′,
x
i
∈
ω
1
\boldsymbol{x}_{i}\in\omega_{1}
xi∈ω1, 则
∥
x
i
−
x
∥
≤
2
r
\|\boldsymbol{x}_{i}-\boldsymbol{x}\|\leq2r
∥xi−x∥≤2r, 这与
x
′
\boldsymbol{x}'
x′是最近邻点矛盾. 因此所有训练样本都属于
ω
2
\omega_{2}
ω2. 反之, 当所有的训练样本都属于
ω
2
\omega_{2}
ω2时, 则一定有
x
′
∈
ω
2
\boldsymbol{x}'\in\omega_{2}
x′∈ω2.
因此, 给定
x
∈
ω
1
\boldsymbol{x}\in\omega_{1}
x∈ω1下,
{
x
′
∈
ω
2
}
=
{
x
i
∈
ω
2
,
i
=
1
,
2
,
.
.
.
,
N
}
\{\boldsymbol{x}'\in\omega_{2}\}=\{\boldsymbol{x}_{i}\in\omega_{2},i=1,2,...,N\}
{x′∈ω2}={xi∈ω2,i=1,2,...,N}.
所以利用训练样本的独立性得到
P
{
x
′
∈
ω
2
∣
x
∈
ω
1
}
=
P
{
x
i
∈
ω
2
,
i
=
1
,
2
,
.
.
.
,
N
}
=
∏
i
=
1
N
P
{
x
i
∈
ω
2
}
=
(
1
2
)
N
\begin{array}{rl} P\{\boldsymbol{x}'\in\omega_{2}|\boldsymbol{x}\in\omega_{1}\} &=P\{\boldsymbol{x}_{i}\in\omega_{2},i=1,2,...,N\}\\ &=\prod^{N}_{i=1} P\{\boldsymbol{x}_{i}\in\omega_{2}\}=\Big(\frac{1}{2}\Big)^{N} \end{array}
P{x′∈ω2∣x∈ω1}=P{xi∈ω2,i=1,2,...,N}=∏i=1NP{xi∈ω2}=(21)N
同理
P
{
x
′
∈
ω
1
∣
x
∈
ω
2
}
=
(
1
2
)
N
P\{\boldsymbol{x}'\in\omega_{1}|\boldsymbol{x}\in\omega_{2}\}=\Big(\frac{1}{2}\Big)^{N}
P{x′∈ω1∣x∈ω2}=(21)N
从而
e
N
N
=
1
2
(
1
2
)
N
+
1
2
(
1
2
)
N
=
(
1
2
)
N
e_{\mathrm{NN}}=\frac{1}{2}\Big(\frac{1}{2}\Big)^{N}+\frac{1}{2}\Big(\frac{1}{2}\Big)^{N}=\Big(\frac{1}{2}\Big)^{N}
eNN=21(21)N+21(21)N=(21)N
现在考虑
e
k
N
N
e_{k\mathrm{NN}}
ekNN. 由于
k
k
k一般是奇数, 所以记
k
=
2
k
0
+
1
k=2k_{0}+1
k=2k0+1. 那么当
x
∈
ω
1
\boldsymbol{x}\in\omega_{1}
x∈ω1时,
而
N
N
N个训练样本属于
ω
1
\omega_{1}
ω1的个数不多于
k
0
k_{0}
k0时, 则
k
k
kNN法则会将
x
\boldsymbol{x}
x归类到
ω
2
\omega_{2}
ω2, 于是出现误判. 因此
e
k
N
N
=
P
{
x
∈
ω
1
,
N
个训练样本属于
ω
1
的个数不多于
k
0
}
+
P
{
x
∈
ω
2
,
N
个训练样本属于
ω
2
的个数不多于
k
0
}
=
P
{
x
∈
ω
1
}
P
{
N
个训练样本属于
ω
1
的个数不多于
k
0
∣
x
∈
ω
1
}
+
P
{
x
∈
ω
2
}
P
{
N
个训练样本属于
ω
2
的个数不多于
k
0
∣
x
∈
ω
2
}
=
1
2
P
{
N
个训练样本属于
ω
1
的个数不多于
k
0
∣
x
∈
ω
1
}
+
1
2
P
{
N
个训练样本属于
ω
2
的个数不多于
k
0
∣
x
∈
ω
2
}
\begin{array}{rl} e_{k\mathrm{NN}} &=P\{\boldsymbol{x}\in\omega_{1},\;N\texttt{个训练样本属于}\omega_{1}\texttt{的个数不多于}k_{0}\}\\ &\hspace{4mm}+P\{\boldsymbol{x}\in\omega_{2},\;N\texttt{个训练样本属于}\omega_{2}\texttt{的个数不多于}k_{0}\}\\ &=P\{\boldsymbol{x}\in\omega_{1}\}P\{N\texttt{个训练样本属于}\omega_{1}\texttt{的个数不多于}k_{0}\;|\boldsymbol{x}\in\omega_{1}\}\\ &\hspace{4mm}+P\{\boldsymbol{x}\in\omega_{2}\}P\{N\texttt{个训练样本属于}\omega_{2}\texttt{的个数不多于}k_{0}\;|\boldsymbol{x}\in\omega_{2}\}\\ &=\frac{1}{2}P\{N\texttt{个训练样本属于}\omega_{1}\texttt{的个数不多于}k_{0}\;|\boldsymbol{x}\in\omega_{1}\}\\ &\hspace{4mm}+\frac{1}{2}P\{N\texttt{个训练样本属于}\omega_{2}\texttt{的个数不多于}k_{0}\;|\boldsymbol{x}\in\omega_{2}\} \end{array}
ekNN=P{x∈ω1,N个训练样本属于ω1的个数不多于k0}+P{x∈ω2,N个训练样本属于ω2的个数不多于k0}=P{x∈ω1}P{N个训练样本属于ω1的个数不多于k0∣x∈ω1}+P{x∈ω2}P{N个训练样本属于ω2的个数不多于k0∣x∈ω2}=21P{N个训练样本属于ω1的个数不多于k0∣x∈ω1}+21P{N个训练样本属于ω2的个数不多于k0∣x∈ω2}
所以利用
x
\boldsymbol{x}
x与训练样本的独立性, 以及训练样本的独立性, 得到
P
{
N
个训练样本属于
ω
1
的个数不多于
k
0
∣
x
∈
ω
1
}
=
P
{
N
个训练样本属于
ω
1
的个数不多于
k
0
}
=
P
{
N
个训练样本属于
ω
1
的个数为零
}
+
P
{
N
个训练样本属于
ω
1
的个数为
1
}
+
⋯
+
P
{
N
个训练样本属于
ω
1
的个数为
k
0
}
=
∑
j
=
1
k
0
(
N
j
)
(
1
2
)
j
(
1
−
1
2
)
N
−
j
=
(
1
2
)
N
∑
j
=
1
k
0
(
N
j
)
\begin{array}{rl} &P\{N\texttt{个训练样本属于}\omega_{1}\texttt{的个数不多于}k_{0}|\boldsymbol{x}\in\omega_{1}\}\\ &=P\{N\texttt{个训练样本属于}\omega_{1}\texttt{的个数不多于}k_{0}\}\\ &=P\{N\texttt{个训练样本属于}\omega_{1}\texttt{的个数为零}\}\\ &\hspace{4mm}+P\{N\texttt{个训练样本属于}\omega_{1}\texttt{的个数为}1\}\\ &\hspace{4mm}+\cdots+P\{N\texttt{个训练样本属于}\omega_{1}\texttt{的个数为}k_{0}\}\\ &=\sum^{k_{0}}_{j=1} \Big(\!\! \begin{array}{c} N \\ j \end{array}\!\!\Big) \big(\frac{1}{2}\big)^{j}\big(1-\frac{1}{2}\big)^{N-j}\\ &=\big(\frac{1}{2}\big)^{N}\sum^{k_{0}}_{j=1} \Big(\!\! \begin{array}{c} N \\ j \end{array}\!\!\Big) \end{array}
P{N个训练样本属于ω1的个数不多于k0∣x∈ω1}=P{N个训练样本属于ω1的个数不多于k0}=P{N个训练样本属于ω1的个数为零}+P{N个训练样本属于ω1的个数为1}+⋯+P{N个训练样本属于ω1的个数为k0}=∑j=1k0(Nj)(21)j(1−21)N−j=(21)N∑j=1k0(Nj)
同理
P
{
N
个训练样本属于
ω
2
的个数不多于
k
0
∣
x
∈
ω
2
}
=
(
1
2
)
N
∑
j
=
1
k
0
(
N
j
)
\begin{array}{rl} &P\{N\texttt{个训练样本属于}\omega_{2}\texttt{的个数不多于}k_{0}|\boldsymbol{x}\in\omega_{2}\}\\ &=\big(\frac{1}{2}\big)^{N}\sum^{k_{0}}_{j=1} \Big(\!\! \begin{array}{c} N \\ j \end{array}\!\!\Big) \end{array}
P{N个训练样本属于ω2的个数不多于k0∣x∈ω2}=(21)N∑j=1k0(Nj)
因此
e
k
N
N
=
1
2
(
1
2
)
N
∑
j
=
1
k
0
(
N
j
)
+
1
2
(
1
2
)
N
∑
j
=
1
k
0
(
N
j
)
=
(
1
2
)
N
∑
j
=
1
k
0
(
N
j
)
\begin{array}{rl} e_{k\mathrm{NN}}=&\frac{1}{2}\Big(\frac{1}{2}\Big)^{N}\sum^{k_{0}}_{j=1} \Big(\!\! \begin{array}{c} N \\ j \end{array}\!\!\Big)+\frac{1}{2}\Big(\frac{1}{2}\Big)^{N}\sum^{k_{0}}_{j=1} \Big(\!\! \begin{array}{c} N \\ j \end{array}\!\!\Big)\\ &=\Big(\frac{1}{2}\Big)^{N}\sum^{k_{0}}_{j=1} \Big(\!\! \begin{array}{c} N \\ j \end{array}\!\!\Big) \end{array}
ekNN=21(21)N∑j=1k0(Nj)+21(21)N∑j=1k0(Nj)=(21)N∑j=1k0(Nj)
当
k
≥
3
k\geq3
k≥3时,
k
0
≥
1
k_{0}\geq1
k0≥1, 所以
e
k
N
N
>
e
N
N
e_{k\mathrm{NN}}>e_{\mathrm{NN}}
ekNN>eNN.