物以类聚，人以群分的KNN算法(上)

什么是KNN

有天，你想着把你另外一套房子租出去，这样还能减轻一下生活的负担。但是你却不知道把房租定为多少比较合适。这时候你就在业主群里加了几个房子已经出租的房主，分别询问了他们的楼层高度、房屋面积、采光率等因素以及他们出租的价格。然后你找到两三个跟你房间差不多情况的，得知他们的出租价格都在a元左右，你就想着：得了，我的房子出租价格也定为a元吧。

这种“根据相似房屋价格确定自己房屋价格”的思维方式，就是K近邻（K-Nearest Neighbors，KNN）算法的核心思想！

KNN是由 Cover 和 Hart 于 1968 年提出的经典机器学习算法，属于监督学习方法，它的工作机制比较简单，通俗点说就是“物以类聚，人以群分”。它给定测试样本，根据某种的距离度量找出训练集中跟它最近的k kk个训练样本，然后基于这k kk个邻居的信息，来对结果进行预测。

KNN与之前介绍的线性回归、逻辑回归不同，它是有名的“惰性学习”的代表，它在训练阶段只是把样本保存好，在有测试样本来了，才在训练集中找到与测试样本相近的k kk个邻居样本，并根据这些邻居样本给出测试样本的最终结果。

应用场景

KNN做为常见的机器学习算法，常见的应用场景如下：

• 分类：垃圾邮件分类、物体识别等

• 回归：销量预测、房价预测、气温预测等。

KNN基本原理

核心思想

KNN的原理可以概况为：给定一个训练数据集，对于新的输入样本，在训练集中找到跟这个样本最邻近的k kk个实例，根据这k kk个示例的标签值，得到新输入样本的预测值。

要想用好KNN，就得先搞清楚以下这三个问题：如何判断最邻近，如何选择合适得k值，以及如何得出最终预测值？

距离计算

在我们日常生活中，说两个人很近，可以是住得近、每天在一起时间很多、共同爱好很多等。在特征空间中两个样本点的距离是两个样本点相似度的反映。KNN中特征空间一般是n nn维实数向量空间R n \mathbf{R}^nRn, 使用的是欧式距离。但是也可以是其他距离，比如更一般的L p L_pLp​距离。

假设特征空间X \mathcal{X}X是n nn维的实数向量空间R n \mathbf{R}^nRn，x i , x j ∈ X , x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( n ) ) T , x j = ( x j ( 1 ) , x j ( 2 ) , . . . , x j ( n ) ) T x_i,x_j\in{\mathcal{X}}, \quad x_i=(x_i^{(1)}, x_i^{(2)},...,x_i^{(n)})^T,\quad x_j=(x_j^{(1)}, x_j^{(2)},...,x_j^{(n)})^Txi​,xj​∈X,xi​=(xi(1)​,xi(2)​,...,xi(n)​)T,xj​=(xj(1)​,xj(2)​,...,xj(n)​)T

• 闵可夫斯基距离

x i , x j x_i,\quad x_jxi​,xj​的L p L_pLp​距离为：
L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_p(x_i, x_j) = (\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}Lp​(xi​,xj​)=(l=1∑n​∣xi(l)​−xj(l)​∣p)p1​
在这里p ≥ 1 p\geq1p≥1，当p pp分别取 1、2、∞ \infty∞时，则分别为曼哈顿距离、欧式距离和切比雪夫距离。

• 曼哈顿距离

曼哈顿距离是各个维度的坐标差之和。其计算公式为：
L 1 ( x i , x j ) = ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ L_1(x_i, x_j) = \sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|L1​(xi​,xj​)=l=1∑n​∣xi(l)​−xj(l)​∣
假设你在坐标点( 1 , 1 ) (1, 1)(1,1)，距离坐标( 3 , 4 ) (3, 4)(3,4)的曼哈顿距离L = ∣ 1 − 3 ∣ + ∣ 1 − 4 ∣ = 5 L=|1-3|+|1-4|=5L=∣1