1、k近邻简介
1-1、算法思路
k近邻（K-Nearest Neighbor）可能是最简单的机器学习算法，它基于有监督，用作于分类。算法的基本思路是：求出对于要推理的样本k个最靠近的样本，这k个样本再进行投票，出现最多的类别则为最终的结果。
这里有三个地方需要注意，第一个是k取多少？第二个是"最靠近"怎么度量？分类决策到底该怎么定？
来一个一个分析，首先k的取值是没有特定的经验公式来告诉我们应该取多大，可以从超参数搜索这个角度尝试，找出一个最优k。
第二个是“最靠近”，一般是两种：一种是距离的“最靠近”，比方k为3，待推理的样本点旁有一个样本属于类别a，两个样本属于类别b，这时2:1，待推理的样本属于类别b；另一种是距离带权重的“最靠近”，比方k为3，待推理的样本点旁有一个样本属于类别a，两个样本属于类别b，和类别a的距离为1，和类别b的距离为2、3，那最终的结果为a--1个a，b--(1/2+1/3)个b，待推理的样本属于类别a。计算距离主要用3个公式：欧拉距离、曼哈顿距离和明科夫斯基距离，其他的公式大家感兴趣可以再研究一下。
最后分类决策到底该怎么定？距离的“最靠近”，又称投票法没有考虑近邻的距离的远近；而距离更近的近邻也许更应该决定最终的分类，所以距离带权重的“最靠近”，又称加权投票法更恰当一些。
1-2、图示
knn
如图所示，待推理的样本点-小蓝点，在两个类别小红和小绿中进行分类。可以看出knn并没有学习/训练的阶段，所有的时间开销都花在了推理/预测的过程中了。额外说明，大部分的机器学习、深度学习方法时间开销都在学习/训练的阶段，推理/预测阶段开销相对少一些。
1-3、算法流程
1---计算待推理的样本和每个训练样本的距离dist ；
2---对dist从小到大排序；
3---取出距离从小到大的k个训练样本，作为待投票的样本点；
4---统计待投票的样本点中每个类别出现的频率；
5---选择类别出现频率最大的类别作为待推理的样本的类别。
1-4、优缺点
1-4-1、优点
a、简单，易于理解，易于实现，无需估计参数，无需训练；
b、适合对稀有事件进行分类；
c、通过对k的选择可以去掉噪音数据；
d、特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。
1-4-2、缺点
a、最大的缺点：效率低下；
如果训练集有m个样本，n个特征，那么每预测一个数据，要O（m*n）
b、内存空间消耗大；
c、预测结果不具有可解释性；
d、高度数据相关。
2、实践
2-1、采用bobo老师创建简单测试用例
# 创建测试数据
raw_data_X = [[3.393533211, 2.331273381],
[3.110073483, 1.781539638],
[1.343808831, 3.368360954],
[3.582294042, 4.679179110],
[2.280362439, 2.866990263],
[7.423436942, 4.696522875],
[5.745051997, 3.533989803],
[9.172168622, 2.511101045],
[7.792783481, 3.424088941],
[7.939820817, 0.791637231]]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)
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.show() #见plt.show1
plt.show1
# 预测
x = np.array([4.593607318, 3.365731514])
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() #见plt.show2
# 计算待推理的样本和每个训练样本的距离dist
distances = [sqrt(np.sum((x_train - x)**2))
for x_train in X_train]
distances
# [1.5843867871267086,
# 2.170377050093879,
# 3.2497995507511233,
# 1.6576788379092104,
# 2.366399101096172,
# 3.1271298897519775,
# 1.1636733650877382,
# 4.657640695999352,
# 3.199708379086047,
# 4.22174207628357]
# 对dist从小到大排序，取出索引
np.argsort(distances)
# array([6, 0, 3, 1, 4, 5, 8, 2, 9, 7], dtype=int64)
nearest = np.argsort(distances)
k = 6
# 取出距离从小到大的k个训练样本，作为待投票的样本点
topK_y = [y_train[neighbor] for neighbor in nearest[:k]]
topK_y
# [1, 0, 0, 0, 0, 1]
from collections import Counter
# 统计待投票的样本点中每个类别出现的频率
votes = Counter(topK_y)
votes
# Counter({1: 2, 0: 4})
votes.most_common(1)
# [(0, 4)]
# 选择类别出现频率最大的类别作为待推理的样本的类别
predict_y = votes.most_common(1)[0][0] # 取出元素
predict_y
# 0
网友评论