Warning: session_start() expects parameter 1 to be array, string given in /www/wwwroot/blog/wp-includes/class-wp-hook.php on line 288
K近邻算法(内附Kd-tree视频演示) | 野风
  • 欢迎访问我的个人博客,如遇博客图片无法显示,请用IE浏览器访问。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧!

K近邻算法(内附Kd-tree视频演示)

机器学习 野风同学 2年前 (2020-01-07) 2747次浏览 0个评论 扫描二维码

K近邻法(k-nearest neighbor,k-NN)是一种基本的分类与回归算法,其算法思想概括起来就是一句话——“近朱者赤,近墨者黑”。K-NN不具有显式的学习过程,而是利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。

学习k-NN算法,有三个基本要素:距离度量、k值选择和分类决策规则

距离度量

既然说是近邻,怎么才算是“近”呢?这个“近”是以什么方法来度量的呢?一般来说,我们使用的是欧氏距离或者更一般的闵可夫斯基距(MinkowskiDistance)。设特征空间\( \chi \)是\( n \) 维实数向量空间\( \mathbf{R}^n \) ,\( x_i,x_j\in \chi ,x_i=\left( x_{i}^{\left( 1 \right)},x_{i}^{\left( 2 \right)},...,x_{i}^{\left( n \right)} \right) ^T,x_j=\left( x_{j}^{\left( 1 \right)},x_{j}^{\left( 2 \right)},...,x_{j}^{\left( n \right)} \right) ^T \),则\( x_i,x_j \)的闵可夫斯基距离为

\[ L_p=\sqrt[p]{\sum_{l=1}^n{\left| x_{i}^{\left( l \right)}-x_{j}^{\left( l \right)} \right|}^p} \]

当p=1时,就是曼哈顿距离,当p=2时,就是欧氏距离,当p→∞时,就是切比雪夫距离。

k值选择

k值就是要求的里目标点最近点的个数。k太小,分类结果易受噪声点影响,容易发生过拟合;k太大,近邻中又可能包含太多的其它类别的点,使预测发生错误,k值增大也就意味着模型整体变简单。(对距离加权,可以降低k值设定的影响)。k值通常是采用交叉检验来确定(以k=1为基准)。有一个经验规则, k一般低于训练样本数的平方根

分类决策规则

k-NN算法中的分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

k-NN的实现:Kd-tree

如何构造Kd-tree?

Kd-Tree,即K-dimensional tree,是一棵二叉树,树中存储的是一些K维数据。在一个K维数据集合上构建一棵Kd-Tree代表了对该K维数据集合构成的K维空间的一个划分,即树中的每个结点就对应了一个K维的超矩形区域(Hyperrectangle)。 在介绍Kd-tree的相关算法前,我们先回顾一下二叉查找树(Binary Search Tree)的相关概念和算法。

二叉查找树(Binary Search Tree,BST),是具有如下性质的二叉树(来自wiki):

  1. 若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值;
  3. 它的左、右子树也分别为二叉排序树;

如图为一棵二叉查找树:

要满足以上性质的话,则Kd-Tree的构造步骤可以分为以下两步:

  1. 在K维数据集合中选择具有最大方差的维度k,然后在该维度上选择中位数点对该数据集合进行划分,得到两个子集合;同时创建了一个树结点;如果是偶数个数据,中位数不是取排序后中间两个的平均数,而是两个点任选其一。
  2. 对两个子集合重复(1)步骤的过程,直至所有子集合都不能再划分为止。

如何搜索Kd-tree找到目标点P最邻近的k个点?

    1. 根据P的坐标值和每个节点的切分向下搜索(也就是比较该结点切分维度上的坐标值,比如一个结点是按照y维分的,就比较P点和结点的y坐标,若P点小,则走向左枝,若P点大,则走向右枝。
    2. 当到达一个底部结点时,将其标记为已访问。 如果L中不足k个点,则将该点加入到L中;如果L不为空且该点与P的距离小于L中离P远的点的距离,则用该结点替换那个最远点 。
    3. 当前结点不是顶端结点时或是顶端结点却未被标记已访问(若是且已被被标记访问则停止),则 向上爬,若已被标记访问,则继续向上爬;若未被标记,则标记已访问,并依次执行下面两步:
      1. L中不足k个点,则加入;若L已满,则计算P与该点距离,若小于L中最大距离,则替换之。
      2. 计算P和当前结点切分线的距离D,若D大于L中最大距离且L已满,则该结点的另一分支不会有更近的点,至此结束。若D小于L中最大距离或L未满,则该结点的另一分支可能有更近的点,继续在另一分支搜索(从1开始)。 下面来一段小视频演示一下吧,用PPT画的0.0

Sklearn实现

#%%读取iris数据集
from sklearn import datasets
import numpy as np
iris = datasets.load_iris()
#sepal length,sepal width ,petal length,ptal width
x =iris['data'] 
#0:setosa,1:versicolor,2:virginica
y = iris['target']
#%%
from sklearn import neighbors
clf = neighbors.KNeighborsClassifier(3)
clf.fit(x,y)
nearests = clf.kneighbors([[4.6,3,1.2,0.15]],3,False)
#Out:[38,2,12]表示数据中第38,2,12位数据里这个点最近,这三个点都是类别0
prediction = clf.predict([[4.6,3,1.2,0.15]])
#Out:0 代表setosa

参考

[1] 《统计学习方法》李航

[2] 【量化课堂】kd 树算法之详细篇

 


本站提供的一切软件、教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序,请支持正版,购买注册,得到更好的正版服务。如有侵权请邮件与我们联系处理。敬请谅解!
喜欢 (2)
[打赏赞助]
分享 (0)
野风同学
关于作者:
我是野风同学,这是我的主页。
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址