Building & Improving a K-Nearest Neighbors Algorithm in Python
K-Nearest Neighbors算法，简称K-NN，是一种经典的机器学习算法，但在深度学习大热的现今经常被忽略。在本教程中，我们将在Scikit-Learn中构建K-NN算法并在MNIST数据集上运行它。从那里开始，我们将构建我们自己的K-NN算法，以期开发出比Scikit-Learn K-NN有更高准确度和分类速度的分类器。
K-最近邻分类模型
K-Nearest Neighbors算法是一种监督机器学习算法，易于实现，但能够进行强大的分类。K-NN最大的优势之一就是它是一个懒惰的学习者 。这意味着该模型不需要训练，并且可以正确分类数据，这与其他ML兄弟，如SVM，回归（regression）和多层感知（multi-layer perception）不同。
K-NN如何运作
为了对某些给定数据点p进行分类，K-NN模型将首先使用一些距离度量（distance metric）将p与其数据库中可用的每个其他点进行比较。距离度量是诸如欧几里德距离之类的东西，一个取两个点作为参数的简单函数，并返回这两个点之间的距离。因此，可以假设它们之间具有较小距离的两个点比它们之间具有较大距离的两个点更相似 。这是K-NN背后的核心理念。
此过程将返回无序数组，其中数组中的每个条目保持p与模型数据库中n个数据点之一之间的距离。因此返回的数组大小为n 。这是K-NN的K部分的来由：k是一些任意值，它告诉模型，分类p时，其应考虑选择多少个（通常是3-11之间） 最 相似于 p点的点。然后，该模型将采用那些k个最相似的值，并使用投票技术来决定如何对p进行分类，如下图所示。
图像中的K-NN模型的k值为3，中心箭头指向的点是p，是需要进行分类的点。如你所见，圆中的三个点是最接近或最类似p的三个点。因此，使用简单的投票技术， p将被归类为“白色”，因为白色构成k个最相似值的大部分。
太酷了！令人惊讶的是，这种简单的算法可以在某些情况下实现超乎想象的结果，并且可以应用于各种各样的问题，我们将在下面看到。
在Scikit中实现K-NN算法 - 学习对MNIST图像进行分类
数据：
对于此示例，我们将使用无处不在的MNIST数据集。MNIST数据集是机器学习中最常用的数据集之一，因为它易于实现，且是作为证明模型的可靠方法。
MNIST是70,000个手写数字的数据集，编号为0-9。没有两个手写数字是相同的，有些可能很难正确分类。对MNIST进行分类的人类基准测试精度约为97.5％，因此我们的目标是击败它！
算法：
我们将使用Scikit-Learn Python库中的KNeighborsClassifier()来开始。这个函数需要很多参数，但在这个例子中我们只需要担心一些。具体来说，我们只传递n_neighbors参数的值（这是k值）。weights参数给出了模型使用的投票系统的类型，其中默认值是uniform，这意味着在对p进行分类时，每个k点的权重相等。algorithm参数也将保留其默认值auto，因为我们希望Scikit-Learn找到用于对MNIST数据本身进行分类的最佳算法。
下面，我嵌入了一个Jupyter笔记本，用Scikit-Learn构建K-NN分类器。开始了！
用基于Scikit-Learn的K-NN分类器来分类MNIST
让我们通过导入所需的库直接进入它。
- 输入【1】
import numpy as np
from sklearn import datasets, model_selection
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report
mnist = datasets.fetch_mldata('MNIST original')
data, target = mnist.data, mnist.target
# 确保所有内容都已正确导入
data.shape, target.shape
- 输出【1】
((70000, 784), (70000,))((70000
构建数据集
让我们通过制作一些我们可以使用的不同数据集来开始构建K-NN模型。 我们将创建一个可以获取我们想要的数据集大小的函数并将其返回。 模型将使用这些数据集对我们的测试数据进行分类。
让我们在下面构建一些模型的存储数据集。
- 输入【2】
# 创建一个与MNIST大小一致的索引数组，用于制作数据集。
# 该数组是随机排列的，因此我们可以用它来加扰MNIST数据。
indx = np.random.choice(len(target), 70000, replace=False)
# method for building datasets to test with
def mk_dataset(size):
"""
生成“size”大小的数据集，并返回该数据集图像和目标。
这用于生成将由模型存储的数据集，并用于试验不同的存储数据集大小。
"""
train_img = [data[i] for i in indx[:size]]
train_img = np.array(train_img)
train_target = [target[i] for i in indx[:size]]
train_target = np.array(train_target)
return train_img, train_target
很好。 现在，我们将使用此函数构建两个不同大小的数据集，我们可以使用这些数据集来查看模型在进行分类时具有不同数据量时的性能。提示：制作一个较小的数据集就像在教程中的图像中取走一些点一样，您仍然可以进行分类，但模型使用的点更少了，从而使得更难进行正确的分类。
- 输入【3】
# 让我们创建一个大小为50,000的数据集，这意味着该模型将有50,000个数据点来比较每个数据点。
# 新点是分类的点
fifty_x, fifty_y = mk_dataset(50000)
fifty_x.shape, fifty_y.shape
- 输出【3】
((50000, 784), (50000,))
- 输入【4】
# 让我们再做一个20000大小的数据集，看看当我们使用那个时分类准确度如何降低。
twenty_x, twenty_y = mk_dataset(20000)
twenty_x.shape, twenty_y.shape
- 输出【4】
((20000, 784), (20000,))
注意这些数据集如何使模型需要标签。 模型需要这些标签来理解每个点代表什么，并且因此可以将我们尝试分类的点（p）放入特定的类中，而不是说“这就是这一点最相似的”，你做不了多少。
现在我们将构建一个大小为10,000的测试数据集。 这是我们将在模型中运行的数据集，并查看模型在对测试数据集中的每个点进行分类时的作用。
- 输入【5】
# 构建模型测试数据集。
test_img = [data[i] for i in indx[60000:70000]]
test_img1 = np.array(test_img)
test_target = [target[i] for i in indx[60000:70000]]
test_target1 = np.array(test_target)
test_img1.shape, test_target1.shape
- 输出【5】
((10000, 784), (10000,))
很好！ 现在我们已经完成了所有数据设置，我们可以开始使用K-NN模型了！
建立模型
我们将首先将Scikit-Learn K-NN模型放入一个函数中，以便我们可以轻松调用它并进行调整。
- 输入【6】
def skl_knn(k, test_data, test_target, stored_data, stored_target):
"""
k: 在分类中使用的邻居数量
test_data: 用于测试分类器的数据/目标
stored_data: 用于对test_data进行分类的数据/目标
"""
classifier = KNeighborsClassifier(n_neighbors=k)
classifier.fit(stored_data, stored_target)
y_pred = classifier.predict(test_data)
print(classification_report(test_target, y_pred))
测试
现在让我们看看这个模型如何在两个不同的测试集上执行。
- 输入【7】
%%time
# 存储的数据集大小为50,000
skl_knn(5, test_img1, test_target1, fifty_x, fifty_y)
precision recall f1-score support
0.0 0.98 0.99 0.99 997
1.0 0.96 1.00 0.98 1118
2.0 0.98 0.96 0.97 1041
3.0 0.96 0.98 0.97 1036
4.0 0.98 0.97 0.97 966
5.0 0.97 0.97 0.97 924
6.0 0.98 0.99 0.99 918
7.0 0.96 0.98 0.97 1053
8.0 0.99 0.92 0.96 977
9.0 0.96 0.96 0.96 970
avg / total 0.97 0.97 0.97 10000
CPU times: user 8min, sys: 244 ms, total: 8min 1s
Wall time: 8min 1s
- 输入【8】
%%time
# 存储的数据集大小为20,000
skl_knn(5, test_img1, test_target1, twenty_x, twenty_y)
precision recall f1-score support
0.0 0.98 0.99 0.98 997
1.0 0.95 0.99 0.97 1118
2.0 0.98 0.94 0.96 1041
3.0 0.94 0.97 0.95 1036
4.0 0.97 0.95 0.96 966
5.0 0.96 0.96 0.96 924
6.0 0.98 0.99 0.99 918
7.0 0.95 0.97 0.96 1053
8.0 0.99 0.90 0.94 977
9.0 0.93 0.95 0.94 970
avg / total 0.96 0.96 0.96 10000
CPU times: user 3min 24s, sys: 240 ms, total: 3min 24s
Wall time: 3min 24s
甜美！ 我们的模型与人类相匹配！ 如您所见，当模型有更多数据可用时（50,000而不是20,000点），它表现更好。 关于这个模型的一个更显著的事情是，它是如此简单，但却可以捕捉人类层面上独特图像之间的复杂关系。
要查看更深入的分析，请访问此GitHub存储库。
太棒了！我们使用Scikit-Learn构建了一个非常简单的K近邻模型，它在MNIST数据集上获得了非凡的性能。
问题是啥呢？嗯，它花了很长时间才对这些点进行分类（两个数据集分别为8分钟和近4分钟），具有讽刺意味的是，K-NN仍然是最快的分类方法之一。必须有一个更快的方式......
建立更快的模型
大多数K-NN模型使用欧几里德或曼哈顿距离作为首选距离度量。这些指标很简单，在各种情况下都表现良好。
很少使用的一个距离度量是余弦相似度 。余弦相似度通常不是首选距离度量，因为它违反了三角不等式，并且不适用于负数据。然而，余弦相似性对于MNIST来说是完美的。它快速，简单，并且比MNIST上的其他距离指标具有稍微更好的准确性。但要真正实现最佳性能，我们必须编写自己的K-NN模型。在我们自己制作K-NN模型之后，我们应该获得比Scikit-Learn模型更好的性能，甚至可能更好的准确性。让我们看看下面的笔记本，我们建立自己的K-NN模型。
建立更快的KNN分类器
在这个笔记本中，我们将构建一个简约的K-NN模型，该模型使用余弦相似度作为距离度量来对MNIST图像进行分类，以试图找到比Scikit-Learn K-NN模型更快的速度和/或精度。
首先导入所需的库，并构建与Scikit-Learn K-NN笔记本中相同的数据集。
- 输入【1】
import numpy as np
import heapq
from collections import Counter
from sklearn.metrics.pairwise import cosine_similarity
from sklearn import datasets, model_selection
from sklearn.metrics import classification_report
mnist = datasets.fetch_mldata('MNIST original')
data, target = mnist.data, mnist.target
# make sure everything was correctly imported
data.shape, target.shape
- 输出【1】
((70000, 784), (70000,))
使用与Scikit-Learn K-NN笔记本中相同的方法设置完全相同的数据集。
- 输入【2】
# 创建一个与MNIST大小一致的索引数组，用于制作数据集。
# 该数组是随机排列的，因此我们可以用它来加扰MNIST数据。
indx = np.random.choice(len(target), 70000, replace=False)
# method for building datasets to test with
def mk_dataset(size):
"""makes a dataset of size "size", and returns that datasets images and targets
This is used to make the dataset that will be stored by a model and used in
experimenting with different stored dataset sizes
"""
train_img = [data[i] for i in indx[:size]]
train_img = np.array(train_img)
train_target = [target[i] for i in indx[:size]]
train_target = np.array(train_target)
return train_img, train_target
- 输入【3】
# 让我们创建一个大小为50,000的数据集，这意味着该模型将有50,000个数据点来比较每个数据点.
# 新点是要分类的点。
fifty_x, fifty_y = mk_dataset(50000)
fifty_x.shape, fifty_y.shape
- 输出【3】
((50000, 784), (50000,))
- 输入【4】
# 让我们再做一个20000大小的数据集，看看当我们使用此数据集时分类准确度如何降低。
twenty_x, twenty_y = mk_dataset(20000)
twenty_x.shape, twenty_y.shape
- 输出【4】
((20000, 784), (20000,))((20000
- 输入【5】
# 构建模型测试数据集
test_img = [data[i] for i in indx[60000:70000]]
test_img1 = np.array(test_img)
test_target = [target[i] for i in indx[60000:70000]]
test_target1 = np.array(test_target)
test_img1.shape, test_target1.shape
- 输出【5】
((10000, 784), (10000,))
构建模型
下面我们将创建函数cos_knn()，它将作为我们最新和最好的MNIST K-NN分类器。 请按照函数中的注释获取有关其工作原理的详细信息。
- 输入【6】
def cos_knn(k, test_data, test_target, stored_data, stored_target):
"""
k: 用于投票的邻居数量
test_data: 一组未观察到的图像进行分类
test_target: test_data的标签（用于计算精度）
stored_data: 已经观察到并可用于模型的图像
stored_target: stored_data的标签
"""
# 找到test_data中每个点与stored_data中每个其他点之间的余弦相似度。
cosim = cosine_similarity(test_data, stored_data)
# 获取stored_data中与任何给定test_data点最相似的图像的前k个索引。
top = [(heapq.nlargest((k), range(len(i)), i.take)) for i in cosim]
# 使用存储的目标值将索引转换为数字。
top = [[stored_target[j] for j in i[:k]] for i in top]
# 投票，并返回test_data中每个图像的预测
pred = [max(set(i), key=i.count) for i in top]
pred = np.array(pred)
# 打印表，使用test_target给出分类器准确性。
print(classification_report(test_target, pred))
测试模型
现在，就像Scikit-Learn K-NN模型一样，我们将在两个数据集上测试cos_knn()模型，看看它如何比Scikit-Learn K-NN模型更好。
- 输入【7】
%%time
# 存储的数据集大小为50,000
cos_knn(5, test_img1, test_target1, fifty_x, fifty_y)
precision recall f1-score support
0.0 0.97 0.99 0.98 992
1.0 0.98 0.99 0.98 1123
2.0 0.98 0.98 0.98 984
3.0 0.98 0.97 0.97 1089
4.0 0.99 0.97 0.98 1016
5.0 0.99 0.96 0.97 857
6.0 0.98 0.99 0.98 979
7.0 0.97 0.96 0.97 1001
8.0 0.96 0.96 0.96 993
9.0 0.95 0.97 0.96 966
avg / total 0.97 0.97 0.97 10000
CPU times: user 5min 17s, sys: 1.21 s, total: 5min 18s
Wall time: 4min 59s
- 输入【8】
%%time
# 存储的数据集大小为20,000
cos_knn(5, test_img1, test_target1, twenty_x, twenty_y)
precision recall f1-score support
0.0 0.96 0.99 0.98 992
1.0 0.96 0.98 0.97 1123
2.0 0.97 0.97 0.97 984
3.0 0.97 0.95 0.96 1089
4.0 0.98 0.95 0.97 1016
5.0 0.97 0.94 0.96 857
6.0 0.97 0.99 0.98 979
7.0 0.96 0.96 0.96 1001
8.0 0.96 0.95 0.95 993
9.0 0.94 0.96 0.95 966
avg / total 0.97 0.97 0.97 10000
CPU times: user 2min 9s, sys: 528 ms, total: 2min 9s
Wall time: 2min 1s
太棒了！ 我们自己构建的余弦相似度模型优于Scikit-Learn K-NN！ 值得注意的是，该模型在分类速度（相当大的幅度）和准确性方面均优于Scikit-Learn K-NN，而且模型非常简单！
有关模型如何工作以及如何在许多不同情况下与Scikit-Learn K-NN比较的进一步分析，请参阅此GitHub存储库。
如笔记本所示，我们自己的K-NN模型在分类速度（相当大的幅度）和准确性（一个数据集上提高1％）方面优于Scikit-Learn K-NN！现在，我们可以在实践中继续实施这个模型，因为我们已经开发出了一种真正快速的算法。
结论
说了很多，但我们学到了几个宝贵的经验教训。首先，我们了解了K-NN的工作原理，以及如何轻松实现它。但最重要的是，我们了解到，始终考虑你要解决的问题以及可用于解决该问题的工具非常重要。有时，最好在解决问题时花时间尝试 - 并且是的，建立自己的模型。正如在笔记本中证明的那样，它可以带来巨大的收益：我们的第二个专有模型使用了1.5-2倍的加速，节省了使用该模型的实体很多时间。
如果你想了解更多信息，我建议你查看这个GitHub存储库 ，在这里你可以找到两个模型之间更全面的分析，以及一些关于我们更快的K-NN模型的更有趣的功能！
