机械学习knn算法 kd树构建

### KNN算法中KD树的构建方法

在机器学习领域，K近邻(KNN)算法是一种监督学习的方法，用于分类和回归分析。为了提高查找最接近邻居的速度，通常会采用kd树(k-d tree)，这是一种高效的数据结构来组织多维键值[^1]。

#### 特征选择与分割点确定

对于给定的一组样本数据，首先需要选取一个维度来进行首次切分。一般做法是从所有可用特征中挑选出具有最大方差的那个作为当前层次上的切割标准；接着求取选定属性下全体记录对应值域内的中间数(median value),以此为界区分左右两支子集合[^3]。

import numpy as np

def find_splitting_feature(data_points):
    variances = []
    
    for feature_index in range(len(data_points[0])):
        values_for_this_feature = [point[feature_index] for point in data_points]
        variance_of_this_feature = np.var(values_for_this_feature)
        
        variances.append((variance_of_this_feature, feature_index))
        
    largest_variance, best_feature_to_split_on = max(variances)

    return best_feature_to_split_on

#### 创建节点并递归建立子树

一旦决定了哪个特性用来做分裂依据之后，则按照此特性的中位数创建一个新的内部结点，并将其余元素分配至相应的左侧或右侧分支内继续上述过程直至满足终止条件—比如叶子节点所含实例数目少于预定阈值`leaf_size`时停止进一步细分。

class Node:
    def __init__(self, median_value=None, split_dimension=None, left_child=None, right_child=None):
        self.median_value = median_value
        self.split_dimension = split_dimension
        self.left_child = left_child
        self.right_child = right_child


def build_kd_tree(points, depth=0, leaf_size=1):
    num_samples = len(points)
    
    if num_samples <= leaf_size:
        return points
    
    axis = depth % len(points[0])
    
    sorted_points = sorted(points, key=lambda point: point[axis])
    median_idx = int(np.floor(num_samples / 2))

    node_location = sorted_points[median_idx]

    next_depth = depth + 1
    
    return Node(
        median_value=node_location,
        split_dimension=axis,
        left_child=build_kd_tree(sorted_points[:median_idx], next_depth),
        right_child=build_kd_tree(sorted_points[median_idx + 1:], next_depth)
    )

通过这种方式构造出来的kd树能够有效地支持范围查询以及最近邻搜索操作，在高维空间里也能保持较好的性能表现[^2]。