岁虚山

行由不得,反求诸己

0%

K近邻算法

概述

存在一个样本数据集合(训练样本集),并且每个样本都有确定的标签,即样本与标签之间存在一一对应的关系。输入没有标签的样本(测试样本),将测试样本的数据与训练样本集中的数据进行比较,然后提取训练样本集中与测试样本最相似(最近邻)的分类标签,选择提取标签中的前K个标签(可能会重复),在K个标签集中出现次数最多的标签,作为测试样本的分类。

简单举例

举个简单的例子,二维空间中存在两类样本(训练样本)A、B,那么当给出一个样本(测试样本)C时,我们怎样判断C是属于哪一类呢?

Set

上图中,存在7个训练样本(A1,A2,A3,B1,B2,B3,B4),1个测试样本(C)。

训练样本共分为两类:

A:A1,A2,A3

B:B1,B2,B3,B4

当我们想要确定测试样本C的分类时,K近邻算法的思想是:

1.计算训练样本集合中所有样本与C点的距离;

2.对训练样本集合中所有样本与C点的距离排序;

3.找出与C点距离最近的的前K个训练样本;

4.在第3步找出的前K个样本中出现最多的分类;

5.确定C的分类。

我们按照K近邻算法来对C点进行分类:

1.计算训练样本集合中所有样本与C点的距离

C —> A1:1.41

C —> A2:2.00

C —> A3:1.00

C —> B1:1.00

C —> B2:3.00

C —> B3:3.16

C —> B4:2.24

2.对训练样本集合中所有样本与C点的距离排序

C —> A3:1.00

C —> B1:1.00

C —> A1:1.41

C —> A2:2.00

C —> B4:2.24

C —> B2:3.00

C —> B3:3.16

3.找出与C点距离最近的的前K个训练样本,我们取K=4

C —> A3:1.00

C —> B1:1.00

C —> A1:1.41

C —> A2:2.00

4.在第3步找出的前K个样本中出现最多的分类

我们可以明显看出,按照距离排序吼的前K(K=4)个训练样本中,A类出现了3次,B类出现了1次,记作:

A:3

B:1

5.确定C的分类

由第四步得到的结果,我们将测试样本C归为A类。

代码实现

接下来就按上例来用Python代码实现。

首先,导入所需的库:

1
2
3
4
# 导入numpy库
import numpy as np
# 导入operator库
import operator

然后,创建训练样本数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 创建训练数据
def get_train_data():
# 创建训练样本集
group=np.array([
[1.00,2.00],
[2.00,3.00],
[2.00,2.00],
[3.00,1.00],
[5.00,1.00],
[5.00,2.00],
[4.00,0.00]])
# 创建样本标签集
labels=['A','A','A','B','B','B','B']
return group,labels

上述代码定义了一个函数 get_train_data ,用来创建我们想用来训练的7个样本数据集:group,以及每个样本相对应的标签数据集:labels。

每个样本包括两个数据:x 坐标和 y 坐标。标签数据集则包含每个样本的分类名称。样本与其标签存在着一一对应的关系,比如样本数据集中的第二个样本:[2.00,3.00],便对应着标签数据集中的第二个标签 ’A‘ ,意味着样本 [2.00,3.00] 属于分类 A。

1
2
# 获取样本数据集以及标签数据集
group,labels=create_train_data()

我们用两个变量 group , labels 来保存我们创建样本数据集函数的返回值,即: group 保存样本数据集,labels 保存标签数据集。

现在,我们来创建我们的分类函数。

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
# 分类函数
"""
in_data:输入的测试点
train_data:用于训练的样本数据集
train_labels:用于训练的标签数据集
k:截取相似样本个数
"""
def classify(in_data,train_data,train_labels,k):
# 计算样本个数
train_data_size=train_data.shape[0]

# (以下四行)计算距离
diff_mat=np.tile(in_data,(train_data_size,1))-train_data
sq_diff_mat=diff_mat**2
sq_distances=sq_diff_mat.sum(axis=1)
distances=sq_distances**0.5

# 提取对距离进行降序排序后的索引
sorted_distance_indexes=distances.argsort()
# 类别计数
class_count={}
# 从 distances 中选择距离最小的 k 个点
for i in range(k):
vote_lable=labels[sorted_distance_indexes[i]]
class_count[vote_lable]=class_count.get(vote_lable,0)+1

#将类别计数器按其类数个数排序
sorted_class_count=sorted(class_count.items(),key=operator.itemgetter(1),reverse=True)
# 返回计数最多的类别
return sorted_class_count[0][0]

下面,我们来详细解释上述分类函数的欧式距离计算方式。

首先,函数共有4个参数:

in_data: 输入的测试点
train_data: 用于训练的样本数据集
train_labels: 用于训练的标签数据集
k: 截取相似样本个数

我们假设用创建训练样本数据集函数得到的样本数据:

group,labels=create_train_data()

来进行分类,用 测试样本

C=[2.00,1.00]

来用作测试数据。取 K=4 ,则函数所得到的参数如下:

in_data=[2.00,1.00]

train_data=[[1. 2.]
[2. 3.]
[2. 2.]
[3. 1.]
[5. 1.]
[5. 2.]
[4. 0.]]

train_labels=[‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’, ‘B’]

k=4

我们先计算训练样本的个数,将其保存在变量 train_data_size 中,此时:

train_data_size=7

我们再看:

diff_mat=np.tile(in_data,(train_data_size,1))-train_data

我们知道, in_data 是一个一行两列的矩阵,in_data=[2.00,1.00],虽然我们可以用 for 循环的方式,来计算每个训练样本与测试样本的欧式距离,但 for 循环的效率相当低下,因此我们采用效率更高的计算方法:矩阵操作。

首先使用 np.tile() 函数将 测试样本in_data 扩展为与测试样本相同大小的矩阵(7行2列)

再用得到的矩阵与训练样本矩阵作减法运算,结果保存在 diff_mat 矩阵中,具体过程如下:

得到 diff_mat 矩阵后,计算欧式距离:

sq_diff_mat=diff_mat**2

当然,此处的平方操作并不是严格意义上的矩阵(乘法)运算,而是矩阵内各元素求平方。

接下来,我们将 sq_diff_mat 矩阵按行求和得到 sq_distances 矩阵:

sq_distances=sq_diff_mat.sum(axis=1)

然后,再对 sq_distances 矩阵按行开平方得到 distances 矩阵:

接下来,将所得到的距离矩阵 distances 按升序排序后的索引保存在 sorted_distance_indexes 中:

sorted_distance_indexes=distances.argsort()

结果如下:

sorted_distance_indexes=[2 3 0 1 6 4 5]

定义一个类别计数器:

class_count={}

用 for 循环来记录测试样本与训练样本的最小的前 K 个样本的类别出现的次数:

for i in range(k):
  vote_lable=labels[sorted_distance_indexes[i]]
  class_count[vote_lable]=class_count.get(vote_lable,0)+1

得到的结果如下:

class_count={‘A’: 3, ‘B’: 1}

最后,将 class_cont 按值排序后,返回出现次数最高的分类(A),作为对 C 的分类。

调用:

1
2
3
4
# 测试样本
C=[2.00,1.00]
# 获取分类
result=classify(C,group,labels,4)

源码链接:

https://github.com/xudapengarh/Machine-Learning/tree/master/K%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95/K%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95

K近邻算法——进阶

当然,真正用到K近邻算法的情形并不会如上面的例子般简单,但是上例却已经能够很好的表达出K近邻算法的核心思想。接下来,我们将探讨K近邻算法更复杂的运用。

-------------本文结束 感谢阅读-------------
打赏一包辣条