在Python中构建和改进K最近邻算法
K-最近邻居算法，简称K-NN，是一种经典的机器学习工作算法，在深度学习的当天经常被忽略。在本教程中，我们将在Scikit-Learn中构建一个K-NN算法，并在MNIST数据集上运行它。从那里开始，我们将建立自己的K-NN算法，希望能够开发出比Scikit-Learn K-NN更好的分类精度和分类速度。
K-最近邻分类模型
K-最近邻居算法是一种有监督的机器学习算法，其易于实现，并且具有进行可靠分类的能力。K-NN最大的优点之一就是它是一个懒惰的学习者。这意味着该模型不需要培训，并且可以对数据进行分类，而不像其他ML兄弟姐妹，如SVM，回归和多层感知。
K-NN如何工作
为了对某个给定的数据点p进行分类，一个K-NN模型将首先使用某个距离度量将p与其数据库中可用的每个其他点进行比较。距离度量是诸如欧几里得距离之类的东西，一个简单的函数需要两个点，并返回这两个点之间的距离。因此，可以假设它们之间距离较小的两个点比它们之间具有较大距离的两个点更类似。这是K-NN背后的核心思想。
该过程将返回一个无序数组，其中数组中的每个条目都保存p与模型数据库中n个数据点之一之间的距离。所以返回的数组的大小为n。这是K-近邻K个部分来自于：ķ是告诉模型选择（通常是3-11之间）的一些任意值多少最相似点p时，分级应考虑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％，因此我们的目标是打败它！
算法：
我们将使用KNeighborsClassifier()Scikit-Learn Python库开始。这个函数需要很多参数，但在这个例子中我们只需要担心几个参数。具体来说，我们只会传递一个n_neighbors参数值（这是k值）。该weights参数给出由模型，其中，所述默认值是用于表决系统的类型uniform，这意味着每一个的ķ个分级被均等地加权p。因为我们希望Scikit-Learn找到用于归类MNIST数据本身的最佳算法，所以该algorithm参数也将保留其默认值auto。
我用Scikit-Learn构建K-NN分类器。分类这些点需要很长时间（两个数据集分别为8分钟和4分钟），具有讽刺意味的是，K-NN仍然是最快的分类方法之一。
建立更快的模型
大多数K-NN模型使用欧几里得或曼哈顿距离作为前往距离度量。这些指标非常简单，适用于各种各样的情况。很少使用的一个距离度量是余弦相似度。余弦相似度通常不是前往距离度量，因为它违反了三角不等式，并且不适用于负数据。但是，余弦相似性对于MNIST是完美的。它快速，简单，并且比MNIST上的其他距离度量准确度稍高。但要真正实现最佳性能，我们必须编写我们自己的K-NN模型。在自己制作K-NN模型之后，我们应该获得比Scikit-Learn模型更好的性能，甚至可能更好的准确性。
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
((70000, 784), (70000,))
设置数据
# make an array of indices the size of MNIST to use for making the data sets.
# This array is in random order, so we can use it to scramble up the MNIST data
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
fifty_x, fifty_y = mk_dataset(50000)
fifty_x.shape, fifty_y.shape
((50000, 784), (50000,))
twenty_x, twenty_y = mk_dataset(20000)
twenty_x.shape, twenty_y.shape
((20000, 784), (20000,))
# build model testing dataset
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
((10000, 784), (10000,))
构造模型
def cos_knn(k, test_data, test_target, stored_data, stored_target):
"""k: number of neighbors to use for voting
test_data: a set of unobserved images to classify
test_target: the labels for the test_data (for calculating accuracy)
stored_data: the images already observed and available to the model
stored_target: labels for stored_data
"""
# find cosine similarity for every point in test_data between every other point in stored_data
cosim = cosine_similarity(test_data, stored_data)
# get top k indices of images in stored_data that are most similar to any given test_data point
top = [(heapq.nlargest((k), range(len(i)), i.take)) for i in cosim]
# convert indices to numbers using stored target values
top = [[stored_target[j] for j in i[:k]] for i in top]
# vote, and return prediction for every image in test_data
pred = [max(set(i), key=i.count) for i in top]
pred = np.array(pred)
# print table giving classifier accuracy using test_target
print(classification_report(test_target, pred))
测试模型
%%time
# stored data set size of 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
我们自己制作的K-NN模型在分类速度（相当大的保证金）和准确性（一个数据集提高1％）方面都超过了Scikit-Learn K-NN！