K近邻算法，简称K-NN。在当今的深度学习时代，这种经典的机器学习算法常常被低估。本教程将带您使用Scikit-Learn构建K最近邻算法并将其应用于MNIST数据集。然后，作者将带大家构建自己的K-NN算法，开发出比Scikit-LearnK-NN更准确、更快的算法。1.K近邻分类模型K近邻算法是一种易于实现的有监督机器学习算法，其分类性能的鲁棒性不差。K-NN的最大优点之一是它是一种惰性算法，即该模型无需训练即可对数据进行分类，这与其他需要训练的ML算法（如SVM、回归和多层感知器）不同。K-NN的工作原理为了对给定的数据点p进行分类，K-NN模型首先使用某种距离度量将p与其数据库中的其他点进行比较。距离度量有点像欧几里得距离，一个简单的函数，它将两个点作为输入并返回这两个点之间的距离。因此，可以假设距离较小的两个点比距离较大的两个点更相似。这就是K-NN的核心思想。此过程返回一个无序数组，其中数组中的每一项代表模型数据库中p和n个数据点之间的距离。所以返回数组的大小是n。KforK-NearestNeighbors的含义是：k是一个任意值（通常在3-11之间），表示模型在对p进行分类时应该考虑多少个最相似的点。然后模型会记录这k个最相似的值，并使用投票算法来决定p属于哪个类，如下图所示。上图中K-NN模型的k值为3，箭头所指的中心点为p，算法会对该点进行分类。可以看到，圆圈中的三个点就是距离p最近或者说最相似的三个点。因此，使用简单的投票算法，p将被归类为“白色”，因为白色在k个最相似的值中占多数。凉爽的！但令人惊讶的是，这个简单的算法在某些情况下可以取得不错的结果，并且可以应用于各种各样的问题，我们接下来将介绍这些问题。2.在Scikit-Learn中实现K-NN算法对MNIST图像进行分类1.数据对于这个例子，我们将使用常见的MNIST数据集。MNIST数据集是机器学习中最常用的数据集之一，因为它易于实现并且是验证我们模型的可靠方法。MNIST是一个包含70,000个手写数字0-9的数据集。没有两个手写数字是相同的，有些可能很难正确分类。2.算法我们从Scikit-LearnPython库的KNeighborsClassifier()函数开始。这个函数有很多参数，但是在这个例子中我们只需要用到几个参数。具体来说，我们只会传递n_neighbors参数的值（即k值）。weights参数给出了模型使用的投票算法的类型，其中默认值是统一的。这意味着在对p进行分类时，k个点中的每一个都具有相同的权重。algorithm参数也将使用默认值auto，因为我们希望Scikit-Learn自动找到对MNIST数据进行分类的最佳算法。以下是使用Scikit-Learn构建K-NN分类器的JupyterNotebook：Scikit-Learn的K-nearestneighboralgorithmforMNISTNotebook地址：https://gist.github.com/samgrassi01/82d0e5f89daac3e65531a6ef497cc129#file-skl-knn-ipynb我们直接从导入所需的库开始。在[1]:importnumpyasnpfromsklearnimportdatasets,model_selectionfromsklearn.neighborsimportKNeighborsClassifierfromsklearn.metricsimportclassification_reportmnist=datasets.fetch_mldata('MNISToriginal')数据,target=mnist.data,mnist.target#makesureeverythingwascorrectlyimporteddata.shape,target.shapeOut[1]:,(74000),(70000,))(1)构建数据集我们通过制作不同的数据集来构建K-NN模型。我们将创建一个函数，它接受一定大小的数据集并返回数据集的大小。In[2]:#makeanarrayofindicesthesizeofMNISTtouseformakingthedatasets.#Thisarrayisinrandomorder,sowecanuseittoscrambleuptheMNISTdataindx=np.random.choice(len(target),70000,replace=False)#methodforbuildingdatasetstotestwithdefmk_dataset(size):"""makesadatasetofsize"size",andreturnsthatdatasetsimagesandtargetsThisisusedtomakethedatasetthatwillbestoredbyamodelandusedinexperimentingwithdifferentstoreddatasetsizes"""train_img=[data[i]foriinindx[:size]]train_img=np.array(train_img)train_target=[target[i]foriinindx[:size]]train_target=np.array(train_target)不错。现在我们将使用此函数构建两个不同大小的数据集，以查看模型在不同数据集上的表现。提示：当制作较小的数据集时，仍然可以进行分类，但模型的数据会变少，这可能会导致错误分类。In[3]:#lettsmakeadatasetofsize50,000,meaningthemodelwillhave50,000datapointstocompareeach#newpointitistoclassifytofifty_x,fifty_y=mk_dataset(50000)fifty_x.shape,fifty_y.shapeOut[3]:((50000,784),(50000,))In[4]#letsmakeonemoreofsize20,000并查看当我们使用那个网络wenty_x,twenty_y=mk_dataset(20000)twenty_x.shape,twenty_y.shapeOut[4]:((20000,784),(20000,))时分类精度如何降低，请注意此数据如何匹配模型的标签。模型需要这些标签来理解每个点代表什么，所以它可以把我们要分类的点放在特定的类中，而不是说“这是与要分类的点最相似的类”。现在我们将构造一个大小为10000的测试集。In[5]:#buildmodeltestingdatasettest_img=[data[i]foriinindx[60000:70000]]test_img1=np.array(test_img)test_target=[target[i]foriinindx[60000:70000]]test_target1=np.array(test_target)test_img1.shape,test_target1.shapeOut[5]:((10000,784),(10000,))不错！现在我们已经完成了所有的数据处理，我们可以开始构建K-NN模型了！(2)为了构建模型，我们首先将Scikit-LearnK-NN模型放在一个函数中，以便于调用和调整。在[6]:defskl_knn(k,test_data,test_target,stored_data,stored_target):"""k:numberofneighborstouseinclassificationtest_data:thedata/targetsusedtotesttheclassifierstored_data:thedata/targetsusedtoclassifythetest_data"""classifier=KNeighborsClassifier(n_torgetsused_arget=k))y_pred=分类器.预测(test_data)print(classification_report(test_target,y_pred))(3)测试现在让我们看看这个模型如何在两个不同的测试集上工作。In[7]:%%time#storeddatasetsizeof50,000skl_knn(5,test_img1,test_target1,fifty_x,fifty_y)In[8]:%%time#storeddatasetsizeof20,000skl_knn(5,test_img1,test_target1,twenty_x,twenty_y)好的！我们上的模型，跟人眼识别差不多！如您所见，当模型有更多数据可供使用时（50,000个而不是20,000个点），它的性能会更好。更引人注目的是，它非常简单，可以在人类层面捕捉不同图像之间的复杂关系。如需更详细的分析，请访问此GitHub存储库：https://github.com/samgrassi01/Cosine-Similarity-Classifier。惊人的！我们使用Scikit-Learn构建了一个非常简单的K最近邻模型，该模型在MNIST数据集上表现惊人。不足之处？对点进行分类需要很长时间（两个数据集分别需要8和4分钟），具有讽刺意味的是，K-NN仍然是最快的分类方法之一。我们必须有一个更快的方法。3.构建更快的模型大多数K-NN模型使用欧氏距离或曼哈顿距离作为首选距离度量。这些指标非常简单，适用于各种情况。另一个很少使用的标准距离度量是余弦相似度。余弦相似度通常不是首选距离度量，因为它违反了三角不等式并且不适用于负数。然而，余弦相似度对MNIST非常有用。它快速、简单，并且比MNIST中应用的其他距离测量更准确。但是，为了获得最好的性能，我们需要自己编写K-NN模型。那么，我们应该能够获得比Scikit-Learn模型更高的性能，甚至更高的准确率。下面看一下搭建的K-NN模型的Notebook：BuildafasterKNNclassifierNotebook地址：https://gist.github.com/samgrassi01/15a1fe53dcde8813eed9367b103676b2#file-cos-knn-ipynb在这个notebook中，我们将构建一个简单的K-NN模型，该模型使用余弦相似度作为距离度量对MNIST图像进行分类，以尝试找到更快或更准确的模型。首先，您需要导入所需的库，然后构建与Scikit-LearnK-NN笔记本相同的数据集。在[1]中：importnumpyasnpimportheapqfromcollectionsimportCounterfromsklearn.metrics.pairwiseimportcosine_similarityfromsklearnimportdatasets，model_selectionfromsklearn.metricsimportclassification_reportmnist=datasets.fetch_mldata（'MNISToriginal'）数据，target=mnist.data，mnist.target#makesureeverythingwascorrectlyimporteddata.shape[0，target.shapeedOut[0]（0，目标。784),(70000,))使用与Scikit-LearnK-NN笔记本相同的方法，具有完全相同的数据集设置。In[2]:#makeanarrayofindicesthesizeofMNISTtouseformakingthedatasets.#Thisarrayisinrandomorder,sowecanuseittoscrambleuptheMNISTdataindx=np.random.choice(len(target),70000,replace=False)#methodforbuildingdatasetstotestwithdefmk_dataset(size):"""makesadatasetofsize"size",andreturnsthatdatasetsimagesandtargetsThisisusedtomakethedatasetthatwillbestoredbyamodelandusedinexperimentingwithdifferentstoreddatasetsizes"""train_img=[数据[i]foriinindx[:size]]train_img=np.array(train_img)train_target=[target[i]foriinindx[:size]]train_target=np.array(train_target)returntrain_img,train_targetIn[3]:#lettsmakeadatasetofsize50,000,meaningthemodelwillhave50,000datapointstocompareeach#newpointitistoclassifytofifty_x,fifty_y=mk_dataset(50000)fifty_x.shape,fifty_y.shapeOut[3]:((50000,784),(50000,))In[4]:#letsmakeonemoreofsize20,000andseehowclassificationaccuracydecreaseswhenweusethatonetwenty_x,twenty_y=mk_dataset(20000)twenty_x.shape,twenty_y.shapeOut[4]:((20000,784),(20000,))In[5]:#buildmodeltestingdatasettest_img=[data[i]foriinindx[60000:70000]]test_img1=np.array(test_img)test_target=[target[i]foriinindx[60000:70000]]test_target1=np.array(test_target)test_img1.shape,test_target1.shapeOut[5]:((10000,784),(10000,))1。.构建下面的模型，我们创建函数cos_knn()作为MNIST数据集的分类器。您可以使用函数的注释来了解它是如何工作的。In[6]:defcos_knn(k,test_data,test_target,stored_data,stored_target):"""k:numberofneighborstouseforvotingtest_data:asetofunobservedimagestoclassifytest_target:thelabelsforthetest_data(forcalculatingaccuracy)stored_data:theimagesalreadyobservedandavailabletothemodelstored_target:labelsforstored_data"""#findcosinesimilarityforeverypointintest_databetweeneveryotherpointinstored_datacosim=cosine_similarity(test_data,stored_data)#gettopkindicesofimagesinstored_datathataremostsimilartoanygiventest_datapointtop=[(heapq.nlargest((k),range(len(i)),i.take))foriincosim]#convertindicestonumbersusingstoredtargetvaluestop=[[stored_target[j]forjini[:k]]foriintop]#vote,andreturnpredictionforeveryimageintest_datapred=[max(set(i),key=i.count)foriintop]pred=np.array(pred)#printtablegivingclassifieraccuracyusingtest_targetprint(classification_report(test_target,pred))2.测试模型现在，就像Scikit-LearnK-NN模型一样，我们在两个数据集上测试cos_knn()模型并查看其性能In[7]:%%time#storeddatasetsizeof50,000cos_knn(5,test_img1,test_target1,fifty_x,fifty_y)In[8]:%%time#storeddatasetsizeof20,000cos_knn(5,test_img1,test_target1,twenty_x,twenty_y)怎么样？余弦相似度模型的性能超过Scikit-LearnK-NN！值得一提的是，模型的分类速度和准确率都优于Scikit-LearnK-NN（速度有了很大的提升），而且模型但是非常简单！要进一步分析该模型的工作原理，以及为什么它在许多不同情况下优于Scikit-LearnK-NN模型，请参阅此GitHub存储库：https://github.com/samgrassi01/Cosine-Similarity-Classifier。如notebook所示，K-NN模型在分类速度和准确率上均优于Scikit-LearnK-NN，速度提升较大，在一个数据集上准确率提升1%。既然如此，我们就可以在实践中继续沿用这个模型。4.结论首先，我们了解了K-NN的工作机制以及如何轻松实现它。但最重要的是，我们发现始终考虑需要解决的问题和解决问题的工具很重要。有时候，在解决一个问题的过程中，最好花点时间练习——当然，你也需要建立自己的模型。正如笔记本中所展示的那样，它有很大的好处：我们的第二个专有模型获得了1.5-2倍的加速，节省了大量时间。原文链接：https://towardsdatascience.com/building-improving-a-k-nearest-neighbors-algorithm-in-python-3b6b5320d2f8【本文为《机器之心》专栏原文翻译，微信♂》《机器之心》（id：almosthuman2014）》】点此阅读作者更多好文
