前言

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个训练样例的集合ZZD

5:y’=argmax∑(xi,yi)∈DZI(V=YI)

6:end for

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

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

二 KNN注意点

2.1 KNN算法的距离度量

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

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

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

2.3 KNN算法中K的奥妙

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

机器学习笔记--KNN算法1

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

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

2.3 对于KNN的补充
2.3.1 权重化

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

2.3.2归一化

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

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

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