纯Python实现kNN机器学习算法

刘江     2019年03月03日    分类: 技术分享   机器学习   标签: Python   机器学习   阅读:  879     评论3


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


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

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

image.png-70.6kB

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

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

比如,在分类任务中可以使用‘投票法’,选择邻居最多的那一类;在回归任务中使用‘平均法’,将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))


评论总数: 3



user_image

试试 微博接入.!



user_image

还有评论回复的感觉!



user_image

k近邻



博客目录:


    最新博客:

    Django之contenttypes框架
    Django REST framework 核心组件: 序列化器
    HTTPie--命令行下的HTTP工具
    独家首发!Django2.2新特性
    纯Python实现kNN机器学习算法