统计学习方法第三章 k近邻法

• 第三章 k近邻法
• • k近邻算法
  • k近邻模型的距离划分
  • k值的选择
  • k近邻分类决策规则

只讨论分类问题的k近邻法

k近邻三个基本要素：

1. k值选择
2. 距离度量
3. 分类决策规则

k近邻方法没有显示的模型形式，与感知机的分离超平面不同

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VpUjJMxZ-1659022513532)(https://cdn.mathpix.com/snip/images/XT4ehkO9xMyjrMbB_3TAwq2p3dFrLumDpobWUUA-YYQ.original.fullsize.png)]

特征空间中，对每个实例点 x i x_i xi​,距离该点比其他点近的所有点组成一个区域，叫做单元，每个训练实例点拥有一个单元，所有训练实例蒂娜的单元构成对特征空间的一个划分。

距离度量

k k k 近邻模型的特征 空间一般是 n n n 维实数向量空间 R n mathbf{R}^{n} Rn 。使用的距离是欧氏距离, 但也可以是其他距离, 如 更一般的 L p L_{p} Lp​ 距离（ L p L_{p} Lp​ distance）或 Minkowski 距离 (Minkowski distance)。
设特征空间 X mathcal{X} X 是 n n n 维实数向量空间 R n , x i , x j ∈ X , x i = ( x i ( 1 ) , x i ( 2 ) , ⋯   , x i ( n ) ) T mathrm{R}^{n}, x_{i}, x_{j} in mathcal{X}, x_{i}=left(x_{i}^{(1)}, x_{i}^{(2)}, cdots, x_{i}^{(n)}right)^{mathrm{T}} Rn,xi​,xj​∈X,xi​=(xi(1)​,xi(2)​,⋯,xi(n)​)T, x j = ( x j ( 1 ) , x j ( 2 ) , ⋯   , x j ( n ) ) T , x i , x j x_{j}=left(x_{j}^{(1)}, x_{j}^{(2)}, cdots, x_{j}^{(n)}right)^{mathrm{T}}, x_{i}, x_{j} xj​=(xj(1)​,xj(2)​,⋯,xj(n)​)T,xi​,xj​ 的 L p L_{p} Lp​ 距离定义为
L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_{p}left(x_{i}, x_{j}right)=left(sum_{l=1}^{n}left|x_{i}^{(l)}-x_{j}^{(l)}right|^{p}right)^{frac{1}{p}} Lp​(xi​,xj​)=(l=1∑n​∣ ∣​xi(l)​−xj(l)​∣ ∣​p)p1​
其中：
p = 1 , 城市街区距离 L 1 范数 L 1 ( x i , x j ) = ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p = 2 , 欧几里得距离 L 2 范数 L 2 ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ 2 ) 1 2 p = ∞ , 最大距离 L ∞ 范数 L ∞ ( x i , x j ) = max ⁡ i ∣ x i ( l ) − x j ( l ) ∣ begin{aligned} p&=1,quad城市街区距离quadquad L_1 范数quad L_{1} left(x_{i}, x_{j}right)=sum_{l=1}^{n}left|x_{i}^{(l)}-x_{j}^{(l)}right| \ p&=2,quad欧几里得距离quadquad L_2 范数quad L_{2}left(x_{i}, x_{j}right)=left(sum_{l=1}^{n}left|x_{i}^{(l)}-x_{j}^{(l)}right|^{2}right)^{frac{1}{2}} \ p&= infin,quad最大距离quadquadquad L_{infin} 范数quad L_{infin}left(x_{i}, x_{j}right) = max limits_i |x_i^{(l)}-x_j^{(l)}| end{aligned} ppp​=1,城市街区距离L1​范数L1​(xi​,xj​)=l=1∑n​∣ ∣​xi(l)​−xj(l)​∣ ∣​=2,欧几里得距离L2​范数L2​(xi​,xj​)=(l=1∑n​∣ ∣​xi(l)​−xj(l)​∣ ∣​2)21​=∞,最大距离L∞​范数L∞​(xi​,xj​)=imax​∣xi(l)​−xj(l)​∣​

k值选择会对k近邻算法产生重大影响

1. 若选择较小k值：（过拟合）

   优点：学习的近似误差 ↓ downarrow ↓

   缺点：学习的估计误差 ↑ uparrow ↑

   k值减小意味着整体模型变得复杂，容易发生过拟合

2. 若选择较大k值：（欠拟合）

   优点：学习的估计误差 ↓ downarrow ↓

   缺点：学习的近似误差 ↑ uparrow ↑

   k值增大意味着整体模型变得简单，容易发生欠拟合

3. 若k=N：

   模型过于简单，完全忽略了训练实例中大量有用信息，不可取

一般采用交叉验证法来选取最优k值

多数表决（majority voting rule）

如果分类的损失函数为 0-1 损 失函数, 分类函数为以下多分类
f : R n → { c 1 , c 2 , ⋯   , c K } f: mathbf{R}^{n} rightarrowleft{c_{1}, c_{2}, cdots, c_{K}right} f:Rn→{c1​,c2​,⋯,cK​}
那么误分类的概率是
P ( Y ≠ f ( X ) ) = 1 − P ( Y = f ( X ) ) P(Y neq f(X))=1-P(Y=f(X)) P(Y=f(X))=1−P(Y=f(X))
对给定的实例 x ∈ X x in mathcal{X} x∈X, 其最近邻的 $k$ 个训练实例点构成集合 N k ( x ) N_{k}(x) Nk​(x) 。如果涵盖 N k ( x ) N_{k}(x) Nk​(x) 的区域的类别是 c j c_{j} cj​, 那么误分类率是
1 k ∑ x i ∈ N k ( x ) I ( y i ≠ c j ) = 1 − 1 k ∑ x i ∈ N k ( x ) I ( y i = c j ) frac{1}{k} sum_{x_{i} in N_{k}(x)} Ileft(y_{i} neq c_{j}right)=1-frac{1}{k} sum_{x_{i} in N_{k}(x)} Ileft(y_{i}=c_{j}right) k1​xi​∈Nk​(x)∑​I(yi​=cj​)=1−k1​xi​∈Nk​(x)∑​I(yi​=cj​)
其中： y i y_i yi​ 表示真实类别， C j C_j Cj​ 表示判别类别

要使误分类率最小即经验风险最小, 就要使 ∑ x i ∈ N k ( x ) I ( y i = c j ) sum_{x_{i} in N_{k}(x)} Ileft(y_{i}=c_{j}right) ∑xi​∈Nk​(x)​I(yi​=cj​) 最大, 所以多数表决规 则等价于经验风险最小化。