开言
从本篇起，将开始我们的机器学习算法系列文章。
机器学习算法的作用不言而喻，是数据挖掘的核心部分也是比较难的一部分。 但是别担心，跟着文章一步步来。
现在网上有很多现有的机器学习框架，例如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 需要进一步做的处理以及应该考虑的情况。
Be First to Comment