K近邻算法代码实现

前面学习了K近邻算法的基本原理，本节课将学习用Python来实现K近邻算法。

数据准备

将样本数据的特征用X表示，标签用y表示，未知样本的特征用X_test表示，代码如下。

import numpy as np

X=np.array([[5,57],[3,65],[6,21],[45,9],[21,5],[54,11],[39,31]])
y=np.array(['动作片','动作片','动作片','喜剧片','喜剧片','喜剧片','喜剧片'])
X_test=[23,17]

距离计算

接着计算未知样本和各已知样本的记录，代码如下。

diff=np.tile(X_test,(len(X),1))-X
#计算差值的平方和
sqDiff = diff**2
sqDistances = sqDiff.sum(axis=1)
#开根号
distances = sqDistances**0.5
print(distances)

运行结果：

[43.8634244  52.         17.4642492  23.40939982 12.16552506 31.57530681
 21.26029163]

对距离进行排序

将计算出来的距离按照升序排列，代码如下。

sort_distance=distances.argsort()
sort_distance

说明：这里使用了argsort函数，该函数返回的是距离的索引。

选择距离最近的K个点

接着，按照K近邻算法的原理，假定K=3，选择距离未知样本距离最近的三个样本点，并统计这三个样本的标签数量，即y=0出现了多少次，y=1出现了多少次，将结果放在一个字典中。

k=3
count={}

for i in range(k):
    sort_label=y[sort_distance[i]]
    count[sort_label]=count.get(sort_label,0)+1

print(count)

运行结果：

{'喜剧片': 2, '动作片': 1}

从运行结果看出，这三个样本中，有两个是喜剧片，有一个是动作片。
接着，还需要对这个count结果进行降序排列，即出现次数最多的标签应该放在第一个位置，方便获取结果。
说明：以上count虽然已经是降序排列，只是一个巧合现象，如果是其他数据，结果未必就是降序排列。

#对count进行排序
import operator

#operator.itemgetter函数获取对象指定索引的值，这里表示按照字典的值排序
sort_count=sorted(count.items(),key=operator.itemgetter(1),reverse=True)
print(sort_count)

运行结果：

[('喜剧片', 2), ('动作片', 1)]

从以上运行结果可以看到，在K=3的情况下，有两部是喜剧片，一部是动作片，因此我们判定未知电影是喜剧片。

定义knn函数

以上为了方便大家理解，故分步讲解，下面将以上过程合在一起定义成一个函数，方便以后调用。

#将以上过程定义成一个函数
def knn(trainData,labels,testData,k):
    diff=np.tile(testData,(len(trainData),1))-X
    #计算距离
    sqDiff = diff**2
    sqDistances = sqDiff.sum(axis=1)
    distances = sqDistances**0.5
    #对距离进行排序
    sort_distance=distances.argsort()
    #选择距离最近的k个点
    count={}

    for i in range(k):
        sort_label=labels[sort_distance[i]]
        count[sort_label]=count.get(sort_label,0)+1

    sort_count=sorted(count.items(),key=operator.itemgetter(1),reverse=True)
    return sort_count[0][0]

调用函数：

knn(X,y,X_test,3)

运行结果：

'喜剧片'

好了，我们学会了如何用Python实现K近邻算法。