本文共 7554 字，大约阅读时间需要 25 分钟。

$KNN$(K-nearest neighbor)

$K$近邻算法

• 输入：训练数据集

$$T=\{$$

​ 其中，$x_i\in R^n$ 为实例的特征向量，$y_i\in Y=\{$

​ 输出：实例 $x$ 所属的类 $y$

• 算法过程：
  1. 根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这$k$ 个点的 $x$ 领域记作 $N_k(x)$;
  2. 在 $N_k(x)$ 中根据分类决策规则(例如多数表决)决定 $x$ 的类别 $y$；

$K$近邻模型

• 距离度量：

  特征空间中两个实例点的距离是两个实例点相似程度的反映。$k$ 近邻模型的特征空间一般是$n$维实数向量空间$R^n$。使用的距离一般是欧式距离，也可以是其他距离，比如**$L_p$距离或者$Minkowski$距离**。

  设特征空间$X$是$n$维实数向量空间$R^n$，$x_i,x_j\in X$ ，$x_i=(x_i^{(1)},x_i^{(2)},\cdot \cdot \cdot ,x_i^{(n)})$，$x_j=(x_j^{(1)},x_j^{(2)},\cdot \cdot \cdot ,x_j^{(n)})$，则$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}}(p\ge 1)$$
  • 当$p=2$ 时，称为欧式距离$(Euclidean$ $distance)$
  • 当$p=1$ 时，称为曼哈顿距离$(Manhattan$ $distance)$
  • 当$p=\infty$ 时，它是个个坐距离的最大值

  选择不同的距离度量对预测结果的影响不同

• $k$值选择：

  $k$的选择会对$k$近邻结果产生重大影响

  $k$值较小学习的“近似误差”会减小，但是“估计误差”会增大，如果$k$实例点所在的领域恰好包含噪声，预测则会出错；$k$值较大可以减少“估计误差”，但是“近似误差会增大”，也就是说离实例点较远的训练点也会对其产生一定影响。

• 分类决策规则：

  一般采用多数表决的方法

$K$近邻的实现

暴力解法(线性查找)

以下代码参考于

import numpy as npimport pandas as pdfrom collections import Counterfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitclass KNN():    def __init__(self,X_train,Y_train,n_neighbors = 3,p = 2,):        """        :params        	n_neighbors:前面所讨论的k        	p:Lp距离参数        """        self.X_train = X_train        self.Y_train = Y_train        self.p = p        self.n_neighbors = n_neighbors    def predict(self,X):        """        :param            X: 输入空间中的变量        :return            Y: 预测的结果        """        # knn_list存放筛选出来的n个结果        knn_list = []        # 先选出n个凑满knn_list        for i in range(self.n_neighbors):            # 计算X和训练集中前n个的距离，范数为p            distance = np.linalg.norm(abs(X-self.X_train[i]),ord = self.p)			knn_list.append((distance,self.Y_train[i]))        # 遍历整个训练集寻找最小的n个值        for i in range(self.n_neighbors,len(self.X_train)):            # 计算距离            distance = np.linalg.norm(abs(X-self.X_train[i]),ord = self.p)            # 找到最大值的下标，knn_list元素是元组，比较对象为元组的第一个元素            max_index = knn_list.index(max(knn_list,key= lambda x:x[0]))            # 如果distance小于knn_list中的最大值，则替换            if knn_list[max_index][0] > distance:                knn_list[max_index] = (distance,self.Y_train[i])        # n个最小距离的标签值        labels = [k[1] for k in knn_list]        # 返回一个Counter对象，含有label以及其出现的次数(dict)        label = Counter(labels)        # 将label中的字典元素根据出现次数即x[1]从大到小排序，并且取Y为第一个字典中的第一个元素        Y = sorted(label.items(),key=lambda x: x[1],reverse = True)[0][0]        return Y    def score(self,X_test,Y_test):        """        :param            X_test:测试数据集输入            Y_test:测试数据集target        :return            返回估计正确率        """        # 计算正确的个数        counter = 0        for index in range(len(X_test)):            # 预测结果            Y = self.predict(X_test[index])            # 预测结果等于真实值则counter增加            if Y == Y_test[index]:                counter+=1        # 返回正确率        return counter/len(X_test)

