K-近邻算法(KNN)概述

       我们知道有很多题材的电影。如果我们给电影分类可以根据电影的一些特征进行分类。如动作片的打斗场景比较多而爱情片的亲吻镜头比较多。对于一部没有看过的电影，如何确定它是爱情片还是动作片？

       首先我们需要知道这部电影有多少个打斗和亲吻的镜头，然后计算这部电影与我们所知的几步电影(分类已知)之间的距离，按照距离递增排序，取与这部电影最近的前K项，把这部电影归为前K项中所属分类最多的哪一类。

       距离的定义：设X是任一非空集，对X中任意两点x,y有一实数d(x,y)与之对应且满足，非负性、统一性、对称性、值递性。称d(x,y)为X中的一个距离，定义了距离d的集X称为一个距离空间。

       马氏距离(闵可夫斯基距离)

其中d是维数，p是阶数，也称为范数

当p=1时，是曼哈顿距离

当p=2时，是欧氏距离

当p趋于无穷时，是切比雪夫距离

当p=0时，是海明距离

      欧式距离：

       曼哈顿距离：

      在KNN距离一般使用欧式距离和曼哈顿距离。

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。