k近邻算法（k-NearestNeighbor）

KNN 概述

\(k\)-近邻（k-NearestNeighbor, KNN）算法是一种基本分类与回归方法。

\(k\)近邻算法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。\(k\)近邻算法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其\(k\)个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，\(k\)近邻算法不具有显式的学习过程。

\(k\)近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。\(k\)值的选择、距离度量以及分类决策规则是\(k\)近邻算法的三个基本要素。

\(k\)近邻算法

\(k\)近邻算法简单的说就是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的\(k\)个实例，这\(k\)个实例的多数属于某个类，就把该输入实例分为这个类。

假设有包含\(m\)个实例的训练数据集\(D\)，

\[D= \{(\pmb x_1, y_1),(\pmb x_2,y_2), \dots, (\pmb x_m,y_m)\} \]

其中，每个实例由\(d\)个属性描述，则每个实例\(\pmb x_i=(x_{i1};x_{i2};\dots;x_{id})\)是\(d\)维空间中的一个向量。\(y_i=\{c_1,c_2,\dots,c_N\}\)为实例的类别，\(i=1, 2, \dots, m\);

算法过程：

1）输入实例特征向量\(\pmb x\)；

2）根据给定的距离度量，在训练数据集\(D\)中找出与\(\pmb x\)最邻近的\(k\)个点，将包含这\(k\)个点的\(\pmb x\)的邻域记作\(N_k(\pmb x)\)；

3）在\(N_k(\pmb x)\)中根据分类决策规则（如多数表决）决定\(\pmb x\)的类别\(y\)：

\[y = argmax_{c_j}\sum_{\pmb {x_i}\in {N_k(\pmb x)}}I(y_i=c_j), i=1,2,\dots,m; j=1, 2, \dots, N \]

上式中，\(I\)为指示函数，即当\(y_i=c_j\)时值为1，否则为0。

\(k\)近邻算法的特殊情况是\(k=1\)的情形，称为最近邻算法。对于输入的实例特征向量\(\pmb x\)，最近邻法将训练数据集中与\(\pmb x\)最邻近点的类别作为\(\pmb x\)的类别。

\(k\)近邻算法没有显式的学习过程。

\(k\)近邻算法模型

\(k\)近邻算法中，当训练数据集、距离度量、\(k\)值及分类决策规则（如多数表决）确定后，对于一个新的输入实例，它所属的类别唯一地确定。

1. 距离度量

特征空间中两个实例点的距离是两个点相似程度的反应。\(k\)近邻模型的特征空间一般是\(n\)维实数向量空间\(R^n\)。使用的距离是欧氏距离，但也可以是其他距离，如更一般的\(L_p\)(\(L_p\) distance)，机器学习笔记-距离度量与相似度(一)闵可夫斯基距离。

当然，不同的距离度量所确定的最近邻点是不同的。

2.\(k\)值的选择

\(k\)值的选择会对\(k\)近邻算法的结果产生重大的影响。

如果选择较小的\(k\)值，就相当于用较小的邻域中的训练实例进行预测，这会导致预测结果对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，\(k\)值越小，整体模型的复杂度就越大，模型的方差就会越大，容易造成过拟合。

如果选择较大的\(k\)值，就相当于用较大的邻域中的训练实例进行预测。这时，与输入实例较远的训练实例也会对预测起作用，当然，较远也可能意味着它与输入实例不相似，从而导致预测发生错误。换句话说，\(k\)值越大，模型的偏差越大，对噪声数据越不敏感，当k值很大时，可能造成欠拟合。极端情况是\(k=m\)，即是\(k\)等于训练集中的实例总数，那么无论输入是什么，我们都可以简单地预测它属于训练实例中最多的类，显然这样的预测是没有任何用处的。

在实际应用中，\(k\)值一般取一个较小的数值，可以采用交叉验证的方法来选取合适的\(k\)值。

3.分类决策规则

1. 分类

\(k\)近邻算法的分类决策规则往往是多数表决，即由输入实例的\(k\)个邻近的训练实例中的多数类决定输入实例的类。

多数表决有如下解释：如果我们选择的损失函数为\(0-1\)损失函数，分类函数为\(f{:}R^n \rightarrow \{c_1,c_2,\dots, c_N\}\)，即输入一个\(n\)维特征向量，得到一个类别\(c_N\)。

那么，误分类的概率是：

\[P(Y \ne f(X)) = 1- P(Y = f(X)) \]

