《统计学习方法》——第三章、k近邻法

文档中心

K-近邻算法（KNN）是一种用于回归任务和分类任务的简单模型。邻居用于估计一个测试实例（未分类样本）对应的响应变量值。超参k用来指定估计过程应该包含多少个邻居。超参k是用来控制算法如何学习的参数，它不通过训练数据来估计，样本需要人为指定。最后，算法通过某种距离函数，从特征空间中选取k个距离测试实例最近的邻居。

对于分类问题：对新的样本，根据其𝑘个最近邻的训练样本的类别，通过多数表决等方式进行预测。

对于回归问题：对新的样本，根据其𝑘个最近邻的训练样本标签值的均值作为预测值。

KNN模型不会从训练数据中估计固定数量的模型参数k，它会将所有训练实例存储起来，并使用离测试实例最近的实例去预测响应变量。

一、k近邻算法

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。而k近邻法的特殊情况是k=1的情形，称为最近邻算法。对于输入的实例点（特征向量）x，最近邻法将训练数据集中与x最近邻点的类作为x的类。

基本做法：对给定的训练实例点和输入实例点，首先确定输入实例点的k个最近邻训练实例点，然后利用着k和训练实例点的类的多数来预测输入实例点的类。

KNN算法的工作原理其实就是寻找距离最相近的分类样本，可以用一句话来形容：”近朱者赤，近墨者黑“。KNN的算法整个算法分为三步：第一、计算待分类样本与其他样本之间的距离；第二、统计距离最近的k个近邻点；第三、对于k个最近邻的点，它们属于哪个分类最多，那么待分类样本就属于哪一类的。

from sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom sklearn.neighbors import KNeighborsClassifierimport numpy as np# 获取数据iris = load_iris()data = iris.datatarget = iris.target# 处理数据---划分数据，random_state 的作用相当于随机种子，是为了保证每次分割的训练集和测试集都是一样的x_train, x_test, y_train, y_test = train_test_split(data, target, random_state=0)# 设置邻居数K，即 n_neighbors 的大小KNN = KNeighborsClassifier(n_neighbors=6)# 构建模型KNN.fit(x_train, y_train)# 评估模型print('score:{:.2f}'.format(KNN.score(x_test, y_test)))

score:0.97

二、k近邻模型

三要素：距离度量、k值得选择与分类决策规则。

1、模型

k近邻法中，当训练集、距离度量（如欧氏距离）、k值及分类决策规则（如多数表决）确定后，对于任何一个新的输入梳理，它所属的类唯一地确定。

特征空间中，对每个训练实例点，距离该点比其他点更近的所有点组成一个区域，叫做单元。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。最近邻法将实例的类作为其单元中所有点的类标记，由此，每个单元的实例点的类别是确定的。

2、距离度量

两个样本点之间的距离代表了这两个样本之间的相似度，距离越大，差异性越大；距离越小，相似度越大。

特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间。使用的距离是欧氏距离，除了欧式距离公式可以计算距离，还有哪些距离公式可以使⽤？但也可以是其他距离，如更一般的 $L_{p}$ 距离或Minkowski距离。

（1）、欧氏距离

又称为欧几里得距离，其实这个距离计算公式就是数学上的两点间距离的计算公式： $d=\sqrt{\left ( x_{1} -y_{1}\right )^2+\left ( x_{2}-y_{2} \right )^2}$ ，从而得到两点之间的欧氏距离： $d=\sqrt{\sum_{i=1}^{n}\left ( x_{i}-y_{i} \right )^2}$ 。

import numpy as np# 计算两个数据点之间的欧几里得距离def Distance(x, y, length):    distance = 0    for i in range(length): distance += np.square(x[i] - y[i])    return np.sqrt(distance)d = Distance([1, 2, 3], [4, 5, 6], 3)print(d)

5.196152422706632

（2）、曼哈顿距离

表示两个点在标准坐标系上的绝对轴总和，公式： $d=\left | x_{1}-y_{1} \right |+\left | x_{2}-y_{2} \right |$ 。

x = [1, 2, 3]y = [4, 5, 6]print(sum(map(lambda i, j: abs(i - j), x, y)))

