1、k近邻法（k-nearest neighbor，k-NN）是一种基本分类与回归方法，该方法的输入是实例的特征向量，对应于特征空间的点，输出是实例的类别。刚开始给定一个训练数据集，其中的实例类别已定，分类时对新的实例会根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。 k近邻法不具有显式的学习过程，实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”，k值的选择、距离度量以及分类决策规则是k近邻法的三个基本要素。
2、k近邻算法的定义：给定一个数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这些实例多数属于哪个类，就把输入实例分为这个类。 输入——训练数据集T={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈χ⊆R为实例的特征向量，yi∈γ={c1,c2,…,ck}为实力类别 输出——实例x所属类别y (1)根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x邻域记作Nk(x)； (2)在Nk(x)中根据分类决策规则（如多数表决）决定x的类别y 其中I是指示函数，当yi=cj时I为1，否则为0。 k近邻算法的特殊情况是k=1的情形，称为最近邻算法，对于输入的实例点（特征向量）x，最近邻法将训练数据集中与x最邻近点的类作为x的类别。
3、k近邻模型：k近邻法中，当训练集、距离度量、k值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类别被唯一确定，相当于根据上述要素将特征空间划分为一些子空间，确定子空间中每个点所属的类别。 特征空间中，对每个训练实例点xi，距离该点比其他点更近的所有点组成一个区域，叫做单元（cell），每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分，最近邻法将实例xi的类yi作为其单元中所有点的类标记，这样每个单元的实例点的类别是确定的。
4、距离度量：特征空间中两个实例点的距离是这两个实例点相似程度的反映，k近邻模型的特征空间一般是n维实数向量空间R，使用的距离可以是是欧氏距离、Lp距离等，由不同的距离度量所确定的最近邻点是不同的。设特征空间χ是n维实数向量空间R,xi、xj∈χ，其中 则xi、xj的Lp距离定义为： (1)当p=2时，称为欧氏距离 (2)当p=1时，称为曼哈顿距离 (3)当p=∞时，它是各个坐标距离的最大值 5、k值的选择：k值的选择会对k近邻法的结果产生重大影响，在应用中k值一般去一个比较小的数值，通常采用交叉验证法选取最优的k值。
选择较小的k值——相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用，缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感，如果邻近的实例点恰巧是噪声，预测就会出错，也就是说k值的减小意味着整体模型变得复杂，容易发生过拟合；选择较大的k值——相当于用较大邻域中的训练实例进行预测，优点是可以减少学习的估计误差，缺点是学习的近似误差会增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误，k值的增大意味着整体的模型变得简单；k=N时，无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类，这时模型过于简单，完全忽略训练实例中的大量有用信息。6、分类决策规则：k近邻法中的分类决策规则往往是多数表决，由输入实例的k个邻近训练实例中的多数类决定输入实例的类。如果分类的损失函数为0-1损失函数，分类函数为f：R→{c1,c2,…,cK}，那么误分类概率为P（Y≠f(X)）=1-P（Y=f(X)），对给定的实例x∈χ，其最近邻的k个训练实例点构成集合Nk(x)，如果涵盖该集合的区域类别是cj，那么误分类率为 要使误分类率最小即经验风险最小，就要使∑I（yi=cj）最大，多以多数表决规则等价于经验风险最小化。
7、实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索，在特征空间的维数大及训练数据容量大时尤为重要。最简单的实现方法是线性扫描，这时要计算输入实例和每一个训练实例的距离，当训练集较大时计算非常耗时。为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数，比如kd树方法。
import numpy as np import pandas as pd import matplotlib.pyplot as plt data = pd.read_csv('iris.data.csv', header=None) data.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'species'] # 特征及类别名称 X = data.iloc[0:150, 0:4].values y = data.iloc[0:150, 4].values y[y == 'Iris-setosa'] = 0 # Iris-setosa 输出label用0表示 y[y == 'Iris-versicolor'] = 1 # Iris-versicolor 输出label用1表示 y[y == 'Iris-virginica'] = 2 # Iris-virginica 输出label用2表示 X_setosa, y_setosa = X[0:50], y[0:50] # Iris-setosa 4个特征 X_versicolor, y_versicolor = X[50:100], y[50:100] # Iris-versicolor 4个特征 X_virginica, y_virginica = X[100:150], y[100:150] # Iris-virginica 4个特征 # training set X_setosa_train = X_setosa[:30, :] y_setosa_train = y_setosa[:30] X_versicolor_train = X_versicolor[:30, :] y_versicolor_train = y_versicolor[:30] X_virginica_train = X_virginica[:30, :] y_virginica_train = y_virginica[:30] X_train = np.vstack([X_setosa_train, X_versicolor_train, X_virginica_train]) y_train = np.hstack([y_setosa_train, y_versicolor_train, y_virginica_train]) # validation set X_setosa_val = X_setosa[30:40, :] y_setosa_val = y_setosa[30:40] X_versicolor_val = X_versicolor[30:40, :] y_versicolor_val = y_versicolor[30:40] X_virginica_val = X_virginica[30:40, :] y_virginica_val = y_virginica[30:40] X_val = np.vstack([X_setosa_val, X_versicolor_val, X_virginica_val]) y_val = np.hstack([y_setosa_val, y_versicolor_val, y_virginica_val]) # test set X_setosa_test = X_setosa[40:50, :] y_setosa_test = y_setosa[40:50] X_versicolor_test = X_versicolor[40:50, :] y_versicolor_test = y_versicolor[40:50] X_virginica_test = X_virginica[40:50, :] y_virginica_test = y_virginica[40:50] X_test = np.vstack([X_setosa_test, X_versicolor_test, X_virginica_test]) y_test = np.hstack([y_setosa_test, y_versicolor_test, y_virginica_test]) class KNearestNeighbor(object): def __init__(self): pass # 训练函数 def train(self, X, y): self.X_train = X self.y_train = y # 预测函数 def predict(self, X, k=1): # 计算L2距离 num_test = X.shape[0] num_train = self.X_train.shape[0] dists = np.zeros((num_test, num_train)) # 初始化距离函数 # because(X - X_train)*(X - X_train) = -2X*X_train + X*X + X_train*X_train, so d1 = -2 * np.dot(X, self.X_train.T) # shape (num_test, num_train) d2 = np.sum(np.square(X), axis=1, keepdims=True) # shape (num_test, 1) d3 = np.sum(np.square(self.X_train), axis=1) # shape (1, num_train) dist = np.sqrt(d1 + d2 + d3) # 根据K值，选择最可能属于的类别 y_pred = np.zeros(num_test) for i in range(num_test): dist_k_min = np.argsort(dist[i])[:k] # 最近邻k个实例位置 y_kclose = self.y_train[dist_k_min] # 最近邻k个实例对应的标签 y_pred[i] = np.argmax(np.bincount(y_kclose)) # 找出k个标签中从属类别最多的作为预测类别 return y_pred plt.scatter(X_setosa[:, 0], X_setosa[:, 2], color='red', marker='o', label='setosa') plt.scatter(X_versicolor[:, 0], X_versicolor[:, 2], color='blue', marker='^', label='versicolor') plt.scatter(X_virginica[:, 0], X_virginica[:, 2], color='green', marker='s', label='virginica') plt.xlabel('sepal length') plt.ylabel('petal length') plt.legend(loc = 'upper left') plt.show() # 训练集 plt.scatter(X_setosa_train[:, 0], X_setosa_train[:, 2], color='red', marker='o', label='setosa_train') plt.scatter(X_versicolor_train[:, 0], X_versicolor_train[:, 2], color='blue', marker='^', label='versicolor_train') plt.scatter(X_virginica_train[:, 0], X_virginica_train[:, 2], color='green', marker='s', label='virginica_train') # 测试集 plt.scatter(X_setosa_test[:, 0], X_setosa_test[:, 2], color='y', marker='o', label='setosa_test') plt.scatter(X_versicolor_test[:, 0], X_versicolor_test[:, 2], color='y', marker='^', label='versicolor_test') plt.scatter(X_virginica_test[:, 0], X_virginica_test[:, 2], color='y', marker='s', label='virginica_test') plt.xlabel('sepal length') plt.ylabel('petal length') plt.legend(loc = 4) plt.show()8、构造kd树：kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分，构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分，构成一系列k维超矩形区域，每一个结点对应一个k维超矩形区域。
输入——k维空间数据集T={x1,x2,…,xN} 输出——kd树步骤： (1)开始：构造根节点，对应于包含T的k维空间的超矩形区域。选择x(1)为坐标轴，以T中所有实例的x(1)坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域，切分由通过切分点并与坐标轴x(1)垂直的超平面实现。 由根结点生成深度为1的左、右子结点：左子结点对应坐标x(1)小于切分点的子区域，右子结点对应坐标x(1)大于切分点的子区域，将落在切分超平面上的实例点保存在根结点； (2)重复：将深度为j的结点，选择x(l)为切分的坐标轴，l=j(mod k) + 1，以该点的区域中所有实例的x(l)坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域，切分由通过切分点并与坐标轴x（l)垂直的超平面实现， 由该结点生成深度为j+1的左、右子结点：左子结点对应坐标x(l)小于切分点的子区域，右子结点对应坐标x(l)大于切分点的子区域，将落在切分超平面上的实例点保存在根结点； (3)直到两个子区域没有实例存在时停止，从而形成kd树的区域划分。9、搜索kd树： 如果实例点随机分布，kd树搜索的平均计算复杂度是O(logN)，N是训练实例数，kd树适用于训练实例数远大于空间维数时的k近邻搜索，当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。
输入——已构造的kd树，目标点x输出——x的最近邻步骤： (1)在kd树中找出包含目标点x的叶结点，从根结点出发，递归向下访问kd树，若目标点x当前维的坐标小于切分点的左边，则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止； (2)以此叶结点为“当前最近点”； (3)递归向上回退，在每个结点进行以下操作： （a）如果该节点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”； （b）当前最近点一定存在于该结点一个子结点对应的区域，检查该子结点的父结点的另一子结点对应的区域是否有更近的点，具体地，检查另一子结点对应的区域是否以目标点为秋心、以目标点与当前最近点间的距离为半径的超球体相交。 如果相交，可能在另一个子结点对应的区域内存在距离目标点更近的点，移动到另一个子结点，接着递归地进行最近邻搜索；如果不相交向上回退； (4)当回退到根结点时搜索结束，最后的“当前最近点”即为x的最近邻点。 T = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]] # 定义节点类 class node: def __init__(self, point): self.left = None self.right = None self.point = point self.parent = None pass def set_left(self, left): if left == None: pass left.parent = self self.left = left def set_right(self, right): if right == None: pass right.parent = self self.right = right # 计算中位数 def median(lst): m = len(lst) / 2 return lst[int(m)], int(m) # 构建kd树 def build_kdtree(data, d): # 按照元组里面第d个元素进行排序 ，lambda隐函数固定写法，可不变 data = sorted(data, key=lambda x: x[d]) p, m = median(data) tree = node(p) del data[m] # 递归搭建二叉树，不断在0和1之间循环排序 if m > 0: tree.set_left(build_kdtree(data[:m], not d)) if len(data) > 1: tree.set_right(build_kdtree(data[m:], not d)) return tree # 欧氏距离 def distance(a, b): print(a, b) return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5 # 搜索kd树 def search_kdtree(tree, d, target): best = [tree.point, 100000.0] # tree.point即为根节点，10000.0即为预设的很大的初始距离值 if target[d] < tree.point[d]: if tree.left != None: return search_kdtree(tree.left, not d, target) else: if tree.right != None: return search_kdtree(tree.right, not d, target) # 不断更新最优值，也就是最小距离 def update_best(t, best): if t == None: return t = t.point d = distance(t, target) if d < best[1]: best[1] = d best[0] = t # 从最底端子节点开始不断向上优化 while (tree.parent != None): # 对比左子树和右子树与最优值，从而不断优化 update_best(tree.parent.left, best) update_best(tree.parent.right, best) tree = tree.parent return best[0] kd_tree = build_kdtree(T, 0) # print (kd_tree.point) print('距离测试点[9, 4]最近的点为：', search_kdtree(kd_tree, 0, [9, 4]))【拓展知识】
k近邻算法的优点：1.KNN分类方法是一种非参数的分类技术，简单直观，易于实现！只要让预测点分别和训练数据求距离，挑选前k个即可，简单直观。
2.KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练
k近邻算法的缺点：1.当样本不平衡时，比如一个类的样本容量很大，其他类的样本容量很小，输入一个样本的时候，K个邻近值大多数都是大样本容量的那个类，这时可能会导致分类错误。
改进方法：对K邻近点进行加权，也就是距离近的权值大，距离远的点权值小。
2.计算量较大，每个待分类的样本都要计算它到全部点的距离，根据距离排序才能求得K个临近点。
改进方法：先对已知样本带你进行裁剪，事先去除分类作用不大的样本，采取kd树以及其它高级搜索方法BBF等算法减少搜索时间。
kd树的最差情况：当给定的数据分布很差的时候，我们每一次计算画圆过程中，都会与每一个分割面相交，都会递归搜索到该结点的另一个子空间中遍历，那么这样最坏的情况是进行线性时间搜索，几乎退化为线性时间0（n）。来源：统计学习方法、博客园
