Press "Enter" to skip to content

【数据挖掘算法系列(一)】k-近邻(KNN)算法

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

开言

 

从本篇起,将开始我们的机器学习算法系列文章。

 

机器学习算法的作用不言而喻,是数据挖掘的核心部分也是比较难的一部分。 但是别担心,跟着文章一步步来。

 

现在网上有很多现有的机器学习框架,例如scikit-learn,很方便,直接调用就可以。 那我们为什幺还要费时间学习这些算法的原理呢? 因为如果不懂得这些算法背后的理论,逻辑,可以很肯定的说你将无法灵活运用这些框架。

 

本系列文章力争将这些算法原理,重点,应用描述得简单易懂,深入浅出。 那就让我们开始吧。

 

 

从最简单的 K 最近邻(kNN,k-NearestNeighbor)开始 。为什幺说它最简单呢。因为,不需要高深的数学知识,而且直观易懂。

 

下面我们通过一个场景代入来了解 KNN 的原理。 相信我们都投过票,最后我们选出的结果是不是票数最高的那个。 投票的结果决策依据便是多数表决法,这也是 KNN 的底层思想。

 

现在有5个日本男生和5个韩国男生,然后第十一个男生的国籍是未知的,我们叫他为 Tony ,需要你来判断他是来自韩国还是日本的。 经过我们对头发,身份,五官等特征的比对,发现跟 Tony 比较像的5个人里,有4个是韩国人,1个是日本人,那我们是不是可以说,Tony是韩国人的概率大一点,从而初步判定他是韩国人。

 

前面我们判断 Tony 是哪国人用的方法,其实就是我们今天要讲 KNN 。 KNN 的原理就是通过当前对象跟已知类别对象对比,选取最像的前 k 个对像,看看这 k 个对象中哪个类别最多,就认为这个对象就是 这个类别,从而得出这个未知对象的类别。 是不是很简单?

 

那幺怎幺判断像不像呢? 根据对象之间的距离大小来判断。

 

数学理论

 

前面我们已经了解了 KNN 算法的基本思想,下面我们来通过数学理论来解决 ‘多像’ 的问题,也就是如何计算对象之间的距离。

 

计算对象之间的距离,有很多公式,比如欧拉距离,这是最简单的,是我们初中学的。 除此之外还有曼哈顿距离,闵可夫斯基距离等,本文只用欧拉距离。

 

 

上图是欧拉距离公式。 在二维坐标系中的a,b 两个点的x 坐标之间,y坐标之间分别相减,然后平方相加再开方,便得到 a, b 两个点的距离。

 

如果三维坐标系中,a,b两点的距离公式便是

 

 

拓展这条公式,代入我们的实际应用中,x,y,z就是我们对象中的一个个特征,比如前面的国籍猜测例子,有头发,身高,嘴巴,眼睛的特征,便可以得出下面的公式

 

 

xa1,xa2,Xan便是 a 对象的一个个特征值。

 

得出来的便是对象与对象之间的距离啦。

 

KNN 的基本原理以及数学依据就是这些了,是不是很简单,下面我们通过代码来加深理解。

 

首先,定义10个二维的数据点 x 作为训练数据,并且设置类别 y

 

import numpy as np
import matplotlib.pyplot as plt
raw_data_x = [[3.39,2.33],
[3.11,1.78],
[1.34,3.36],
[3.58,4.67],
[2.28,2.86],
[7.42,4.69],
[5.74,3.53],
[9.17,2.51],
[7.79,3.42],
[7.93,0.79]
]
raw_data_y = [0,0,0,0,0,1,1,1,1,1]

 

其中 raw_data_x 为样本点,两列分别为样本的两个特征值 raw_data_y 则对应 raw_data_x 的每个样本的类别。

 

定义一个数据,并将它和样本数据进行数据可视化,更直观的查看数据分布。

 


# 转为 向量
X_train = np.array(raw_data_x)
Y_train = np.array(raw_data_y)
x = np.array([8.09,3.36])
plt.scatter(X_train[Y_train==0,0],X_train[Y_train==0,1],color='g')
plt.scatter(X_train[Y_train==1,0],X_train[Y_train==1,1],color='r')
plt.scatter(x[0],x[1],color='b')
plt.show()

 

 

如图,其中绿点为类别为0 的样本点,红点为类别为1的样本点。 蓝点就是我们要预测的数据点。

 

数据准备好之后,接下来开始我们的 KNN 算法

 

根据我们前面的这条公式,计算预测点与样本点之间的距离

 

 

 

 

from math import sqrt
#存放距离的数组
distances = []
#遍历样本数组,计算预测点与每个样本点之间的距离
for x_train in X_train:
#各特征距离差的平方相加后开方
d = sqrt(np.sum((x_train-x)**2))
distances.append(d)

 

看下预测点与各样本计算的距离

 

 

接下来就要对距离进行排序

 

#使用numpy的排序函数对距离数组进行排序
nearset = np.argsort(distances)

 

我们来看下排序后的结果

 

 

注意: 这里存的是排序后的样本点下标

 

我们设 k 为 6,获取前 k 个 距离最近的元素

 

k = 6
# 获取 y_train 数组所对应下表的元素来得到这些样本点的类别
topK_y = [y_train[i] for i in nearset[:k]]

 

我们看下这前6个元素的类别

 

 

接下来就要统计这 k 个元素中各个类别的个数

 

from collections import Counter
#分类统计
votes = Counter(topK_y)

 

 

我们可以看到分类统计的结果,其中键值为类别,值为数量。

 

现在我们取个数最多的那个类别,也就是取第一个对象的第一个元素

 

predict_y = votes.most_common(1)[0][0]

 

 

得出预测点的类别是 1

 

这样我们 knn实例就完成了。

 

总结

 

本文我们通过场景来理解 KNN 算法的原理以及学习了底层的数学理论,并用代码完整实现了一个 简单的 knn 案例。 相信各位读者大大对 KNN 算法的原理能掌握。

 

读者大大们可以思考下如果出现这种情况,该怎幺办。

 

 

 

 

绿点是我们要预测的点,现在离它最近的3个点是如图的红蓝点,但是我们发现,虽然蓝点数量上比较多,但实际上红点距离绿点比较近。用我们前面的还能正确预测出来吗。

 

下文我们将对这个问题做出解答,并用一个应用案例来补充实际情况中应用 KNN 需要进一步做的处理以及应该考虑的情况。

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注