（3）、闵可夫斯基距离和切比雪夫距离

闵可夫斯基距离不是严格距离而是一组距离。公式： $d=\sqrt[p]{\sum_{i=1}^{n}\left | x_{1}-y_{i} \right |^p}$ ，其中p代表空间的维数，是一个可变参数。当p=1时，是曼哈顿距离；当p=2时，是欧氏距离；当 $p\rightarrow \propto$ 时，是切比雪夫距离。

（4）、余弦距离

利用余弦距离分析两个特征向量之间的相关性。公式： $dist(A,B)=1-cos(A,B\in)\in [0,2]$ 。

两个向量的夹角的余弦值是余弦相似度，其取值范围是[-1,1]，两个向量之间的夹角的余弦值越接近于1，说明两个向量越相似。

常用的距离度量是欧氏距离及更一般的 $L_{p}$ 距离。

3.k值的选择

k的选取对结果会产生重大影响，那么如何选取k值的大小？

如果k值比较小，那么就相当于未分类样本与输入实例较近的（相似的）训练实例非常接近才行，这样才会对预测结果起作用。但如果邻近的实例点是一个噪声点，那么样本的分类将会产生误差，即预测会出错，分类就会产生过拟合的问题。也就是说，k值较小意味着整体模型变得复杂，容易发生过拟合。——k值过小，容易受到异常点的影响。

如果k值比较大，这时与输入实例较远的（不相似的）训练实例也会对预测结果起作用，使预测发生错误，分类就会产生欠拟合的问题，原因是没有将未分类样本真正分类出来。k值较大意味着整体模型变得简单，容易发生欠拟合。——k值过大，受到样本均衡的影响。

k值一般选取一个比较小的数值。在实践中，一般采用交叉验证的方式选取最优的k值。交叉验证的核心思想是将一些可能的k值逐个去尝试一遍，然后选出效果最好的k值。

交叉验证是在机器学习建立模型和验证模型参数时常用的办法。顾名思义，就是重复的使用数据，把得到的样本数据进行切分，组合为不同的训练集和测试集。用训练集来训练模型，用测试集来评估模型预测的好坏这就是”验证“；在此基础上可以得到多组不同的训练集和测试集，某次训练集中的某样本在下次可能成为测试集中的样本，即所谓“交叉”。

最有效的交叉验证方法就是针对于整个数据集进行重复测试模型。交叉验证的目的就是为了得到可靠稳定的模型。

下面介绍了以下三种交叉验证的方法：

Holdout 交叉验证：按照一定比例将数据集拆分为训练集和测试集
K-Fold 交叉验证：将数据分为K个部分，每个部分分别当做测试集
Leave-P-Out 交叉验证: 使用P种选择的~CPN CNP 可能性分别测试

其中，在KNN算法中常用的是K-Fold 交叉验证。

K-Fold 交叉验证会将数据集分成K个部分，其中一个单独的样本作为测试集，而其余K-1个样本作为训练集。交叉重复验证K次，每个子集都会作为测试集，对模型进行测试。最终平均K次所得到的结果，最终得出一个单一的模型。假如有100个数据点，并且分成十次交叉验证。那么会将数据分成十个部分，每个部分有十个数据点。可分别对十个数据点进行验证，而对使用另外的90个数据点进行训练。重复十次这样的操作，将得到十个模型。对这些模型进行平均，最终得出一个适合的模型。K-Fold 交叉验证适用于数据集样本比较小的情况。

import numpy as npfrom sklearn.model_selection import KFold# 创建数据集--获取数据data = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])# 设置K值为2k = 2# 导入交叉验证，将K值设置为2kfold = KFold(n_splits=k)# 使用kfold分割数据--处理数据split_data = kfold.split(data)# 使用for循环分两次导出KFold的情况下训练集和测试集的数据内容for train, test in split_data:    # 初始输出设置为空    output_train = ''    output_test = ''    # 将所有的初始情况标志为T    mark = ["T"] * (len(train) + len(test))    for i in train: # 训练集的数据下标和数据内容 output_train = f"{output_train}({i}: {data[i]}) "    for i in test: # 将测试集的标志改成t mark[i] = "t" # 测试集的数据下标和数据内容 output_test = f"{output_test}({i}: {data[i]}) "    # 输出训练集和测试集    print(f"[ {' '.join(mark)} ]")    print(f"训练集: {output_train}")    print(f"测试集:  {output_test}\n")

