摘要：K近邻算法是机器学习中的一个非常基础的算法。本文通过自生成数据，通过绘图的方式演示KNN算法的思路，让你不看数学公式就看了解什么是KNN算法。

关键词：KNN算法

1 生成一个二分类的数据集

本文很多内容参考文献[1]。

先生成一个两个类别的数据集，然后修改这个数据集中的一些数据（提高分类难度、或者有一些杂质数据），最后再剔除一些数据使得数据不那么均衡，但也不能差距太大（主要还是希望进一步接近现实数据）。为了能够可视化我们的数据，这里生成的数据为二维的，也就是一条数据具有两个特征。

from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import numpy as np
def makeTwoClassData():
    X, y = make_blobs(centers=2, random_state=4, n_samples=30)
    y[np.array([7, 27])] = 0   # 生成错误数据
    mask = np.ones(len(X), dtype=np.bool)  # 得到一个与数据集大小同的全一矩阵
    mask[np.array([0, 1, 5, 26])] = 0      # 剔除这些索引数据
    X, y = X[mask], y[mask]                # 选出剔除数据后的数据
    return X, y

（其中涉及的模块，参数，如有不懂的百度或留言评论）
将生成的数据可视化：

X, y = makeTwoClassData()
# 绘图
plt.scatter(X[y==0][:,0], X[y==0][:,1], marker='o', s=50)
plt.scatter(X[y==1][:,0], X[y==1][:,1], marker='^', s=50)
plt.legend(['Class 0', 'Class 1'], loc=4)
plt.xlabel("First feature")
plt.ylabel("Second feature")
plt.show()

2 k近邻算法原理介绍

k紧邻算法是一种监督学习算法，算法的思想是这样子的：我们已经有了一堆具有标记的数据DDD，例如我们生成的有两个特征的数据，我们的任务是利用这些已有的数据预测新的数据xxx属于哪个类别，这个新的数据类型也理所当然与已有的数据集是一致的，下一步要做的就是计算这一条需要预测类别数据与已有数据之间的距离（这里距离通常是欧氏距离，也不排除还有其他计算方法），然后选择距离最小的前k条已有的数据，根据这k条数据的类别判定（判定方式可使用哪个类别多选择哪个方式）数据xxx属于哪个类别。（希望这些废话你能够理解）

下面让用代码和画图的方式辅助你了解。

构建几个需要预测的数据

# 选取测试点
X_test = np.array([[8.2, 3.66214339], [9.9, 3.2], [11.2, .5]])

绘制不同个邻居数据的分类图：

from sklearn.metrics import euclidean_distances
from sklearn.neighbors import KNeighborsClassifier

def plot_knn_classification(X, y, X_test, n_neighbors):
    plt.figure()
    dist = euclidean_distances(X, X_test)  # 计算训练数据与测试数据之间的距离
    closest = np.argsort(dist, axis=0)  # 从dist计算结果根据值的进行排序，并返回索引
    # 绘制箭头
    for x, neighbors in zip(X_test, closest.T):
        for neighbor in neighbors[:n_neighbors]:
            plt.arrow(x[0], x[1], X[neighbor, 0] - x[0], X[neighbor, 1] - x[1], head_width=0, fc='k', ec='k')

    # 原始数据图形
    plt.scatter(X[y==0][:,0], X[y==0][:,1], marker='o', s=50, label="training class 0")
    plt.scatter(X[y==1][:,0], X[y==1][:,1], marker='^', s=50, label="training class 1")
    plt.xlabel("First feature")
    plt.ylabel("Second feature")
    # 预测值
    clf = KNeighborsClassifier(n_neighbors=n_neighbors).fit(X, y)  # 训练得到模型
    y_pre = clf.predict(X_test)
    plt.scatter(X_test[y_pre==0][:, 0], X_test[y_pre==0][:, 1], marker='*', s=50, c='red', label="test_pre 0")
    plt.scatter(X_test[y_pre==1][:, 0], X_test[y_pre==1][:, 1], marker='*', s=50, c='black', label="test_pre 1")

    plt.legend()

# 绘制相邻1个点的情况
plot_knn_classification(X, y, X_test, 1)
# 绘制相邻3个点的情况
plot_knn_classification(X, y, X_test, 3)

上面的图分类已经很明了，无需多言。下面我们使用sklearn来构建一个KNN分类器（上面已经构建了）。

3 使用sklearn构建KNN分类器

只需要几步就可以了，不过需要知道相关参数。如下：

from sklearn.model_selection import train_test_split
# 数据集划分
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
# 构建模型，并训练
clf = KNeighborsClassifier(n_neighbors=3)
clf.fit(X_train, y_train)
# 预测
print("Test set prediction:{}".format(clf.predict(X_test)))
"""
Test set prediction:[1 0 1 0 1 0 0]
"""

查看模型分类正确率：

print("Test set accuracy:{:.2f}%".format(clf.score(X_test,y_test)*100))
"""
Test set accuracy:85.71%
"""

