目录

kNN 算法的算法流程

kNN 算法的优缺点

 实现kNN算法

kNN 算法的算法流程

假设现在有这样的一个样本空间，该样本空间里有宅男和文艺青年这两个类别，其中红圈表示宅男，绿圈表示文艺青年。如下图所示：

其实构建出这样的样本空间的过程就是 kNN 算法的训练过程。可想而知 kNN 算法是没有训练过程的，所以 kNN 算法属于懒惰学习算法。

假设我在这个样本空间中用黄圈表示，如下图所示：

现在使用 kNN 算法来鉴别一下我是宅男还是文艺青年。首先需要计算我与样本空间中所有样本的距离。假设计算得到的距离表格如下：

然后找出与我距离最小的 k 个样本(k 是一个超参数，需要自己设置，一般默认为 5)，假设与我离得最近的 5 个样本的标签和距离如下：

最后只需要对这 5 个样本的标签进行统计，并将票数最多的标签作为预测结果即可。如上表中，宅男是 4 票，文艺青年是 1 票，所以我是宅男。

注意：有的时候可能会有票数一致的情况，比如 k=4 时与我离得最近的样本如下：

可以看出宅男和文艺青年的比分是 2:2，那么可以尝试将属于宅男的 2 个样本与我的总距离和属于文艺青年的 2 个样本与我的总距离进行比较。然后选择总距离最小的标签作为预测结果。在这个例子中预测结果为文艺青年(宅男的总距离为 4.2+9.5，文艺青年的总距离为 7.7+5.8)。

kNN 算法的优缺点

从算法流程中可以看出，kNN 算法的优点有：

• 原理简单，实现简单；
• 天生支持多分类，不像其他二分类算法在进行多分类时要使用 OvO、 OvR 的策略。

缺点也很明显：

• 当数据量比较大或者数据的特征比较多时，预测过程的时间效率太低。

 实现kNN算法

fit 函数用于 kNN 算法的训练过程，其中：

• feature ：训练集数据，类型为 ndarray；

• label ：训练集标签，类型为 ndarray。

  predict 函数用于实现 kNN 算法的预测过程，函数返回预测的标签，其中：

• feature ：测试集数据，类型为 ndarray。（PS：feature中有多条数据）

import numpy as np
from collections import Counter
class kNNClassifier(object):
    def __init__(self, k):
        '''
        初始化函数
        :param k:kNN算法中的k
        '''
        self.k = k
        # 用来存放训练数据，类型为ndarray
        self.train_feature = None
        # 用来存放训练标签，类型为ndarray
        self.train_label = None
        self.train_vars = 0
    def fit(self, feature, label):
        '''
        kNN算法的训练过程
        :param feature: 训练集数据，类型为ndarray
        :param label: 训练集标签，类型为ndarray
        :return: 无返回
        '''
        self.train_feature = feature
        self.train_label = label
        self.train_vars = feature.shape[0]
    def predict(self, feature):
        '''
        kNN算法的预测过程
        :param feature: 测试集数据，类型为ndarray
        :return: 预测结果，类型为ndarray或list
        '''
        # distance = self.calculateDistance(feature)
        # KLabels = self.getKLabels(distance)
        # return self.getAppearMostLabel(KLabels)
        result = []
        for data in feature:
            distance = self.calculateDistance(data)
            KLabels = self.getKLabels(distance)
            result.append(self.getAppearMostLabel(KLabels))
        return result
    def calculateDistance(self, feature):
        diffMat = np.tile(feature, (self.train_vars, 1)) - self.train_feature
        sqDistance = (diffMat ** 2).sum(axis=1)
        
        return sqDistance ** 0.5
    def getKLabels(self, distance):
        argOder = distance.argsort()[0:self.k]
        return (self.train_label[i] for i in argOder)
    def getAppearMostLabel(self, KLabels):
        label, count = Counter(KLabels).most_common(1)[0]
        return label