机器学习实战总结(1) K-邻近算法
1 KNN概述
K-邻近算法采用测量不同特征值之间的距离方法进行分类，工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，意思是我们知道样本集中的每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
比如上图中，假如五角星为新数据，k=3，那么我们明显可以看出来与其最相近的三点为红色圆圈，那么可以将红色圈的类别作为五角星⭐️的类别
2 KNN操作流程
对未知类别的数据集中的每个点依次执行以下操作：
- 计算已知类别数据集中的点与当前点之间的距离；
- 按照距离递增次序排序；
- 选取与当前距离最小的k个点；
- 确定前k个点所在类别的出现频率；
- 返回前k个点出现频率最高的类别作为当前点的预测分类；
3 常见距离公式
3.1 欧式距离
3.2 曼哈顿距离
3.3 余弦相似度
3.4 Levenshtein距离
莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
def lev(a, b):
if not a: return len(b)
if not b: return len(a)
return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1)3.5 JACCARD DISTANCE
雅卡尔指数，又称为并交比、雅卡尔相似系数，是用于比较样本集的相似性与多样性的统计量。雅卡尔系数能够量度有限样本集合的相似度，其定义为两个集合交集大小与并集大小之间的比例： 如果A与B完全重合，则定义J = 1。于是有 雅卡尔距离则用于量度样本集之间的不相似度，其定义为1减去雅卡尔系数.
3.6 MAHALANOBIS DISTANCE
马哈拉诺比斯距离是由印度统计学家马哈拉诺比斯 (英语)提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的（scale-invariant），即独立于测量尺度。
si为xi的标准差，如果协方差矩阵为单位矩阵，马哈拉诺比斯距离就简化为 欧氏距离。
3.7 Minkowski distance
明氏距离又叫做明可夫斯基距离，是欧氏空间中的一种测度，被看做是欧氏距离和曼哈顿距离的一种推广。
下面是p取不同值的距离公式图像：
p取1或2时的明氏距离是最为常用的，p=2即为欧氏距离，而p=1时则为曼哈顿距离。当p取无穷时的极限情况下，可以得到切比雪夫距离。
讲了这么多，KNN常用的距离公式是欧式距离和曼哈顿距离，但是也希望大家记住其他的距离公式，面试的时候通常也会考察，另外文本相似性也会用到其他距离公式。
4 KNN优点和缺点
4.1 优点
- 精度高
- 对异常值不敏感
- 无数据输入假定
4.2 缺点
- 计算复杂度高，尤其K值较大时
- 空间复杂度高
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）
- 最大的缺点是无法给出数据的内在含义
5 如何选择合适的K值
- K值较小，则模型复杂度较高，容易发生过拟合，学习的估计误差会增大，预测结果对近邻的实例点非常敏感。
- K值较大可以减少学习的估计误差，但是学习的近似误差会增大，与输入实例较远的训练实例也会对预测起作用，使预测发生错误，k值增大模型的复杂度会下降。
- 在应用中，k值一般取一个比较小的值，通常采用交叉验证法来来选取最优的K值。