【20210922】【机器/深度学习】KNN (K近邻) 算法详解

小鱼儿 2022-09-12 06:43 212阅读 0赞

# 一、算法概念 #

KNN, K-near neighbor，即最近邻算法。它是一种分类算法，算法思想是：一个样本与数据集中的 k 个样本最相似，如果这 k 个样本中的大多数属于某一个类别，则该样本也属于这个类别，即每个样本都可以用它最接近的 k 个邻居来代表。

**KNN 算法的关键点有两个：k 值的选择和点距离（通常使用欧氏距离）的计算。**

**KNN是一种非参的、惰性的算法模型。**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16][]

# 二、基本流程 #

第一步：计算已知类别数据集中的点与当前点之间的距离；

第二步：按距离递增排序；

第三步：选取与当前点距离最小的 k 个点；

第四步：统计前 k 个点所在的类别出现的频率；

第五步：返回前 k 个点出现频率最高的类别作为当前点的预测分类。

# 三、K值的选择 #

### 1. 近似误差和估计误差 ###

近似误差：对现有训练集的训练误差，更关注于”训练“；

估计误差：对测试集的测试误差，更关注于”测试“、”泛化“。

（参考：[近似误差和估计误差][Link 1]）

### 2. k 值的选择 ###

k 值过小，相当于用较小领域中的训练实例进行预测，学习的近似误差会减小，缺点是学习的估计误差会增大，预测结果会对近邻的实例点分成敏感，如果周围刚好是噪声，那么预测就会出错。所以 k 值过小，容易发生过拟合；（可以这么理解，k 值过小，可用的邻域较小，类似于模型训练时训练集小，那么容易出现过拟合。）

k 值过大，相当于用较大邻域中的训练实例进行预测，优点是可以减少学习的估计误差，但近似误差会增大。

**通常通过交叉验证来选取最优的 k 值。****（详见交叉验证那一篇 blog~）**

# 四、优缺点 #

### 1. 优点 ###

（1）简单易用；

（2）模型训练时间快（惰性模型，不需要对数据作出任何的假设，完全根据数据决定）；

（3）预测效果好；

（4）对异常值不敏感。

### 2. 缺点 ###

（1）计算量较大，预测阶段可能较慢；

（2）对内存要求高，该算法存储了所有训练数据；

（3）对不相关的功能和数据规模敏感。

**总结来说，当数据量比较大的时候，如果需要用分类算法，那么就可以尝试使用 KNN 算法进行分类了。**

（参考：[深入浅出KNN算法（一） KNN算法原理][KNN_ KNN]）

# 五、简单示例 #

### 1. 手撕 KNN 算法 ###

（参考：[机器学习之KNN（k近邻）算法详解][KNN_k]）

'''
        功能：根据每部电影内搞笑镜头、拥抱镜头、打斗镜头出现的次数对测试电影样本进行分类
        分类算法：KNN
        距离计算方式：欧氏距离
    '''
    
    # 第一步：导入函数库
    import numpy
    import pandas as pd
    import math
    import matplotlib.pyplot as plt
    
    
    # 第二步：确认训练集和测试样本
    #     测试样本：唐人街探案[23, 3, 17, '？片']
    #     训练集数据如下
    movie_data = {
        '宝贝当家': [45, 2, 9, '喜剧片'],
        '美人鱼': [21, 17, 5, '喜剧片'],
        '澳门风云3': [54, 9, 11, '喜剧片'],
        '功夫熊猫3': [39, 0, 31, '喜剧片'],
        '谍影重重': [5, 2, 57, '动作片'],
        '叶问3': [3, 2, 65, '动作片'],
        '伦敦陷落': [2, 3, 55, '动作片'],
        '我的特工爷爷': [6, 4, 21, '动作片'],
        '奔爱': [7, 46, 4, '爱情片'],
        '夜孔雀': [9, 39, 8, '爱情片'],
        '代理情人': [9, 38, 2, '爱情片'],
        '新步步惊心': [8, 34, 17, '爱情片']
    }
    
    
    # 第三步：计算测试样本到训练集各个电影的距离
    x = [23, 3, 17]
    dist = []
    for key, value in movie_data.items():
        d = math.sqrt((x[0]-value[0])**2 + (x[1]-value[1])**2 + (x[2]-value[2])**2)
        dist.append([key, round(d, 2)])
    
    print(dist)
    
    
    # 第四步：对距离大小按递增排序
    dist.sort(key=lambda dis: dis[1])
    print(dist)
    
    
    # 第五步：选取距离最小的 k 个样本，这里选取 k=5
    distK5 = dist[:5]
    print(distK5)
    
    
    # 第六步：确定前 k 个样本所在类别出现的频率，并输出出现频率最高的类别
    label_times = {'喜剧片': 0, '动作片': 0, '爱情片': 0}
    for s in distK5:
        label = movie_data[s[0]][-1]
        label_times[label] += 1
    
    print(label_times)
    
    print(label_times.items())
    
    label_times_sorted = sorted(label_times.items(), key=lambda l: l[1], reverse=True)
    print(label_times_sorted, label_times_sorted[0][0], sep='\n')

**几个中间运行结果：**

1. 测试样本到训练集样本的距离

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

2. 排序后的距离

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

