# KNN算法
KNN算法的输入基于对实例的学习，或称作懒惰学习（Lazy Learning），在处理训练集的时候没有建立模型，在开始归类的时候，根据之前的比较再进行归类。
# 例子
| 电影名称 | 打斗场景数 | 结婚场景数 | 电影类型 |
|---|---|---|---|
| a | 20 | 77 | 爱情片 |
| b | 12 | 55 | 爱情片 |
| c | 90 | 21 | 动作片 |
| d | 13 | 88 | 爱情片 |
| 未知 | 76 | 12 | 未知 |
根据之前的实例，对未知的电影进行归类。
对于这个问题，可以简化为以下的数学模型。
| 点 | x坐标 | y坐标 | 点类型 |
|---|---|---|---|
| a | 20 | 77 | 爱情片 |
| b | 12 | 55 | 爱情片 |
| c | 90 | 21 | 动作片 |
| d | 13 | 88 | 爱情片 |
| e | 76 | 12 | 未知 |
# 算法描述
- 算法步骤
- 为了判断未知实例的类型，用已知类别的实例作为参考
- 选择一个参数K（K代表选取这个未知类型最近的K个元素）
- 计算所有点到未知点的距离
- 在所有距离中，选择出K个最近的距离
- 根据少数服从多数的法则，让未知实例的类型是K个中实例最多的那个类型
- 算法的细节
- 对于距离，有很多种定义方式，比如最普遍的欧式距离（两点之间的直线距离）、曼哈顿距离、相关度等等。
# 优缺点及改进
# 优点
简单、易于理解、容易实现、可以选择不同的K值增强算法的健壮性。
# 缺点
- 需要大量的空间去存储已知实例的距离
- 算法的复杂度高
- 当某一类的样本数过多的时候，未知实例容易被归为样本多的那个类别。
# 改进
优化距离，距离加上一个权重，比如权重 = 1/距离