1.基本概念

KNN简单的说就是在特征空间内找到该样本最近的几个‘邻居’出现次数最多的那一类。

KNN是一种分类算法，基于实例学习(没有训练阶段的直接预测)

2.三种空间距离计算

欧氏距离(两点之间直线距离):

$d = \sqrt{\sum_{i=1}^n(x1i-x2i)^2 }$

曼哈顿距离(对角线距离之和):

$d = \sum_{i=1}^N\vert x1i - x2i \vert$

切比雪夫距离(两点之间走斜线或直线的最短距离):

$d = max(\vert x1i - x2i \vert )$

3.关于K值选取标准

K过小，易被噪声印象，发生过拟合；

K过大，较远的测试集也会对预测发生影响；

K应该选奇数，避免偶数可能相等的情况出现；

一般K的取值不超过20，可以取多个K值，计算该测试集下产生的误差，选取误差最小的；

K一般低于训练样本数的平方根；

4.优化

1.考虑权重:将每个点到预测数据的距离的倒数作为权重

2.关于数据的归一化

常见归一化处理:加快梯度下降求最优解的速度并且提高了准确度

最值归一化(所有数据映射到0-1之间):适用于样本有明显边界

均值方差归一化(符合正态分布，所有数据诡异到均值为0，方差为1的分布中):适用于有极端数据存在的情况

方差:描述随机变量对于数学期望的偏离程度

3.KD树

BST二叉查找树:简单的说就是构建出来的二叉树，左侧永远小于右侧。

KD树:对特征向量进行划分，构建二叉树。KD树来源于BST，但是BST只能处理二维，而KD树是高维索引树，常用于大规模高维数据密集的查找比对的使用场景中。KD树每次选择其中一个维度的某一个值作BST。

维度选取顺序:取方差最大的维度作为当前划分维度(特征值最为分散)

划分数值选取条件:取当前维度中值

简单的说，KD树就是将特征空间分为多个超平面，然后在超平面内找到预测对象属于哪个范围。

过程:找到距离最小的叶节点，然后回溯（往回查找预测样本最近的结点）

5.核心代码

import numpy as np

def knn_method(test_data,train_set,labels,k):

# 1.将test_data复制为和训练集一样的大小，便于每行操作

rows = train_set.shape[0]

test_data = np.tile(test_data,(rows,1))

# 2.利用矩阵向量计算距离（欧式距离）

train_set = np.sqrt(np.sum((train_set - test_data) ** 2,axis = 1))

# 3.按照每个距离的所在位置的索引，进行距离大小排序，便于从label中取指定位置

sort_distance = np.argsort(train_set)

out = []

for i in range(k):

out.append(labels[sort_distance[i]])

# 4.获取K个点中出现次数最多的label 对外输出

result = {}

for item in out:

if item in result:

result[item] = result[item] + 1

else:

result[item] = 1

key_name = max(result, key=result.get)

return key_name;

KNN近邻算法