从零开始学Python【32】--KNN分类回归模型（理论部分）

• 前言

KNN算法属于有监督的学习算法，它的中文名称为K最近邻算法，同样是十大挖掘算法之一。它与很多其他的监督算法不同，属于“惰性”学习算法，即不会预先生成一个分类或预测模型，用于新样本的预测，而是将模型的构建与未知数据的预测同时进行。

KNN算法可以针对离散因变量作分类，又可以对连续因变量作预测，其核心思想就是比较已知y值的样本与未知y值样本之间的相似度，然后寻找最相似的k个样本用作未知样本的预测。

• KNN算法的思想

K最近邻算法，顾名思义就是搜寻最近的k个已知类别样本用于未知类别样本的预测。“最近”的度量就是应用点之间的距离或相似性，如果距离越小或相似度越高，则说明它们之间越近，关于样本间的远近度量将在后文中介绍。

“预测”，对于离散型的因变量来说，从个最近的已知类别样本中挑选出频率最高的类别用于未知样本的判断；对于连续型的因变量来说，则是将个最近的已知样本均值用作未知样本的预测。为了能够使读者理解KNN算法的思想，简单绘制了下方的示意图：

如上图所示，假设数据集中一共含有两种类别，分别用五角星和三角形表示，待预测样本为各圆的圆心。如果以近邻个数k =5为例，就可以通过投票方式快速得到未知样本所属的类别。该算法的背后是如何实现上面的分类呢，它的具体步骤可以描述为：

1）确定未知样本近邻的个数k值；

2）根据某种度量样本间相似度的指标（如欧氏距离），将每一个未知类别样本的最近k个已知样本搜寻出来，形成一个个簇；

3） 对搜寻出来的已知样本进行投票，将各簇下类别最多的分类用作未知样本点的预测；

通过上面的步骤，也能够解释为什么该算法被称为“惰性”学习算法，如果该算法仅仅接受已知类别的样本点，它是不会进行模型运算的，只有将未知类别样本加入到已知类别样本中，它才会执行搜寻工作，并将最终的分类结果返回出来。

所以，执行KNN算法的第一个任务就是指定最近邻的个数k值，接下来需要探讨KNN算法中该如何选择合理的k值。

• 最佳k值的选择

根据经验发现，不同的k值对模型的预测准确性会有比较大的影响，如果k值过于偏小，可能会导致模型的过拟合；反之，又可能会使模型进入欠拟合状态。为了使读者理解上述的含义，这里举两个极端的例子加以说明。

假设k值为1时，意味着未知样本点的类别将由最近的1个已知样本点所决定，投票功能将不再起效。对于训练数据集本身来说，其训练误差几乎为0；但是对于未知的测试数据集来说，训练误差可能会很大，因为距离最近的1个已知样本点可以是异常观测也可以是正常观测。所以，k值过于偏小可能会导致模型的过拟合。

假设k值为N时，意味着未知样本点的类别将由所有已知样本点中频数最高的类别所决定。所以，不管是训练数据集，还是测试数据集，都会被判为1种类别，进而导致模型无法在训练数据集和测试数据集上得到理想的准确率。进而可以说明，如果k值越大，模型偏向于欠拟合的可能性就越大。

为了获得最佳的值，可以考虑两种解决方案，一种是设置k近邻样本的投票权重，假设读者在使用KNN算法进行分类或预测时，设置的k值比较大，担心模型发生欠拟合的现象，一个简单有效的处理办法就是设置近邻样本的投票权重，如果已知样本距离未知样本比较远，则对应的权重就设置的低一些，否则权重就高一些，通常可以将权重设置为距离的倒数；另一种是采用多重交叉验证法，该方法是目前比较流行的方案，其核心就是将k取不同的值，然后在每种值下执行m重的交叉验证，最后选出平均误差最小的k值。当然，还可以将两种方法的优点相结合，选出理想的k值。具体的实战部分将在下一期中跟大家分享，帮助读者理解最佳k值的确定过程。

• 相似度的度量方法

