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树的例子
参考网址
