输入:训练数据集T${(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$,其中$x_i\in\chi\subseteqR^n$为实例的特征向量,$y_i\in\gamma=\{c_1,c_2,...,c_k\}$.i=1,2,...,N.实例特征向量x;
输出:实例x所属的类别y
式1中,I为指示函数,但$y_i=c_i$时为1,否则为0.
K近邻算法的特殊情况是k=1的情形,称为最近邻算法,对于输入的实例点(特征向量)x，最近邻法将训练数据集中与x最邻近点的类作为x的类。k近邻法没有显式的学习过程。
K近邻算法使用的模型实际上对应于特征空间的划分.模型由三个基本要素-距离度量、K值的选择和分类决策规则决定。
K近邻法当训练集、距离度量（如欧氏距离）、k值及分类决策规则（如多数表决））确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。如下图所示。
特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间$R^n$。使用的距离是欧氏距离，但也可以是其他距离，如更一般的$L_p$距离或Minkowski距离
设特征空间x是n维实数向量空间$R^n;x_i,x_j\in\chi,x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^T$,$x_i,x_j$的$L_p$距离定义为
$$L_p(x_i,x_j)=(\sum_{l=1}^N|(x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p}\tag{2}$$
这里p>0。当p=2时，$L_p$距离为欧式距离。
当p=1时，$L_p$距离为曼哈顿距离。
$$L_p(x_i,x_j)=\sum_{l=1}^N|(x_i^{(l)}-x_j^{(l)}|\tag{3}$$
当p=$\infty$时，它是各个坐标距离的最大值，即
$$L_p(x_i,x_j)=max_{(l)}|(x_i^{(l)}-x_j^{(l)}|\tag{4}$$
如下图给出了二维空间中p取不同值时，与原点的$L_p$距离为1（$L_p$＝1）的点的图形。
k值的选择会对k近邻法的结果产生重大影响。如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。k值的增大就意味着整体的模型变得简单。如果k＝N，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。
在应用中，k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。
k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。多数表决规则（majorityvotingrule）有如下解释：如果分类的损失函数为0-1损失函数，分类函数为
$$f:R^n\rightarrow\{c_1,c_2,...,c_k\}$$
那么误分类的概率为
$$P(Y\neqf(X))=1-P(Y=f(X))\tag{5}$$
对给定的实例$x\in\chi$，其最近邻的k个训练实例点构成的集合$N_k(x)$。如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率是
$$\frac{1}{k}\sum_{x_i\inN_k(x)}=1-\frac{1}{k}\sum_{x_i\inN_k(x)}I(y_i=c_j)\tag{6}$$
要使误分类率最小即经验风险最小，就要使$\sum_{x_i\inN_k(x)}I(y_i=c_j)$最大，所以多数表决规则等价于经验风险最小化
classKnn:def__init__(self,x_train,y_train,k=3):self.k=kself.x_train=x_trainself.y_train=y_traindefpredict(self,x,y_test=None):assertlen(x.shape)==2,'dimensionofxmustbeequalwith2'#计算距离矩阵dis=(self.x_train[:,None,:]-x)**2dis=dis.sum(-1)#按照距离升序排序，取出前k个样本的索引n_k_idx=dis.argsort(0)[:self.k]#n_k_labels=[self.y_train[n_k_idx[:,i]]foriinrange(n_k_idx.shape[1])]#根据索引获取labeln_k_label=self.y_train[n_k_idx]#得到出现次数最多的标签作为最终结果y_pred=np.array([np.argmax(np.bincount(n_k_label[:,i]))foriinrange(n_k_label.shape[1])])#如果y_test不为空，计算预测得分ify_testisnotNone:self.score=self._score(y_pred,y_test)returnresdef_score(self,y_pred,y_test):returnnp.count_nonzero(y_test==y_pred)/len(y_pred)这里使用鸢尾花数据作为演示
data=load_iris()X,y=data['data'],data['target']x_train,x_test,y_train,y_test=train_test_split(X,y,random_state=20190303,shuffle=True,test_size=0.1)net=Knn(x_train,y_train)net.predict(x_test,y_test)#输出：0.9333333333333333print(net.score)使用sklearn中的knn分类器
fromsklearn.neighborsimportNeighborsClassifiernet1=NeighborsClassifier()net1.fit(x_train,y_train)#输出：0.9333333333333333net1.score(x_test,y_test)K近邻法的实现：kd树k近邻法最简单的实现方法是线性扫描。这时要计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。下面介绍kd树(kdtree)算法
构造kd树的算法如下
输入：k维空间数据集$T=\{x_1,x_2,...,x_N\}$,其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T,i=1,2,...,N$；
输出：kd树
给定一个二维空间的数据集：
$$T=\{(2,3)^T,(5,4)^T,(9,6)^T,(4,7)^T,(8,1)^T,(7,2)^T\}$$
构建一个平衡kd树
kd树构建的代码如下
classNode:def__init__(self,x0):self.left=Noneself.right=Noneself.x0=x0self.split=Nonedefcreate_node(data,depth=0):n,f=data.shapeifn==0:returnifn==1:node=Node(data[0])node.split=depth%freturnnode#构建根节点feat=data[:,depth%f]sorted_feat=feat.argsort()x0=data[sorted_feat[int(n/2)]]node=Node(x0)node.split=depth%fnode.left=create_node(data[sorted_feat[:int(len(feat)/2)]],depth+1)node.right=create_node(data[sorted_feat[int(len(feat)/2)+1:]],depth+1)returnnode#树的前序遍历defpreorder(node):ifnodeisnotNone:print(node.x0)preorder(node.left)preorder(node.right)classKDTree:def__init__(self,data):self.root=create_node(data)kd搜索树下面介绍如何利用kd树进行k近邻搜索
给定一个目标点，搜索它的k个近邻。首先找到包含目标点的叶子结点；然后从该叶子节点出发，依次回退到父结点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。
现在上图构建的kd树的基础上，找到$[3,4.5]^T$的3个近邻。
搜索代码如下所示：
a=np.array([[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]])tree=KDTree(a)find_k_nearest(tree,[3,4.5])运行结果：
在400000样本点中找目标点的3个近邻点，看一下kd树的效率
frompprintimportpprintN=400000t0=time()#构建包含N个3维空间样本点的kd树kd2=KDTree(np.random.randn(N,3))#在N个样本点中寻找离目标最近的k个点ret2=find_k_nearest(kd2,[0.1,0.5,0.8])t1=time()print("time:",t1-t0,"s")pprint(ret2)运行结果：
1．k近邻法是基本且简单的分类与回归方法。k近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的k个最近邻训练实例点，然后利用这k个训练实例点的类的多数来预测输入实例点的类。
2．k近邻法三要素：距离度量、k值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的$p_L$距离。k值小时，k近邻模型更复杂；k值大时，k近邻模型更简单。k值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的k。常用的分类决策规则是多数表决，对应于经验风险最小化。
3．kd树是一种便于对k维空间中的数据进行快速检索的数据结构，如果实例点是随机分布的，kd树搜索的平均计算复杂度是O(logN)，这里N是训练实例数。kd树更适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。