KNN算法

K最近邻算法

简述

K 最近邻算法是一种懒惰学习方法，其基于已有数据进行分类，需要确认五个信息：

  1. 已有数据的数据集 $T = {(x_1,y_1),(x_2,y_2),(x_3,y_3)···(x_N,y_N)}$
  2. 采用的距离度量$D(·)$
  3. 邻近点的个数K
  4. 待分类的实例点的特征向量 $x$
  5. 邻近算法的分类决策机制（如：多数表决法、权重法）

KNN算法的过程

KNN算法的过程主要分为3个步骤：

  1. 计算实例点到所有训练实例点距离$D$，时间复杂度为$O(Np)$

  2. 选取K个离实例点最近的邻近点，构成集合$N_k(x)$,此时要选取最小的K个值需要对集合$D$进行排序，此时时间复杂度根据排序算法计算

  3. 根据集合$N_k(x)$ 中点对应的标签，对输入的新实例进行分类决策（如：投票表决法，若该点邻近的k个点均为+实例，则该点被判定为+实例）

    image-20230709164655244

距离度量

常用距离度量：

  1. 欧式距离image-20230709165014759
  2. 曼哈顿距离

image-20230709165031755

​ 3.$L_∞$ norm distance

image-20230709165047123

参数选择与分类方法

在K最近邻算法中，重点需要设置的参数就是K，K会影响模型的泛化性，不同的K值预测结果也会不同；K很小时，模型对数据比较敏感，在现实生活中，拥有很多的“噪音”，都会对分类的结果产生影响，K很大时，收到“噪声”的影响的可能性越大；因此为了能够寻找到一个平衡，对K值的选择需要十分的谨慎

image-20230709165448818

  1. 多数表决法

    这个方法与投票过程类似，在 K 个最近邻中找出样本数量最多的那个类别作为新数据的类别（如二分类问题：圈定K个最小值构成一个集合，在这个集合内为正例的概率大于为负例，则将该实例点分类为正例；为了尽可能避免正例等于负例的情况导致分类方法失灵，我们选择K为一个奇数）

  2. 权重法

    权重法会根据近邻点和待分类点之间的距离来为近邻点分配一个权重 w，然后计算每个类别的权重来进行分类。这种分类方法称作加权 K 最近邻算法。如何对每个实例点计算权重呢？

    • 1范数和2范数求权重:：$w_j = \frac{1}{d_1(x_i,x_j)}$ 或 $w_j = \frac{1}{d_2(x_i,x_j)}$
      • $d_1(x_i,x_j) = ||x_i-x_j||_1$
      • $d_2(x_i,x_j) = ||x_i-x_j||_2$
    • 高斯函数求权重
      • $w_j = exp(-λ||x_i-x_j||^2_2)$

KNN算法复杂度

KNN算法的时间开销主要由两个部分组成：计算数据点之间距离以及排序算法image-20230709173413325

编程实现

  1. 多数投票法
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
31
32
33
34
35
36
37
38
39
import numpy as np
from sklearn.datasets import make_classification
import matplotlib.pyplot as plt

# 生 成 二 分 类 的 数 据
N = 200
p = 3
x, y = make_classification(N, p, n_informative=p, n_redundant=0, n_classes=2)
# 将 数 据 划 分 为 训 练 集 和 测 试 集； 对 于K近 邻 算 法， 训 练 集 并 不 会 用来 训 练， 只 表 示 我 们 已 经 存 储 的 带 有 类 别 标 签 的 数 据
train_x = x[:60, :]
train_y = y[:60]
testing_x = x[60:, :]
testing_y = y[60:]

# 定 义K最 近 邻 算 法
def KNN(train_x, train_y, testing_x, K=15):
    predicted_y = []
    for sample in testing_x:
        # 使 用L1范 数 计 算 数 据 点 距 离
        distance = np.linalg.norm(train_x - sample, axis=1, ord=1)
        # 找 到 距 离 最 小 的K个 数 据 点
        sort_index = np.argsort(distance)
        neighbors = sort_index[:K]
        neighbors_y = train_y[neighbors]
        # 利 用 多 数 投 票 法 对 数 据 进 行 分 类
        class1_vote = np.sum(neighbors_y == 0)
        class2_vote = np.sum(neighbors_y == 1)
        predicted_y.append(0) if class1_vote > class2_vote else predicted_y.append(1)
    return predicted_y


predicted_y = KNN(train_x, train_y, testing_x, K=2)

# 计 算 分 类 准 确 度
correct_count = 0
for index in range(len(testing_y)):
    if testing_y[index] == predicted_y[index]:
        correct_count += 1
print('分 类 正 确 率 为： ', correct_count / len(testing_y))

image-20230709172328227

  1. 权重法
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
31
32
33
34
35
36
37
38
39
import numpy as np
from sklearn.datasets import make_classification
import matplotlib.pyplot as plt

# 生 成 二 分 类 的 数 据
N = 200
p = 3
x, y = make_classification(N, p, n_informative=p, n_redundant=0, n_classes=2)
# 将 数 据 划 分 为 训 练 集 和 测 试 集； 对 于K近 邻 算 法， 训 练 集 并 不 会 用来 训 练， 只 表 示 我 们 已 经 存 储 的 带 有 类 别 标 签 的 数 据
train_x = x[:60, :]
train_y = y[:60]
testing_x = x[60:, :]
testing_y = y[60:]

# 定 义K最 近 邻 算 法
def KNN(train_x, train_y, testing_x, K=15):
    predicted_y = []
    for sample in testing_x:
        # 使 用 L1 范 数 计 算 数 据 点 距 离
        distance = np.linalg.norm(train_x - sample, axis=1, ord=1)
        # 找 到 距 离 最 小 的K个 数 据 点
        sort_index = np.argsort(distance)
        neighbors = sort_index[:K]
        neighbors_y = train_y[neighbors]
        # 利 用 权 重 法 对 数 据 进 行 分 类
        pass
        predicted_y.append(0) if class1_vote > class2_vote else predicted_y.append(1)
    return predicted_y


predicted_y = KNN(train_x, train_y, testing_x, K=15)

# 计 算 分 类 准 确 度
correct_count = 0
for index in range(len(testing_y)):
    if testing_y[index] == predicted_y[index]:
        correct_count += 1
print('分 类 正 确 率 为： ', correct_count / len(testing_y))