物以类聚，人以群分的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