监督学习之最近邻算法

一、概念理解

K最近邻（kNN，k-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。
我们可以假设在一个N维空间中有很多个点，然后这些点被分为几个类。相同类的点，肯定是聚集在一起的，它们之间的距离相比于和其他类的点来说，非常近。如果现在有个新的点，我们不知道它的类别，但我们知道了它的坐标，那只要计算它和已存在的所有点的距离，然后以最近的k个点的多数类作为它的类别，则完成了它的分类。
所以kNN算法无非就是计算一个未知点与所有已经点的距离，然后根据最近的k个点类别来判断它的类别。简单，粗暴，实用。

二、执行步骤

STEP1：计算已知类别数据集中的点与当前点之间的距离；
STEP2：按照距离递增次序排序；
STEP3：选取与当前点距离最小的k个点；
STEP4：确定前k个点所在类别的出现频率；
STEP5：返回前k个点出现频率最高的类别作为当前点的预测分类。

三、代码实现

import numpy as np
 
def KNN(X_train, y_train, X_test, k):
    '''
    K最近邻方法
    遍历测试样本, 计算每个测试样本与训练样本的距离值并排序, 根据前K个投票选举出预测结果
    '''
    X_train = np.array(X_train)
    y_train = np.array(y_train)
    X_test = np.array(X_test)

    # 获得训练、测试集的长度
    X_train_len = len(X_train)
    X_test_len = len(X_test)
    # 存储预测标签
    pred_labels = []

    for test_index in range(X_test_len):
        dis = []
        for train_index in range(X_train_len):
            temp_dis = abs(sum(X_train[train_index,:] - X_test[test_index,:]))**0.5
            dis.append(temp_dis)
        dis = np.array(dis)
        sort_id = dis.argsort()

        # 为最近的k个样本的标签记数
        dic = {}
        for i in range(k):
            label = y_train[sort_id[i]]
            dic[label] = dic.get(label, 0)+1
        # 找出最可能的标签
        max = 0
        for label, v in dic.items():
            if v > max:
                max = v
                pred_label = label
        pred_labels.append(pred_label)
    print(pred_labels)
 
if __name__=="__main__":

    X_train = [[1,  2,  3,  4],
               [5,  6,  7,  8],
               [9, 10, 11, 12],
               [1,  2,  3,  4],
               [5,  6,  7,  8],
               [9, 10, 11, 12]]
    y_train = [1, 2, 3, 1, 2, 3]
 
    X_test = [[1, 2, 3, 4], 
              [5, 6, 7, 8]]
    # 预测数据应为 1、2
    KNN(X_train,y_train,X_test,2)