统计学习与方法实战——K近邻算法

2024-09-04 11:04

本文主要是介绍统计学习与方法实战——K近邻算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

K近邻算法

K近邻算法

备注

  1. kNN是一种基本分类与回归方法.
  • 多数表决规则等价于0-1损失函数下的经验风险最小化,支持多分类, 有别于前面的感知机算法
  • kNN的k和KDTree的k含义不同
  • KDTree是一种存储k维空间数据的树结构
  • 建立空间索引的方法在点云数据处理中也有广泛的应用,KDTree和八叉树在3D点云数据组织中应用比较广
  • KDTree是平衡二叉树
  • KDTree的搜索问题分为k近邻查找范围查找,一个是已知 k k k,求点集范围,一个是已知范围,求里面有k个点。范围查找问题在维度高的时候复杂度非常高,不太推荐用KDTree做范围查找。
  • K近邻问题在杭电ACM里面有收录,HUD4347
  • 图像的特征点匹配,数据库查询,图像检索本质上都是同一个问题–相似性检索问题。Facebook开源了一个高效的相似性检索工具Faiss,用于有效的相似性搜索和稠密矢量聚类。
    𝑘 近邻法是基本且简单的分类与回归方法。 𝑘 近邻法的基本做法是:对给定的训练实例点和输入实例点,首先确定输入实例点的 𝑘 个最近邻训练实例点,然后利用这 𝑘 个训练实例点的类的多数来预测输入实例点的类。

2. 𝑘 近邻模型对应于基于训练数据集对特征空间的一个划分。 𝑘 近邻法中,当训练集、距离度量、 𝑘 值及分类决策规则确定后,其结果唯一确定。

3. 𝑘 近邻法三要素:距离度量、 𝑘 值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的pL距离。 𝑘 值小时, 𝑘 近邻模型更复杂; 𝑘 值大时, 𝑘 近邻模型更简单。 𝑘 值的选择反映了对近似误差与估计误差之间的权衡,通常由交叉验证选择最优的 𝑘 。常用的分类决策规则是多数表决,对应于经验风险最小化。

4. 𝑘 近邻法的实现需要考虑如何快速搜索k个最近邻点。kd树是一种便于对k维空间中的数据进行快速检索的数据结构。kd树是二叉树,表示对 𝑘 维空间的一个划分,其每个结点对应于 𝑘 维空间划分中的一个超矩形区域。利用kd树可以省去对大部分数据点的搜索, 从而减少搜索的计算量。

k近邻模型

算法

输入: T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } , x i ∈ X ⊆ R n , y i ∈ Y = { c 1 , c 2 , … , c k } T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}, x_i\in \cal{X}\sube{\bf{R}^n}, y_i\in\cal{Y}=\{c_1,c_2,\dots, c_k\} T={(x1,y1),(x2,y2),,(xN,yN)}xiXRn,yiY={c1,c2,,ck}; 实例特征向量 x x x

输出: 实例所属的 y y y

K近邻算法三要素如下黑体:
步骤:

  1. 根据指定的距离度量,在 T T T中查找 x x x最近邻的 k k k个点,覆盖这 k k k个点的 x x x的邻域定义为 N k ( x ) N_k(x) Nk(x)

  2. N k ( x ) N_k(x) Nk(x)中应用分类决策规则决定 x x x的类别 y y y
    y = arg ⁡ max ⁡ c j ∑ x i ∈ N k ( x ) I ( y i = c j ) , i = 1 , 2 , … , N , j = 1 , 2 , … , K y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_j), i=1,2,\dots,N, j=1,2,\dots,K y=argcjmaxxiNk(x)I(yi=cj),i=1,2,,N,j=1,2,,K

距离度量

特征空间中的两个实例点的距离是两个实例点相似程度的反映。
距离越近(数值越小), 相似度越大
这里用到了 L p L_p Lp距离,

  1. p = 1 p=1 p=1 对应 曼哈顿距离
  2. p = 2 p=2 p=2 对应 欧氏距离
  3. 任意 p p p 对应 闵可夫斯基距离

L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 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}} Lp(xi,xj)=(l=1n xi(l)xj(l) p)p1
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FR0NLtYn-1640089789079)(assets/fig3_2.png)]
考虑二维的情况, 上图给出了不同的 p p p值情况下与原点距离为1的点的图形。

