k-近邻算法的Python实现

一、概述

k-近邻算法（k-Nearest Neighbour algorithm），又称为KNN算法，是数据挖掘技术中原理最简单的算法。KNN的工作原理：给定一个已知标签类别的训练数据集，输入没有标签的新数据后，在训练数据集中找到与新数据最邻近的k个实例，如果这k个实例的多数属于某个类别，那么新数据就属于这个类别。可以简单理解为：由那些离X最近的k个点来投票决定X归为哪一类。

图1中有红色三角和蓝色方块两种类别，我们现在需要判断绿色圆点属于哪种类别

当k=3时，绿色圆点属于红色三角这种类别；

当k=5时，绿色圆点属于蓝色方块这种类别。

举个简单的例子，可以用k-近邻算法分类一个电影是爱情片还是动作片。（打斗镜头和接吻镜头数量为虚构）

我们可以从散点图中大致推断，这个未知电影有可能是爱情片，因为看起来距离已知的三个爱情片更近一点。k-近邻算法是用什么方法进行判断呢？没错，就是距离度量。这个电影分类例子中有两个特征，也就是在二维平面中计算两点之间的距离，就可以用我们高中学过的距离计算公式：

如果是多个特征扩展到N维空间，怎么计算？没错，我们可以使用欧氏距离（也称欧几里得度量），如下所示

通过计算可以得到训练集中所有电影与未知电影的距离，如表2所示

通过表2的计算结果，我们可以知道绿点标记的电影到爱情片《后来的我们》距离最近，为29.1。如果仅仅根据这个结果，判定绿点电影的类别为爱情片，这个算法叫做最近邻算法，而非k-近邻算法。k-近邻算法步骤如下：

(1)计算已知类别数据集中的点与当前点之间的距离；

(2)按照距离递增次序排序；

(3)选取与当前点距离最小的k个点；

(4)确定前k个点所在类别的出现频率；

(5)返回前k个点出现频率最高的类别作为当前点的预测类别。

比如，现在K=4，那么在这个电影例子中，把距离按照升序排列，距离绿点电影最近的前4个的电影分别是《后来的我们》、《前任3》、《无问西东》和《红海行动》，这四部电影的类别统计为爱情片:动作片=3:1，出现频率最高的类别为爱情片，所以在k=4时，绿点电影的类别为爱情片。这个判别过程就是k-近邻算法。

二、k-近邻算法的Python实现

在了解k-近邻算法的原理及实施步骤之后，我们用python将这些过程实现。

1.1构建已经分类好的原始数据集为了方便验证，这里使用python的字典dict构建数据集，然后再将其转化成DataFrame格式。

import pandas as pd

rowdata = {'电影名称': ['无问东西', '后来的我们', '前任3', '红海行动', '唐人街探案', '战狼'],
           '打斗镜头': [1, 5, 12, 108, 112, 115],
           '接吻镜头': [101, 89, 97, 5, 9, 8],
           '电影类型': ['爱情片', '爱情片', '爱情片', '动作片', '动作片', '动作片']}
movie_data = pd.DataFrame(rowdata)
print(movie_data)
'''
电影名称  打斗镜头  接吻镜头 电影类型
0   无问东西     1   101  爱情片
1  后来的我们     5    89  爱情片
2    前任3    12    97  爱情片
3   红海行动   108     5  动作片
4  唐人街探案   112     9  动作片
5     战狼   115     8  动作片
'''

“”“使用{}创建字典”""

scores = {'张三': 100}
print(scores)  # {'张三': 100}

2.计算已知类别数据集中的点与当前点之间的距离

new_data = [24, 67]
dist = list((((movie_data.iloc[:6, 1:3] - new_data) ** 2).sum(1)) ** 0.5)
print(dist)

'''创建列表的第二种方式,使用内置函数list()'''

lst2 = list(['hello', 'world', 98])
print(lst2)  # ['hello', 'world', 98]

列相加所以sum（1）

3.将距离升序排列，然后选取距离最小的k个点

dist_l = pd.DataFrame({'dist': dist, 'labels': (movie_data.iloc[:6, 3])})
print(dist_l)
k = 4;
dr = dist_l.sort_values(by='dist')[:4]
print(dr)

4.确定前k个点所在类别的出现频率

re = dr.loc[:, 'labels'].value_counts()
print(re);

5.选择频率最高的类别作为当前点的预测类别

result = []
result.append(re.index[0])
print(result)#[爱情片]