纯Python实现kNN机器学习算法

博主 2019年03月03日 分类： Python 机器学习 阅读：10466 评论：3

最近在写文档，突然想自己实现一下k近邻算法，随手编写的，可能不太严谨，仅供大家参考。

k近邻（k-Nearest Neighbor）算法，简称kNN，可能是最简单也最好理解的监督学习方法了。

其工作机制为：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个‘近邻’的信息来进行测试样本的预测。

这是一种很朴素的分类思维，事物属于哪一类，只要看它在种群集合中所处的位置。和它在位置上靠得越近的族类，必定是和它更亲近的同类。

从kNN的工作机制可以分析出以下几个要点：

某种距离度量方法：一般是欧氏距离。当然也可以使用其它的。
最靠近的：只看邻居，不看远亲。
k个：显而易见的超参数。也就是考察的邻居数量。
基于邻居的信息进行预测，有不同的预测方法。分类和回归又有不同。

比如，在分类任务中可以使用‘投票法’，选择邻居最多的那一类；在回归任务中使用‘平均法’，将k个邻居的标记值取平均值作为预测结果；还可以基于距离远近进行加权投票或加权平均，距离越近的邻居权重越大。

k是k近邻算法最重要的参数，不同的k值，可能导致完全不同的分类结果。当k为1的时候，被称为‘最近邻分类器’。

与其它的机器学习方法相比，k近邻没有显式的训练过程，它是‘懒惰学习’（lazy learning）的著名代表，此类学习方法在训练阶段仅仅是把样本保存起来，训练时间开销为0，待有预测任务时，再用测试样本和训练样本去逐一比较。相应的，那些在训练阶段就对训练样本进行学习处理的方法称为‘积极学习’（eager learning），线性回归、决策树、支持向量机等大多数机器学习算法都是‘积极学习’类型。

积极学习
懒惰学习

另外，根据数学推导，最近邻分类器虽然简单，但它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。

在Python的Scikit-learn库中有专门的kNN算法实现。但是，这里先给出一个用纯python实现的k近邻算法，用于展示其原理和机制。该方法只实现了二维下的kNN对单个点的分类预测，可拓展到多维、多个对象的预测分类任务。该方法未过多考虑算法效率，内存开销、参数合法性检验等其它问题。

import random
import bisect

"""
该方法使用纯Python环境，展示kNN分类算法的基本原理。
该方法实现了二维的kNN对单个点的分类预测。可拓展到多维、多个对象的预测分类任务。
该方法未过多考虑算法效率，内存开销、参数合法性检验等。
"""

def cal_distance(a, b):
    """
    只计算平方和，省去开根号的计算开销。
    :param a:
    :param b:
    :return: 欧氏距离的平方
    """

    return (a[0]-b[0])**2 + (a[1]-b[1])**2


def kNNClassifier(train_set, k, i):
    """
    构造三个包含k个元素的列表，分别用来保存最小距离、最小距离点、点对应的分类标记。
    当数据集较大的时候，这个方法可能会快一点。数据集较小的时候，建议直接排序。
    :param train_set: 训练集
    :param k: 判定的邻居数量
    :param i: 预测点
    :return: 预测分类
    """

    # 使用训练集的第一个元素初始化三个列表
    distances = [cal_distance(train_set[0][0], i)]*k   # 从小到大排列的k个元素
    points = [train_set[0][0]]*k        # 与distances对应的点的列表
    labels = [train_set[0][13]]*k        # 与points对应的点的分类

    # 遍历训练集中的每个点
    for item in train_set:
        dis = cal_distance(item[0], i)   # 计算它与点i的距离
        if dis < distances[-1]:    # 如果这个距离比当前distances列表中最后一个元素的值小
            index = bisect.bisect(distances, dis)   # 使用Python内置的bisect二分法，查找插入的位置
            distances.insert(index, dis)   # 执行插入操作
            distances.pop()     # 弹出最后一个元素，保证distances中始终只有k个元素

            points.insert(index, item[0])   # 与上面的操作类似
            points.pop()

            labels.insert(index, item[1])   # 与上面的操作类似
            labels.pop()

    print('最小的距离值列表：   ', distances)
    print('对应的点的列表：   ', points)
    print('点的分类标记列表：   ', labels)

    # 统计每类标记的数量
    count_dic = {labels.count(key): key for key in set(labels)}

    # 返回数量最多的标记以及对应的数量
    return count_dic[max(count_dic)], max(count_dic)


if __name__ == '__main__':

    # random.seed(42)  # 如果不执行这行代码，每次生成的数据集都是随机的，结果不可重现。如果定义相同的seed，则每次执行的结果可重现。

    # 随机获取1万个，1-10000的整数点(x, y)
    random_points = [(random.randint(1, 10000), random.randint(1, 10000)) for _ in range(10000)]

    # print(points)
    # print(len(points))

    # 去掉可能产生的重复点，这可能导致实际训练集中点的数量小于10000.
    points = set(random_points)

    # print(points)
    # print(len(points))

    # 随机为每个点标记分类
    train_data = {}

    for item in points:
        train_data[item] = random.choice(['A', 'B'])   # 可以自己指定分类标记和数量

    # list(train_data.items())类似
    # [((4879, 4728), 'B'), ((7417, 3998), 'A'), ....,((3312, 4037), 'B'), ((1944, 7900), 'A')]
    predict, num = kNNClassifier(list(train_data.items()), 10, (23, 48))

    print('预测分类为：', predict, '  有{}个最近邻属于该分类'.format(num))

纯Python实现kNN机器学习算法

评论总数： 3