给定一个训练集，再给定一个输入数据，我们在训练集中找到与 k 个与这个输入数据最邻近的实例，这 k 个实例多数属于某个类，我们就把这个数据归为这个类。

K 近邻算法

• 输入：训练数据集
  T={(x_1,y_1),(x_2,y_2)…(x_n,y_n)}
  其中x_i\in\chi\subseteq\Re^n是实例的特征向量，y_i\in\mathcal{y}=\left \{ c_1,c_2,…,c_k \right \}是实例的类别。
• 输出：实例 x 所属的类别 y
• 步骤：

1. 根据已经给定的距离度量方法，在 T 中找出与 x 相近的 k 个点。

2. 在这 k 个点中通过多数表决决定 x 的类别 y

3. k 近邻算法有三个要素：

• k 的值

• 距离度量 k 近邻模型的特征空间一般是 n 维实数空间。一般情况下距离度量的方法是欧氏距离，但也可以是其他距离，比如 L_p 距离或者 Minkowski 距离。 假设特征空间 \chi 是 n 维实数向量空间，x_i,x_j\in\chi，x_i=\left\{x_i^{(1)},x_i{(2)},…,x_i^{{(n)}\right\}}T，x_j=\left\{x_j^{(1)},x_j{(2)},…,x_j^{{(n)}\right\}}T 那么二者之间的 L_p 距离定义如下：
  L_p(x_i,x_j) = \left ( \sum_{l=1}^{n}\left | x_i^{(l)} - x_j^{(l)} \right |^p \right ) ^\frac{1}{p}
  其中 p\ge1 当 p=2 时，这个距离称为欧氏距离。p=1 时为曼哈顿距离。 当p=\infty 时候，是各个坐标距离的最大值L_\infty(x_i,x_j) = max_l\left | x_i^{(l)}-x_j{(l)}\right |

• 分类决策规则 k 近邻的决策规则往往是多数表决，即由输入实例的 k 个最邻近的训练实例中的多数类决定 多数表决规则等价于经验风险最小化

k-D Tree 具有二叉搜索树的形态，二叉搜索树上的每个结点都对应 𝑘维空间内的一个点．其每个子树中的点都在一个 𝑘维的超长方体内，这个超长方体内的所有点也都在这个子树中．

• 构造平衡 kd 树

• 输入：一个 k 维空间的数据集合 T=\left\{ x_1,x_2,…,x_n\right\}

• 输出：一个 kd 树

• 算法：

1. 构造根节点（对应于包含 T 的 k 维空间的超矩形区域）
2. 重复: 对深度为 j 的节点，选择 x^{(l)} 为切分坐标轴，l =j(mod k)+1 ,将这个节点区域中所有示例的 x^{(l)} 坐标的中位数作为切分点。，将其对应的超矩形区域切分为两个子区域。
3. 两个子区域没有实例存在时停止

• 用 kd 树的最近邻搜索

• 输入：kd 树，目标点 x

• 输出：x 的最近邻

• 算法

1. 寻找当前最近点

2. 回溯

3. 代码：

class Node():
    def __init__(self,split_dim,value):
        self.lChild =   None
        self.rChild =   None
        self.point = value
        self.split_dimension = split_dim


class KDTree():
    def __init__(self,points):
        #获取维度数
        self.k = len(points[0])
        self.root = self._build_tree(points,split_dim=0)
    
    def _build_tree(self,points,split_dim):
        n = len(points)
        if n==0:
            return None
        #先对数组进行排序
        points = sorted(points,key = lambda p:p[split_dim])
        mid_point = points[n//2]

        current_node = Node(split_dim, mid_point)
        next_split_dim = (split_dim + 1) % self.k

        current_node.lChild = self._build_tree(points[:n//2], next_split_dim)
        current_node.rChild = self._build_tree(points[n//2+1:], next_split_dim)

        return current_node
    
    @staticmethod
    def _euclidean_dist(p1, p2) -> float:
        #计算两个 K 维点的欧氏距离
        return sum((x1 - x2) ** 2 for x1, x2 in zip(p1, p2))
    
    def search_nearest_neighbour(self,node:Node,target,best):
        if node is None:
            return
        #先计算这个点与目标的欧氏距离
        current_point = node.point
        current_split_dim = node.split_dimension
        dist = self._euclidean_dist(current_point,target)

        if dist<best[0][0]:
            best[0] = (dist,current_point.copy())

         # 决定向下搜索的子树：目标点在当前维度≤切分点→左子树，否则→右子树
        if target[current_split_dim] <= current_point[current_split_dim]:
            self.search_nearest_neighbour(node.lChild, target, best)
            other_subtree = node.rChild
        else:
            self.search_nearest_neighbour(node.rChild, target, best)
            other_subtree = node.lChild

        # 向上回溯，检查另一子树是否有更近点
        # 判定条件：目标点到切分超平面的距离平方 < 当前最小距离平方（超球体与超平面相交）
        plane_dist = (target[current_split_dim] - current_point[current_split_dim]) ** 2
        if plane_dist < best[0][0]:
            self.search_nearest_neighbour(other_subtree, target, best)
        
    #找目标点的最近邻居
    def find_nearest(self, target: List[float]):
        # 初始化最优解：（初始距离平方为无穷大，初始点为空）
        best = [(float(『inf』), [])]
        self.search_nearest_neighbour(self.root, target, best)
        return best[0][1]

    def find_k_nearest(self, target, k):
        # 找目标点的 K 个近邻（按距离由近到远排序）
        # 收集所有点的（距离平方，点），按距离排序后取前 k 个
        all_points = []
        queue = deque([self.root])  # 层序遍历 KD 树，收集所有点
        while queue:
            node = queue.popleft()
            if node:
                dist = self._euclidean_dist(node.point, target)
                all_points.append((dist, node.point))
                queue.append(node.lChild)
                queue.append(node.rChild)
        
        if len(all_points) < k:
            raise ValueError(f「k={k}超过点集总数{len(all_points)}！」)
        
        # 按距离平方升序排序，取前 k 个点的坐标
        all_points_sorted = sorted(all_points, key=lambda x: x[0])
        return [p for (d, p) in all_points_sorted[:k]]