ch3-KNN

K 近邻算法

直接解释：

给定一个训练集 $T$ ，对于新输入的实例 $x{i}$，选取 $T$ 中与该实例最解决的 $K$ 的实例中占多数的那个类别，作为 $x{i}$ 的类别

K 近邻算法没有显式的学习过程。

三大要素

三大要素确定后，模型即可确定。

距离度量

特征空间中两个点的距离是两个点相似程度的反应。在一般的 $n$ 维空间中我们可以使用 欧式距离，还有 $L_{p}$，他们之间是有关系的。

$$L_{p} = (\sum_{l=1}^{n}(|x_{i}^{l} - x_{j}^{l}|)^p)^{\frac {1}{p}}$$

其中 $x{i} = { x{i}^{1}, x{i}^{2},… x{i}^{l} }$ 。

当 $p = 1$，则是曼哈顿距离；

当 $p=2$，则是欧式距离

$$L_{2} = \sum_{l=1}^{n}|x_{i}^{l} - x_{j}^{l}|^{ 1 \over 2}$$

K 值的选择

K 值的选择会对结果产生重大影响：

• 过小：敏感，受近的数据点支配，容易过拟合
• 过大：不敏感，近似误差大

解决方法：选择一个较小的 K 值，然后交叉验证

决策规则

一般是多数表决。

KNN 的多数表决是让误分类的概率最小，是满足经验风险最小化的要求的。

计算优化

这一块的知识还得再了解。

资料：kd 树