【机器学习】7 ——k近邻算法

机器学习7——k近邻

输入：实例的特征向量
输出：类别

懒惰学习（lazy learning）的代表算法

---

---

1.k近邻

少数服从多数，物以类聚

和这个实例最近的那几个实例，属于哪个类别的多，这个实例就是这个类别的
这个最近。二维举例，就是确定某个距离，画圆，圆内所有实例参与比较

算法

input：训练集T，要判断类别的实例x
output：实例x的类别
步骤：

1. 根据具体的距离度量，找T中和x最近的k个实例，这k个实例构成Nk（x）判断依据的范围
2. 根据分类规则，判断x的类别

2.模型——距离，k，分类规则

2.1距离——相似程度的反映

2.2 k值

决定了那些实例决定判断结果
过小的k值会使模型对噪声敏感，容易过拟合

近似误差：简化了模型
主要源于近似模型的局限性。由于真实模型往往非常复杂，难以直接求解或处理，所以采用较为简单的近似模型。而这种简化过程必然会导致与真实模型存在一定的偏差。
例如，在数值计算中，用有限项的泰勒级数去逼近一个函数，由于舍去了高阶无穷小项，就会产生近似误差。
估计误差：
一方面是由于样本的随机性。我们通常只能通过有限的样本数据来进行估计，而样本只是总体的一个部分，具有随机性，不能完全代表总体，从而导致估计值与真实值之间存在误差。
另一方面，估计方法的选择也会影响估计误差。不同的估计方法可能会产生不同大小的估计误差。

分类规则

通常是多数表决

---

算法实现——kd树

kd树：组织k维数据的二叉树，常用于高维空间的最近邻搜索、范围查询等问题。它通过将数据集递归划分为不同的维度，构建一棵可以快速查询的树结构。

对特征空间的划分

构造平衡kd树

• 选择维度：从数据集中选择一个轴（或维度）来划分数据。常见的策略是每次选择不同的维度，以轮流划分不同的维度空间。
  通常，这个轴是数据点的某个坐标轴，例如 x 轴或 y 轴。在每一层递归中，选择的轴通常是当前节点深度d对n取余的结果，其中 n 是数据的维度。

• 选择分割点：在选定的轴上，找到一个切分点，该切分点将数据集分为两部分。常见的选择是中位数这可以平衡树的构造，使得左右子树中的数据量大致相同。

• 创建节点：用选定的切分点创建一个 kd 树的节点，并将数据集分为两部分，一部分包含所有在该轴上小于切分点的点，另一部分包含所有在该轴上大于切分点的点。

• 递归构建：将数据点按中位数划分为两部分，左子树包含小于中位数的点，右子树包含大于中位数的点。然后在剩余的数据上重复此过程，选择下一个维度继续递归构建。

示例
假设我们有一系列二维点：points = [(3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19)]

• 首先，我们选择 x 轴作为第一层的划分轴，因为当前深度d=0，n=2，d%n=0对应 x 轴。这里有的时候也会叫做第0层
  根据x轴的数值排序[(2, 7), (3, 6), (6, 12), (9, 1), (10, 19), (13, 15), (17, 15)]，中位数点为 (9, 1)，作为根节点。如果双数的数据量，中间两个随便哪个都可以，但整个过程最好都一致，比如都选右侧的

• 第2层（选择y轴，即第2维度）；
  左子树：[(2, 7), (3, 6), (6, 12)]——对左子树按y轴排序，中位数点为 (2, 7)
  右子树：[(10, 19), (13, 15), (17, 15)]——对右子树按y轴排序，中位数点为 (13, 15)

• 第3层（选择x轴）左子树继续递归：
  [(3, 6), (6, 12)]——中位数点为 == (6, 12)==
  右子树为 == (17, 15)==

结果x            (9, 1)/         \
y     (2, 7)       (13, 15)/           /       \
x (6, 12)      (10, 19)  (17, 15)/
y(3, 6)

代码

class Node:def __init__(self, point, left=None, right=None):self.point = point  # 节点存储的点self.left = left     # 左子树self.right = right   # 右子树def create_kd_tree(data, depth=0):if not data:return None# 选择切分轴（根据深度选择维度）k = len(data[0])  # 数据的维度axis = depth % k  # 当前的切分轴# 对数据按照切分轴的值进行排序，并选择中位数对应的点作为切分点data.sort(key=lambda x: x[axis])median = len(data) // 2  # 中位数的索引# 创建节点，并递归地创建子树return Node(point=data[median],left=create_kd_tree(data[:median], depth + 1),right=create_kd_tree(data[median + 1:], depth + 1))# 示例数据（每个点是二维空间中的一个坐标）
points = [(2, 3), (5, 4), (1, 8), (4, 7), (6, 3), (5, 2)]
kd_tree = create_kd_tree(points)# 函数用于打印Kd树（递归）
def print_kd_tree(node, depth=0, prefix="Root"):if node is not None:print(f"{prefix}('x{depth % 2 + 1}': {node.point})")print_kd_tree(node.left, depth + 1, prefix="L---")print_kd_tree(node.right, depth + 1, prefix="R---")# 打印Kd树
print_kd_tree(kd_tree)

