分类问题是机器学习中的一类问题。比如生物可以按照一定的特征分类，电影可以按题材分类等。K 近邻算法是解决分类问题的一种方法。
例子：对电影按题材分类
有人曾统计过很多电影的打斗镜头和接吻镜头，如下图。假如有一部未看过的电影，如何确定它是爱情片还是动作片？
| 电影名称 | 打斗镜头 | 接吻镜头 | 电影类型 |
|---|---|---|---|
| California Man | 3 | 104 | 爱情片 |
| He’s Not Really into Dudes | 2 | 100 | 爱情片 |
| Beautiful Woman | 1 | 81 | 爱情片 |
| Kevin Longblade | 101 | 10 | 动作片 |
| Robo Slayer 3000 | 99 | 5 | 动作片 |
| Amped II | 98 | 2 | 动作片 |
| ? | 18 | 90 | 未知 |
我们可以计算出未知电影与样本中的电影的距离，以此来推断该电影属于哪一类。至于距离怎么算，下面再说。
|已知电影与未知电影的距离|
| 电影名称 | 与未知电影的距离|
|:—————-:|:———–:|
| California Man | 20.5 |
| He’s Not Really into Dudes | 18.7 |
|Beautiful Woman |19.2|
| Kevin Longblade| 115.3 |
|Robo Slayer 3000|117.4|
|Amped II|118.9|
现在我们得到了样本中的电影与未知电影的距离，按照递增排序，可以找到 $k$ 个距离最近的电影。假定 $k=3$，则单个最靠近的电影依次是 He’s Not Really into Dudes、 Beautiful Woman 和 California Man。这样我们可以推断出未知电影与这三部电影属于同一题材，属于爱情片。
K 近邻算法概述
K 近邻算法采用不同测量不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标准型。
距离度量：
k 近邻模型的特征空间一般是 $n$ 维实向量空间 $R^n$，可采用欧式距离进行度量，或者更一般的 $L_p$ 距离：
$$L_p(x,y)= \left( \sum_{i=1}^n \vert x_i - x_j \vert ^p\right)^ \frac{1}{p},p \geq 1$$