概述
存在一个样本数据集合(训练样本集),并且每个样本都有确定的标签,即样本与标签之间存在一一对应的关系。输入没有标签的样本(测试样本),将测试样本的数据与训练样本集中的数据进行比较,然后提取训练样本集中与测试样本最相似(最近邻)的分类标签,选择提取标签中的前K个标签(可能会重复),在K个标签集中出现次数最多的标签,作为测试样本的分类。
简单举例
举个简单的例子,二维空间中存在两类样本(训练样本)A、B,那么当给出一个样本(测试样本)C时,我们怎样判断C是属于哪一类呢?
上图中,存在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 | # 导入numpy库 |
然后,创建训练样本数据
1 | # 创建训练数据 |
上述代码定义了一个函数 get_train_data ,用来创建我们想用来训练的7个样本数据集:group,以及每个样本相对应的标签数据集:labels。
每个样本包括两个数据:x 坐标和 y 坐标。标签数据集则包含每个样本的分类名称。样本与其标签存在着一一对应的关系,比如样本数据集中的第二个样本:[2.00,3.00],便对应着标签数据集中的第二个标签 ’A‘ ,意味着样本 [2.00,3.00] 属于分类 A。
1 | # 获取样本数据集以及标签数据集 |
我们用两个变量 group , labels 来保存我们创建样本数据集函数的返回值,即: group 保存样本数据集,labels 保存标签数据集。
现在,我们来创建我们的分类函数。
1 | # 分类函数 |
下面,我们来详细解释上述分类函数的欧式距离计算方式。
首先,函数共有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 | # 测试样本 |
源码链接:
K近邻算法——进阶
当然,真正用到K近邻算法的情形并不会如上面的例子般简单,但是上例却已经能够很好的表达出K近邻算法的核心思想。接下来,我们将探讨K近邻算法更复杂的运用。