k最近邻分类器是一种机器学习算法，它将一个新数据点分配给其k个最近邻中最常见的类在本教程中，您将学习使用Python构建和应用此分类器的基本步骤
又是新的一天，又是一个经典算法：k-最近邻算法。和朴素贝叶斯分类器一样，它是一个解决分类问题相当简单的方法。这个算法很直观，训练时间也无与伦比，适合你在机器学习生涯刚刚开始的时候学习。但是，预测速度非常慢，尤其是对于大型数据集而言。对于具有许多特征的数据集，由于维数灾难的存在，性能也可能不令人满意。
在本文中，您将学习：
- k-最近邻分类器的工作原理
- 为什么它被设计成这样
- 为什么它具有这些严重的缺点，以及
- 如何使用NumPy在Python中实现它
由于我们将以scikit-learn兼容的方式实现分类器，因此也值得查看我的文章“构建自己的自定义scikit-learn回归器”。但是，scikit-learn的开销非常小，您应该能够跟随本文。
您可以在我的Github上找到代码。
理论
这个分类器的主要思想是惊人的简单。它直接源于分类的基本问题：
给定一个数据点x，它属于某个类别c的概率是多少？
用数学语言来说，我们寻找条件概率p(c|x)。尽管朴素贝叶斯分类器试图使用一些假设直接模拟这个概率，但是还有另一种直观的方法来计算这个概率——概率的频率论观点。
关于概率的幼稚观点
好吧，那现在是什么意思呢？让我们考虑以下简单的例子：你掷一个六面的、可能被篡改的骰子，并想计算掷出六的概率，即p(掷出号码6)。怎么做呢？你掷骰子n次，并记录它显示出六的次数。如果你看到数字6出现了k次，那么你就会说看到数字6的概率是大约k/n。这里没有什么新奇的东西，对吧？
现在，想象一下我们要计算一个条件概率，例如
p(掷出号码6|掷出偶数)
你不需要贝叶斯定理来解决这个问题。只需再掷一次骰子，并忽略所有奇数的结果。这就是条件的作用：过滤结果。如果你掷骰子n次，看到m个偶数，其中k个是6，那么上面的概率就是大约k/m，而不是k/n。
激励k-最近邻算法
回到我们的问题。我们想要计算p(c|x)，其中x是包含特征的向量，c是某个类别。就像在掷骰子的例子中一样，我们
- 需要大量的数据点，
- 过滤出具有特征x的数据点，
- 检查这些数据点属于类别c的频率。
相对频率是我们对概率p(c|x)的猜测。
你看到这里的问题了吗？
通常，我们没有许多具有相同特征的数据点。通常只有一个或两个。例如，想象一个具有两个特征的数据集：人的身高（以厘米为单位）和体重（以千克为单位）。标签是男性或女性。因此，x=(x?,x?)，其中x?是身高，x?是体重，c可以取值为男性或女性。让我们看一些虚拟数据：
由于这两个特征是连续的，拥有两个甚至几百个数据点的概率是微不足道的。
另一个问题：如果我们想要预测具有我们从未见过的特征的数据点的性别，例如(190.1, 85.2)？这就是预测实际上所涉及的内容。这就是为什么这种朴素方法不起作用的原因。相反，k-最近邻算法做的是：
它尝试用具有接近x特征的数据点而不是具有完全相同特征x的数据点来逼近概率p(c|x)。
从某种意义上说，它比较宽松。不需要等待很多身高=182.4和体重=92.6的人，并检查他们的性别，k-近邻算法允许考虑具有这些特征的人附近的人。算法中的k是我们考虑的人数，它是一个超参数。
这些是我们或网格搜索等超参数优化算法必须选择的参数。它们不是由学习算法直接优化的。
算法
我们现在拥有描述算法所需的一切。
训练：
- 以某种方式组织训练数据。在预测时，这个顺序应该能够为任何给定的数据点x提供k个最接近的点。
- 就这样了！😉
预测：
- 对于新的数据点x，在组织的训练数据中找到k个最接近的邻居。
- 合并这k个邻居的标签。
- 输出标签/概率。
迄今为止，我们无法实现这一点，因为我们必须填写很多空白。
- 组织意味着什么？
- 如何衡量接近程度？
- 如何聚合？
除了k的值外，这些都是我们可以选择的事情，不同的决策会给我们不同的算法。让我们简单地回答以下问题：
- 组织=只是保存训练数据集
- 接近程度=欧几里得距离
- 聚合=平均值
这需要一个例子。让我们再次检查具有人员数据的图片。
我们可以看到k = 5与黑色点最接近的数据点具有4个男性标签和一个女性标签。因此，我们可以输出黑色点所属的人实际上是4/5 = 80％的男性和1/5 = 20％的女性。如果我们更喜欢单个类作为输出，我们将返回男性。没问题！
现在，让我们来实现它。
实现
最难的部分是找到最接近点。
快速入门
让我们用Python的一个小例子来演示如何做到这一点。我们从
import numpy as np
features = np.array([[1, 2], [3, 4], [1, 3], [0, 2]])
labels = np.array([0, 0, 1, 1])
new_point = np.array([1, 4])
我们创建了一个由四个数据点组成的小数据集，以及另一个点。哪些是最接近的点？新点应该有标签0还是1？让我们找出来。输入
distances = ((features - new_point)**2).sum(axis=1)给出四个距离值distances=[4, 4, 1, 5]，它是从 new_point 到 features 中所有其他点的平方欧几里得距离。太好了！我们可以看到编号为3的点是最接近的，其次是编号为1和2的点。第四点最远。
我们如何从数组[4,4,1,5]中提取最接近的点？使用 distances.argsort()。结果是[2,0,1,3]，告诉我们具有索引2的数据点最小（出点三），然后是索引0的点，然后是索引1的点，最后是具有索引3的点是最大的。
请注意，argsort 将前四个元素放在 distances 中，然后是后四个元素。根据排序算法，这也可能相反，但是对于本入门文章，我们不需要关注这些细节。
如果我们想要最接近的三个邻居，例如，我们可以通过以下方式获取它们：
distances.argsort()[:3]并且这些最接近点对应的标签通过以下方式获取：
labels[distances.argsort()[:3]]我们得到[1, 0, 0]，其中1是最接近点（1，4）的标签，而零是属于下两个最近点的标签。
就这些，让我们进入真正的主题吧。
最终代码
您应该对代码非常熟悉。唯一的新函数是 np.bincount，它计算标签的出现次数。请注意，我首先实现了 predict_proba 方法来计算概率。方法 predict 只是调用这个方法，并使用 argmax 函数返回具有最高概率的索引（=类）。该类等待从0到C-1的类，其中C是类的数量。
免责声明：此代码未经过优化，仅用于教育目的。
import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin
from sklearn.utils.validation import check_X_y, check_array, check_is_fitted
class KNNClassifier(BaseEstimator, ClassifierMixin):
def __init__(self, k=3):
self.k = k
def fit(self, X, y):
X, y = check_X_y(X, y)
self.X_ = np.copy(X)
self.y_ = np.copy(y)
self.n_classes_ = self.y_.max() + 1
return self
def predict_proba(self, X):
check_is_fitted(self)
X = check_array(X)
res = []
for x in X:
distances = ((self.X_ - x)**2).sum(axis=1)
smallest_distances = distances.argsort()[:self.k]
closest_labels = self.y_[smallest_distances]
count_labels = np.bincount(
closest_labels,
minlength=self.n_classes_
)
res.append(count_labels / count_labels.sum())
return np.array(res)
def predict(self, X):
check_is_fitted(self)
X = check_array(X)
res = self.predict_proba(X)
return res.argmax(axis=1)就是这样！我们可以进行一小部分测试，看看它是否与scikit-learn k -nearest neighbor分类器一致。
测试代码
让我们创建另一个用于测试的小数据集。
from sklearn.datasets import make_blobs
import numpy as np
X, y = make_blobs(n_samples=20, centers=[(0,0), (5,5), (-5, 5)], random_state=0)
X = np.vstack([X, np.array([[2, 4], [-1, 4], [1, 6]])])
y = np.append(y, [2, 1, 0])它看起来像这样：
使用我们的分类器，k=3：
my_knn = KNNClassifier(k=3)
my_knn.fit(X, y)
my_knn.predict_proba([[0, 1], [0, 5], [3, 4]])我们得到：
array([[1. , 0. , 0. ],
[0.33333333, 0.33333333, 0.33333333],
[0. , 0.66666667, 0.33333333]])解读输出：第一个点100％属于类1，第二个点在每个类中均等分布，占33％，第三个点约为67％属于类2，33％属于类3。
如果您想要具体的标签，请尝试
my_knn.predict([[0, 1], [0, 5], [3, 4]])输出为 [0, 0, 1]。请注意，在平局的情况下，我们实现的模型输出较低的类，这就是为什么点（0，5）被分类为属于类0的原因。
如果您查看图片，这是有意义的。但让我们借助scikit-learn来确认一下。
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X, y)
my_knn.predict_proba([[0, 1], [0, 5], [3, 4]])结果：
array([[1. , 0. , 0. ],
[0.33333333, 0.33333333, 0.33333333],
[0. , 0.66666667, 0.33333333]])哎呀！一切看起来都很好。让我们检查算法的决策边界，因为它很漂亮。
同样，顶部的黑点不是100%的蓝色，它是33%的蓝色、红色和黄色，但算法决定为最低类，即蓝色。
我们还可以检查不同k值的决策边界。
请注意，蓝色区域最终变得更大，因为该类别得到了优先处理。我们还可以看到，对于k=1时，边界是一团糟：模型正在过度拟合。另一方面，k的值为数据集的大小，所有点都用于聚合步骤。因此，每个数据点都得到相同的预测：大多数类别。在这种情况下，模型欠拟合。最佳值在其中间，并可以使用超参数优化技术找到。
在结束之前，让我们看看这个算法有哪些问题。
k-最近邻的缺点
以下是问题：
- 查找最近邻需要很长时间，特别是在我们的朴素实现中。如果我们要预测新数据点的类别，则必须将其与数据集中的每个其他点进行比较，这很慢。有更好的方法可以使用高级数据结构组织数据，但问题仍然存在。
- 遵循问题1：通常，您会在更快、更强大的计算机上训练模型，并可以在之后的较弱机器上部署模型。例如，考虑深度学习。但是对于k-最近邻，训练时间很短，而在预测时间进行了繁重的工作，这不是我们想要的。
- 如果最近邻不接近怎么办？那么它们就没有意义。这已经可以在具有少量功能的数据集中发生，但是在更多的功能中遇到这个问题的机会急剧增加。这也是人们所说的维数灾难。可以在Cassie Kozyrkov的这篇文章中找到一个很好的可视化效果。
特别是由于问题2，您不会经常在野外看到k-最近邻分类器。它仍然是一种您应该了解的好算法，您也可以将其用于小型数据集，这没有问题。但是，如果您有数百万个数据点和数千个功能，则会遇到困难。
结论
在本文中，我们讨论了k-最近邻分类器的工作原理以及为什么它的设计是有意义的。它试图使用最接近的数据点来尽可能地估计数据点x属于类别c的概率。这是一种非常自然的方法，因此这种算法通常在机器学习课程的开始阶段教授。
请注意，构建 k 近邻回归器也非常简单。只需将最近邻居的标签平均值作为预测结果，而不是计算类的出现次数。你可以自行实现这个算法，只需要做一点点小改变！
我们以一种直接的方式实现了它，模仿了 scikit-learn 的 API。这意味着您也可以在 scikit-learn 的管道和网格搜索中使用此估计器。这是一个很大的好处，因为我们甚至有可以使用网格搜索、随机搜索或贝叶斯优化来优化的超参数 k。
然而，这个算法有一些严重的问题。它不适用于大型数据集，也不能在性能较弱的设备上部署以进行预测。加上对维度灾难的敏感性，这是一个理论上很好但只能用于较小数据集的算法。
Robert Kübler 博士是 METRO.digital 的数据科学家和 Towards Data Science 的作者。
原文。获得授权转载。