对于给定的实例\(\pmb x\)，其最近邻的\(k\)个训练实例点构成集合\(N_k(\pmb x)\)。如果涵盖\(N_k(\pmb x)\)的区域的类别是\(c_j\)，那么误分类率是

\[\frac{1}{k}\sum_{\pmb {x_i}\in {N_k(\pmb x)}}I(y_i \ne {c_j}) =1-\frac{1}{k} \sum_{\pmb {x_i}\in {N_k(\pmb x)}}I(y_i=c_j) \]

要使误分类率最小，就要使\(\sum_{\pmb {x_i}\in {N_k(\pmb x)}}I(y_i=c_j)\)最大，所以选择多数表决规则。

2. 回归

当\(k\)近邻算法用于回归问题时，将会取\(k\)个邻近实例的均值来作为最终的预测值。

现用一维空间中的样本证明样本均值是最优的输出值，如果我们选择平方损失函数：给定随机数列\(\{x_1, x_2, \dots, x_n\}\)，设该空间中最优的输出值为\(\hat y\)，根据最小平方误差准则，构造\(\hat y\)的函数，这是一个凸函数，如下：

\[F(\hat y) = (x_1-\hat y)^2+(x_2-\hat y)^2+\dots+(x_n-\hat y)^2 \]

其一阶导数为：

