【机器学习】K近邻算法的实现

一、k近邻（k-NN）算法介绍

k近邻（k-NN）算法，中文翻译为k进零算法，是机器学习中的经典算法。k-NN算法适用于初学者，因其思想简单、实现容易，且数学要求低。k-NN算法效果良好，实验中可见其有效性。

二、k近邻算法原理

1. k-NN算法基于样本相似性进行分类，认为相似的样本属于同一类别。
2. 算法步骤：计算新样本与训练集中所有样本的距离，找到最近的k个样本，根据这k个样本的类别进行投票，确定新样本的类别。
3. 距离度量通常使用欧拉距离，计算公式为各维度差值的平方和的平方根。

三、k近邻算法实现

1. 实现思路

1. 使用Python和NumPy库实现k-NN算法的具体步骤。
2. 包括数据加载、距离计算、排序、索引查找和类别投票等过程。
3. 通过示例数据集演示如何计算新样本与训练样本之间的距离，并找到最近的k个样本。
4. 使用Counter类进行类别投票，确定新样本的类别。

2. 在jupyter中实现过程

1. 设置数据集及绘制散点图

   import numpy as np
   import matplotlib.pyplot as plt
   
   # 原始数据集X
   raw_data_X = [[3.393533211, 2.331273381],
                 [3.110073483, 1.781539638],
                 [1.343808831, 3.368360954],
                 [3.582294042, 4.679179110],
                 [2.280362439, 2.866990263],
                 [7.423436942, 4.696522875],
                 [5.745051997, 3.53398803],
                 [9.172168622, 2.511101045],
                 [7.792783481, 3.424088941],
                 [7.939820817, 0.791637231]]
   # 原始标签数据集y，前五个元素是0表示一种类型，后五个元素是1表示另外一种类型
   raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
   
   # 训练集: 将原始数据集转成numpy中的array类型
   X_train = np.array(raw_data_X)
   y_train = np.array(raw_data_y)
   
   # 散点图绘制
   # X_train是一个二维数组，通常代表训练数据集的特征矩阵，每一行是一个样本，每一列是一个特征。
   # y_train是一个一维数组，代表训练数据集的标签。y_train==0是一个布尔数组，用于筛选出y_train中值为0的索引。
   # X_train[y_train==0,0]表示从X_train中选取y_train值为0的那些样本的第 1 个特征（索引为 0）的数据。
   # X_train[y_train==0,1]表示从X_train中选取y_train值为0的那些样本的第 2 个特征（索引为 1）的数据。
   # color='g'指定散点图中这些点的颜色为绿色（green）。
   plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1],color='g')
   plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1],color='r')
   plt.show()
   

   执行效果如下：
   

2. 针对新的样本x，绘制其在散点图的位置

   # 假如现在有个新的样本x，需要判断x是属于绿色还是红色的点的类型
   x = np.array([8.093607318, 3.365731514])
   # 为了查看该新的样本点所在位置，先需要将该点在坐标中查看其所在位置，也就是先在坐标中绘制出来
   plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1],color='g')
   plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1],color='r')
   plt.scatter(x[0],x[1],color='b') # 新样本位置
   plt.show() # 根据位置和knn算法，可看出来其属于红色类型
   

   执行效果如下：
   

3. knn算法的实现过程

   1. 使用for循环来求出新样本x和X_train数据集中每个样本中的欧式距离：

      # knn算法的实现过程
      # 思路：
        # 1. 求x新样本与X_train数据集中每一个样本的欧式距离
        # 2. 对距离进行排序
      from math import sqrt
      distances = []  # 定义u一个数组，用于存储x样本与X_train数据集中每个样本的欧拉距离
      for x_train in X_train:
          d = sqrt(np.sum((x_train - x)**2))  # x新样本与数据集中每个样本点的欧式距离
          distances.append(d)  # 将每个欧式距离存入数组中
      # 打印distances中的值
      distances
      

      执行结果如下：

      [4.812566907609877,
       5.229270827235305,
       6.749798999160064,
       4.6986266144110695,
       5.83460014556857,
       1.4900114024329525,
       2.354574770733321,
       1.3761132675144652,
       0.3064319992975,
       2.5786840957478887]
      

   2. 使用生成式语法来求出新样本x和X_train数据集中每个样本中的欧式距离：

      # 使用生成表达式语法，一行代码即可实现: 对于X_train数据集中的每一个x_train执行一个sqrt(np.sum((x_train - x)**2))计算
      distances = [sqrt(np.sum((x_train - x)**2)) for x_train in X_train]
      distances
      

      执行结果如下：

      [4.812566907609877,
       5.229270827235305,
       6.749798999160064,
       4.6986266144110695,
       5.83460014556857,
       1.4900114024329525,
       2.354574770733321,
       1.3761132675144652,
       0.3064319992975,
       2.5786840957478887]
      

