KNN(K-Nearest Neighbors)一般指K最近邻算法,属于机器学习中常见的一种分类算法.
本文目的在于快速地教大家对KNN算法有个直观的理解,同时为了方便大家实现该算法,文中所涉及的模型仅使用Python和Numpy库进行开发.

1 引言

从KNN的名字中我们就可以大致了解该算法的原理,该模型使用k个邻居的类别来对当前样本进行预测分类.这里的k代表特征空间中距离当前样本最近的邻居样本的数目.
如果k=1,那么待分类样本的类别完全取决于特征空间中距离该样本最近的邻居所属类别.
如果k=n,那么待分类样本的类别取决于样本空间中n个最近的邻居.以上两种情况的图例可以参考下图:

2 距离衡量

通过观察上图,有同学就要提问了,我们如何来确定那些点是属于待分类样本的邻居的呢?
这里我们引入特征向量的相异性度量,可以参考之前的博文.
上述博文中给出了很多种特征向量间距离的计算公式,这里不再进行类述.我了方便演示,这里采用最简单的欧式距离进行说明,其计算方式如下:
实现代码如下:

ldist = ['euclidian', 'manhattan', 'chebyshev', 'canberra', 'cosine']

class Distance(object):
  def __init__(self, metric='euclidian'):
    super(Distance, self).__init__()
    if metric not in ldist:
      raise ValueError('Metric does not exist! Choose between: {}'.format(ldist))
    self._metric = metric
  
  @property
  def metric(self):
    return self._metric
  
  @metric.setter
  def metric(self, m):
    if m not in ldist:
      raise ValueError('Metric does not exist! Choose between: {}'.format(ldist))
    self._metric = m
  
  def distance(self, p, q):
    return np.sum((p - q)**2, axis=1)**0.5

3 k-NN 分类

KNN分类算法非常简单，该算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别.
换句话说就是待分类样本的类别由k个最相邻的样本投票,取投票中最多数类别最为该样本的类别.
上图左侧图中,我们生成了三个类别的样本,分别用红色绿色和蓝色实心圆来表示三个类别,我们待分类的样本用五角星表示.
随着k值的增加,左侧可视化出待分类样本k个最近邻居以及其投票后的结果,右侧表示投票中三个类别各自的数目.

代码实现如下:

class kNNClass(Distance):
  def __init__(self, k=1):
    super(kNNClass, self).__init__()
    self._k = k
    self._q = None
    self._class = None
  
  def fit(self, X, y):
    self._q = X
    self._class = y
  
  def pred(self, P):
    y, NNs = [], []
    for i, p in enumerate(P):
      dist = self.distance(p, self._q)
      odist = np.argsort(dist)[:self._k]
      fdist = np.ravel(self._class[odist])
      hist = np.bincount(fdist)
      index = np.argmax(hist)
      y += [index]
      NNs += [odist]
    return np.array(y), np.array(NNs)

上述代码中:

• fit函数用来给输入x打上标签赋值为y
• pred函数使用KNN来预测待分类样本p的类别

我们使用不同的k值,来对另一组数据进行预测,使用不同的k值得到的对比图如下:
上图中实心红绿蓝圆圈代表我们标注的训练样本,五角星代表KNN投票后的结果图.

4 k-NN 预测

和分类算法类似,KNN预测过程就是根据k个邻居的取值来预测当前样本的取值,这里和一般的回归方法类似,采用k个邻居的距离加权平均来获得当前样本的预测值.
我们来产生样例数据,左侧为以下二元函数的热力图:
我们对其均匀采点作为我们的训练样本,采样点的分布图如右侧所示.
我们参考k-NN分类样例代码来实现预测代码,如下所示:

class kNNRegr(Distance):
  def __init__(self, k=1):
    super(kNNRegr, self).__init__()
    self._k = k
    self._q = None
    self._v = None
  
  def fit(self, X, y):
    self._q = X
    self._v = y
    
  def pred(self, P):
    y, NNs = [], []
    for i, p in enumerate(P):
      dist = self.distance(p, self._q)
      odist = np.argsort(dist)[:self._k]
      fdist = np.ravel(self._v[odist])
      ndist = dist[odist]
      ndist /= np.sum(ndist)
      y += [np.sum(fdist*np.flipud(ndist))]
      NNs += [odist]
    return np.array(y), np.array(NNs)

上述代码中:

• fit函数用来给输入x打上标签赋值为y
• pred函数使用KNN来预测待预测样本p的取值,其中计算公式为距离加权

得到结果如下:

5 总结

本文介绍了机器学习领域中k-NN进行分类和回归模型的原理以及相应的代码实现,并给出了完整的代码示例.

您学废了吗?

6 参考

参考 链接一
链接二

关注公众号《AI算法之道》，获取更多AI算法资讯。

注： 完整代码，关注公众号，后台回复 KNN , 即可获取。