机器学习实战之kNN算法

左手的ㄟ右手 2022-05-26 22:25 287阅读 0赞

**一、kNN算法基本概念**

> 1.  基本概念： kNN算法采用测量不同特征值之间的**距离**方法进行分类
> 2.  kNN算法  
>     a.优点：精度高、对异常值不敏感、无数据输入假定  
>     b.缺点：计算复杂度高、空间复杂度高  
>     c\*\*.使用数据范围：数值型和标称型。（标称型：一般在有限的数据中取，而且只存在‘是’和‘否’两种不同的结果，一般用于分类；数值型：可以在无限的数据中取，而且数值比较具体化，例如4.02,6.23这种值（一般用于回归分析））\*\*
> 3.  kNN工作原理：训练样本集中的每个数据都存在标签（即知道样本集中每一数据与所属分类的对应关系），输入待分类（没有标签）的新数据后，**将新数据的每个特征与样本集中数据对应的特征进行比较（求距离的过程）**，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，故称为kNN算法，通常k是不大于20的整数。**最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。**
> 
> kNN算法伪代码  
> （1）计算已知类别数据集中的每个点与当前点的距离，可以使用欧式距离公式  
> ![这里写图片描述][70]  
> （2）按照距离递增次序排序  
> （3）选取与当前距离最小的k个点  
> （4）确定前k个点所在类别的出现频率  
> （5）返回前k个点出现频率最高的类别作为当前点的预测分类

**二、kNN算法的Python3实现**

# -*- coding: utf-8 -*-
    import numpy as np
    import operator
    """ 模拟一个电影训练数据集 打斗镜头 接吻镜头 所属分类 1.0 1.1 A 1.0 1.0 A 0 0 B 0 0.1 B """
    def create_traing_dataset():
        features = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
        labels = ['A', 'A', 'B', 'B']
        return features, labels
    """ inX：输入的待分类的样本，结构为[x, y] features:电影训练数据集的镜头特征，结构为[打斗镜头， 接吻镜头] labels:电影训练数据集的电影分类， k:kNN算法的前k个点 return；返回inX最可能所属的电影分类 """
    def classify0(inX, features, labels, k):
        # 输入的是一个样本点，为了训练数据集中所有点计算距离，需要将其扩展成与features形状相同的矩阵
        # 注意：接下来的操作是以矩阵或向量为单位进行的
        rows = features.shape[0]
        matrix = np.tile(inX, (rows, 1))
    
        # 应用欧几里得函数计算距离
        # 1、作差
        diff_mat = matrix - features
        # 2、平方
        sq_diff_mat = diff_mat ** 2
        # 3、以行为单位求和
        sq_distances = sq_diff_mat.sum(axis=1)
        # 4、求平方根
        distances = sq_distances ** 0.5
        # 欧几里得函数计算结束，此时distances中存储的就是inX到features中的距离
        # 按距离进行升序排序，因为这里features和labels是割裂的，其关系是用下标维护的
        # 所以用argsort排序，返回distances排序后的下标，sorted_dist_indices中存储的下标
        sorted_dist_indices = distances.argsort()
        # 排序完成后，对前k个数据，用字典统计“电影类型：频率”
        class_count = {}
        for i in range(k):
            vote_label = labels[sorted_dist_indices[i]]
            class_count[vote_label] = class_count.get(vote_label, 0) + 1
        #统计完成，按value出现频率降序排序，转为列表，第一个元素即为inX所属电影分类
        sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
        return sorted_class_count[0][0]
    
    # 测试
    features, labels = create_traing_dataset()
    inX = [0, 0]
    k = 3
    inX_label = classify0(inX, features, labels, k)
    print(inX, "属于", inX_label)

**三、总结说明**  
kNN算法不难理解，可是在用python实现时，还是有一些常用的小技巧的，这里总结一下：

1.  将输入的向量inX用numpy的tile函数扩展为矩阵，后续统一以矩阵为单位进行操作，关于tile函数的使用可见[博文][Link 1]
2.  Python 字典(Dictionary) get() 函数返回指定键的值，如果值不在字典中返回指定值：class\_count\[vote\_label\] = class\_count.get(vote\_label, 0) + 1。通过使用这种方式就将key不存在时的处理和加一操作统一了起来
3.  使用python内置的sorted函数对字典按照value进行降序排序：sorted\_class\_count = sorted(class\_count.items(), key=operator.itemgetter(1), reverse=True)，其中operator.itemgetter方法实现按指定域进行排序
4.  可以看到python，尤其是numpy中很多时候都是以矩阵为单位进行操作的，这不同于以往的编程，这是数据分析的特点，所以我们在解决问题的时候，为了理清思路，可以先用线性代数进行手工模拟，再用代码进行实现
5.  要充分将语言的特性与所要解决的问题联系起来，毕竟互联网只是一个工具，起到的是一个桥梁连接作用

[70]: /images/20220527/7902b6285eb8475aa1538b3d6bf169af.png
[Link 1]: https://blog.csdn.net/newmemory/article/details/79859098