4. 对求出的欧式距离数组进行排序

   # 2. 对求出来的欧式距离进行排序
   # argsort函数返回的是排序后的元素所在数组中的索引位置
   nearest = np.argsort(distances)  
   

5. 取k=6，计算新样本x距离最近的是什么

   # 假设k=6
   k = 6
   # 从欧式距离数组中取前6个点所对应的y_train中的值
   topK_y = [ y_train[i] for i in nearest[:k]]
   # 打印topK_y的结果为：[1, 1, 1, 1, 1, 0]，而y_train是array([0, 0, 0, 0, 0, 1, 1, 1, 1, 1])
   

6. 词频统计与投票过程

   # 做一次词频统计，即计算topK_y中不同值的元素在数组中出现的次数
   from collections import Counter
   Counter(topK_y) # 打印Counter的结果为：({1: 5, 0: 1})，表示数组中1出现的次数是5次，0出现1次
   # 投票过程
   votes = Counter(topK_y)
   # 找到票数最多的前几种元素，如找到票数最多的前2种元素
   votes.most_common(2)  # 打印结果为[(1, 5), (0, 1)]
   # 这里我们需要找到票数最多的是哪种元素
   votes.most_common(1) # 打印结果为：[(1, 5)]，是一个数组，数组中存放的是tuple类型的元素，前面1表示标签，5表示次数
   

7. 获取预测值

   # 这里我们只关心是新样本x属于哪种类型，因此只需要将标签找到
   votes.most_common(1)[0][0]
   # 其实这里就是预测值
   predict_y = votes.most_common(1)[0][0]
   predict_y
   

   执行结果：1，表示新样本x的类型可能是y_train中为1的类型。

四、k近邻算法的封装与优点

1. KNN代码封装成函数

在PyCharm中将代码写成如下函数，并保存为一个文件取名为KNN_Classification.py:

import numpy as np
from math import sqrt
from collections import Counter


def kNN_classify(k, X_train, y_train, x):
    # 第一个assert语句检查k的值是否在有效范围内（至少为 1 且不超过训练样本的数量）
    assert 1 <= k <= X_train.shape[0], "k must be valid"
    # 第二个assert语句检查训练特征矩阵X_train的样本数量是否与标签数组y_train的长度相等。
    assert X_train.shape[0] == y_train.shape[0], \
        "the size of X_train must equal to the size of y_train"
    # 第三个assert语句检查待预测样本x的特征数量是否与训练样本的特征数量一致。
    assert X_train.shape[1] == x.shape[0], \
        "the feature number of x must be equal to X_train"

    # 计算距离，使用列表推导式计算待预测样本x与训练集中每个样本x_train之间的欧几里得距离，将结果存储在distances列表中。
    distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
    
    # 找到最近邻，使用np.argsort函数对distances列表进行排序，并返回排序后的索引，nearest中存储的是按距离从小到大排列的训练样本的索引。
    nearest = np.argsort(distances)

    # 选取前 k 个最近邻的标签，使用列表推导式从y_train中选取距离最近的k个样本的标签，存储在topK_y列表中。
    topK_y = [y_train[i] for i in nearest[:k]]

    # 统计标签出现次数并返回预测结果，使用Counter统计topK_y中各个标签出现的次数。
    votes = Counter(topK_y)

    # votes.most_common(1)返回出现次数最多的元素及其出现次数的列表，[0][0]则提取出出现次数最多的标签，作为对样本x的预测类别返回。
    predict_y = votes.most_common(1)[0][0]

    return predict_y

2. 在jupyter中调用并执行

1. 准备数据集和新样本x

   import numpy as np
   import matplotlib.pyplot as plt
   
   # 原始数据集X
   raw_data_X = [[3.393533211, 2.331273381],
                 [3.110073483, 1.781539638],
                 [1.343808831, 3.368360954],
                 [3.582294042, 4.679179110],
                 [2.280362439, 2.866990263],
                 [7.423436942, 4.696522875],
                 [5.745051997, 3.53398803],
                 [9.172168622, 2.511101045],
                 [7.792783481, 3.424088941],
                 [7.939820817, 0.791637231]]
   # 原始标签数据集y，前五个元素是0表示一种类型，后五个元素是1表示另外一种类型
   raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
   
   # 训练集: 将原始数据集转成numpy中的array类型
   X_train = np.array(raw_data_X)
   y_train = np.array(raw_data_y)
   
   # 新样本x
   x = np.array([8.093607318, 3.365731514])
   

2. 使用魔法命令导入KNN_Classification.py

   %run D:/JupyterNoteBookWorkspace/helloml/KNN_Classification.py
   

3. 运行并得到预测结果

   predict_y = kNN_classify(6,X_train,y_train,x)
   predict_y
   

   执行结果为：1
   

3. 封装的好处

1. 将k-NN算法进行封装，提高代码的可重用性和可读性。
2. 封装后的算法更易于使用和维护，同时保留了算法的核心思想。
3. 封装的优点包括简化代码、提高效率、便于调试和扩展。