K-NN (k -最近邻)是最简单的机器学习算法之一，可以直观地理解。它既用于分类任务，又用于回归任务。

K-NN是一种非参数的、惰性的方法。

• 之所以称为非参数方法，是因为它对底层数据分布没有任何假设。在线性回归中，假设数据通常是提取的，这是不可能的，在这种情况下，线性回归没有更好的表现。如果我们对数据的分布不确定，我们可以使用K-NN。
• 它被称为惰性方法，因为在训练阶段它不从训练数据中学习。只有在测试阶段，它才开始寻找离测试点最近的邻居，这在计算上非常昂贵。

但它与K-means算法有何不同?

K-NN是用于分类和回归任务的监督学习算法，而K-means是用于聚类任务的非监督学习算法。

K-nearest neighbors with k=3

目标:

给定一个测试点' Xq '，我们需要确定类标签(如果是分类任务)或实际值(如果是回归任务)

直觉:

如果几何上接近Xq的大多数点都是正的，那么类标签就会是正的。

但是如何找到几何上接近的点呢?

我们使用欧几里德， manhattan, minkowski, 余弦相似度等距离度量来找到K个最近邻。

距离度量的选择是主观的，欧几里得距离对于高维数据来说是一种维度诅咒。与wise一样，我们需要根据数据类型和使用情况选择距离度量。

让我们看看如何逐步实现K-NN。

K-NN算法步骤：

1. 我们将数据分为训练（m点）和测试（n点）集。
2. 从测试集中获取数据点并测量从测试集中的点到训练集中的每个点的距离，我们得到“m”距离。
3. 按升序对获得的“m”距离进行排序。
4. 从排序的距离及其相应的标签中选择顶部的“K”点。
5. 如果大多数标签是正的，那么测试点的预测标签是正的，反之亦然。
6. 从步骤2开始重复，直到我们预测所有测试设定点的标签。

没关系，但是如何执行回归任务？

回归K-NN:

而不是像在分类任务中那样进行多数投票。对于回归，我们需要对顶部K点的相应目标值取均值或中位数。

从这篇文章开始你就在谈论K个最近邻。我们如何选择“K”?

选择K:

我们通常通过交叉验证来选择最优的K。

记住几点:

• 如果我们取较低的K值，我们的模型就会过度拟合。
• 如果我们取高的K值，我们的模型就会underfit。

如果我取K=m(训练集中没有数据点)会发生什么??

不管测试数据点如何，它只对测试集中的所有点进行正或负预测。假设在我们的训练集中有m1正数据点和m2负数据点，其中m1+m2 = m。

• 如果m1>m2，模型将对测试集中的所有点进行正预测。
• 如果m2>m1，模型对测试集中所有点的预测均为负值。

如果您使用K- nn进行二元分类(2个类)或具有偶数个类(2、4、6、8…)，那么最好选择带有奇数的K，以避免并列。同样的道理，如果有奇数个类(3 5 7 9…)，选择K为偶数。

异常值的影响：

• 如果“K”值较低，则模型容易受到异常值的影响。
• 如果“K”值很高，则模型对异常值很稳健。

为什么会这样？

假设K = 1，假设我们的测试点附近有1个异常值，然后模型预测对应于异常值的标签。在同样的场景中，如果我们采用K = 7，则在测试点附近将有其他6个最近邻（不是异常值）和1个异常值，当我们采取多数投票时，我们倾向于基于6个最近邻居得到结果。

规模的影响：

如果特征范围非常不同（如f1值范围在0-1000和f2值范围在0-1），则K-NN中存在比例影响。在构建模型之前，最好应用列标准化或归一化。

决策树和随机森林等算法与比例无关。

使用Scikit-learn实现代码：

#Divide the data into X_train,Y_train and X_test,Y_test

from sklearn.model_selection import GridSearchCV

from sklearn.neighbors import KNeighborsClassifier

from sklearn.metrics import accuracy_score

#Using Grid search cv to find the optimal K(n_neighbors)

neigh = KNeighborsClassifier()

parameters = {'n_neighbors':(1,3,5,7,9,11)}

gs_clf = GridSearchCV(neigh, parameters, cv = 5)

gs_clf.fit(X_train,Y_train)

#To select optimal K

optimal_k = gs_clf.best_params_.get('n_neighbors')

print(optimal_k)

#Use the obtained optimal_k to train our model

knn_final = KNeighborsClassifier(n_neighbors = optimal_k)

knn_final.fit(X_train,Y_train)

predictions_test = knn_final.predict(X_test)

predictions_train = knn_final.predict(X_train)

#The test and train accuracy

test_acc = accuracy_score(Y_test, predictions_test)*100

train_acc = accuracy_score(Y_train, predictions_train)*100

K-NN的优点：

• 它易于理解且易于实现。
• 非参数性质有时可能是有用的。
• K-NN可以轻松扩展，用于多级分类。

K-NN的缺点：

• 测试阶段计算量很大，不能用于低延迟要求。
• 如果我们使用非常常见的欧几里德距离测量，则会受到更高维数据（d> 500）的维数诅咒的影响。