kNN分类算法

    kNN(k-Nearest Neighbor，简称kNN)算法是一种常用的分类于回归方法。它的工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最相近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。通常采用“多数表决”的决策规则对输入的测试样本进行分类，即选择k个最近样本中出现次数最多的类别标记作为预测结果，类似于我们常说的“近朱者赤，近墨者黑”；在回归任务中可以使用“平均法”，即将这k个样本的实值输入标记的平均值作为预测结果；当然，还可以基于距离远近进行加权平均或加权投票，距离越小的样本权重越大。其中，k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。
    根据前文所述，我们可以看出k近邻算法没有显式的训练过程。实际上，它是“惰性学习”(lazy learning，亦称“消极学习”)的代表，这类算法在训练阶段不对数据进行建模，而是直到需要对测试样本进行分类时再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法被称为“急切学习”(eager learning，亦称“积极学习”)，例如决策树和基于规则的分类器。
k值选择

    上图是kNN算法的一个例子，其中绿色圆点代表我们的测试样例，而红色和蓝色小点则代表着两种不同的类。当k = 1(图中实线部分)时，离测试用例有2个红点和1个蓝点，根据多数表决原则，我们可以将绿色小点归为红点所在的类；而当k = 2(图中虚线部分)时，可以看到离测试用例最近的有3个蓝点和2个红点，所以我们可以将绿点归为蓝点所在类。由此可见，k值的选择对k近邻算法的结果会产生巨大影响。
    如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差(approximation error)会减小，因为只有与输入测试样例较近的训练实例才会对预测结果起作用。但是，“学习”的估计误差(estimation error)会增大，预测结果会对近邻的训练实例非常敏感，如果邻近的实例恰好是噪声，那么预测就会出错。换句话说，较小的k值会使得模型变得复杂，容易发生过拟合。
    如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。这样可以减少“学习”的估计误差，但是近似误差又会增大。因为这时与输入测试样例较远的训练实例也会对预测起作用，使预测变得不准确。特殊情况是k=N，那么无论输入测试样例是什么，模型都将简单地预测它属于训练实例中最多的类，完全忽略了训练实例中大量有用信息。由此可见，较大的k值意味着整体分类模型过于简单。
    在实际应用中，k值一般取一个比较小的数值，通常采用交叉验证的方法选择最优k值。

距离度量
    特征空间中两个实例之间的距离是两个实例相似程度的反映。k近邻模型中最常使用的距离是欧氏距离，但也可以是其他距离，如更一般的Minkowski距离(Minkowski distance)。
    给定样本xi=(xi1;xi2;...xin)${\mathbf{x}}_i=\left(x_{i1};x_{i2};...x_{in}\right)$与xj=(xj1;xj2;...xjn)${\mathbf{x}}_j=\left(x_{j1};x_{j2};...x_{jn}\right)$，其中，闵可夫斯基距离定义如下：

distmk(xi,xj)=(∑u=1n|xiu−xju|p)1p$$dis{t}_{mk}({\mathbf{x}}_i,{\mathbf{x}}_j)={\left(\sum _{u=1}^n{\left|x_{iu}-x_{ju}\right|}^p\right)}^{\frac{1}{p}}$$

    p = 2时，闵可夫斯基距离成为欧氏距离(Euclidean distance)

disted(xi,xj)=∥xi−xj∥2=∑u=1n|xiu−xju|2−−−−−−−−−−−−√$$dis{t}_{ed}({\mathbf{x}}_i,{\mathbf{x}}_j)={\Vert {\mathbf{x}}_i-{\mathbf{x}}_j\Vert }_2=\sqrt{\sum _{u=1}^n{\left|x_{iu}-x_{ju}\right|}^2}$$

    p = 1时，闵可夫斯基距离成为曼哈顿距离(Manhattan distance)

distman(xi,xj)=∥xi−xj∥1=∑u=1n|xiu−xju|1$$dis{t}_{man}({\mathbf{x}}_i,{\mathbf{x}}_j)={\Vert {\mathbf{x}}_i-{\mathbf{x}}_j\Vert }_1=\sum _{u=1}^n{\left|x_{iu}-x_{ju}\right|}^1$$

分类决策规则
    k近邻算法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类：

y′=argmaxv∑(xi,yi)∈DzI(v=yi)$$y^{{}^{\prime }}=\underset{v}{argmax}\sum _{(x_i,y_i)\in D_z}I(v=y_i)$$

其中，v$v$是类标号，yi$y_i$是一个邻近实例的类标号，I(.)$I(.)$是指示函数，如果参数为真则返回1，否则返回0。
    在多数表决方法中，每个近邻对分类的影响都一样，这使得算法对k的选择很敏感。降低k的影响的一种途径是根据每个最近邻xi$x_i$距离的不同对其作用进行加权：wi=1d(x′,xi)2$w_i=\frac{1}{d({\mathbf{x}}^{{}^{\prime }},{\mathbf{x}}_i{)}^2}$.这样会使得远离z的训练实例对分类的影响比靠近z的训练实例弱一些。使用距离加权表决方案，类标号可由下面的公式确定：

y′=argmaxv∑(xi,yi)∈Dzwi×I(v=yi)$$y^{{}^{\prime }}=\underset{v}{argmax}\sum _{(x_i,y_i)\in D_z}{w}_i\times I(v=y_i)$$

import operator
import numpy as np


class KNearestNeighbours(object):
    def __init__(self, n_neighbours):
        self._n_neighbours = n_neighbours
        self._X = None
        self._y = None

    def fit(self, X, y):
        self._X = X
        self._y = y

    def predict(self, X):
        _X = self._X
        _y = self._y

        n_samples = X.shape[0]
        y_pred = []
        for sample in range(n_samples):
            distances = np.linalg.norm(np.array(X[sample]) - _X, axis=1)
            sorted_distance_indicies = distances.argsort()
            class_count = {}
            for i in range(self._n_neighbours):
                curr_label = _y[sorted_distance_indicies[i]]
                class_count[curr_label] = class_count.get(curr_label, 0) + 1
            sorted_label_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
            y_pred.append(sorted_label_count[0][0])
        return np.array(y_pred)

参考资料：
[1]李航, 《统计学习方法》, 第一版, 北京: 清华大学出版社 2012
[2]周志华, 《机器学习》, 第一版, 北京: 清华大学出版社 2016
[3]Pang-Ning Tan, Michael Steinbach, Vipin Kumar, 《数据挖掘导论：完整版》, 第二版, 北京: 人民邮电出版社 2011
[4]Peter Harrington, 《机器学习实战》, 第一版, 北京: 人民邮电出版社 2013