KNN算法-python实现

$k$近邻算法

$k$近邻(k-Nearest Neighbor, KNN)分类算法，是机器学习中最简单的算法之一。该算法的基本思路是：在一个未知的样本附近选取k个距离最短的已知样本（有类别标签），将这k个已知样本中数量最多的类别（标签）作为未知样本的类别（标签）。直观一点，如下图所示：

可以看到上图选取了$k=5$个距离未知样本最近的已知样本，5个已知样本中有三个红色矩形和两个蓝色矩形，由算法的基本思路可知，未知样本应标记为红色。

距离的度量

$x$和$y$分别为两个样本，$n$为特征总数。一般用到的是以下两种距离：

欧式距离： $d\left ( x,y \right )=\sqrt{\sum_{k=1}^{n}\left ( x_{k}-y_{k} \right )^{2}}$
曼哈顿距离： $d\left ( x,y \right )=\sqrt{\sum_{k=1}^{n}\left | x_{k}-y_{k} \right |}$

无论用那种距离，目的都是为了刻画已知样本和未知样本的相似度，从而描述预知样本的特征。

用python实现算法

算法思路

初始化：已知类别标签的样本集$X_{n}$和最多近邻数$k$，
输入：未知样本$x$
步骤：

对于每个样本集中的样本$X_{i}$和未知样本$x$计算距离$d_{i}$。得到距离集$D_{n}$。

将距离集$D_{n}$中的数从小到大排序，选择前$k$个距离数据。

根据步骤2的$k$距离数据中的样本下标，得到对应的类别标签集$C_{k}$

选择$C_{k}$中数量最多的类别标签$c_{max}$作为未知样本$x$的类别标签$c$

python实现

python实现knn算法的代码如下：

import numpy as np


class KNN:
    def __init__(self, k):
        """
        the k of KNN
        :param k: 
        """
        self.k = k
        self.samples_nums = 0

    def predict(self, x_train, y_train, test):
        """
        predict the categorie of test sample
        :param x_train: the set of train sample
        :param y_train: the label set of train sample
        :param test: 
        :return: 
        """
        x_train = np.array(x_train)
        self.samples_nums = x_train.shape[0]
        y_train = np.array(y_train)
        sorted_k_v = self.__cal_dist(x_train, test)
        lab_dict = {}
        for ind in range(self.k):
            s = sorted_k_v[ind]
            if y_train[s[0]] not in lab_dict.keys():
                lab_dict[y_train[s[0]]] = 1
            else:
                lab_dict[y_train[s[0]]] += 1
        return max(lab_dict, key=lab_dict.get)

    def __cal_dist(self, x_train, x_test):
        """
        calculate the distance between train set and test sample
        :param x_train: 
        :param x_test: 
        :return: 
        """
        d = {}
        for ind in range(self.samples_nums):
            d[ind] = np.sqrt(sum(np.power(x_train[ind, :] - x_test, 2)))
        sort_list = sorted(d.items(), key=lambda itm: itm[1])
        return sort_list

测试案例如下：

if __name__ == "__main__":
    my_knn = KNN(3)
    x = [[0.1, 0.2], [-1.5, -1.1], [0.7, 1.9], [-0.3, 1.0]]
    y = ['a', 'a', 'b', 'b']
    print(my_knn.predict(x, y, [1, 1]))

输出：b