1.KNN介绍

k临近算法 也叫Knn 是一种基于样本的模型,当K取值为1时
算法原理是 对于新的实例, 在训练集中找到距离最相近的K个样本,根据这K个样本的所属的类别,来归类这个新样本.
采取多数表决机制. 多数表决等价于经验风险最小化

维基百科的图

2.K近邻的距离度量方法

由于KNN是基于实例的, 所以要进行距离度量,常见的距离度量方法有

• 欧氏距离

  
  欧氏距离.png

• 曼哈顿距离
  曼哈顿距离 指的是在坐标轴上的投影距离
  二维空间点的曼哈顿距离
  |x1-x2|+|y1-y2|

曼哈顿距离

• 切比雪夫距离

  
  切比雪夫距离

• 余弦夹角

  
  余弦夹角

各种距离的算法实现.png
image.png

还有许多距离算法 以后再慢慢写

3 k值的选择

4 算法实现 KD树

knn的实现方法

1. 线性扫描

线性扫描是对整个数据集进行遍历,计算每个输入实例与数据集的向量距离,时间复杂度很高.

- 2. kd树

对k维空间中的数据进行存储,并进行检索的树形数据结构

k维生成kd树的例子 检索kd树的例子

参考网址

• http://blog.csdn.net/v_july_v/article/details/8203674