文章目录

• 一、简介
• • 1、概念
• 二、k近邻算法api的初步使用
• • 1、目标：
  • 2、Scikit-learn的介绍
  • 3、 K-近邻算法API
  • 4、案例
• 三、距离度量
• • 1、距离公式的基本性质
  • 2、常见的距离公式
• 四、K值选择说明
• • 1、举例说明
  • 2、K值选择问题
  • 3、近似误差与估计误差
• 五、kd树
• • 1、kd树的定义
  • 2、树的建立
  • 3、最近邻域搜索（Nearest-Neighbor Lookup）

一、简介

1、概念

K-近邻算法（KNN）全称为K Nearest Neighbor，是指如果⼀个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的⼤多数属于某⼀个类别，则该样本也属于这个类别。

简单来说，就是看你的邻居是哪个类别，你就是哪个类别

那么怎么判断最相似（也就是你的邻居）呢？

我们使用欧氏距离来进行判断两个样本之间的距离。
欧氏距离我们初中就已经学过，就是两个点之间的距离。

就比如下面的例子，假设我们现在有⼏部电影，其中9号电影不知道类别，我们可以利⽤K近邻算法进行预测

我们可以把唐人街探案的的每个指标与其他电影的指标做差，最后得出距离最近的5个样本（这里的k是我们自己取的）

最后得到的结果如下

这5个电影是距离《唐人街探案》最近的5个电影，其中3个喜剧片，2个爱情片，所以我们姑且可以认为《唐人街探案》是一个喜剧片。

通过这个例子，我们再回顾K-近邻算法的定义

如果⼀个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的⼤多数属于某⼀个类别，则该样本也属于这个类别。

我们就可以基本理解了

二、k近邻算法api的初步使用

1、目标：

1、了解sklearn⼯具的优点和包含内容
2、应⽤sklearn中的api实现KNN算法的简单使⽤

2、Scikit-learn的介绍

（1）简介

我们需要使用一个工具Scikit-learn来进行学习，首先了解一下什么是Scikit-learn

Python语⾔的机器学习⼯具
Scikit-learn包括许多知名的机器学习算法的实现
Scikit-learn⽂档完善，容易上⼿，丰富的API
⽬前稳定版本0.19.1

（2）安装

pip3 install scikit-learn==0.19.1

安装好之后可以通过以下命令查看是否安装成功

import sklearn

注：安装scikit-learn需要Numpy, Scipy等库

教程说安装这个版本，但是我安装的时候一直报错，所以我就没有指定版本，安装成功了，上面的安装失败可以试试下面这句

pip install -U scikit-learn

（3）Scikit-learn包含的内容

• 分类、聚类、回归
• 特征⼯程
• 模型选择、调优

3、 K-近邻算法API

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)

n_neighbors：int,可选（默认= 5），k_neighbors查询默认使⽤的邻居数

4、案例

（1）步骤分析

• 1.获取数据集
• 2.数据基本处理（该案例中省略）
• 3.特征⼯程（该案例中省略）
• 4.机器学习
• 5.模型评估（该案例中省略）

（2）代码过程

导入模块

from sklearn.neighbors import KNeighborsClassifier

训练模型

#2.1 实例化一个估计器对象
estimator=KNeighborsClassifier(n_neighbors=1)

#2.2 调用fit方法进行训练
estimator.fit(x,y)

数据预测

ret=estimator.predict([[0]])
print(ret)

ret=estimator.predict([[100]])
print(ret)

学到这里，我们可能会有几个问题：

1.距离公式，除了欧式距离，还有哪些距离公式可以使⽤？

2.选取K值的大小？

3.api中其他参数的具体含义？
 

三、距离度量

1、距离公式的基本性质

2、常见的距离公式

（1）欧氏距离

欧氏距离是最容易直观理解的距离度量⽅法，我们小学、初中和⾼中接触到的两个点在空间中的距离⼀般都是指欧氏距离。

（2）曼哈顿距离

在曼哈顿街区要从⼀个⼗字路⼝开⻋到另⼀个⼗字路⼝，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。

(3)切⽐雪夫距离 (Chebyshev Distance)

国际象棋中，国王可以直⾏、横⾏、斜⾏，所以国王⾛⼀步可以移动到相邻8个⽅格中的任意⼀个。国王从格⼦(x1,y1)走到格⼦(x2,y2)最少需要多少步？这个距离就叫切比雪夫距离。

（4） 闵可夫斯基距离(Minkowski Distance)

闵氏距离不是⼀种距离，⽽是⼀组距离的定义，是对多个距离度量公式的概括性的表述。

两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

其中p是⼀个变参数：

• 当p=1时，就是曼哈顿距离；
• 当p=2时，就是欧⽒距离；
• 当p→∞时，就是切⽐雪夫距离。

根据p的不同，闵⽒距离可以表示某⼀类/种的距离。

小结：

