K近邻算法的理解和KD树的构造A类，实例归入此类。输入：训练数据集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；output：根据指定的距离度量，实例x所属的类别y在训练集T中找到距离实例x最近的k个点，覆盖这k个点的x的域记为$N_k(x)$；在$N_K(x)$中，根据分类决策规则确定x的类别y：$$y=argmax_{c_j}\sum_{x_i\inN_k(x)}{I(y_i=c_i)}，i\in\{1,2,...,N\},j\in\{1,2,...,K\}\tag{1}$$式1中，I为指示函数，但是$y_i=c_i$为1，否则为0。K最近邻算法的特例是k=1的情况，称为最近邻算法。对于输入的实例点（特征向量）x，最近邻法将训练数据集中与x最近邻的点的类作为x的类。k最近邻方法没有明确的学习过程。K近邻模型K近邻算法使用的模型实际上对应的是特征空间的划分。该模型由三个基本要素确定——距离度量、K值的选择和分类决策规则。模型K最近邻法当训练集、距离度量（如欧氏距离）、k值和分类决策规则（如多数表决）确定后，对于任何新的输入实例，其所属的类是唯一确定的。这相当于将特征空间根据上述元素划分为一些子空间，并确定子空间中每个点所属的类。如下所示。特征空间中两个实例点之间的距离是两个实例点相似性的反映。k近邻模型的特征空间一般是n维实数向量空间$R^n$。使用的距离是欧氏距离，但也可以是其他距离，比如更一般的$L_p$距离或者闵可夫斯基距离让特征空间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值的增加意味着整体模型变得更简单。如果k=N，那么无论输入实例是什么，都会简单的预测它属于训练实例中的最多的类。此时模型过于简单，完全忽略训练样例中的大量有用信息是不可取的。在应用中，k的取值一般取较小的值。通常，交叉验证方法用于选择最优秀的k值。分类决策规则k近邻法中的分类决策规则往往是多数表决，即输入实例的类别由输入实例的k个相邻训练实例中的多数决定。多数表决规则解释如下：如果分类损失函数是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$，a设置其最近邻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)$最大，所以多数表决规则等价于经验风险最小化K最近邻方法类Knn的代码实现：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,'维数x必须等于2'#计算距离矩阵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])]#获取根据索引n_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)#output:0.93333333333333333print(net.score)在sklearn中使用knn分类器fromsklearn.neighborsimportNeighborsClassifiernet1=NeighborsClassifier()net1.fit(x_train,y_train)#输出：0.9333333333333333net1.score(x_test,y_test)K近邻法的实现：K近邻法最简单的实现方式是线性扫描。这时候就需要计算输入实例和每个训练实例之间的距离。当训练集很大时，计算非常耗时，这种方法不可行。为了提高k近邻搜索的效率，可以考虑使用特殊的结构来存储训练数据，减少计算距离的次数。下面介绍kd树（kdtree）算法构造kd树。构造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$;output:startofkdtree:构造根节点，根节点对应包含T的k维空间的超矩形区域。选择$x^{(1)}$作为坐标轴，取T中所有实例的$x^{(1)}$坐标的中位数作为分割点（如果数据集个数为偶数，选择中间坐标或者右边的树作为分割点，不影响），将根节点对应的超矩形区域划分为两个子区域。分割是通过一个超平面通过分割点并垂直于坐标轴$x^{(1)}$来实现的。从根节点生成深度为1的左右子节点：左子节点对应坐标$x^{(1)}$小于分割点的子区域，右子节点-node对应坐标$x^{(1)}$大于分割点的子区域。将落在分割超平面上的实例点存储在根节点中。重复：对于深度为j的节点，选择$x^{(l)}$作为分割的坐标轴，$l=j\quad\%\quadk+1$（%表示取余），以及用这个结点区域内所有实例的$x^{(l)}$坐标的中值作为切分点，将该结点对应的超矩形区域划分为两个子区域。分裂是通过一个超平面通过分裂点并垂直于坐标轴$x^{(l)}$来实现的。从该节点生成深度为j+1的左右子节点：左子节点对应坐标$x^{(l)}$小于分割点的子区域，右子节点子节点对应的坐标$x^{(l)}$大于分割点的子区域。将落在分割超平面上的实例点保存在该节点中。停止直到两个子区域中不存在实例。从而形成kd树的区域划分。给定二维空间中的数据集：$$T=\{(2,3)^T,(5,4)^T,(9,6)^T,(4,7)^T,(8,1)^T,(7,2)^T\}$$构建一棵平衡的kd树首先构建根节点，$x^{(1)}$坐标的中位数为7（如果数据个数为对于偶数，可以用中位数的左右两边，这里以右边作为切点），空间被平面$x分成左右两个子矩形（节点）^{(1)}=7$；$x如果^{(1)}$小于7，向左移动，如果$x^{(1)}$大于7，向右移动。然后，左边的矩形被$x^{(2)}=4$分成2个子矩形（节点）。如此递归，最终得到如下图所示的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):如果node不是None: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个邻居。令L为包含目标点的k个最近邻居的列表。首先找到包含目标点的叶子节点，从根节点开始，以根节点为当前节点，在当前节点的切割维度上比较当前节点和目标点的大小，移动到根节点，因为左边3<7。以(5,4)为当前节点，因为4.5>4，所以转到(5,4)的右边，即(4,7)。以(4,7)为当前节点，因为(4,7)没有子节点，L的长度小于3，将(4,7)添加到L。回到根节点(5,4)of(4,7),并使用(5,4)作为当前节点。如果L的长度小于3，则将(5,4)加到L上，转为当前节点的另一个子节点。如果L的长度等于3，计算当前节点到目标点的距离。如果距离大于L中的最大距离，则说明当前节点的另一条分支与目标点的超球面没有交集（另一条分支不会有更近的点）。由于L的长度为2，小于3，所以转到节点(2,3)作为当前节点添加到L中。由于当前节点没有子节点，所以返回父节点(5,4)。由于已经访问过父节点，继续退回到父节点，当到达节点(7,2)时，将(7,2)作为当前节点。由于L的长度为3，此时计算当前节点到目标点的距离，计算出的距离大于L中的最大距离。结束搜索过程，返回L。搜索代码为如下：deftravel(node,target,L,k=3):"""Params:node(Node):当前节点L(dict):k，也就是对应的距离。{'nearest':[],'dist':[],'max_dist':float('inf')}k(integer):指定搜索附近点的个数"""ifnodeisNone:return#ofthecurrentnodesplitdimensions=node.split#当前节点的值pivot=node.x0#如果目标节点的splitdimension的值小于当前节点#目标点更接近左子树iftarget[s]