[ t t T ]训练集: (2: [7 8 9]) 测试集:  (0: [1 2 3]) (1: [4 5 6]) [ T T t ]训练集: (0: [1 2 3]) (1: [4 5 6]) 测试集:  (2: [7 8 9])

k值小时，k近邻模型更复杂；k值大时，k近邻模型更简单。k值得选择反映了对近似误差与估计误差之间得权衡，一般采用交叉验证得方法选择最优得k值。PS：k值选择尽可能是奇数。

4、分类决策规则

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

常用的分类决策规则是多数表决，对应于经验风险最小化。

k近邻法中，当训练集、距离度量、k值及分类决策规则确定后，其结果是唯一确定的。

三、k近邻法的实现：KD树

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。在二维空间中，两个特征的相似度一般采用欧氏距离来表示，也就是说，每个新的输入实例都需要与所有的训练实例计算一次距离并进行排序。当训练集非常大时，计算就非常耗时、耗内存，导致算法的效率降低，这种方法是不可行的。为了提高k近邻的搜索效率，有一种可以减少计算距离次数的方法——KD树方法。

树是由 $n\left ( n\geq 0 \right )$ 个节点或元素组成的有限集合。树是一种递归定义的数据结构。

树的特点：每个结点有零个国多个子节点；有且仅有一个没有前驱的节点称为根节点；其余节点只有一个前驱，但可以有零个或多个后继；每一个非根节点有且只有一个父节点；除根节点外，每个子结点可以分为多个互不相交的子树。

二叉树是一个有限的节点集合，这个集合或者为空，或者由一个根节点和两棵互不相交的称为左子树和右子树的二叉树组成。树和二叉树的区别在于，二叉树的每个节点最多只有两棵子树且有序的、严格区分左子树、右子树的。

KD 树是对数据点在 K 维空间中划分的⼀种数据结构。在 KD 树的构造中，每个节点都是 k 维数值点的⼆叉树。既然是⼆叉树，就可以采⽤⼆叉树的增删改查操作，这样就大大提升了搜索效率。

KD树采用了分治的思想。利用已有的数据对k维空间进行切分，然后进行存储以便对其进行快速搜索的二叉树结构，利用KD树可以省去对大部分数据点的搜索，从而达到减少搜索的计算量的目的。

KD树算法分为两个部分，第一部分是构造KD树，对数据点建立KD树数据结构；第二部分是搜索KD树，在建立的KD树上进行最邻近查找的算法。

1、构造KD树

首先分别计算x，y维度上的方差，选择方差更大的维度；然后确定二叉树的根节点即构造根节点，对维度上的值进行排序选取节点作为中值即为切分点，确定一个超平面，之后用分割超平面将整个空间分为左右两个子空间；最后，将实例被分到两个子空间，直到没有实例时终止。这是将实例保存在相应的结点上。得到平衡的KD树，但平衡的KD树的搜素效率未必是最优的。

2、搜素KD树

如何利用KD树快速搜索k个最近邻点。给定一个目标实例点，搜索其最近邻。首先找到包含目标实例点的叶结点；然后从该叶节点出发，依次回退到父节点；不断查找与目标实例点最近邻的点，当确定不可能存在更近的结点时终止。

《统计学习方法》——第二章、感知机模型

http://t.csdn.cn/wFuy0http://t.csdn.cn/wFuy0

数据结构1800试题.pdf（C语言版）：

https://download.csdn.net/download/weixin_64215932/85253966

数据结构代码实现（C语言版及考研党）-算法与数据结构文档类资源-CSDN下载

参考资料

1.《统计学习方法》第二版--李航

2.《机器学习》--周志华

3.《人工智能数学基础与Python机器学习》--刘润森

4.《scikit-learn机器学习》第二版--加文.海克著，张浩然译

5.机器学习个人笔记完整版--黄海广