K近邻算法

概述

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

简单举例

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

上图中，存在7个训练样本（A₁，A₂，A₃，B₁，B₂，B₃，B₄），1个测试样本（C）。

训练样本共分为两类：

A：A₁，A₂，A₃；

B：B₁，B₂，B₃，B₄；

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

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

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

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

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

5.确定C的分类。

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

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

C —> A₁：1.41

C —> A₂：2.00

C —> A₃：1.00

C —> B₁：1.00

C —> B₂：3.00

C —> B₃：3.16

C —> B₄：2.24

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

C —> A₃：1.00

C —> B₁：1.00

C —> A₁：1.41

C —> A₂：2.00

C —> B₄：2.24

C —> B₂：3.00

C —> B₃：3.16

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

C —> A₃：1.00

C —> B₁：1.00

C —> A₁：1.41

C —> A₂：2.00

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

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

A：3

B：1

5.确定C的分类

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

代码实现

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

首先，导入所需的库：

# 导入numpy库
import numpy as np
# 导入operator库
import operator

然后，创建训练样本数据

# 创建训练数据
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 保存标签数据集。

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

# 分类函数
"""
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列）

$np.tile(in\_data,(tra\_data\_size,1))= \left[ \begin{matrix} 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ \end{matrix} \right]$

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

$diff\_mat= \left[ \begin{matrix} 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ 2.00&1.00\\ \end{matrix} \right] - \left[ \begin{matrix} 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\\ \end{matrix} \right] = \left[ \begin{matrix} 1.00&-1.00\\ 0.00&-1.00\\ 0.00&-2.00\\ -1.00&0.00\\ -3.00&0.00\\ -3.00&-1.00\\ -2.00&1.00\\ \end{matrix} \right]$

得到 diff_mat 矩阵后，计算欧式距离：

sq_diff_mat=diff_mat**2
$sq\_diff\_mat= \left[ \begin{matrix} 1.00&-1.00\\ 0.00&-1.00\\ 0.00&-2.00\\ -1.00&0.00\\ -3.00&0.00\\ -3.00&-1.00\\ -2.00&1.00\\ \end{matrix} \right] ^2 = \left[ \begin{matrix} 1.00&1.00\\ 0.00&1.00\\ 0.00&4.00\\ 1.00&0.00\\ 9.00&0.00\\ 9.00&1.00\\ 4.00&1.00\\ \end{matrix} \right]$
当然，此处的平方操作并不是严格意义上的矩阵（乘法）运算，而是矩阵内各元素求平方。

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

sq_distances=sq_diff_mat.sum(axis=1)
$sq\_distances= sum( \left[ \begin{matrix} 1.00&1.00\\ 0.00&1.00\\ 0.00&4.00\\ 1.00&0.00\\ 9.00&0.00\\ 9.00&1.00\\ 4.00&1.00\\ \end{matrix} \right] ) = \left[ \begin{matrix} 2.00\\ 1.00\\ 4.00\\ 1.00\\ 9.00\\ 10.00\\ 5.00\\ \end{matrix} \right]$

然后，再对 sq_distances 矩阵按行开平方得到 distances 矩阵：

$distances= \left[ \begin{matrix} 2.00\\ 1.00\\ 4.00\\ 1.00\\ 9.00\\ 10.00\\ 5.00\\ \end{matrix} \right] ^{0.5} = \left[ \begin{matrix} 1.41\\ 1.00\\ 2.00\\ 1.00\\ 3.00\\ 3.16\\ 2.24\\ \end{matrix} \right]$

接下来，将所得到的距离矩阵 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 的分类。

调用：

# 测试样本
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近邻算法更复杂的运用。