【机器学习】7 ——k近邻算法
机器学习7——k近邻
输入：实例的特征向量
输出：类别
懒惰学习（lazy learning）的代表算法
文章目录
- 机器学习7——k近邻
- 1.k近邻
- 2.模型——距离，k，分类规则
- 2.1距离——相似程度的反映
- 2.2 k值
- 分类规则
- 算法实现——kd树
- 构造平衡kd树
- 代码
- 搜索kd树——最近邻搜索
1.k近邻
少数服从多数，物以类聚
和这个实例最近的那几个实例，属于哪个类别的多，这个实例就是这个类别的
这个最近。二维举例，就是确定某个距离，画圆，圆内所有实例参与比较
算法
input：训练集T，要判断类别的实例x
output：实例x的类别
步骤：
- 根据具体的距离度量，找T中和x最近的k个实例，这k个实例构成Nk（x）
判断依据的范围- 根据分类规则，判断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}")