深入代码 kNN

为深入了解算法的细节，开始深入代码学习，计划把常见的机器学习算法亲自实现一遍，加深理解。虽然成熟的算法都有非常成熟而且高度优化了的库，但是，手动实现可以对算法有更清晰的认识。而且，大部分算法，工程实现经常无法完全与理论一致。例如在 Batch Normalization 中 test 的参数就是通过训练阶段的 moving average 来计算的，而不是重新跑一遍。

先从最简单的 KNN 开始。KNN 思想非常简单，当一个新的数据输入的时候，把该数据和训练集中的所有的数据比较一下，距离输入数据最近的一个训练样本所属类别就是该输入数据的预测值，这是 NN (最近邻) 算法。如果，把上述过程的最近的一个修改成最近的 k 个，然后这 k 个进行投票来决定预测结果，那么，这就是 kNN. 原理非常简单，实现起来也不难。

# -*- coding: utf8 -*-
import numpy as np
from collections import Counter
class kNN(object):
    #
    def __init__(self):
        pass
    # knn 不需要预先训练，所以，这里只需要把训练集保存下来
    def train(self, X, y):
        self.train_X = X
        self.train_y = y
    # 预测过程就是找距离最近的 k 个 sample 然后进行投票
    def predict(self, X, k=1):
    # 第一步，计算输入数据和训练集中数据的距离
    n_test = X.shape[0]
    n_train = self.train_X.shape[0]
    # 用于保存距离信息
    dists = np.zeros((n_test, n_train))
    for i in range(n_test):
        dists[i, :] = np.linalg.norm(X[i, :]-self.train_X, axis=1)
    # 投票
    pred_y = np.zeros(n_test)
    for i in range(n_test):
        # 先按照距离从小到大进行排序，获取对应样本的 label 数据
        labels = self.train_y[np.argsort(dists[i, :])]
        # 取前距离最近的 k 个训练样本的 label 信息
        closest_y = labels[:k]
        # 进行投票
        c = Counter(closest_y)
        pred_y[i] = c.most_common(1)[0][0]
    reurn pred_y