搜索kd树——最近邻搜索

• 从根节点开始：将查询点与根节点进行比较。
• 决定搜索方向：根据查询点在当前分割轴上的值与节点在该轴上的值的比较结果，决定是向左子树搜索还是向右子树搜索
• 递归搜索：在选定的子树中递归地执行步骤1和2，直到达到叶子节点。
• 回溯：在回溯过程中，检查是否有可能在之前跳过的子树中找到更近的邻居。这通常涉及到检查当前节点的另一个子树（如果之前没有搜索过），并考虑是否有可能在该子树中找到比当前最近点更近的点。这通常通过计算一个“边界框”的距离来实现，该边界框包围了未搜索的子树中的所有点。
• 更新最近点：如果在搜索过程中找到了比当前最近点更近的点，则更新最近点。
• 继续回溯：继续回溯，直到回到根节点。

假设我们使用KD树进行最近邻查找，查询点是 (12, 8)。具体过程如下：

x            (9, 1)/         \
y     (2, 7)       (13, 15)/           /       \
x (6, 12)      (10, 19)  (17, 15)/
y(3, 6)

根节点比较：我们在x轴上选择 (9, 1) 作为根节点，比较 (12, 8) 在右边12>9，因此进入右子树。
第二层比较：在y轴上比较，选择的点是 (13, 15)，查询点 (12, 8) 位于左侧8<15，因此进入左子树。
第三层比较：进入x轴上选择 (10, 19)，查询点 (12, 8) 在右侧12>10，进入右子树（没有，开始回溯）。
叶节点返回：到达叶节点后，返回当前最近邻点（此时为 (10, 19)）。
回溯：回溯到(13, 15)，发现更近，更新当前最近邻点（此时为(13, 15)）
查看另一子树：查看(17, 15)，不更新，继续回溯
到根节点： (9, 1)，还是(13, 15)，所以结果是(13, 15)

# 导入数学库用于计算距离
import math# 定义KD树节点类
class KDNode:def __init__(self, point, axis=0):# 节点存储的数据点self.point = point# 左子树self.left = None# 右子树self.right = None# 划分维度self.axis = axis# 构建KD树
def build_kd_tree(points, depth=0):# 如果当前数据集为空，则返回空节点if not points:return None# 根据深度确定划分维度axis = depth % len(points[0])# 按照当前维度排序数据点points.sort(key=lambda point: point[axis])# 找到中位数的位置median_idx = len(points) // 2# 创建当前维度的节点node = KDNode(points[median_idx], axis)# 递归构建左子树node.left = build_kd_tree(points[:median_idx], depth + 1)# 递归构建右子树node.right = build_kd_tree(points[median_idx + 1:], depth + 1)# 返回当前节点return node# 打印KD树结构
def print_kd_tree(node, depth=0):if node is None:return# 缩进显示层次结构indent = "    " * depthprint(f"{indent}Point: {node.point}, Axis: {node.axis}")# 递归打印左子树print_kd_tree(node.left, depth + 1)# 递归打印右子树print_kd_tree(node.right, depth + 1)# 在KD树中搜索最近邻点
def search_kd_tree(node, target, best=None):if node is None:return best# 当前节点的划分维度axis = node.axis# 根据目标点与当前节点在划分维度上的值决定先访问哪一侧if target[axis] < node.point[axis]:next_node = node.leftother_node = node.rightelse:next_node = node.rightother_node = node.left# 递归搜索下一层best = search_kd_tree(next_node, target, best)# 更新最佳结果if best is None or distance(target, node.point) < distance(target, best):best = node.point# 计算目标点与当前节点在划分维度上的距离dist = abs(target[axis] - node.point[axis])# 如果这个距离小于当前最佳结果的距离，则需要检查另一侧if dist < distance(target, best):best = search_kd_tree(other_node, target, best)return best# 计算两点之间的欧氏距离
def distance(p1, p2):return math.sqrt(sum((a - b)**2 for a, b in zip(p1, p2)))# 定义一组二维数据点
points = [(3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19)]
# 构建KD树
root = build_kd_tree(points)
# 打印KD树结构
print("KD Tree:")
print_kd_tree(root)# 定义一个目标点
target_point = (12, 8)
# 在KD树中搜索最近邻点
result = search_kd_tree(root, target_point)
# 输出结果
print(f"Nearest point to {target_point}: {result}")