邻居来投票：机器学习之快速掌握K-近邻算法分类（Python实战）

K-近邻算法又称KNN算法(K-Nearest Neighbors)，既可以用来解决分类问题，也可以用来解决回归问题。

如标题所言，KNN算法的核心原理就是让距离最近的“邻居们”来帮忙投票，邻居们决定预测对象的分类或者取值。

假设我们有一个已经标记好的数据集，我们知道这个数据集中每个样本的类别（标记），现在有一个新的样本，我们不知道它的分类（标记）是什么，我们的任务就是预测它所属的分类。按照KNN的方法，我们要计算这个新样本到数据集中每个样本的距离，并按照距离逆序排列，取前K个样本的分类，以多数战胜少数的原则来决定新样本的分类。

当分类只有两个的时候，这个K值一般会选择一个单数，这样就不会出现两个分类投票数量相等的情况。但是当有多个分类时，很可能会出现多个分类等票的情况。

一个很常见的处理是减小K的值，直到最终只有1个分类胜出；使用这种方法时，如果最后有两个或者多个邻居与新样本的距离相等，那我们可以随机选择一个样本，或者通过别的策略从其中抽取一个。

另一个常用的处理方法是根据距离做一个加权，比如A点距离测试样本1厘米，B点距离测试样本2厘米，那么我认为A点的投票更重要，我就可以给他更大的权重；

KNN算法有很多优点，比如可解释性非常强、精度高、对异常值不敏感、没有数据输入假设（有一些模型要求数据符合特定的分布，或者属于特定的数据类型），原理也很简单，但它也存在一些问题。

它最大的问题就是需要大量的计算。对于每个待预测的样本，都要计算它和所有已知样本之间的距离，这会消耗大量的计算资源。因此它适合在探索初期做一个基准模型，或者是在小数据样本量时使用。

一、scikit-learn实战：鸢尾花数据集

我们先使用scikit-learn提供的分类器来看一下如何使用KNN分类模型。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets

# 设定邻居数量
n_neighbors = 15

# 鸢尾花数据集
iris = datasets.load_iris()

# 使用数据集的前两列
X = iris.data[:, :2]
y = iris.target

# step size
h = 0.02

# color map
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])

for weights in ['uniform', 'distance']:
    # 创建模型
    clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
    
    # 训练模型
    clf.fit(X, y)
    
    # 创建测试数据矩阵
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    # 预测测试数据集
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    # 画图
    plt.figure(figsize=(12, 8))
    
    # 将测试数据矩阵的预测结果以背景可视化出来
    # pcolormesh可以实现在区域中对分类进行可视化，这种可视化方法的一个优点是可以将分类边界表现出来
    plt.pcolormesh(xx, yy, Z, cmap=cmap_light)
    
    # 将训练数据以散点图的形式画出来
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold)
    
    # 设置图边界、标题
    plt.xlim(xx.min(), xx.max())
    plt.ylim(yy.min(), yy.max())
    plt.title('3-class classification (k = {0}, weights = {1})'.format(n_neighbors, weights))
    
plt.show()

上边两张图为我们展示了我们的模型预测效果。其中，三种颜色的散点代表着我们的训练数据，三种颜色代表了三种分类；同时我们可以看到有三种颜色的区域作为背景，这一部分是我们以0.02为间隔遍历整个区域内的所有数据点，并以每个数据点的坐标作为输入来预测其分类，不同区域的不同颜色代表了这些区域里的数据被我们的模型预测给了不同的分类。

也就是说，当一个散点的颜色与它的背景颜色不同时，就出现了一个我们模型预测错误的案例。可以看到，我们的这个简单的模型预测的准确率还是挺不错的，大部分散点都与背景的颜色一致。接下来大家就可以通过调整邻居数量等参数将模型优化，来提高模型的表现。

值得一提的是，假如我们将k值调整的低一点，一般来说在训练数据上表现的会更好，但是这样很容易会出现过拟合的问题，也就是说，这样的模型很可能只是针对训练数据量身定制的，它在新的数据集上的表现往往不会太好；但是k值过高的话准确率等指标又会很差，容易出现拟合不足的问题。k值的选择是一门学问，值得你花更多时间去探索。

二、从零开始搭建KNN分类器

接下来，我们尝试着自己造一个*出来。先明确下流程：

1. 针对一个测试样本，一个训练数据集，计算测试样本到训练集中每个点的距离；
2. 将这些距离排序，并取前K个样本的分类；
3. 取票数最高的分类作为测试样本的分类；
4. 若出现同票，则K减1，重复步骤1。

