【机器学习】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 = "    " * depth
    print(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.left
        other_node = node.right
    else:
        next_node = node.right
        other_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}")