1 闵⽒距离，包括曼哈顿距离、欧⽒距离和切⽐雪夫距离，都存在明显的缺点:
e.g. ⼆维样本(身⾼[单位:cm],体重[单位:kg]),现有三个样本：a(180,50)，b(190,50)，c(180,60)。
a与b的闵⽒距离（⽆论是曼哈顿距离、欧⽒距离或切⽐雪夫距离）等于a与c的闵⽒距离。但实际上身⾼的10cm并不能和体重的10kg划等号。

2 闵⽒距离的缺点：
(1)将各个分量的量纲(scale)，也就是“单位”相同的看待了;
(2)未考虑各个分量的分布（期望，⽅差等）可能是不同的。

3、 “连续属性” 和 “离散属性” 的距离计算

我们常将属性划分为"连续属性" (continuous attribute)和"离散属性" (categorical attribute)，前者在定义域上有⽆穷多个可能的取值，后者在定义域上是有限个取值。

• 若属性值之间存在序关系，则可以将其转化为连续值，例如：身⾼属性 “⾼” “中等” “矮” ，可转化为{1, 0.5, 0}。（闵可夫斯基距离可以⽤于有序属性）
• 若属性值之间不存在序关系，则通常将其转化为向量的形式，例如：性别属性 “男” “女” ，可转化为{（1,0）,（0,1）}。

四、K值选择说明

1、举例说明

• K值过小：容易受到异常点的影响
• k值过大：受到样本均衡的问题

2、K值选择问题

李航博⼠的⼀书「统计学习⽅法」上所说：

（1）选择较小的K值，就相当于⽤较小的领域中的训练实例进⾏预测，
“学习”近似误差会减⼩，只有与输⼊实例较近或相似的训练实例才会对预测结果起作⽤，与此同时带来的问题是“学习”的估计误差会增⼤，换句话说，K值的减⼩就意味着整体模型变得复杂，容易发⽣过拟合；

（2）选择较大的K值，就相当于⽤较大领域中的训练实例进⾏预测，
其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增⼤。这时候，与输⼊实例较远（不相似的）训练实例也会对预测器作⽤，使预测发⽣错误。且K值的增⼤就意味着整体的模型变得简单。

（3） K=N（N为训练样本个数），则完全不足取，
因为此时⽆论输⼊实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有⽤信息。

在实际应⽤中，K值⼀般取⼀个比较小的数值，例如采用交叉验证法（简单来说，就是把训练数据在分成两组:训练集和验证集）来选择最优的K值。

3、近似误差与估计误差

近似误差：

• 对现有训练集的训练误差，关注训练集，
• 如果近似误差过⼩可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较⼤偏差的预测。
• 模型本身不是最接近最佳模型。

估计误差：

• 可以理解为对测试集的测试误差，关注测试集，
• 估计误差⼩说明对未知数据的预测能⼒好，
• 模型本身最接近最佳模型。

五、kd树

实现k近邻算法时，主要考虑的问题是如何对训练数据进⾏快速k近邻搜索。

这在特征空间的维数⼤及训练数据容量⼤时尤其必要。

k近邻法最简单的实现是线性扫描（穷举搜索），即要计算输⼊实例与每⼀个训练实例的距离。计算并存储好以后，再查找K近邻。当训练集很⼤时，计算⾮常耗时。

为了提⾼kNN搜索的效率，可以考虑使⽤特殊的结构存储训练数据，以减⼩计算距离的次数。

1、kd树的定义

根据KNN每次需要预测⼀个点时，我们都需要计算训练数据集⾥每个点到这个点的距离，然后选出距离最近的k个点进行投票。当数据集很⼤时，这个计算成本⾮常⾼，针对N个样本，D个特征的数据集，其算法复杂度为O（DN ）。

kd树：为了避免每次都重新计算⼀遍距离，算法会把距离信息保存在⼀棵树里，这样在计算之前从树⾥查询距离信息，尽量避免重新计算。其基本原理是，如果A和B距离很远，B和C距离很近，那么A和C的距离也很远。有了这个信息，就可以在合适的时候跳过距离远的点。

这样优化后的算法复杂度可降低到O（DNlog（N））

2、树的建立

（1）构造根节点

（2）通过递归的⽅法，不断地对k维空间进行切分，⽣成⼦节点

（3）重复第⼆步骤，直到子区域中没有示例时终止

需要关注细节：a.选择向量的哪⼀维进行划分；b.如何划分数据

3、最近邻域搜索（Nearest-Neighbor Lookup）

（1）⼆叉树搜索⽐较待查询节点和分裂节点的分裂维的值，（小于等于就进⼊左子树分支，大于就进⼊右子树分支直到叶子结点）

（2）顺着“搜索路径”找到最近邻的近似点

（3）回溯搜索路径，并判断搜索路径上的结点的其他⼦结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他⼦结点空间中去搜索

（4）重复这个过程直到搜索路径为空