统计学习与方法实战——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

相关文章

Windows 上如果忘记了 MySQL 密码 重置密码的两种方法

《Windows上如果忘记了MySQL密码重置密码的两种方法》:本文主要介绍Windows上如果忘记了MySQL密码重置密码的两种方法,本文通过两种方法结合实例代码给大家介绍的非常详细,感... 目录方法 1:以跳过权限验证模式启动 mysql 并重置密码方法 2:使用 my.ini 文件的临时配置在 Wi

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

SQL中redo log 刷⼊磁盘的常见方法

《SQL中redolog刷⼊磁盘的常见方法》本文主要介绍了SQL中redolog刷⼊磁盘的常见方法,将redolog刷入磁盘的方法确保了数据的持久性和一致性,下面就来具体介绍一下,感兴趣的可以了解... 目录Redo Log 刷入磁盘的方法Redo Log 刷入磁盘的过程代码示例(伪代码)在数据库系统中,r

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil