进击数据挖掘十大算法(二):KNN

一、概述

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

GitHub源码:QzmVc1/Data-Mining/KNN/

参考链接:
【智源学院】30分钟KNN算法-有意思专题系列(K-Nearest Neighbor, KNN)
【菊安酱的机器学习】第1期 k-近邻算法


二、KNN算法的简单理解

图中有红色三角和蓝色方块两种类别,我们现在需要判断绿色圆点属于哪种类别。
当k=3时,绿色圆点属于红色三角这种类别;
当k=5时,绿色圆点属于蓝色方块这种类别。

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

上表就是我们已有的数据集合,也就是训练样本集。这个数据集有两个特征——打斗镜头数和接吻镜头数。除此之外,我们也知道每部电影的所属类型,即分类标签。粗略看来,接吻镜头多的就是爱情片,打斗镜头多的就是动作片。以我们多年的经验来看,这个分类还算合理。如果现在给我一部新的电影,告诉我电影中的打斗镜头和接吻镜头分别是多少,那么我可以根据你给出的信息进行判断,这部电影是属于爱情片还是动作片。

而k-近邻算法也可以像我们人一样做到这一点。但是,这仅仅是两个特征,如果把特征扩大到N个呢?我们人类还能凭经验“一眼看出”电影的所属类别吗?想想就知道这是一个非常困难的事情,但算法可以,这就是算法的魅力所在。

我们已经知道k-近邻算法的工作原理,根据特征比较,然后提取样本集中特征最相似数据(最近邻)的分类标签。 那么如何进行比较呢?比如表1中新出的电影,我们该如何判断他所属的电影类别呢?如下图所示:

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

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

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

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

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

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


三、KNN算法的Python实现

3.1 Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import csv
import random
# 读取数据集
with open('iris.csv','r') as fp:
reader = csv.DictReader(fp)
datas = [row for row in reader]

# 对数据分成训练集和测试集
random.shuffle(datas)
n = len(datas) // 3
test_set = datas[0:n]
train_set = datas[n:]

# 计算欧几里得距离
def distance(d1,d2):
res = 0
for key in ("Sepal.Length","Sepal.Width","Petal.Length","Petal.Width"):
res += (float(d1[key])-float(d2[key]))**2
return res**0.5

K = 3
def KNN(data):
# 1.计算距离
res = [
{'result':train['Species'],'distance':distance(data,train)}
for train in train_set
]

# 2.升序排序
res = sorted(res,key=lambda item:item['distance'])

# 3.取前K个数据
res2 = res[0:K]

# 4.加权平均
result = {'versicolor':0,'setosa':0}
sum = 0
for r in res2:
sum += r['distance']
for r in res2:
result[r['result']] += 1-r['distance']/sum

if result['versicolor'] > result['setosa']:
return 'versicolor'
else:
return 'setosa'


# 测试阶段
correct = 0
for test in test_set:
result1 = test['Species']
result2 = KNN(test)
if result1 == result2:
correct += 1

print("{:.2f}%".format(correct*100/len(test_set)))

3.2 数据集

1
2
3
4
5
6
7
8
ID	Sepal.Length	Sepal.Width	Petal.Length	Petal.Width	 Species
1 5.1 3.5 1.4 0.2 setosa
2 4.9 3 1.4 0.2 setosa
3 4.7 3.2 1.3 0.2 setosa
4 4.6 3.1 1.5 0.2 setosa
5 5 3.6 1.4 0.2 setosa
6 5.4 3.9 1.7 0.4 setosa
... ... ... ... ... ...

四、算法总结

KNN
算法功能 分类(核心),回归
算法类型 有监督学习 - 惰性学习,距离类模型
数据输入 包含数据标签y,且特征空间中至少包含k个训练样本(k>=1) 特征空间中各个特征的量纲需统一,若不统一则需要进行归一化处理自定义的超参数k (k>=1)
模型输出 包含数据标签y,且特征空间中至少包含k个训练样本(k>=1) 特征空间中各个特征的量纲需统一,若不统一则需要进行归一化处理自定义的超参数k (k>=1)

4.1 优点

  • 简单好用,容易理解,精度高,理论成熟,既可以用来做分类也可以用来做回归
  • 可用于数值型数据和离散型数据
  • 无数据输入假定
  • 适合对稀有事件进行分类

4.2 缺点

  • 计算复杂性高;空间复杂性高;
  • 计算量太大,所以一般数值很大的时候不用这个,但是单个样本又不能太少,否则容易发生误分。
  • 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少)
  • 可理解性比较差,无法给出数据的内在含义