算法原理

KNN算法(k-near-neighbours algorithm)可用来将样本分类，也可以用来预测样本走向。我们本次先说归类。

借鉴一个图片，

img

通俗地讲，图中绿色的是未知点，红色和蓝色是两个标签，已经分好类了，我们要判断绿色属于红色类还是蓝色类。于是我们选择了参数K=3，从绿色的点旁边找三个距离最近的点，然后计算红色点和蓝色点的占比，哪个占比大，就属于哪一类。

K的选取很重要，因为K很小容易出现过拟合，K很大，在回归问题中，如果样本点呈现二次函数走势，取很多很远的样本纳入考虑，会使得走势不准，也就是欠拟合。

所以我们的算法流程如下

1
2
3
计算待分类点与已知类别点之间的距离
将所有点按照距离递增次序排序，选择参数K，取距离待定点最近的K个点
计算K个点中不同类别的占比，占比最大的类，即为结果。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#我们假设dataset是二维数组，每个向量之中两个分量，第一个表示类别比如红色，第二个表示值。
int a#待定点
dataset.reshape(-1, 2)#也就是修改成列向量的形式。
for i in range(dataset):
	to_each_sample_distance[i][1] = distance(a, dataset(i)(1))
	to_each_sample_distance[i][0] = dataset(i)(0)#把类别也归进去
k = 5
for i in range(to_each_sample_distance):
	for j in i:
		if(to_each_sample_distance[j][1] > to_each_sample_distance[j+1][1]):
			swap(to_each_sample_distance[j], to_each_sample_distance[j+1])用冒泡排序把小的放前面
count = [[0, 0] * 100]#因为最多也不会有很多类，每个类对应其个数
for i in range(5):
	if to_each_sample_distance[i][0]:
		count[i][0] = to_each_sample_distance[i][0]
		count[i][1]++#个数+1
count.reshape(-1, 2)#转化为列向量
max = [0, 0]
for i in range(count)-1:
	if count[i][1] > count[i+1][1]
		max[1] = count[i][1]
		max[0] = count[i][0]
print(max[0])#即为我们最后判定的类。