chap3 KNN模型简洁总结

由于KNN是一种基于实例学习的算法，不需要训练过程。

只需要确定了数据集、距离度量、k值以及分类规则，某个样本的类别就能被唯一确定。

因此下文不介绍学习策略和学习算法。

1、KNN模型

输入空间：$\mathcal{X} \in \mathbb{R}^n$

输出空间：$\mathcal{y} \in \{c_1,c_2,…,c_K\}$

特征空间：不显式学习

2、距离度量

一般采用 $L_p$ 距离(闵可夫斯基距离，Minkowski distance).

$L_p$ 的表达式：$L_p(\vec{x_i},\vec{x_j}) = (\sum\limits_{l=1}^n \lvert x_i^{(l)} - x_j^{(l)} \rvert ^p)^{\frac{1}{p}}$ $\quad$ ($p \geq 1$)

$p = 2$ 时就是欧氏距离：$L_2(\vec{x_i},\vec{x_j}) = \sqrt{\sum\limits_{l=1}^n (x_i^{(l)} - x_j^{(l)})^2}$

$p = 1$ 时称为曼哈顿距离：$L_1(\vec{x_i},\vec{x_j}) = \sum\limits_{l=1}^n \lvert x_i^{(l)} - x_j^{(l)} \rvert$

$p = \infty$ 时，它是各个维度坐标距离的最大值：$L_{\infty} = \max\limits_{l} \lvert x_i^{(l)} - x_j^{(l)} \rvert$

3、k值选择

k值过小，模型容易受到噪声点影响导致过拟合；k值过大则容易欠拟合.

k值一般通过交叉验证选取。

4、分类决策规则

一般考虑让经验风险最小，也就是误分类率 $\frac{1}{K} \sum\limits_{\vec{x_i} \in N_K(\vec{x})} \mathbb{I}(y_i \neq c_k)$ 最小

也就是要让 $\frac{1}{K} \sum\limits_{\vec{x_i} \in N_K(\vec{x})}\mathbb{I}(y_i = c_j) = 1 - \frac{1}{K} \sum\limits_{\vec{x_i} \in N_K(\vec{x})} \mathbb{I}(y_i \neq c_k)$ 最大

当损失函数为0-1损失很熟时，多数表决规则分类函数为：$y = \mathop{\arg\max}\limits_{c_j} \sum\limits_{\vec{x_i} \in N_K(\vec{x})}\mathbb{I}(y_i = c_j)$

所以多数表决规则等价于经验风险最小