5分钟学习KNN 算法

什么是KNN?下文作者会介绍它的工作原理,以及它的重要应用。

KNN(k-Nearest-Neighbors)方法是Machine learning中最简单的方法之一,也是介绍ML和分类的一种很好的方法之一。在最基本的层次上,它是通过在训练数据中找到最相似的数据点来分类,并根据它们的分类作出有根据的猜测。该方法虽然理解和实现起来非常简单,但是这种方法在很多领域有广泛的应用,比如推荐系统、语义搜索和异常检测。

在任何机器学习问题中,我们都需要首先找到一种将数据点表示为特征向量的方法。特征向量是我们数据的数学表示,并且由于我们数据的期望特性可能不是固有的数值,因此可能需要预处理和特征工程来创建这些向量。给定具有N个唯一特征的数据,特征向量将是长度为N的向量,其中向量的条目I表示该数据点对于特征I的值,因此,每个特征向量可以被认为是R ^ N中的点。

KNN与大多数其他分类方法不同,属于懒惰学习,这意味着在分类之前没有明确的训练阶段。相反,任何对数据的概括或抽象的尝试都是在分类时进行的。虽然这意味着一旦我们有了数据就可以立即开始分类,但这种算法存在一些固有的问题。我们必须能够将整个训练集保存在内存中,除非我们对数据集应用某种类型有一定的约简,并且执行分类可能在计算量上巨大的,因为需要通过算法解析每个分类的所有数据点。因此,KNN在很多没有特性的较小数据集上应用的最好。

一旦我们形成了训练数据集(表示为M×N矩阵,其中M是数据点的数量,N是特征的数量),我们现在就可以开始分类。KNN方法的要点是,

l计算待分类项与训练数据集中的每个项之间的距离值

l选择k个最接近的数据点(距离最小的项目)

l在这些数据点之间进行“多数投票”—该池中的主要分类被确定为最终分类

计算距离有许多不同的方法,因为它是一个相当模糊的概念,并且最好的距离计算方式总是由数据集和分类任务决定。两种流行的方法是欧几里得距离和余弦相似性。

欧几里得距离可能广为人知的;它本质上是通过从要分类的点减去训练数据点而获得的矢量的幅度。

一般公式另一个常见指标是余弦相似性。余弦相似性不是计算幅度,而是使用两个向量之间的方向差来计算量值。

余弦相似性的一般公式

选择一个度量标准通常很棘手,最好只使用交叉验证来决定,除非你有一些先前的知识能清楚地了解一种肯定比另一种好。例如,对于像单词向量这,您可能会使用余弦相似性,因为单词的方向比分量值的大小更有意义。通常,这两种方法将在大致相同的时间内运行,并且将受到高维数据的影响。

在执行上述所有操作并确定度量之后,kNN算法的结果是将R ^ N划分为多个部分的决策边界。每个部分(下面清楚地着色)表示分类问题中的一个类。边界不需要通过实际训练示例形成,而是使用距离度量和可用训练点来计算。通过在(小)块中取R N,我们可以计算该区域中假设数据点的最可能类别,因此我们将该块着色为该类的区域。

这是开始实现算法所需的全部信息,这样做应该相对简单。当然,有许多方法可以改进这个基本算法。常见的修改包括加权、特定的预处理,以减少计算和减少噪声,例如各种算法的特征提取和减少尺寸。

此外,kNN方法也已经被用于回归任务,虽然不太常见,但它的操作方式和分类器十分相似。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180619B0IQG300?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券