k-nearest neighbor(kNN,k近邻算法)理论与实操及KNeighborsClassifier参数详解

1. k-NN算法简介

k近邻法是基本且简单的分类与回归方法，这里只讨论分类方法，利用数据集对特征向量空间进行划分，可以进行多分类。如下图：
三角形与矩形分别代表两类数据，标签已知。现要对新输入的为分类点(绿色)进行分类，k-NN的做法是寻找与该绿点相邻最近的k个点(k-NN算法的k的含义，图中的距离为欧式距离)，然后通过多数表决的方式把绿点划分到这k个最近点出现频数最高的类。例如如果k取3，则绿点最近的3个点中频数最高为三角形类，所以归为三角形类；若k取5，则距离绿点最近的5个点中频数最高为矩形类，所以归绿点为矩形类。

1.1 模型

输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}, 实例特征向量$x$
总共N个样本，$x_i\in \mathcal{X}\subseteq R^n$为实例的特征向量， y i ∈ Y = { c 1 , c 2 , . . . , c K } 为 实 例 的 类 别 , i = 1 , 2 , . . . , N y_i \in \mathcal{Y}=\{c_1,c_2,...,c_K\}为实例的类别, i=1,2,...,N yi​∈Y={c1​,c2​,...,cK​}为实例的类别,i=1,2,...,N
输出：实例$x$所属的类$y$
step1:根据给定的距离度量，在训练集T中找出与$x$最近的k个点，涵盖这k个点的x的邻域记为$N_k(x);$
step2:在$N_k(x)$中根据决策规则（如多数表决）决定$x$的类别$y$
$$y=\underset{c_j}{\mathrm{argmax}}\sum _{x_i\subseteq N_k(x)}I(y_i=c_j)，i=1,2,...,N,j=1,2,...,K；$$
其中I为指示函数

1.2 学习策略

$$\underset{c_j}{\max }\sum _{x_i\subseteq N_k(x)}I(y_i=c_j)，i=1,2,...,N,j=1,2,...,K；$$

1.3 学习算法

学习算法即如何求出以上的学习策略的最大值，用的是多数表决法，即将$c_1到c_K$得到的指示函数和的值排序，选择最大值对应的类别$c^{\ast }$作为输出。假设$c^{\ast }$为最大值对应的类别，那么得到的最终模型为：
$$y=c^{\ast }$$

1.4 距离度量

从以上公式可以看出，关键是确定输入实例$x$的邻域$N_k(x)$，而这个邻域又由两个方面决定，一个就是如何计算各点与输入实例$x$的距离（怎么判断离某些点近不近)？
$$L_p\left(x_i,x_j\right)={\left(\sum _{i=1}^n{\left|x_i^{(i)}-x_j^{(l)}\right|}^p\right)}^{\frac{1}{p}}$$

• $p=1$ 曼哈顿距离
• $p=2$ 欧氏距离
• $p=\infty$ 切比雪夫距离
  一般使用欧式距离。

1.5 k值选择

知道了怎么判断点之间离的近不近，那么要确定邻域还得需要知道该邻域包含多少个“最近”点,这就是k值决定的，该邻域会包含k个离输入实例最近的点。k值越小，模型越复杂，过拟合的风险越大，当k=1时成为最近邻模型。而k值越大，模型越简单，最极端情况就是k=N，这时直接把样本中出现频数最高的类当成所有输入实例的类。

距离的度量以及k值作为超参数，可以通过验证集来选择合适的超参数。

2. 实例操作

选取sklearn内置数据库的iris数据集进行实战演练。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
# %matplotlib notebook
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter

1
2
3
4
5
6
7
8

iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = ['sepal_length', 'sepal_width','petal_length','petal_widthth','label']
df
1
2
3
4
5

总共有4个特征，且分为三类，每一类各50个样本。为了方便画散点图更利于观察，只选取前两个特征’sepal_length’以及’sepal_width’训练模型，

plt.figure()
ax = plt.subplot(1,1,1)
plt.scatter(df[:50]['sepal_length'], df[:50]['sepal_width'], label='0')
plt.scatter(df[50:100]['sepal_length'], df[50:100]['sepal_width'], label='1')
plt.scatter(df[100:150]['sepal_length'], df[100:150]['sepal_width'], label='2')
plt.xlabel('sepal_length')
plt.ylabel('sepal_width')
plt.legend()
plt.show()
1
2
3
4
5
6
7
8
9

