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

开言

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

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

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

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

k-近邻（KNN）

从最简单的 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 需要进一步做的处理以及应该考虑的情况。