Press "Enter" to skip to content

从理论到实践:构建k最近邻分类器

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可以取值为男性或女性。让我们看一些虚拟数据:

从理论到实践:构建k最近邻分类器 机器学习 第1张

由于这两个特征是连续的,拥有两个甚至几百个数据点的概率是微不足道的。

另一个问题:如果我们想要预测具有我们从未见过的特征的数据点的性别,例如(190.1, 85.2)?这就是预测实际上所涉及的内容。这就是为什么这种朴素方法不起作用的原因。相反,k-最近邻算法做的是:

它尝试用具有接近x特征的数据点而不是具有完全相同特征x的数据点来逼近概率p(c|x)。

从某种意义上说,它比较宽松。不需要等待很多身高=182.4和体重=92.6的人,并检查他们的性别,k-近邻算法允许考虑具有这些特征的人附近的人。算法中的k是我们考虑的人数,它是一个超参数。

这些是我们或网格搜索等超参数优化算法必须选择的参数。它们不是由学习算法直接优化的。

从理论到实践:构建k最近邻分类器 机器学习 第2张

算法

我们现在拥有描述算法所需的一切。

训练:

  1. 以某种方式组织训练数据。在预测时,这个顺序应该能够为任何给定的数据点x提供k个最接近的点。
  2. 就这样了!😉

预测:

  1. 对于新的数据点x,在组织的训练数据中找到k个最接近的邻居
  2. 合并这k个邻居的标签。
  3. 输出标签/概率。

迄今为止,我们无法实现这一点,因为我们必须填写很多空白。

  • 组织意味着什么?
  • 如何衡量接近程度?
  • 如何聚合?

除了k的值外,这些都是我们可以选择的事情,不同的决策会给我们不同的算法。让我们简单地回答以下问题:

  • 组织=只是保存训练数据集
  • 接近程度=欧几里得距离
  • 聚合=平均值

这需要一个例子。让我们再次检查具有人员数据的图片。

从理论到实践:构建k最近邻分类器 机器学习 第3张

我们可以看到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])

从理论到实践:构建k最近邻分类器 机器学习 第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最近邻分类器 机器学习 第5张

使用我们的分类器,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]])

哎呀!一切看起来都很好。让我们检查算法的决策边界,因为它很漂亮。

从理论到实践:构建k最近邻分类器 机器学习 第6张

同样,顶部的黑点不是100%的蓝色,它是33%的蓝色、红色和黄色,但算法决定为最低类,即蓝色。

我们还可以检查不同k值的决策边界。

从理论到实践:构建k最近邻分类器 机器学习 第7张

请注意,蓝色区域最终变得更大,因为该类别得到了优先处理。我们还可以看到,对于k=1时,边界是一团糟:模型正在过度拟合。另一方面,k的值为数据集的大小,所有点都用于聚合步骤。因此,每个数据点都得到相同的预测:大多数类别。在这种情况下,模型欠拟合。最佳值在其中间,并可以使用超参数优化技术找到。

在结束之前,让我们看看这个算法有哪些问题。

k-最近邻的缺点

以下是问题:

  1. 查找最近邻需要很长时间,特别是在我们的朴素实现中。如果我们要预测新数据点的类别,则必须将其与数据集中的每个其他点进行比较,这很慢。有更好的方法可以使用高级数据结构组织数据,但问题仍然存在。
  2. 遵循问题1:通常,您会在更快、更强大的计算机上训练模型,并可以在之后的较弱机器上部署模型。例如,考虑深度学习。但是对于k-最近邻,训练时间很短,而在预测时间进行了繁重的工作,这不是我们想要的。
  3. 如果最近邻不接近怎么办?那么它们就没有意义。这已经可以在具有少量功能的数据集中发生,但是在更多的功能中遇到这个问题的机会急剧增加。这也是人们所说的维数灾难。可以在Cassie Kozyrkov的这篇文章中找到一个很好的可视化效果。

从理论到实践:构建k最近邻分类器 机器学习 第8张

特别是由于问题2,您不会经常在野外看到k-最近邻分类器。它仍然是一种您应该了解的好算法,您也可以将其用于小型数据集,这没有问题。但是,如果您有数百万个数据点和数千个功能,则会遇到困难。

结论

在本文中,我们讨论了k-最近邻分类器的工作原理以及为什么它的设计是有意义的。它试图使用最接近的数据点来尽可能地估计数据点x属于类别c的概率。这是一种非常自然的方法,因此这种算法通常在机器学习课程的开始阶段教授。

请注意,构建 k 近邻回归器也非常简单。只需将最近邻居的标签平均值作为预测结果,而不是计算类的出现次数。你可以自行实现这个算法,只需要做一点点小改变!

我们以一种直接的方式实现了它,模仿了 scikit-learn 的 API。这意味着您也可以在 scikit-learn 的管道和网格搜索中使用此估计器。这是一个很大的好处,因为我们甚至有可以使用网格搜索、随机搜索或贝叶斯优化来优化的超参数 k。

然而,这个算法有一些严重的问题。它不适用于大型数据集,也不能在性能较弱的设备上部署以进行预测。加上对维度灾难的敏感性,这是一个理论上很好但只能用于较小数据集的算法。

Robert Kübler 博士是 METRO.digital 的数据科学家和 Towards Data Science 的作者。

原文。获得授权转载。

Leave a Reply

Your email address will not be published. Required fields are marked *