\[F^{'}(\hat y) = -2(x_1-\hat y)-2(x_2-\hat y)+\dots-2(x_n-\hat y) = 2n\hat y - 2\sum_{i=1}^n{x_i} \]

欲求得最小值，令\(F^{'}(\hat y)=0\)，则

\[\hat y=\frac{1}{n}\sum_{i=1}^n{x_i} \]

根据其单调性，易知\(\hat y=\frac{1}{n}\sum_{i=1}^n{x_i}\)为最小值点。

因此，选择邻近实例的均值作为预测值。

其他

1）变种

\(k\)近邻算法有一些变种，其中之一是可以增加邻居的权重。默认情况下，在计算距离时，都是使用相同权重。实际上，可以针对不同的邻居指定不同的距离权重。另一个变种是，使用一定半径内的点取代距离最近的k个点。当数据采样不均匀时，可以有更好的性能。在scikit-learn里，RadiusNeighborsClassifier类实现了这个算法变种。

2）\(k\)近邻算法特点

优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高

3）\(k\)近邻算法的实现

实现\(k\)近邻算法时，一个非常重要的问题是如何对训练数据进行快速\(k\)近邻搜索。这点在特征空间的维数大及样本量大时尤为重要。其中最简单的实现方法是线性扫描，这时计算输入实例与每个训练实例的距离。显然，当样本量很大时，这非常耗时。为了提高效率，可以考虑使用特殊的结构存储训练数据，以减少距离计算次数，比如kd树(kd tree)方法。

\(k\)近邻算法示例

使用机器学习中常用的包scikit-learn进行\(k\)近邻算法示例演示。

1. 使用\(k\)近邻算法进行分类

## python 3.6
## sklearn 0.20.3

# 导入需要使用的模块
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import warnings

from sklearn.datasets.samples_generator import make_blobs
from sklearn.neighbors import KNeighborsClassifier # k近邻分类

# 解决matplotlib绘图时中文显示的问题
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

warnings.filterwarnings("ignore")

# 使用make_blobs函数来生成数据集生成带有标记的模拟数据集
# 生成的训练数据集放在变量X里面，数据集的类别标记放在y里面
centers = [[-2, 2],
           [2, 2],
           [0, 4]]

X, y = make_blobs(n_samples=90, centers=centers,
                  random_state=42, cluster_std=0.6)
"""
参数：
n_samples  指定生成的样本数量
n_feature  指定生成数据集的特征数量，默认为2，这里我们使用默认值，便于绘图
centers  指定不同标记的样本点分布的中心位置
random_state  随机种子
cluster_std  标准差，用来指明生成的点分布的松散程度
"""

# 画出数据
plt.figure(figsize=(12, 8))
# 画出训练集中的所有样本点
colors = ["blue", "green", "red"]
for i in np.unique(y):
    plt.scatter(X[y==i][:,0], X[y==i][:,1], color=colors[i], label="y = %s" % i)
plt.legend(loc="right upper")

如图1所示，我们生成的样本点大致分成三个区域分布在坐标平面上，这里使用三种不同的颜色标出样本的类别。

图1 生成样本点的分布情况

# 使用KNN算法进行分类，这里选择k=5
# 模型训练
k = 5
knn_clf = KNeighborsClassifier(n_neighbors=k)
knn_clf.fit(X, y)
"""
这里会反馈给我们选择的算法的参数设置情况，如：
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=None, n_neighbors=5, p=2,
           weights='uniform')
参数：
n_neighbors 整型，k值，即近邻的数量，默认值为5
weights 近邻点的权重，默认'uniform'表示所有的点的权重相同，'distance'表示按照距离设置权重，距离越近权重越大
algorithm  k个近邻的搜索算法，比如kd树算法，'auto'表示根据输入的数据自动选择合适的算法
p  闵可夫斯基距离的p值，默认为2，即欧氏距离
metric 距离度量方法，默认为闵可夫斯基距离

其他参数可以阅读说明文档获得。
"""
# 接下来对新输入的样本点进行预测
X_test = np.array([0, 2])
y_pred = knn_clf.predict(X_test)
print(y_pred)

这里输出为1，即新的输入被分类为1，图1中绿色表示的类别。

接下来我们将训练集和测试样本画在一个图中，看看\(k\)近邻算法到底怎么完成的分类，见图2：

# 通过实例方法得到k个近邻的在训练数据集中的索引
neighbors = knn_clf.kneighbors(X_test, return_distance=False)
print(neighbors)

# 画出示意图
plt.figure(figsize=(12, 8))

# 画出训练集的所有样本点
colors = ["blue", "green", "red"]
for i in np.unique(y):
    plt.scatter(X[y==i][:,0], X[y==i][:,1], color=colors[i], label="y = %s" % i)
plt.scatter(X_test[0][0], X_test[0][1], marker="*", s=80, c="purple")

# 预测点与距离最近的5个样本的连线
for i in neighbors[0]:
    plt.plot([X[i][0], X_test[0][0]], [X[i][1], X_test[0][1]],
            'k--', linewidth=1.2) 
plt.legend(loc="right upper")

图2 k近邻的分类决策规则

如图2所示，因为在\(k=5\)个近邻样本点中有\(3\)个属于类别\(1\)（绿色），即类别\(1\)为多数，所以新的样本点被分类为\(1\)。

2.使用\(k\)近邻算法进行回归

# k近邻回归
from sklearn.neighbors import KNeighborsRegressor 

# 生成数据集，我们使用一个简单的二次函数，并加入一些随机噪声
rng = np.random.RandomState(1)
X = 5 * rng.rand(50, 1)
y = X ** 2 + 1 + np.random.normal(0, 0.7, size=(50, 1))
# 将训练数据画出来, 见图3
plt.figure(figsize=(12, 8))
plt.scatter(X, y)

图3 训练数据集

# 训练模型
# 设置模型参数，依然选择k=5，其他使用与分类时相同的默认参数
k = 5
knn_reg = KNeighborsRegressor(n_neighbors=k)
knn_reg.fit(X, y)

# 生成待预测数据并进行预测
X_test = np.linspace(0, 5, 500)[:, np.newaxis]
y_pred = knn_reg.predict(X_test)

# 把这些预测点连接起来就构成了拟合曲线，见图4
plt.figure(figsize=(12,8))
plt.scatter(X, y, c='red', label='training data', s=50)
plt.plot(X_test, y_pred, c='blue', label='prediction', lw=2)
plt.axis('tight')
plt.title('KNeighborsRegressor (k=%i)' % k)
plt.legend(loc="best")

图4 k近邻回归拟合曲线

接下来，我们使用其中一个待预测样本，来简单看一看，\(k\)近邻算法在回归应用中是怎么给出预测值的？

# k近邻是怎么计算预测值的
# 生成一个待预测样本
x_test = np.array([[0.05]])
y_pred_2 = knn_reg.predict(x_test)
# 输出预测值：0.94369151
print(y_pred_2)

# 获得预测点的k个近邻
neighbors = knn_reg.kneighbors(X=x_test, n_neighbors=k, return_distance=False)
# print(y[neighbors])
# 求k个最近邻的均值
print(np.mean(y[neighbors]))
# 输出：0.9436915073689807

我们看到，\(k\)近邻算法在回归中预测值为\(k\)个近邻的均值。

3.实例：鸢尾花种类预测

我们使用\(k\)近邻算法，对鸢尾花进行分类，数据来自sklearn，见代码：

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import warnings

# 解决matplotlib绘图时中文显示的问题
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

warnings.filterwarnings("ignore")

from sklearn.datasets import load_iris # 存储在sklearn中的鸢尾花数据集
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.model_selection import cross_val_score, validation_curve

# 加载数据
data = load_iris()

print(data.feature_names)
#  ['sepal length (cm)',
#     'sepal width (cm)',
#     'petal length (cm)',
#    'petal width (cm)']

print(data.target_names)
#array(['setosa', 'versicolor', 'virginica'], dtype='<U10')

# 将数据特征及标签分别存储在变量X和y中
X = data.data
y = data.target

print(X.shape)
#(150, 4)
print(y.shape)
# (150,)
print(np.unique(y))
# [0 1 2]
    
# 查看数据集的前5行
print(X[:5,:])
#    array([[5.1, 3.5, 1.4, 0.2],
#           [4.9, 3. , 1.4, 0.2],
#           [4.7, 3.2, 1.3, 0.2],
#           [4.6, 3.1, 1.5, 0.2],
#           [5. , 3.6, 1.4, 0.2]])

# 查看给类别样本的数量
for i in [0, 1, 2]:
    print("类别{}的数量：{}".format(i, len(y[y==i])))

#    类别0的数量：50
#    类别1的数量：50
#    类别2的数量：50

可知，鸢尾花数据集中的每个样本(实例)具有4个特征，分别是花萼的长度和宽度，花瓣的长度和宽度。共有3个类别，使用\(0\)，\(1\)，\(2\)表示，对应于setosa, versicolor, virginica。数据集中各类别的样本数相同。

# 选择其中的两个特征值，将样本绘制出来，见图5
plt.figure(figsize=(12, 8))
plt.scatter(X[:, 0], X[:,2], c=y, marker="o", cmap="cool")

图5 鸢尾花数据集

可以看出，数据大致分为3类。接下来，我们使用\(k\)近邻算法对样本进行分类。

# 将上述的数据集拆分成训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3,
                                                   random_state=1,
                                                   stratify=y)
# 训练模型
# 选择k=3
k = 3
knn_clf = KNeighborsClassifier(n_neighbors=k)
knn_clf.fit(X_train, y_train)

# 对测试集进行预测
# y_pred = knn_clf.predict(X_test)
# 在测试集上的准确率
print("k=3时预测准确率：{:.3f}".format(knn_clf.score(X_test, y_test)))
# k=3时预测准确率：0.978

当选择近邻数量\(k=3\)时，在测试数据集上，预测准确率为0.978。那么，\(k\)值的选择对模型预测的准确率有什么影响呢？接下来我们选择使用不同的k值，并使用交叉验证的方法来看一看，并绘制出不同\(k\)值对预测结果的影响。

# 使用sklearn中的validation_curve
k_range = np.arange(1, 10)

# 使用5折交叉验证
train_scores, test_scores = validation_curve(KNeighborsClassifier(), X, y,
                                            param_name="n_neighbors",
                                            param_range=k_range,
                                            cv=5)
# 模型交叉验证得分
print(train_scores)
print(test_scores)

# 绘制验证曲线，见图6
train_scores_mean = np.mean(train_scores, axis=1)
# train_scores_std = np.std(train_scores, axis=1)
test_scores_mean = np.mean(test_scores, axis=1)
# test_scores_std = np.std(test_scores, axis=1)
plt.figure(figsize=(12, 8))
plt.plot(k_range, train_scores_mean, c="r", lw=2, label="Training scores")

plt.plot(k_range, test_scores_mean, c="b", lw=2, label="Testing scores")
plt.xlabel("$k$值")
plt.ylabel("预测准确率")
plt.grid()
plt.legend(loc="best")

图6 k值对模型的影响

由图6可见，当\(k\)取值较小时模型的训练误差很小，但测试误差大，说明模型过拟合。而当\(k\)值较大时，测试误差和训练误差均较大，说明模型可能欠拟合。与我们之前对\(k\)值的描述相符。

我们知道，还有其他因素影响\(k\)近邻算法的效果，同样可以通过上面的方法进行验证，这篇笔记就不再展开了。

 
 
 

开心吧

悟空：八戒，你猜我的金箍棒在哪里？
八戒：哼哼，大师兄，是不是因为它和你的发型比较配。

 
 
 
 
 
参考来源：
1）统计学习方法 - 李航
1）https://blog.csdn.net/kun_csdn/article/details/88919091