如前文所说，KNN分类算法的思想是计算未知分类的样本点与已知分类的样本点之间的距离，然后将未知分类最近的k个已知分类样本用作投票。所以该算法的一个重要步骤就是计算它们之间的相似性，那么，都有哪些距离方法可以用来度量点之间的相似度呢？这里简单介绍两种常用的距离公式，分别是欧式距离和曼哈顿距离，然后再拓展另外两种相似度的度量指标，一个是余弦相似度，另一个是杰卡德相似系数。

• 欧式距离

该距离度量的是两点之间的直线距离，如果二维平面中存在两点

，则它们之间的直线距离为：

可以将如上的欧式距离公式反映到下图中，实际上就是直角三角形斜边的长度，即勾股定理的计算公式。

如果将点扩展到n维空间，则点，之间

的欧式距离可以表示成：

• 曼哈顿距离

该距离也称为“曼哈顿街区距离”，度量的是两点在轴上的相对距离总和。所以，二维平面中两点

之间的曼哈顿距离可以表示成：

将曼哈顿距离表示在下图中，读者就能够理解上面公式所表达的含义了：

如上图所示，假设各网格线代表每一条街道，如果从A点出发，前往B点，则两点之间的距离可以是沿着红色虚线行走的路程之和。换句话说，虚线的长度之和其实就是AC与BC的路程和，即曼哈顿距离就是在轴上的相对距离总和。

同样，如果将点扩展到n维空间，则点

之间的曼哈顿距离可以表示成：

• 余弦相似度

该相似度其实就是计算两点所构成向量夹角的余弦值，如果夹角越小，则余弦值越接近于1，进而能够说明两点之间越相似。对于二维平面中的两点

来说，它们之间的余弦相似度可以表示成：

将

两点所构成向量的夹角绘制在下图中，就能够理解夹角越小，两点越相似的结论：

如上图所示，假设A、B代表两个用户从事某件事的意愿，意愿程度的大小用各自的夹角

和

表示，如果两个夹角之差

越小，则说明两者的意愿方向越一致，进而他们的相似度越高（不管是相同的高意愿还是低意愿）。

如果将点扩展到n维空间，则点

之间的余弦相似度可以用向量表示为：

其中，点

代表两个向量之间的内积，符号

代表向量的模，即

正则。

• 杰卡德相似系数

该相似系数与余弦相似度经常被用于推荐算法，计算用户之间的相似性。例如A用户购买了10件不同的商品，B用户购买了15件不同的商品，则两者之间的相似系数可以表示为：

其中,

表示两用户所购买相同商品的数量，

代表两用户购买所有产品的数量。例如，A用户购买的10件商品中，有8件与B用户一致，且两用户一共购买了17件不同的商品，则它们的杰卡德相似系数为8/17。按照上面的公式，如果杰卡德相似系数越大，则代表样本之间越接近。

相似度度量的注意事项

如果使用距离方法来度量样本间的相似性，必须注意两点，一个是所有变量的数值化，如果某些变量为离散型的字符串，它们是无法计算距离的，需要对其作数值化处理，如构造哑变量或强制数值编码（例如将受教育水平中的高中、大学、硕士及以上三种离散值重编码为（0,1,2）；另一个是防止数值变量的量纲影响，在实际项目的数据中，不同变量的数值范围可能是不一样的，这样就会使计算的距离值受到影响，所以必须采用数据的标准化方法对其归一化，使得所有变量的数值具有可比性。

在确定好某种距离的计算公式后，KNN算法就开始搜寻最近的k个已知类别样本点。实际上该算法在搜寻过程中是非常耗内存的，因为它需要不停的比较每一个未知样本与已知样本之间的距离。

KNN在搜寻近邻样本时会采用不同的方法，如暴力搜寻法、KD树搜寻法和球树搜寻法，不同的搜寻方法往往会提升模型的执行效率。关于搜寻法的详细介绍，读者可以查看我的新书《从零开始学Python数据分析与挖掘》。

结语

OK，关于KNN算法的思想和理论知识我们就分享到这里，如果你有任何问题，欢迎在公众号的留言区域表达你的疑问。同时，也欢迎各位朋友继续转发与分享文中的内容，让更多的人学习和进步。