是不是很简单，几步就搞定了。现在能够分类了，那么这个分类器的决策边界是什么样的呢？

4 看看KNN的决策边界是什么样的

绘制决策边界还是相对麻烦的，这里提供一下相关代码：

def plot_2d_separator(classifier, X, fill=False, ax=None, eps=None, alpha=1, cm='viridis', linewidth=None, threshold=None, linestyle="solid"):
    if eps is None:
        eps = X.std() / 2.
    # 获取当前子图
    if ax is None:
        ax = plt.gca()
    # 特征1最值浮动
    x_min, x_max = X[:, 0].min() - eps, X[:, 0].max() + eps
    # 特征2最值浮动
    y_min, y_max = X[:, 1].min() - eps, X[:, 1].max() + eps
    # 在两个特征之间均匀生成1000个点
    xx = np.linspace(x_min, x_max, 1000)
    yy = np.linspace(y_min, y_max, 1000)

    X1, X2 = np.meshgrid(xx, yy)  # 构建网格点矩阵, shape 1000*1000
    X_grid = np.c_[X1.ravel(), X2.ravel()] # 构建坐标点, 则有1000^2个坐标点，即100万个点

    chunk_size = 10000
    Y_result_chunks = []
    for x_chunk in np.array_split(X_grid, np.arange(chunk_size, X_grid.shape[0], chunk_size, dtype=np.int32),axis=0):
        # predict_proba返回的是一个 n 行 k 列的数组， 第 i 行 第 j 列上的数值是模型预测 第 i 个预测样本为某个标签的概率，并且每一行的概率和为1。
        Y_result_chunks.append(classifier.predict_proba(x_chunk)) # 分批预测构造的点的结果, 每批1万个数据
    decision_values = np.concatenate(Y_result_chunks)[:, 1]  # 将list中的结果拼接起来, 然后选取一个列别的预测值
    levels = [.5] if threshold is None else [threshold]
    fill_levels = [0] + levels + [1]  # 填充
    # 开始绘制边界（类似于等高线）
    ax.contourf(X1, X2, decision_values.reshape(X1.shape), levels=fill_levels, alpha=alpha, cmap=cm)
    # 设置坐标轴范围以及对应的数字
    ax.set_xlim(x_min, x_max)
    ax.set_ylim(y_min, y_max)
    ax.set_xticks(())
    ax.set_yticks(())

fig, axes = plt.subplots(1, 3, figsize=(10, 3))
for n_neighbors, ax in zip([1, 3, 9], axes):
    clf = KNeighborsClassifier(n_neighbors=n_neighbors).fit(X, y)
    # 绘制决策边界
    plot_2d_separator(clf, X, fill=True, eps=0.5, ax=ax, alpha=0.4)
    # 原始数据图形
    ax.scatter(X[y==0][:,0], X[y==0][:,1], marker='o', s=50, label="class 0")
    ax.scatter(X[y==1][:,0], X[y==1][:,1], marker='^', s=50, label="class 1")
    ax.set_title("{} neighbor(s)".format(n_neighbors))
    ax.set_xlabel("feature 0")
    ax.set_ylabel("feature 1")
axes[0].legend(loc=3)

决策边界图像如下：

5 用现实中的数据来说话

当然上面的例子使用的自己构建的数据，并且数据还比较少，现在我们使用sklearn自带的数据来分类，使用现实世界的乳腺癌数据集进行knn分类。其操作如下：

from sklearn.datasets import load_breast_cancer

cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(cancer.data, cancer.target, stratify=cancer.target, random_state=66)
training_accuracy = []
test_accuracy = []
# n_nighbors取值从1-10
neighbors_settings = range(1, 11)
for n_neighbors in neighbors_settings:
    # 构建模型
    clf = KNeighborsClassifier(n_neighbors=n_neighbors)
    clf.fit(X_train, y_train)
    # 记录训练精度
    training_accuracy.append(clf.score(X_train, y_train))
    # 记录泛化精度
    test_accuracy.append(clf.score(X_test, y_test))
plt.plot(neighbors_settings, training_accuracy, label="training accuracy")
plt.plot(neighbors_settings, test_accuracy, label="test accuracy")
plt.ylabel("Accuracy")
plt.xlabel("n_neighbors")
plt.legend()

总结

从上面的图形可以看出，并不是选择k越大越好，也不是越小越好，这里选择的就是6最好。其实你慢慢就会发现，我们开始要根据训练的一些参数曲线，去调整模型的参数啦，这在后面的文章会做进一步的介绍。当然本部分内容是参考《Python机器学习基础教程》内容并结合自己的理解写出，所以我还是推荐?一下这本书，或者可以在订阅号“AIAS编程有道”中回复“Python机器学习基础教程”获取电子档后决定?是否要购买，建议购买正版书籍。?

Reference

[1]【机器学习】K近邻(knn)算法是如何完成分类的？: https://piqiandong.blog.csdn.net/article/details/106751155