JavaScript 算法之 KNN k-nearest neighbors K 最近邻算法

Question

从一个很简单的例子来理解 KNN。

假设我们有一堆橙子和一堆柚子，通常情况下，柚子比橙子更大，更红；现在有一个水果，我们怎么判断它是橙子还是柚子？肯定是比较它的大小和颜色，与橙子/柚子哪个更接近。怎么判断接近？我们可以把之前的橙子/柚子画到二维点图上，X轴为颜色，Y轴为大小，然后来看看离这个水果最近的3个点，结果这3个点里，有2个是橙子，那么我们大概率可以确定，这个水果就是橙子。

这里运用到的就是 KNN 算法：给定一个（训练）数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

KNN 算法是一种基本分类和回归方法，是机器学习中最简单的算法之一。

由于给定的数据集都带有label（即是橙子还是柚子），并且新输入的实例也会明确确定label，所以KNN属于监督学习。

下面讲一些KNN算法的注意点：

K 的选取

• K 不能过小，过小就容易被噪声干扰。极端情况，K 取 1，只要新实例最近的一个是噪点，那么新实例的分类就会出错。
• K 不能过大。过大时，表示邻域过大，这个范围内有很多非同类的数据也在起作用（训练实例和输入实例距离大，不相似），容易分类错误。极端情况，K 取全部数据，那么新实例永远归入数量占多的类别。
• 所以 K 不能过大过小，一般取一个较小的数值，并采取交叉验证法来选取最优的K值。

距离计算

• 一般采用欧氏距离（Euclidean Distance）。欧氏距离可以量测任意方向的线段，计算方法是
  
• 不采用曼哈顿距离（Manhattan Distance）。曼哈顿距离就像曼哈顿的街道一样，只有水平和垂直的线段，无法计算多维度，计算方法是
  
• 实际中经常使用余弦相似度（计算角度而非距离）。

特征归一化

假设我们通过两个维度（身高和脚长）来判断性别，很显然，计算距离时，结果会偏向于身高。

所以很容易理解，我们需要对特征归一化。即取每个维度的最大值减去最小值，然后该维度计算时首先除以这个值来进行归一化。