机器学习系列 k近邻法

导语

本系列教程将尝试介绍线性回归、逻辑回归、决策树、支持向量机、朴素贝叶斯、k均值、k近邻、随机森林、Adaboost等常用的机器学习算法。

对于每一种算法，本系列教程都将利用纯python代码对其进行一般性的实现(即不使用sklearn等现成的机器学习库)，并将其应用于一个具体实例中来做进一步的说明。

题外话

本系列教程不定期更新，介绍顺序看心情，详细讲解算法原理，提供但不讲解如何利用纯python复现算法，不过写代码的时候我会尽量注释清楚的。

往期回顾

暂无，就当是占位符吧。

原理介绍

k近邻法(k-NN, k-nearest neighbor)由Cover和Hart于1968年提出，是一种基本分类与回归方法。

k-NN的输入为实例的特征向量，对于分类问题，其输出为实例的类别，对于回归问题，其输出为实例的属性值。由于k近邻法一般用于分类问题，因此本文只讨论分类问题中的k近邻法。

一. 基本思想

“给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。”

即k-NN是一种基于实例的学习，不具有显式的学习过程。人们常常会在无形之中应用它，比如你想要了解一个完全陌生的人，你常常通过他的好友或者说他的圈子来获得他的信息。

注：当k=1时，k近邻法又称最近邻法。

二. 严格定义

三. 进一步理解

k近邻法使用的模型实际上对应于特征空间的划分，模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。

（1）距离度量

特征空间中两个实例点之间的距离是其相似程度的反映。一般而言，特征空间是n维实数向量空间，因此距离度量可选择闵可夫斯基距离(Lp距离)：

当p=1时，又称曼哈顿距离；当p=2时，又称欧式距离；当p趋向于无穷大时，又称切比雪夫距离。

注：特征空间中的特征向量一般为归一化后的特征向量，即特征归一化。

（2）k值的选择

k值的选择会对k近邻法的结果产生重大影响，当k较大时，近似误差(度量与最优误差之间的相近程度，也就是最小的测试误差)较大，估计误差(度量预测结果与最优结果的相近程度，也就是最小测试误差减去减去最小训练误差的绝对值)较小；当k较小时，近似误差较小，估计误差较大。换句话说，k值的减小意味着整体模型变复杂，容易发生过拟合，k值的增大意味着整体模型变简单，容易发生欠拟合。

再直观点的解释就是当k过小(比如等于1)时，预测结果很容易受到某个噪声点的影响，当k过大(比如等于训练集总数据量N)时，预测结果始终为训练实例中数量最多的类。

一般而言，k是不大于20的整数，可通过交叉验证法来选取最优k值。

（3）分类决策规则

一般采用多数表决，即使得经验风险最小化。

四. 问题及解决方案

（1）多数表决

问题：

当训练集类别分布偏斜时，出现频率较高的样本将会主导测试点的预测结果。

解决方案：

抽象数据表示形式，例如SOM；

在指示函数前面加上权重。例如，将某近邻点对测试样本输出结果的影响与该近邻点到测试样本的距离挂钩，公式表述如下：

（2）计算复杂度

问题：

普通的k近邻法时间复杂度为O(n)，当训练集很大时，计算预测结果非常耗时。

解决方案：

使用Ko与Seo提出的TCFP；

使用Han等人提出的WAkNN；

使用kd树。

五. 扩展内容-kd树

注：kd树中的k和k近邻法中的k不是一个意思。

这里我们简单介绍一下kd树。

（1）构造kd树

该算法的严格定义如下：

（2）搜索kd树

该算法的严格定义如下：

应用实例

一. 任务简介

利用纯python代码实现最基本的k-NN模型，并利用该模型解决手写数字识别问题。

二. 任务实现

数据集：

5000张类似下图的手写数字，大小为32*32：

建模：

取k=10，距离度量为欧式距离，分类决策规则为多数表决。令前4500组数据为训练数据，剩余500组数据为测试数据。

具体实现：

具体实现过程详见相关文件中的源代码：

KNN.py：

KNN模型的实现；

example.py：

手写数字识别的实现。

结果展示：

参考文献

《统计学习方法》，李航；

K-nearest_neighbors_algorithm，维基百科；

《Machine Learning in Action》，

其他网络博文。