本文共 1983 字，大约阅读时间需要 6 分钟。

概述

k-近邻算法（k-Nearest Neighbour algorithm），又称为KNN算法，是数据挖掘技术中原理最简单的算法。

KNN 的工作原理：给定一个已知标签类别的训练数据集，输入没有标签的新数据后，在训练数据集中找到与新数据最接近的k个实例，如果这k个实例中的多数属于某个类别，那么新数据就属于这个类别。可以简单理解为：由那些离X最近的k个点来投票决定X归为哪一类。

问题

举个简单的例子，我们可以用k-近邻算法分类一个电影是爱情片还是动作片。

下表记录了六部影片中的打斗次数及接吻次数：

电影名称	打斗镜头	接吻镜头	电影类型
无问西东	1	101	爱情片
后来的我们	5	89	爱情片
前任3	12	97	爱情片
红海行动	108	5	动作片
唐人街探案	112	9	动作片
战狼2	115	8	动作片

现在有一部新电影，其中有24个打斗镜头，67个接吻镜头。我们可以用k-近邻算法来判断这部电影是属于爱情片还是动作片。

解题步骤

我们可以将每部电影画到一张图上：

我们可以从散点图中大致推断，这个未知电影有可能是爱情片，因为看起来距离已知的三个爱情片更近一点。k-近邻算法使用距离度量。这个电影分类例子中有两个特征，也就是在二维平面中计算两点之间的距离，就可以用我们高中学过的距离计算公式： $$|AB|=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$$ 如果这里有是多个特征扩展到N维空间的话，我们可以使用欧氏距离（也称欧几里得度量），如下所示： $$dist(\mathbf{x},\mathbf{y})=\sqrt{\sum _{i=1}^N(x_i-y_i{)}^2}$$ 通过计算可以得到训练集中所有电影与未知电影的距离，如下表所示：

电影名称	与未知电影的距离
无问西东	41.0
后来的我们	29.1
前任3	32.3
红海行动	104.4
唐人街探案	105.4
战狼2	108.5

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

• (1) 计算已知类别数据集中的点与当前点之间的距离；
• (2) 按照距离递增次序排序；
• (3) 选取与当前点距离最小的k个点；
• (4) 确定前k个点所在类别的出现频率；
• (5) 返回前k个点出现频率最高的类别作为当前点的预测类别。

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

python实现

import pandas as pd# 1.构建已经分类好的原始数据集rowdata={   '电影名称':['无问西东','后来的我们','前任3','红海行动','唐人街探案','战狼2'],         '打斗镜头':[1,5,12,108,112,115],         '接吻镜头':[101,89,97,5,9,8],         '电影类型':['爱情片','爱情片','爱情片','动作片','动作片','动作片']}movie_data= pd.DataFrame(rowdata)# 2.计算已知类别数据集中的点与当前点之间的距离new_data = [24,67] dist = list((((movie_data.iloc[:6,1:3]-new_data)**2).sum(1))**0.5)  # sum(1)：对列求和# 3.将距离升序排列，然后选取距离最小的k个点dist_l = pd.DataFrame({   'dist': dist, 'labels': (movie_data.iloc[:6, 3])}) dr = dist_l.sort_values(by = 'dist')[: 4] # 4.确定前k个点所在类别的出现频率re = dr.loc[:,'labels'].value_counts() # 5.选择频率最高的类别作为当前点的预测类别result = [] result.append(re.index[0]) print(result)