实现机器学习的分步指南 I - KNN

引言

K近邻（KNN）是一种简单的机器学习算法，其原理是计算测试对象与训练集之间的距离。然后，根据距离选择训练集中的对象添加到K-NN集合中，直到K-NN集合包含预定义的最近邻数量，可以表示为

其中 是KNN集合， 由下式给出

KNN模型

KNN模型包括距离计算、选择K和分类。

距离计算

距离用于衡量特征空间中两个对象之间的相似性。有很多方法可以计算两个对象之间的距离，例如欧几里得距离、余弦距离、编辑距离、曼哈顿距离等。最简单的方法是欧几里得距离，计算公式如下

其中 n 是特征维度。

由于特征值的尺度不同，较大的值对距离的影响更大。因此，需要对所有特征进行归一化。具体来说，有两种归一化方法。一种是最小-最大归一化，公式如下

    def Normalization(self, data):
        # get the max and min value of each column
        minValue = data.min(axis=0)
        maxValue = data.max(axis=0)
        diff = maxValue - minValue
        # normalization
        mindata = np.tile(minValue, (data.shape[0], 1))
        normdata = (data - mindata)/np.tile(diff, (data.shape[0], 1))
        return normdata

另一种是z-score归一化，公式如下

其中 是 的均值， 是 的标准差。

    def Standardization(self, data):
        # get the mean and the variance of each column
        meanValue = data.mean(axis=0)
        varValue = data.std(axis=0)
        standarddata = (data - np.tile(meanValue, 
                       (data.shape[0], 1)))/np.tile(varValue, (data.shape[0], 1))
        return standarddata

归一化后，欧几里得距离的代码如下所示

train_num = train_data.shape[0]
# calculate the distances
distances = np.tile(input, (train_num, 1)) - train_data
distances = distances**2
distances = distances.sum(axis=1)
distances = distances**0.5

选择K

如果我们选择一个较小的K，模型将使用较小的邻居进行学习，这将导致较小的“近似误差”而较大的“估计误差”。 换句话说，较小的K会使模型复杂并倾向于过拟合。 相反，如果我们选择一个较大的K，模型将使用较大的邻居进行学习，这将导致较大的“近似误差”而较小的“估计误差”。 换句话说，较大的K会使模型简单并倾向于更大的计算量。

分类

确定K后，我们可以利用投票进行分类，这意味着少数服从多数，其代码如下所示

disIndex = distances.argsort()
labelCount = {}
for i in range(k):
    label = train_label[disIndex[i]]
    labelCount[label] = labelCount.get(label, 0) + 1
prediction = sorted(labelCount.items(), key=op.itemgetter(1), reverse=True)
label = prediction[0][0]

在上面的代码中，我们首先使用 argsorts() 获取排序后的索引，然后计算前K个样本中每种标签的数量，最后对 labelCount 进行排序以获得投票最多的标签，这就是对测试对象的预测。 整个预测函数如下所示

def calcuateDistance(self, input_sample, train_data, train_label, k):
        train_num = train_data.shape[0]
        # calculate the distances
        distances = np.tile(input, (train_num, 1)) - train_data
        distances = distances**2
        distances = distances.sum(axis=1)
        distances = distances**0.5

        # get the labels of the first k distances
        disIndex = distances.argsort()
        labelCount = {}
        for i in range(k):
            label = train_label[disIndex[i]]
            labelCount[label] = labelCount.get(label, 0) + 1

        prediction = sorted(labelCount.items(), key=op.itemgetter(1), reverse=True)
        label = prediction[0][0]
        return label

结论与分析

本文通过线性遍历实现KNN。 然而，存在更有效的方法来实现KNN，例如kd树。 此外，应用交叉验证以获得更合适的K是有效的。 最后，让我们将我们的KNN与Sklearn中的KNN进行比较，检测性能如下所示。

从图中可以看出，本文中的KNN在准确性方面优于sklearn knn，运行时间几乎相同。

本文相关的代码和数据集可以在 MachineLearning 中找到。