kd树

# 以下代码包含kd树的建立以及kd树搜索k个近邻点# kd树节点class KdNode():    def __init__(self,split,left,right,value):        self.value = value        self.left = left        self.right = right        self.split = split        self.visited = False# kd树class KdTree():    def __init__(self,data):        # k是维度        k = len(data[0])        # 创建一颗kd树        def CreateTree(split,data_set:np.ndarray):            # 如果为空返回None            if  len(data_set) == 0:                return None            # 将data_set.argsort(axis = 0)按照列从小到大排序            # data_set.argsort(axis = 0)[:,split]选取第split列(这一列是位置)            # data_set[data_set.argsort(axis=0)[:,split]]按照列次序重排            data_set = data_set[data_set.argsort(axis=0)[:,split]]            # 找到中点分隔            split_pos = len(data_set)//2            # 中点的数据            median = data_set[split_pos]            # 下一次的分割点            split_next = (split+1)%k            # 左            left = CreateTree(split_next,data_set[:split_pos])            # 右            right = CreateTree(split_next,data_set[split_pos+1:])            # 当前节点的值            node = KdNode(split,left,right,median)            return node        self.root = CreateTree(0,data)    # 先序非递归遍历kd树    def preorder(self):        lst = []        tree = self.root        while tree or len(lst):            while tree:                print(tree.value)                if tree.right:                    lst.append(tree)                tree = tree.left            if len(lst):                tree = lst.pop().right    # 利用kd树找出X的k个最近点    def search(self,X,p = 2,n_neighbors = 1):        # knn_list用来存放(distance,value)        knn_list = []        # 递归寻找        def Recursive(node:KdNode):            # 节点为空直接返回            if not node:                return True            # node没被访问过            if node.visited == False:                                # 左枝                if X[node.split]<=node.value[node.split]:                    Recursive(node.left)                # 右枝                elif X[node.split] > node.value[node.split]:                    Recursive(node.right)            # 访问过则直接返回            else:                return True            # 标记为访问过            node.visited = True            # 如果knn_list中不够n_neighbors个元素则向其中添加元素            if len(knn_list) < n_neighbors:                # 距离                dist = np.linalg.norm(abs(X - node.value), ord=p)                # 添加(distance,value)元组                knn_list.append((dist,node.value))                # 判断另一枝                if X[node.split] <= node.value[node.split]:                    Recursive(node.right)                else:                    Recursive(node.left)            # 如果knn_list中已经有n_neighbors个元素            else:                # 离边界的距离                edge_dist = abs(X[node.split]-node.value[node.split])                # knn_list中的最大距离所在的元组                max_dist = max(knn_list,key=lambda x:x[0])                # 如果离边界的距离大于最大距离，则在另一边不可能有更小的值                if edge_dist > max_dist[0]:                    return True                # 如果离边界的距离小于最大距离，则当前节点以及另一边可能存在更小值                else:                    # 当前节点和X的距离                   dist = np.linalg.norm(abs(X - node.value), ord=p)                   # 如果当前节点和X距离更小                   if dist < max_dist[0]:                       # 找到下标                       index = knn_list.index(max_dist)                       # 替换                       knn_list[index] = (dist,node.value)                   # 寻找另一枝                   if X[node.split] <= node.value[node.split]:                        Recursive(node.right)                   else:                        Recursive(node.left)            return True        # 深拷贝副本，便于多次使用        root = copy.deepcopy(self.root)        Recursive(root)        return knn_list

读者可自行将kd树建立搜索稍加修改应用到KNN算法中

转载地址：https://blog.csdn.net/weixin_45877045/article/details/106784639 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！