from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
from collections import Counter
from pprint import pprint
import numpy as np
import math


def distance(x1, x2):
    """
    :param x1: 点1
    :param x2: 点2
    :return: 点1和点2的欧氏距离
    """
    sq_sum = 0
    for (a, b) in zip(x1, x2):
        sq_sum += (a - b) ** 2
    return math.sqrt(sq_sum)


def knn(x, y, x_train, y_train, k):
    """
    :param x: 测试样本
    :param y: 测试样本的实际分类
    :param x_train: 训练数据集中的特征
    :param y_train: 训练集的对应分类
    :param k: 选择多少个邻居
    :return: 返回预测分类与实际分类
    """
    distances = [distance(x, i) for i in x_train]
    dist_label = list(zip(distances, y_train))
    sorted_label = sorted(dist_label, key=lambda x: x[0])
    k_label = [i[1] for i in sorted_label[:k]]
    counter = Counter(k_label)
    sorted_counter = sorted(counter.items(), key=lambda x: x[1], reverse=True)
    if len(sorted_counter) == 1:
        # 如果所有投票都一样，则直接返回结果
        return sorted_counter[0][0], y

    if sorted_counter[0][1] == sorted_counter[1][1]:
        # 若出现相同票数，则递归计算下一个K值
        return knn(x, y, x_train, y_train, k - 1)
    else:
        # 票数不同时，直接返回最高票的分类
        return sorted_counter[0][0], y


def split_data(X, Y, i):
    """
    :param X: 特征数据集
    :param Y: 目标（分类）数据集
    :param i: 取第几条数据作为测试样本
    :return: 返回测试样本的特征、分类以及剩余的特征和分类集
    """
    x = X[i, :]
    y = Y[i]
    X_train = np.delete(X, i, 0)
    y_train = np.delete(Y, i, 0)
    return x, y, X_train, y_train


def normalize(Feature_Sets):
    """
    :param X: 特征数据集
    :return: 0-1正则化之后的特征集
    """
    for col in range(X.shape[1]):
        min = Feature_Sets[:, col].min()
        max = Feature_Sets[:, col].max()
        Feature_Sets[:, col] = (Feature_Sets[:, col] - min) / (max - min)
    return Feature_Sets


if __name__ == '__main__':
    # 获取数据集
    iris = load_iris()
    X = iris.data.copy()
    Y = iris.target.copy()

    # 0-1标准化，但是这里不使用，因为使用了反而效果更差了。。
    # X = normalize(X)


    # 用于存储准确率数据
    acc = []

    # 观察K值从1到30时，准确率的表现
    for k in range(1, 31):
        result = []
        # 循环设置一个样本为测试样本，其余样本集作为训练集
        for i in range(150):
            x, y, X_train, y_train = split_data(X, Y, i)
            y_pred, y_act = knn(x, y, X_train, y_train, k)
            result.append(y_pred == y_act)
        acc.append([k, sum(result) / len(result)])

    # 打印结果
    pprint(sorted(acc, key=lambda x: x[1], reverse=True))

    # 画图
    plt.figure(figsize=(10, 6))
    plt.plot([i[0] for i in acc], [i[1] for i in acc], '-g')
    plt.title('不同K值下的准确率趋势')

输出如下：

[[19, 0.98],
 [20, 0.98],
 [21, 0.98],
 [22, 0.98],
 [11, 0.9733333333333334],
 [12, 0.9733333333333334],
 [15, 0.9733333333333334],
 [16, 0.9733333333333334],
 [17, 0.9733333333333334],
 [18, 0.9733333333333334],
 [5, 0.9666666666666667],
 [6, 0.9666666666666667],
 [7, 0.9666666666666667],
 [8, 0.9666666666666667],
 [9, 0.9666666666666667],
 [10, 0.9666666666666667],
 [13, 0.9666666666666667],
 [14, 0.9666666666666667],
 [23, 0.9666666666666667],
 [24, 0.9666666666666667],
 [25, 0.9666666666666667],
 [26, 0.9666666666666667],
 [27, 0.9666666666666667],
 [28, 0.9666666666666667],
 [1, 0.96],
 [2, 0.96],
 [3, 0.96],
 [4, 0.96],
 [29, 0.9533333333333334],
 [30, 0.9533333333333334]]

可以看到，如果我们使用数据集的所有特征的话，在K值等于19、20、21、22时，准确率最高，达到了98%，考虑到计算资源的优势，我们选择19来作为我们模型的邻居数量参数。

好了，一个简易的KNN分类器就被我们从零搭建起来了，有什么问题可以留言，大家一起交流。