3. 离测试样本最近 5 个训练样本的距离

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

4. 最近的 5 个训练样本的标签出现频率（dict 类型）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_12_color_FFFFFF_t_70_g_se_x_16][]

5. dict\_items 类型数据

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_18_color_FFFFFF_t_70_g_se_x_16][]

6. 按标签频率排序后的标签及频率（list 类型，元素为 tuple 类型）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_14_color_FFFFFF_t_70_g_se_x_16][]

7. 测试样本最终标签

![20210922165948203.png][]

### 2. 调用 Python 函数库 ###

# 第一步：导入函数库
    from sklearn import neighbors
    
    
    # 第二步：确认训练集和测试样本
    movie_data = {
        '宝贝当家': [45, 2, 9, '喜剧片'],
        '美人鱼': [21, 17, 5, '喜剧片'],
        '澳门风云3': [54, 9, 11, '喜剧片'],
        '功夫熊猫3': [39, 0, 31, '喜剧片'],
        '谍影重重': [5, 2, 57, '动作片'],
        '叶问3': [3, 2, 65, '动作片'],
        '伦敦陷落': [2, 3, 55, '动作片'],
        '我的特工爷爷': [6, 4, 21, '动作片'],
        '奔爱': [7, 46, 4, '爱情片'],
        '夜孔雀': [9, 39, 8, '爱情片'],
        '代理情人': [9, 38, 2, '爱情片'],
        '新步步惊心': [8, 34, 17, '爱情片']
    }
    x = [23, 3, 17]
    
    x_train = [v[:3] for key, v in movie_data.items()]
    y_train = [v[3:][0] for key, v in movie_data.items()]
    
    
    # 第三步：训练模型
    knn = neighbors.KNeighborsClassifier(n_neighbors=5)
    knn.fit(x_train, y_train)
    
    
    # 第四步：测试样本预测
    y_train_pre = knn.predict(x_train)
    y_test_pre = knn.predict([x])

### 3. knn 函数库参数详解 ###

from sklearn import neighbors
    
    neighbors.KNeighborsClassifier(n_neighbors=5, weight='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=1)
    
    # n_neighbors：近邻样本个数，默认为 5；
    # weights：指定近邻样本的投票权重，默认为"uniform"，表示所有紧邻样本的投票权重相同；如果为"distance"，则表示投票权重与距离成反比；
    # algorithm：指定近邻样本的搜寻算法，如果为"ball_tree"，表示使用球树搜寻法寻找紧邻样本；如果为"kd_tree"，表示使用KD树搜寻法寻找紧邻样本；如果为"brute"，表示使用暴力搜寻法寻找近邻样本；默认为"auto"，表示根据数据特征自动选择最佳的搜寻算法；
    # leaf_size：指定球树或KD树叶子节点所包含的最小样本量，用于控制数的生长条件，会影响树的查询速度；
    # metric：用于指定距离的度量指标，默认为闵可夫斯基距离；
    # p：当参数metric为闵可夫斯基距离时，p=2表示计算点之间的欧氏距离；
    # metric_params：为metric参数所对应的距离指标添加关键字参数
    # n_jobs：用于设置knn算法并行计算所需的CPU数量。

（参考：[Python 第三方库Knn算法][Python _Knn]）

# 六、知识点 #

### 1. KNN 是监督学习，K-means 是无监督学习。 ###

### 2. 交叉验证 ###

将样本数据按照一定比例，拆分出训练用的数据和验证用的数据，比如 6:4 拆分出部分训练数据和验证数据，从选取一个较小的 k 值开始，不断增加 k 的值，然后计算验证集合的方差，最终找到一个比较合适的 k 值。

（详解见：[【20210922】【机器/深度学习】K折交叉验证（k-fold cross validation）][20210922_K_k-fold cross validation]）

### 3. dict items的用法 ###

dict.items()：以**列表**返回可遍历的 (key, value) **元胞**数组。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_19_color_FFFFFF_t_70_g_se_x_16][]

（参考：[Python 字典(Dictionary) items()方法][Python _Dictionary_ items]）

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3574a24a37c14a03a2c597faf9cd8fae.png
[Link 1]: https://www.jianshu.com/p/ff0af5de4935
[KNN_ KNN]: https://www.cnblogs.com/listenfwind/p/10311496.html
[KNN_k]: https://blog.csdn.net/sinat_30353259/article/details/80901746
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/847f90bced524bcb8c9b891485302f25.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/a9d118d4695e4c59986d1ec2b0fc2b94.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/c385dd6ad21647f4bae26a4246b6008a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/445ca317864942cc8bc81d9fe064d8e2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/dd4e7896801449a7b6fe1287799b8fd5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/20519a33421e441e83a918225227b724.png
[20210922165948203.png]: /images/20220828/5c16e00a0d604cf095ddcee1169002b3.png
[Python _Knn]: https://www.cnblogs.com/LiErRui/articles/11361167.html
[20210922_K_k-fold cross validation]: https://blog.csdn.net/weixin_40583722/article/details/120416029
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAU2F0aXNmeWluZw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d40d9e5eb80747279966367a7defca5e.png
[Python _Dictionary_ items]: https://www.runoob.com/python/att-dictionary-items.html