机器学习之 k 近邻算法

机器学习之 k 近邻算法

kNN algorithm

什么是 k 近邻算法

k 近邻(k-Nearest Neighbor,kNN)是机器学习中相对简单且容易理解的算法,是分类数据最简单有效的算法,它基于实例学习,我们必须用最真实的样本数据对模型进行训练,以便预测出的结果更具参考意义。

简单地说,k 近邻算法采用测量不同特征值之间的距离方法进行分类。这句话简单也不简单。更通俗易懂的理解,所谓“物以类聚,人以群分”,kNN 认为彼此相隔最近的点为一类。周围的对象是什么类别,我就是什么类别。如果你的朋友都开法拉利、保时捷等跑车,那么在 kNN 眼你,你也是有钱人,也开豪车。

算法实现

本文不打算用代码实现一个 k 近邻算法,感兴趣的可以查阅资料研究其实现,但我们必须知道算法的实现步骤。

对未知类型的数据集中的每个点依次执行如下操作:

  1. 计算已知类别数据集中的点与当前点之间的距离;
  2. 按距离递增次序排序;
  3. 选取与当前点距离最小的 k 个点;
  4. 确认前 k 个点出现频率最高的类别作为当前点的预测分类;

接下来,举个栗子带大家更好的理解 kNN 算法。如图,有黄色的管理人才,深蓝色的架构师,以及未知的天蓝色。

kNN Sample

当我们需要对员工进行技术和管理两个培养方向分类时,可能会考虑到他们的情商、沟通、技能、协作、远见、解决问题等能力。由于人类大脑的限制,我们只能处理三维以下的事务,这里只列举两个特征“情商”和“技能”评分,假设情商分高可作为管理人才来培养,技能分高作为架构师人才来培养。

我们拿到了七个样本数据,每一个样本带有情商和技能特征,以及对应的标签,他们分布在图中的数据如下:

技能 情商 培养方向
43 92 管理
60 88 管理
69 80 架构师
66 78 管理
88 50 架构师
80 91 管理
96 35 架构师
68 80

现在的需求是通过天蓝色的特征值预测他更适合的培养方向,按照 kNN 算法的实现步骤,计算出天蓝色特征与样本集的距离。计算二维平面上两点 a(x1,y1) 与 b(x2,y2) 间的欧氏距离
Euclidean Distance

按距离升序排序之后结果如下:

技能 情商 欧式距离↑ 培养方向
69 80 1.0 架构师
66 78 2.83 管理
60 88 11.31 管理
80 91 16.27 管理
43 92 27.73 管理
88 50 36.06 架构师
96 35 53.0 架构师

我们得到了预测数据与各个样本间的距离,并按递增排好序。现假设 k = 3,对应的类别分别是“架构师”、“管理”、“管理”,按照算法实现的第 4 步,前 3 个点出现频率最高的类别是“管理”。那么,天蓝色的培养方向应该偏管理。

实例中 k 值取多少没有定论,如果实例中 k = 1 或 k = 2,那么结果未必是最准确的,这是一个经验值。通常 k 是 3 ≤ k < 20 的整数,并且是奇数,这样避免出现相同票数。

回过头来看数据分布图,以你为中心画圆,其中圆 c1 也就是 k = 1,距你最近的是“架构师”,圆 c2 则是当 k = 3 的时候,其中三个“管理”,少数服从多数,统计最多的类别依然是“管理”。

k 近邻算法优缺点

优点:精度高、对异常值不敏感、无数据输入假定。
缺点:kNN 必须保存全部数据集,会占用大量的存储空间,所以空间负责度高;kNN 必须对数据集中的每个数据计算距离值,实际使用时非常耗时,所以计算复杂度高

scikit-learn 简单实现

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
# -*- coding: utf-8 -*-

# 导入 kNN 分类器
from sklearn.neighbors import KNeighborsClassifier
import numpy as np

# 实例化一个 k 为 3 的 kNN 分类器,默认为 5
clf = KNeighborsClassifier(n_neighbors = 3)

# 样本和测试数据集
sample = np.array([
[43,92,"管理"],
[60,88,"管理"],
[69,80,"架构师"],
[66,78,"管理"],
[88,50,"架构师"],
[80,91,"管理"],
[96,35,"架构师"],
[68,80,"?"]])

# 提取样本特征和标签进行训练
X_train, y_train = sample[:-1, :-1], sample[:7, -1:].ravel()
clf.fit(X_train, y_train)

# 提取测试集特征进行预测
X_test = sample[-1:, :-1]
result = clf.predict(X_test)

print result[0]

执行输出:

1
2
3
4
5
6
[Running] python /Users/Fechin/work/ideaproj/td/test-ml/sklearn/knn2.py

--------------------
管理

[Done] exited with code=0 in 0.834598 seconds