如图：

data = np.array(df.iloc[:, [0, 1, -1]])  # 选取前两个特征
X, y = data[:,:-1], data[:,-1]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2) # 划分训练集和测试集
1
2
3

2.1 手写kNN算法

class kNN:
    def __init__(self, X_train, y_train, k_neighbors, p=2):  
        """
        parameter: k_neighbors 所选取的临近点个数
        parameter: p 距离度量，默认p=2为欧式距离
        """
        self.k = k_neighbors
        self.p = p
        self.X_train = X_train
        self.y_train = y_train   # 定义每个模型的私有属性
        
        
    def predict(self,X):
        """
        X：要进行分类的某个输入实例
        """
        knn_list = []  # 取出k个点，组成一个双值子元组列表，元祖包含距离和标签
        
        for i in range(self.k):  # 首先遍历前k个样本
            distance = np.linalg.norm(X - self.X_train[i], ord=self.p) # 计算距离
            knn_list.append((distance, self.y_train[i]))  
        
        for i in range(self.k, len(self.X_train)):  # 再遍历剩下样本，选出最近的k个点
            max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))  # 计算列表中每一次遍历距离最大的点的index
            distance = np.linalg.norm(X - self.X_train[i], ord=self.p)  # 计算剩下点的距离，和列表里最大距离的点相比
            if distance < knn_list[max_index][0] :  # 如果这次遍历的点比较小，那就替换那个距离更大的点
                knn_list[max_index] = (distance, self.y_train[i]) # 最终列表里是距离X最近的k个点
        
        # 下面要统计这最近的k个点中哪个标签出现的次数最多,作为实例X的输出标签
        knn = np.array([int(i[-1]) for i in knn_list]) # 标签数组
        most_lable = np.argmax(np.bincount(knn))  # 出现次数最多的lable
        return most_lable
    
    
    # 下面计算测试集的预测精度
    def score(self, X_test, y_test):
        right_count = 0
        for X, y in zip(X_test, y_test):
            label = self.predict(X)
            if label == y:
                right_count += 1
        return right_count / len(X_test)
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
40
41
42

trained_knn = kNN(X_train,y_train,5)  # 这就是定义好的模型，不需要fit，可以用来预测测试集了
1

trained_knn.score(X_test, y_test)  # 预测精度为0.7
1

用一个测试点来画图：

test_point = [5.0, 3.0]
print(f'Test Point: {trained_knn.predict(test_point)}') #  Test Point: 0
1
2

plt.figure()
ax = plt.subplot(1,1,1)
plt.scatter(df[:50]['sepal_length'], df[:50]['sepal_width'], label='0')
plt.scatter(df[50:100]['sepal_length'], df[50:100]['sepal_width'], label='1')
plt.scatter(df[100:150]['sepal_length'], df[100:150]['sepal_width'], label='2')
plt.plot(test_point[0], test_point[1], 'ko', label='test_point')
plt.xlabel('sepal_length')
plt.ylabel('sepal_width')
plt.legend()
plt.show()
1
2
3
4
5
6
7
8
9
10

可以看出测试点（5,3)明显离0类的大部分点更近，所以输出0。

kNN算法一般步骤就演示完了，可是存在一个效率问题，因为在寻找最近的k个点时，手写的模型要求计算出所有点到输入实例$x$的距离，再从中挑选k个最近的点，当样本数量非常大且实例的维度很高时，计算量都会很大，所以为了提高效率，在搜索k个最近值时会用到kd树。

2.2 k近邻法的实现：kd树

k近邻法需要考虑的问题就是如何把邻域找出来。k近邻法最简单的一种实现方法就是线性扫描，计算出输入实例与每个训练实例的距离，然后按距离排序，选择距离最近的k个样本进入邻域，将其标签作为多数表决的标签数据来源。

然而，当数据集很大或者说特征数量很多时，计算非常耗时，通常是不可行的。为了提高邻域的搜索效率，可以考虑用特殊的结构存储训练数据，以减少距离的计算次数。kd树就是一种比较高效实现k近邻法的实现方法。

• kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。
• kd树是二叉树，表示对k 维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将
  声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/465831