KNN(k-nearestneighbor的缩写)又叫最近邻算法

前言

Hello ,everyone. 我是小花。大四毕业，留在学校有点事情，就在这里和大家吹吹我们的狐朋狗友算法---KNN算法，为什么叫狐朋狗友算法呢，在这里我先卖个关子，且听我慢慢道来。

一 KNN算法简介

KNN(k-nearest neighbor的缩写)又叫最近邻算法。是1968年由Cover和Hart提出的一种用于分类和回归的无母数统计方法。什么叫无母统计方法呢，这里作个补充：无母统计方法又称非参数统计学，是统计学的一个分支，适用于母群体情况未明，小样本，母群体分布不为常态也不易转换为常态。特点在于尽量减少或不修改其建立之模型，比较适合处理样本不大的数据。（我怎么感觉这么像韦小宝啊。。。哈哈，有点扯远了，你懂得）。

KNN的工作原理是：存在一个样本数据集合，也称为训练样本集，而且样本集中每个数据都存在标签，也就是我们知道样本集中每一个数据与所属分类对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。怎样理解这句话呢，现在我们想，假如广场上有很多狗，这些狗都是一条母狗带一群小狗，各个品种的都有。每条狗都都知道自己的母亲是谁。但是有一条狗喝了不下心忘情水，不知道自己妈妈在哪了，如何找他的母亲呢。那我们就把这条狗的特征与那些小狗的特征进行对比。然后取最相似的狗，那么他的母亲就是这只单身狗的母亲~~我们可以想象，一只吉娃娃一定离一直泰迪很远吧。

K-最近邻分类算法

1：令k是最近邻数目，D是训练样本的集合

2 : for每个测试样例 z=（x’,y’）do

3：计算z 和每个样例（x,y）∈D之间的距离d(x’,x)

4：选择离z最近的K个训练样例的集合Z_ZD

5：y’=argmax∑(x_i,y_i)∈D_Z^I(V=YI)

6：end for

又扯远了，现在言归正传。我想看这个都是像我这样天天撸代码的“抠脚大汉”。那我们直接上伪代码！

啧啧，有了伪代码果然神清气爽。那我们就来说说伪代码吧。首先大家肯定会问第三行，如何求取z 和每个样例（x,y）∈D之间的距离d(x’,x)？他们之间的距离公式是什么，这个真就问对人了。我们的祖师爷们早就给我们想好了招式了，现在请把任督二脉打开，我要传功给你！

二 KNN注意点

2.1 KNN算法的距离度量

特征空间中两个实例点的距+离是两个实例点相似程度的反应。（一定要重点理解，可以拿单身狗的想想）。K近邻模型的特征空间一般是n 维实数向量空间R^N.使用的距离是欧式距离，但也可以是其他距离，例如更加一般的L_P距离（L_p distance）或Minkowski距离（Minkowski distance）

1. 欧氏距离，最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为：

2.曼哈顿距离, 曼哈顿距离依赖坐标系统的转度，而非系统在坐标上的平移或映射。

2.3 KNN算法中K的奥妙

现在有很多小伙伴要问我了，你说这个是狐朋狗友算法，你怎么解释？ 中国有句古话叫观其友而知其人，就是说啊，我看你身边的朋友我就知道你是什么样的人，就像我周围的同学大部分是比较傻叉的，余下的我还要解释么？。。。又自黑了。。。。估计有些朋友要怼我了，你罗里吧嗦半天，K是什么意思？其实K 就是我们最近的K个朋友，比如我最近的朋友是一个人，他是流氓，那么我是流氓的可能性是不是很大？假如K是四个，他们三个中有三个流氓，一个人渣。Vote 3:1 。好，小花是流氓，判定正确。。。下面看图：

对于未知类黑爱心,他可能是五角星，也可能是菱形。当K=3的时候，菱形PK 五角星=2:1 ，菱形胜利，老婆归我（黑色星）。当K=7时，菱形PK五角星=5:2，五角星胜利，老婆归我。这个怎么像黑帮斗殴，人多力量大啊！对了，就是人多力量大，识时务者为俊杰。

综上所述，K的选择很大程度决定了算法是否能正确分类。这也是KNN欠缺的地方。

2.3 对于KNN的补充

2.3.1 权重化

很多聪明的小伙伴会问，你的距离公式是不是有点问题？假如我现在给百合网做一个推荐系统，根据的分高低为你推荐一个你们会觉得合适的人。对象特性（身高，体重，相貌，学历，收入，爱好），假如你是一个颜控，你对身高体重外貌比较在意，对收入及学历不是太在乎，我想这也是我们在现实相亲中经常遇到的问题。那如果我们按照上面的欧氏距离公式去求，似乎收入和学历对分数的影响和相貌，身高体重一样大啊。那么为了解决这个问题，我们引入了权重的概念，比如当我们进入系统，系统会可以让我们输入：（身高，体重，相貌，学历，收入，爱好）的权重w^T（w₁, w_2, w₃, w_4,w₅, w₆）,你认为重要你就输入大一点，你认为不重要，你就输入小一定，当然这些权重最好都是小于1 的。改变的公式如下:

2.3.2归一化

现在带入公式发现，假如身高180和收入8000，即使收入的权重比较小，但是对距离的影响还是很大。在处理这种不同权值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转化为0到1区间内的值：

newValue=(oldValue – min)/(max – min)

最后说一句，小花的算法讲解，算法1一般先介绍基本理论，算法二开始都是这个算法在具体生活中的实例，总之，跟着小花一步一步学吧，毕竟我也刚接触，有很多理解不到位的地方还请大家指出来，一起去思考。哈哈。