这个图有几点理解下:

  1. 与原点的距离
  2. 与原点距离为1的点
  3. 前一点换个表达方式, 图中的点向量( x 1 x_1 x1, x 2 x_2 x2)的 p p p范数都为1
  4. 图中包含多条曲线, 关于p=1并没有对称关系
  5. 定义中 p ⩾ 1 p\geqslant1 p1,这一组曲线中刚好是凸的
    补充:
    范数是对向量或者矩阵的度量,是一个标量,这个里面两个点之间的 L p L_p Lp距离可以认为是两个点坐标差值的 p p p范数。

k k k值选择

  1. 关于 k k k大小对预测结果的影响, 书中给的参考文献是ESL, 这本书还有个先导书叫ISL.
  2. 通过交叉验证选取最优 k k k, 算是超参数
  3. 二分类问题, k k k选择奇数有助于避免平票

分类决策规则

Majority Voting Rule
误分类率:
1 k ∑ x i ∈ N k ( x ) I ( y i ≠ c i ) = 1 − 1 k ∑ x i ∈ N k ( x ) I ( y i = c i ) \frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i\ne c_i)}=1-\frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i= c_i)} k1xiNk(x)I(yi=ci)=1k1xiNk(x)I(yi=ci)

如果分类损失函数是0-1损失, 误分类率最低即经验风险最小.

构造KDTree

KDTree的构建是一个递归的过程
注意: KDTree左边的点比父节点小,右边的点比父节点大。
这里面有提到,KDTree搜索时效率未必是最优的,这个和样本分布有关系。随机分布样本KDTree搜索(这里应该是近邻搜索)的平均计算复杂度是 O ( log ⁡ N ) O(\log N) O(logN),空间维数 K K K接近训练样本数 N N N时,搜索效率急速下降,几乎 O ( N ) O(N) O(N)
看维度,如果维度比较高,搜索效率很低。当然,在考虑维度的同时也要考虑样本的规模。
考虑个例子

[[1, 1],[2, 1],[3, 1],[4, 1],[5, 1],[6, 1],[100, 1][1000, 1]]
k k k近邻查找

KNN查找已知查询点 p p p,树当前节点 o o o,近邻数目 k k k

可以用一个优先队列存储最优的 k k k个点,每次比对回溯节点是否比当前最优点更优的时候,就只需用当前最优中距离 p p p最远的节点来对比,而这个工作对于优先队列来说是 O ( 1 ) O(1) O(1)的[^3]

范围查询

给定一个范围,问其中有多少点。比较常见的应用是GIS类应用,使用者附近多大半径内包含多少单车,多少酒店等。
实际上为了实现快速搜索, 在空间数据的存储结构上要有考虑。
这段代码实现了一个简单的 K 最近邻(KNN)算法,使用了 KD 树(K-Dimensional Tree)来加速最近邻搜索。以下是对代码的逐行解释:

