简介

k-nearest neighbour, 简称KNN算法，是用来进行分类和回归的算法，这里仅介绍分类问题。在原始训练数据集的基础上，给定现有数据，经过一定的算法使现有的数据属于某个类别。

• 输入格式： T = {(x1, y1), …, (xn,yn)}，其中xi表示训练数据的特征向量，yi表示训练数据的类别，一般类别用离散的常量表示。待分类数据的特征向量为x
• 输出格式：给出输入特征向量的类别

算法

repeat1.根据距离度量的算法（例如欧氏距离），在训练数据集T中找到与x最邻近的k个点，涵盖k此k个点的邻域记为Nk(x)2.在nk(x)中根据分类决策规则决定x的类别y：y = argmax (对每个类别求和)3.在结果集中增加类别
until 所有数据均处理完毕

代码实现

import matplotlib.pyplot as pltdef loadDataSet(file):data_set = []label_set = []fr = open(file)for line in fr.readlines():line = line.strip().split(',')  # 这里默认数据使用英文，分割data_set.append([float(line[0]),float(line[1])])label_set.append([float(line[2])])return data_set, label_setdef calDis(x1, x2): # 计算两点间的欧式距离sum = 0for t1, t2 in zip(x1, x2):sum += (t1-t2) ** 2return sum ** 0.5def knn(data, data_set, labels, k):n = len(data_set)for i in range(n):dist = calDis(data, data_set[i])labels[i].append(dist)labels.sort(key = lambda x:x[1])count = {}for i in range(k):key = labels[i][0]if count[key]:count[key] += 1else:count[key] = 1sort_count = sorted(count.items(), key=lambda x:x[1], reverse=True)return sort_count[0][0]def drawPoints(data, dataSet, labels):xcord1, ycord1 = [], []xcord2, ycord2 = [], []for i in range(len(dataSet)):if labels[i][0] == 0:xcord1.append(dataSet[i][0])ycord1.append(dataSet[i][1])if labels[i][0] == 1:xcord2.append(dataSet[i][0])ycord2.append(dataSet[i][1])fig = plt.figure()ax = fig.add_subplot(111)ax.scatter(xcord1,ycord1,s=30,c='blue',marker='s',label=0)ax.scatter(xcord2,ycord2,s=30,c='green',label=1)ax.scatter(data[0],data[1],s=30,c='red',label='testdata')plt.legend(loc='upper right')plt.show()def main():dataSet, labels = loadDataSet('dataSet.txt')data = [0.67, 0.212]drawPoints(data, dataSet, labels)newlabels = knn(data, dataSet, labels, 5)print(newlabels)main()
# 结果为第0类

数据集：

0.697,0.460,1
0.774,0.376,1
0.720,0.330,1
0.634,0.264,1
0.608,0.318,1
0.556,0.215,1
0.403,0.237,1
0.481,0.149,1
0.437,0.211,1
0.525,0.186,1
0.666,0.091,0
0.639,0.161,0
0.657,0.198,0
0.593,0.042,0
0.719,0.103,0
0.671,0.196,0
0.703,0.121,0
0.614,0.116,0