统计学习方法-第3章-k近邻法
- 适用问题：多分类、回归
- 模型特点：特征空间，样本点
- 模型类型：判别模型
- 多数表决、无显示的学习过程
- 三个基本要素：k值的选择、距离度量、分类决策规则
模型
k 近邻法的模型对应特征空间的一个划分。
距离度量
特征空间中的两个实例点的距离是两个实例点相似程度的反映。距离越近(数值越小)， 相似度越大。
$L_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 } }\]-
p = 1，曼哈顿距离
-
p = 2，欧式距离
-
p = ∞
k 值的选择
-
k 值的选择反应了对近似误差与估计误差之间的权衡；
-
k 值减小，整体模型变得复杂，易发生过拟合；
-
k 值增大，整体模型变得简单；
在应用中，k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。
分类决策规则
多数表决规则，对应于经验风险最小化。
损失函数：0-1 损失函数
分类函数：$f: \mathbf { R } ^ { n } \rightarrow \left{ c_1, c_2,\cdots,c_K \right}$
误分类的概率：$P \left( Y \neq f\left( X \right) \right) = 1 - P \left( Y = f\left( X \right) \right)$
给定实例 $x \in \mathcal {X}$，其最近邻的 k 个训练实例点构成集合 $N_k\left( x \right)$。如果涵盖 $N_k\left( x \right)$ 的区域的类别是 $c_j$，那么误分类率是
\[\frac { 1 } { k } \sum _ { x _ { i } \in N _ { k } ( x ) } I \left( y _ { i } \neq c _ { i } \right) = 1 - \frac { 1 } { k } \sum _ { x _ { i } \in N _ { k } ( x ) } I \left( y _ { i } = c _ { i } \right)\]策略
无显示的学习过程
算法
输入：$T = \left{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \cdots , \left( x _ { N } , y _ { N } \right) \right}$，$x _ { i } \in \mathcal { X } = \mathbf { R } ^ { n }$，$y _ { i } \in \mathcal { Y } = { c _ { 1 } , c _ { 2 }, \cdots ,c _ { k } }$，实例特征向量 $x$;
输出：实例所属的类 $y$
步骤：
-
根据指定的距离度量，在 $T$ 中查找 $x$ 的最近邻的 $k$ 个点，覆盖这 $k$ 个点的 $x$ 的邻域定义为 $N_k(x)$
-
在 $N_k(x)$ 中应用分类决策规则决定 $x$ 的类别 $y$
$I$ 为指示函数。