1、模型介绍
KNN是通过测量不同特征值之间的距离进行分类。它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。KNN算法的结果很大程度取决于K的选择。
1.1 模型
就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：
- 计算测试数据与各个训练数据之间的距离；
- 按照距离的递增关系进行排序；
- 选取距离最小的K个点；
- 确定前K个点所在类别的出现频率；
- 返回前K个点中出现频率最高的类别作为测试数据的预测分类。
1.2 常用的距离计算公式
欧式距离
曼哈顿距离
切比雪夫距离(Chebyshev Distance)
起源于国际象棋中，国王从一个格子到另一个格子要走的最少的步数
闵可夫斯基距离(Minkowski Distance)
闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。
其中p是一个变参数：
当p=1时，就是曼哈顿距离；
当p=2时，就是欧氏距离；
当p→∞时，就是切比雪夫距离。
标准化欧氏距离 (Standardized Euclidean Distance)
标准化欧氏距离是针对欧氏距离的缺点而作的一种改进。标准欧氏距离的思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。
标准化
假设样本集X的均值(mean)为$ \mu$ ，标准差(standard deviation)为s，X的“标准化变量”表示为：
标准化欧氏距离公式：
马氏距离(Mahalanobis Distance)
上图有两个正态分布的总体，它们的均值分别为a和b，但方差不一样，则图中的A点离哪个总体更近？或者说A有更大的概率属于谁？显然，A离左边的更近，A属于左边总体的概率更大，尽管A与a的欧式距离远一些。这就是马氏距离的直观解释。
概念：马氏距离是基于样本分布的一种距离。物理意义就是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解。再对所有主成分分解轴做归一化，形成新的坐标轴。由这些坐标轴张成的空间就是规范化的主成分空间。
定义：某个类别有M个样本向量，其协方差矩阵记为S，均值记为向量μ，则一个样本向量X到μ的马氏距离表示为：
马氏距离是衡量样本点距离一个整体集合中心的距离
- 若协方差矩阵是单位矩阵（各个样本向量之间独立同分布），则Xi与Xj之间的马氏距离等于他们的欧氏距离
若协方差矩阵是对角矩阵，则就是标准化欧氏距离。
马氏距离的特点：
量纲无关，排除变量之间的相关性的干扰；
- 计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在，这种情况下，用欧式距离计算即可。
余弦距离(Cosine Distance)
夹角余弦可用来衡量两个向量方向的差异，其取值范围为[-1,1]：
2、模型分析
2.1 模型优缺点
优点
- 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
- 可用于数值型数据和离散型数据；
- 训练时间复杂度为O(n)；无数据输入假定；
- 对异常值不敏感。
缺点
- 计算复杂性高；空间复杂性高；
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
- 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。
- 最大的缺点是无法给出数据的内在含义。
参考链接
