大话系列 | k近邻（上）—理论
↑关注+星标，听说他有点东西
全文共2457字，阅读全文需13分钟
写在前面的话
大家好，我是小一
前面已经介绍了两篇分类算法，然而机器学习的分类算法真的是有点多，所以，这篇还是分类算法。
相比起贝叶斯分类，这篇分类算法理解起来超级容易，容易到我都没办法准备背景故事
准备好了吗？
1. KNN是什么？
KNN：K-Nearest Neighbor 中文翻译为k最近邻。
这里面有两个概念，一个是K，一个是近邻
这里K表示的是K个样本，近邻表示的是距离最近的样本，所以K最近邻就是K个距离最近的样本。
这说的什么玩意？举个例子好咩
某公司有一批客户，根据客户的消费水平将客户划分为超高价值客户、高价值客户、普通客户和低价值客户。
现在通过新的促销方式新增了一批新客户，通过观察这一批客户最近一段时间的消费情况，需要对他们进行群体分类。
例子举好了，你倒是分类啊！
在划分的过程中，通过“六度法则”我们将K值设置为6，并且计算新客户和所有已分类客户的差异值。
选取差异值最小的Top6个已分类客户，根据Top6客户所在最多的类别确定为该新客户的类别。
上面这个过程其实就是KNN的分类过程，这里面K值的设置和客户差异值的计算就是上面提到的两个参数。
2. KNN工作原理
2.1. 分类原理
K近邻的分类原理用一句谚语来形容就是：近朱者赤，近墨者黑。
小伙子听好了，下面是重点
在k近邻算法中：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。
整个分类过程分为三步：
①根据给定的距离度量，计算待分类点与其他实例点的距离 ②根据距离，在训练集T中找到与x最近邻的k个点，涵盖这k个点的x的邻域记作 ③在中根据分类决策规则（如多数表决）决定x的类别y
k近邻的特殊情况是k=1的情形，称之为最近邻算法对于输入的实例点x
最近邻法将训练数据集中与x最邻近的类作为x的类
你这不是废话么，你就直接告诉我k近邻要注意啥？
在k近邻算法中，有三个基本要素需要注意，分别是：距离度量，k值的选择和分类决策规则。
下面来详细说说k近邻的三要素
2.2. 距离度量
在特征空间中，两个实例点之间的距离是两个实例点相似程度的反映。
例如，在平面中的两点可以通过距离公式计算相似度，而两段不同的文本可以通过文本距离计算文本相似度，甚至两个不同的图像也可以根据像素点的距离计算图像相似度。
这个我知道，可是这个距离度量有什么用？
在k近邻算法中，一个很重要的计算就是关于距离的度量。距离越大，差异性越大；距离越小，相似度越大。
就找与它最相似的呗，那这个距离一般怎么计算的？
已知的距离计算方式有很多：
欧式距离（k近邻最常用） 曼哈顿距离 余弦距离 切比雪夫距离 闵可夫斯基距离
欧氏距离
这个知道，初中就学过，就那个欧几里得嘛
对，欧式距离又叫欧几里得距离。在二维空间中，两点之间的欧式距离是：
推广至n维空间，则两点之间的欧氏距离是：
曼哈顿距离
莫非是曼哈顿街区？
差不多有内个味
曼哈顿距离等于两个点在标准坐标系上的绝对轴距总和，就像下面这张图一样，城区中两个点之间的最短路径所示。
我说这是曼哈顿街区图你信不信
绿色直线的就是上面说到的欧氏距离，但是城区之间是不能直接这样到达的，虽然它最短。
所以曼哈顿距离就表示两个点在坐标上的绝对轴距总和，就像图中的红色+黄色的线为两点的曼哈顿距离，蓝色的线同样也是。
余弦距离
认识余弦距离，先来看看余弦相似度
余弦相似度是通过计算两个向量的夹角余弦值评估它们的相似度。
根据欧几里得的点积公式：
给定两个属性向量A和B，则其余弦相似度θ为：
所以，余弦距离
根据上面的计算可以发现，余弦距离的取值范围是[0,2]
切比雪夫距离
这个是盲区了，请开始您的表演
两点之间的切比雪夫距离就是两点坐标数值差的绝对值的最大值，用数学表示就是：
闵可夫斯基距离
闵可夫斯基距离可用于多维空间的计算两点间的距离。
例如，对于n维空间中的两个点和，x和y两点之间的闵可夫斯基距离为：
p代表空间的维数，（p常取值为1,2,∞）
需要注意的是当p=1，就是曼哈顿距离；当p=2，就是欧式距离；当p→∞时，就是切比雪夫距离。
2.3. K值的选择
k值的选择会对k近邻法的结果产生重大影响。
怎么说？k值还会影响模型的结果不成？
如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，因为此时只有与输入实例较近（相似）的训练实例才会对预测结果起作用，所以此时的近似误差会减小。
但是由于预测结果会对近邻的实例点非常敏感，所以恰巧邻近的实例点是噪声点，那么预测就会出错。
换句话说，k值的减少意味着整体模型变得复杂，容易发生过拟合
那选了大的k值呢？
相反的，如果选择较大的k值，就相当于用较大的邻域中的训练实例进行预测 ，因为此时与输入实例较远（不相似）的训练实例也会对实例的 预测起作用，所有此时的近似误差会增大。
特别的，当k=N（样本个数）时，无论输入实例是什么，都会预测成在训练实例中最多的类
换句话说，k值的增大意味着整体模型变得简单，容易发生欠拟合。
有没有什么好的选择方法？
在选择k值的时候一般需要经过多次实验确定最优，比如说通过交叉验证等。
2.4. 分类决策规则
一般在分类决策中，我们都选择k个邻居中所属类别最多的类，也就说平时说的众数类。
当然这个也不是很绝对，你也可以根据k个邻居的距离设置不同的权重，根据权重去进行分类
总之，分类决策会根据样本数据的特性去选择
总结
ok，想必你现在应该对k近邻分类不陌生了，稍稍总结一下：
k近邻的三要素：距离度量，k值的选择和分类决策规则
思考一个问题，当需要对一个新的客户进行k近邻分类，我们需要计算新客户与已有所有客户的距离，然后选择k个最近的...
当已有客户量超大的时候，我们还需要去一一进行比较嘛？
这个问题其实在决策树里面也提到过，嗯，优化一下客户的存储方式。
感兴趣的同学可以思考一下答案
我是小一，我们下节见
好巧啊，你也读到这了！
点个在看让小一看到你