作为一个过渡，这一节记录关于knn的知识。
这篇博客不贴关于knn的具体细节了，knn是十分容易理解的，关于knn可参考的博客一大堆，贴一个讲的好的吧一只兔子理解knn

KNN

选择样本数据集中与待预测值前k个最相似的样本，取其中最多的作为该待预测值的类

如果希望knn不给出所述的类，给出可能所述类的概率也是可行的。
很多人会疑惑k应该如何选取，一般来说，k靠经验，或者一个个试。也有个通俗的经验就是k取样本数的平方根。
下面讲维度灾难时会提到关于k的选取问题。

距离

关于具体的选择标准可能比k更重要。
一般来说选择欧式距离（本节不讨论距离，抽时间好好总结下距离）就可以了。即，$x=(x_1, x_2,...,x_n),y=(y_1,y_2,...,y_n)$，则该两个样本的距离如下：

$$d=\sqrt{\sum_{i=1}^{n}{(x_i-y_i)^2}}$$
然而在实际中，有选择的尺度选择的标准不一样，这回影响到具体数值的大小。
比如 $x=(1.74cm,60kg),y=(1,80cm,90kg)$.
因此我们需要做归一化，即将同属性除以该属性的最大值与最小值之差。
两个样本 $样本i和样本j，x_i=(x_{i1},x_{i2},...,x_{in}),x_j=(x_{j1},x_{j2},...,x_{jn})$.总样本数为m。则样本i和样本j的距离如下：
$$d_{ij}=\sqrt{\sum_{k=1}^{n}{\frac{(x_{ik}-x_{jk})^2}{\max \limits_{1\le l\le m}x_{lk}-\min \limits_{1\le l\le m}x_{lk}}}}$$
即做好了归一化处理。

维度灾难

最后详细讲解为什么knn会引起维度灾难。
同样，贴一篇文章分类中的维度灾难
该文章详细解释了为什么会有维度灾难。在关于数据为何增多却没有详细说明。
假设样本点取n维，样本选取的标准是为了覆盖总体20%的范围特征。
我们假设样本点每个维度都有10个可能的取值。
1. 当n为1时
则总体数量为10，只需要2个样本就能覆盖总体的20%
2. 当n取2时
有两个维度，这时总体的数量变为100（10*10），那么就需要20只了。
3. 当取n时
共有$10^n$个数量，样本应取$10^n*0.2$个。
注意，这与我们平时理解的总体不一样。
因为总体的数量从一开始就是固定的，比如，全世界有1亿只苍蝇，如果只需要拿红眼和白眼来作为区分，那么可能取5只就够了，但如果增加属性的维度，比如在增加翅膀长度，个体大小，年龄，那么需要的果蝇数量将呈指数级增长。这是导致维度灾难的主要原因。
从这个意义上说，不仅是knn,其他分类算法都会遇到维度灾难的问题。

距离与维度灾难

knn的基础是距离。维度灾难在使用距离的比较时问题尤甚。
会导致这个问题是因为，当维度增大时，距离某个样本点单位距离内的其他样本点数量的比值会减少，这会导致我们寻找更远的距离才能找到临近的值。
注意，虽然看起来对于knn选择的k个样本点并没有影响，但问题是选择的样本点随着维度的增高，距离该样本是越来越远的，因此没有那么有参考价值了。
这是维度灾难对于knn影响特别大的地方。

另一个问题在于，knn每次需要遍历整个样本，这会导致大量计算。