代码结构

  1. 导入必要的库

    from collections import namedtuple
    from pprint import pformat
    import numpy as np
    
    • namedtuple 用于创建轻量级的类,便于存储节点信息。
    • pformat 用于格式化输出。
    • numpy 是一个用于数值计算的库,提供了高效的数组操作。
  2. 定义 Node 类

    class Node(namedtuple('Node', 'location left_child right_child')):def __repr__(self):return pformat(tuple(self))
    
    • Node 类表示 KD 树中的一个节点,包含三个属性:
      • location:节点的位置(数据点)。
      • left_child:左子树。
      • right_child:右子树。
    • __repr__ 方法用于格式化节点的输出,便于调试。
  3. 定义 KNN 类

    class KNN(object):
    
    • 定义一个名为 KNN 的类,表示 K 最近邻算法的实现。
  4. 初始化方法

    def __init__(self, k=1, p=2):self.k = kself.p = pself.kdtree = None
    
    • __init__ 方法接受两个参数:
      • k:表示要查找的最近邻的数量,默认为 1。
      • p:表示距离度量的阶数,默认为 2(欧几里得距离)。
    • self.kdtree 用于存储构建的 KD 树。
  5. 构建 KD 树

    @staticmethod
    def _fit(X, depth=0):try:k = X.shape[1]except IndexError as e:return Noneaxis = depth % kX = X[X[:, axis].argsort()]median = X.shape[0] // 2try:X[median]except IndexError:return Nonereturn Node(location=X[median],left_child=KNN._fit(X[:median], depth + 1),right_child=KNN._fit(X[median + 1:], depth + 1))
    
    • _fit 方法是一个静态方法,用于递归构建 KD 树。
    • depth 参数用于跟踪当前的深度,以确定在哪个维度上进行分割。
    • 通过 X.shape[1] 获取数据的维度 k k k
    • 使用 depth % k 确定当前分割的轴。
    • 将数据按当前轴排序,并找到中位数。
    • 创建一个 Node,将中位数作为节点位置,并递归构建左子树和右子树。
  6. 计算距离

    def _distance(self, x, y):return np.linalg.norm(x - y, ord=self.p)
    
    • _distance 方法计算两个点之间的距离,使用 NumPy 的 linalg.norm 函数,根据给定的 p p p 值计算距离。
  7. 搜索最近邻

    def _search(self, point, tree=None, depth=0, best=None):if tree is None:return bestk = point.shape[0]if best is None or self._distance(point, tree.location) < self._distance(best, tree.location):next_best = tree.locationelse:next_best = bestif point[depth % k] < tree.location[depth % k]:next_branch = tree.left_childelse:next_branch = tree.right_childreturn self._search(point, tree=next_branch, depth=depth + 1, best=next_best)
    
    • _search 方法用于在 KD 树中查找最近邻。
    • 如果树为空,返回当前最佳结果。
    • 更新最佳结果 next_best,如果当前节点比最佳结果更接近目标点。
    • 根据当前点在当前维度上的值决定搜索左子树还是右子树。
    • 递归调用 _search 方法,继续在选定的子树中查找。
  8. 训练模型

    def fit(self, X):self.kdtree = KNN._fit(X)return self.kdtree
    
    • fit 方法用于训练模型,构建 KD 树并存储在 self.kdtree 中。
  9. 预测最近邻

    def predict(self, X):rst = self._search(X, self.kdtree)return rst
    
    • predict 方法用于预测给定点的最近邻,调用 _search 方法进行查找。

总结

这段代码实现了一个基于 KD 树的 K 最近邻算法。通过构建 KD 树,能够高效地进行最近邻搜索。该实现包括了 KD 树的构建、距离计算和搜索功能,适合用于处理多维数据的最近邻查询。

from collections import namedtuple
from pprint import pformat
import numpy as npclass Node(namedtuple('Node', 'location left_child right_child')):def __repr__(self):return pformat(tuple(self))class KNN(object):def __init__(self,k=1,p=2):""":param k: knn:param p:"""self.k = kself.p = pself.kdtree = None@staticmethoddef _fit(X, depth=0):try:k = X.shape[1]except IndexError as e:return None# todo: 这里可以展开,通过方差选择axis = depth % kX = X[X[:, axis].argsort()]median = X.shape[0] // 2try:X[median]except IndexError:return Nonereturn Node(location=X[median],left_child=KNN._fit(X[:median], depth + 1),right_child=KNN._fit(X[median + 1:], depth + 1))def _distance(self, x, y):return np.linalg.norm(x-y, ord=self.p)def _search(self, point, tree=None, depth=0, best=None):if tree is None:return bestk = point.shape[0]# update bestif best is None or self._distance(point, tree.location) < self._distance(best, tree.location):next_best = tree.locationelse:next_best = best# update branchif point[depth%k] < tree.location[depth%k]:next_branch = tree.left_childelse:next_branch = tree.right_childreturn self._search(point, tree=next_branch, depth=depth+1, best=next_best)def fit(self, X):self.kdtree = KNN._fit(X)return self.kdtreedef predict(self, X):rst = self._search(X, self.kdtree)return rst

这篇关于统计学习与方法实战——K近邻算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1135840

相关文章

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Pandas使用SQLite3实战

《Pandas使用SQLite3实战》本文主要介绍了Pandas使用SQLite3实战,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录1 环境准备2 从 SQLite3VlfrWQzgt 读取数据到 DataFrame基础用法:读

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很