KNN

KNN及其作业

KNN算法原理

​ KNN得全称是K Nearest Neighbors,也被称作最邻近算法，k是指k个最近的邻居的意思，KNN属于一种分类算法。

​ KNN算法的思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

​ 那么我们如何更好的进行了解呢，图示无疑是最好理解的， 我们要确定绿点属于哪个颜色（红色或者蓝色），要做的就是选出距离目标点距离最近的k个点，看这k个点的大多数颜色是什么颜色。当k取3的时候，我们可以看出距离最近的三个，分别是红色、红色、蓝色，因此得到目标点为红色。

算法描述

步骤描述

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点；

4）确定前K个点所在类别的出现频率；

5）返回前K个点中出现频率最高的类别(决策依据方法之一)作为测试数据的预测分类。

简单来说就是：准备数据，计算距离，数据排序，确定K值，寻找邻居，决策分类

距离计算的方法

这里的距离指的是平面上两个点的直线距离。常用的距离计算公式有：

1. 闵可夫斯基距离
2. 欧几里得距离
3. 曼哈顿距离
4. 切比雪夫距离
5. 马氏距离
6. 余弦相似度
7. 皮尔逊相关系数
8. 汉明距离
9. 杰卡德相似系数
10. 编辑距离
11. DTW 距离
12. KL 散度

欧式距离

欧式距离全称欧几里得距离，公式为：
$$
d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}
$$

K值的选择

K称为临近数，即在预测目标点时取几个临近的点来预测。

K值得选取非常重要，因为：

1. 如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
2. 如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单，也就是容易发生欠拟合；
3. 如果K=N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；

为此我们可以这样取K的值:

1. 从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K；
2. 一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大；
3. K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。

关于决策依据/规则

最常用的决策规则是：

1. 多数表决法(更常用)：多数表决法类似于投票的过程，也就是在 K 个邻居中选择类别最多的种类作为测试样本的类别；
2. 加权表决法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大，通过权重计算结果最大值的类为测试样本的类别。

优点

1）简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；

2）可用于数值型数据和离散型数据；

3）训练时间复杂度为O(n)；无数据输入假定；

4）对异常值不敏感。

缺点

1）计算复杂性高；空间复杂性高；

2）样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；

3）一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分；

4）最大的缺点是无法给出数据的内在含义。

代码实现

上面的内容大部分是引用的别人写的，代码部分是我在他的代码的理解基础上重新敲的

#time/2022/1/28
#调用库
import numpy as np
import matplotlib.pyplot as plt
from math import sqrt

#初始化原始数据
data=[[1,0.9],[1,1],[0.1,0.2],[0,0.1]]
labels=["A","A","B","B"]
test_data=[[0.1,0.3]]
#print(labels)

#绘制初始化数据散点图
#print(data[0][1])
print("===============================数据准备================================")
print("原始数据图像绘制...")
for i in range(len(data)):
    plt.scatter(data[i][0],data[i][1],color="b")
plt.scatter(test_data[0][0],test_data[0][1],color="r")
plt.show()

#采用距离方式进行计算
x=[[0.1,0.3]]
distance=[]
labels_xy=[]
for i in range(len(data)):
    d=0
    d=sqrt((x[0][0]-data[i][0])**2+(x[0][1]-data[i][1])**2)
    distance.append(d)
    labels_xy.append(i)
print("计算的距离为: ",distance)
print("现在对应的标签位置为: ",labels_xy)

#按照升序，对距离进行排序并取前三个数
print("===============================距离排序================================")
for i in range(len(data)-1):
    for j in range(i+1,len(data)):
        if distance[i] > distance[j]:
            distance[i],distance[j] = distance[j],distance[i]
            labels_xy[i],labels_xy[j] = labels_xy[j],labels_xy[i]
print("排序后的距离为: ",distance)
print("对应的标签的位置为: ",labels_xy)
print("取距离最近的3个值:",distance[0:3])


#进行投票表决
print("===============================表决投票================================")
A = 0
B = 0
for i in range(3):
    if labels[labels_xy[i]] == "A":
        A+=1
    else:
        B+=1
print("投票为A的数量为:",A)
print("投票为B的数量为:",B)
print("对照初始图中红色点(测试点)与前两个标签为A的离的最近,所以我们的计算与图中所呈现的结果一致!")

本次作业实现

knn1

本次作业是要求填写出所空的代码，并且能够对代码理解，下面有我的运行结果，由于我还不会在博客上上传图片，所以显示不成图片信息，还有就是uniform这个函数我在pycharm上无法运行，所以我把uniform换成了random.uniform,这样填好代码就可以运行了。

import matplotlib.pyplot as plt
import matplotlib
from math import sqrt
import random
#将代码中缺失部分_ _ _ _ _补充完整，成功运行代码将样本点test_data分类（AorB）。

##### 初始化数据集 #####
m = 60 #数据个数
data_A = [[],[]]#数据集 A
data_B = [[],[]]#数据集 B
for i in range(m):
    if i < m/2: 
        data_A[0].append(random.uniform(1,5))#随机设定
        data_A[1].append(random.uniform(1,5))
    elif i < m:
        data_B[0].append(random.uniform(6,10))
        data_B[1].append(random.uniform(1,5))
test_data = [[4.5],[4.5]]#测试集
len_A = len(data_A[0])
len_B = len(data_B[0])

##### 计算距离并排序 #####
distance_A = []#与 A 类数据之间的距离
distance_B = []#与 B 类数据之间的距离
distance = []#全部距离
#计算距离（使用欧氏距离）
for i in range(len_A):
    d = sqrt((test_data[0][0]-data_A[0][i])**2+(test_data[1][0]-data_A[1][i])**2)
    distance_A.append(d)
for i in range(len_B):
    d = sqrt((test_data[0][0] - data_B[0][i]) ** 2 + (test_data[1][0] -data_B[1][i]) ** 2)
    distance_B.append(d)
#由小到大排序（此处使用冒泡排序）
distance = distance_A + distance_B
for i in range(len(distance)-1):
    for j in range(len(distance)-i-1):
        if distance[j] > distance[j+1]:
            distance[j],distance[j+1]=distance[j+1],distance[j]
print("距离所有A类数据的距离为：")
print(distance_A)
print("距离所有B类数据的距离为：")
print(distance_B)
print()
print("对所有的距离升序排序：")
print(distance)
print()

##### 按 K 最近领对测试集进行分类 #####
K = 5
number_A = 0
number_B = 0
#定义删除函数，避免对同一个数据重复计算
def delete(a,b,ls):
    for i in range(b):
        if ls[i]==a:
            ls.pop(i)
            break
#找出与测试数据最接近的 K 个点
for i in range(K):
    if distance[i] in distance_A:
        number_A += 1
        delete(distance[i],len(distance_A),distance_A)
        continue
    if distance[i] in distance_B:
        number_B += 1
        delete(distance[i],len(distance_B),distance_B)
        continue
print("最终结果：")
print("距离待测数据最近的K={:}个数据中，A类数据有{:}个，B类数据有{:}个".format(K,number_A,number_B))
if number_A > number_B:
    print("所以K={:}时，待测数据划分为A类".format(K))
else:
    print("所以K={:}时，待测数据划分为B类".format(K))

##### 画图 #####
matplotlib.rcParams['font.sans-serif'] = ['SimHei']
for i in range(len_A):#A 类，用红色三角形表示
    if i!=len_A-1:
        plt.plot(data_A[0][i],data_A[1][i],'bo',marker='^',color='red')
    else:
        plt.plot(data_A[0][i],data_A[1][i],'bo',marker='^',label='A',color='r')
    #使用 if..else... 是为了避免在图形中重复出现多个标签
for i in range(len_B):#B 类，用蓝色正方形表示
    if i!=len_B-1:
        plt.plot(data_B[0][i],data_B[1][i],'bo',marker='s',color='blue')
    else:
        plt.plot(data_B[0][i],data_B[1][i],'bo',marker='s',label='B',color='b')
plt.plot(test_data[0][0],test_data[1][0],'bo',label='待测数据',color='g')#测试集
plt.xlim(0,10)
plt.ylim(0,10)
plt.legend()
plt.show()

代码运行结果

距离所有A类数据的距离为：
[0.5730634008409403, 3.374734638082625, 4.85238240997041, 1.1386161987769003, 1.3317711401556285, 3.313578111859537, 1.3580830822988061, 1.0734562239393441, 2.008003589617018, 2.0908790315605903, 2.7563597649309943, 3.1933943316208713, 2.6192587763046205, 3.702570545599137, 1.1421411050405643, 2.4799057257365527, 2.235880491670782, 3.593447123627203, 2.9883415325535485, 0.7183532882000413, 3.233504674274472, 2.8400107982328113, 1.554444319906202, 1.5442328971482595, 2.3862341428178944, 2.8407374819139375, 1.5886655333251416, 3.686640883839242, 2.56964609320574, 2.1995320416821915]
距离所有B类数据的距离为：
[5.462302561243948, 3.189998295980043, 5.66016413616719, 2.873928268889639, 2.3588178825180557, 2.845114087378123, 6.249833647339466, 3.6667688503752824, 5.403234449841704, 5.3961820751599445, 5.519290431682128, 4.016026264463092, 4.0860089015555605, 5.027424253197781, 2.2831780876191945, 3.95232218924902, 3.1903419671827993, 5.4025201378493355, 3.5581570467940487, 4.793138584901225, 4.568908221063331, 5.173404779952996, 5.87769926986507, 2.3360721703587806, 1.9668120277152399, 5.160946046477953, 3.1221574869993782, 4.007579734814456, 3.689644116446279, 2.9587240140651914]

对所有的距离升序排序：
[0.5730634008409403, 0.7183532882000413, 1.0734562239393441, 1.1386161987769003, 1.1421411050405643, 1.3317711401556285, 1.3580830822988061, 1.5442328971482595, 1.554444319906202, 1.5886655333251416, 1.9668120277152399, 2.008003589617018, 2.0908790315605903, 2.1995320416821915, 2.235880491670782, 2.2831780876191945, 2.3360721703587806, 2.3588178825180557, 2.3862341428178944, 2.4799057257365527, 2.56964609320574, 2.6192587763046205, 2.7563597649309943, 2.8400107982328113, 2.8407374819139375, 2.845114087378123, 2.873928268889639, 2.9587240140651914, 2.9883415325535485, 3.1221574869993782, 3.189998295980043, 3.1903419671827993, 3.1933943316208713, 3.233504674274472, 3.313578111859537, 3.374734638082625, 3.5581570467940487, 3.593447123627203, 3.6667688503752824, 3.686640883839242, 3.689644116446279, 3.702570545599137, 3.95232218924902, 4.007579734814456, 4.016026264463092, 4.0860089015555605, 4.568908221063331, 4.793138584901225, 4.85238240997041, 5.027424253197781, 5.160946046477953, 5.173404779952996, 5.3961820751599445, 5.4025201378493355, 5.403234449841704, 5.462302561243948, 5.519290431682128, 5.66016413616719, 5.87769926986507, 6.249833647339466]

最终结果：
距离待测数据最近的K=5个数据中，A类数据有5个，B类数据有0个
所以K=5时，待测数据划分为A类

分析：其实我们光看数据随机生成的范围就可以看出，因为测试数据是的大小是在A旁边的，所以距离测试数据的K个最近值肯定大部分都在A区了，所以说待测数据划分成了A类，但是为了避免这样，我们可以在A与B之间来初始化测试数据的。

knn2

这个作业也是对代码进行补充的，下面是代码

import math
#将代码中缺失部分_ _ _ _ _ _补充完整，成功运行代码将样本电影分类
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, "爱情片"]}

# 测试样本  唐人街探案": [23, 3, 17, "？片"]
#下面为求与数据集中所有数据的距离代码：
x = [23, 3, 17]
KNN = []
#计算样本与数据间距离（欧氏距离）
#下面循环说明，例，第一次循环时key=“宝贝当家”；v=[45, 2, 9, "喜剧片"]，v为列表
#a**2即为a的2次方
for key, v in movie_data.items():
    d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2)
    KNN.append([key, round(d, 2)])

# 输出所用电影到 唐人街探案的距离
print("所有样本到唐人街探案的距离：")
print(KNN)

#按照距离大小进行递增排序
KNN.sort(key=lambda dis: dis[1])

#选取距离最小的k个样本，这里取k=5；
KNN=KNN[:5]
print("距离最近的五个样本：")
print(KNN)

#确定前k个样本所在类别出现的频率，并输出出现频率最高的类别
labels = {"喜剧片":0,"动作片":0,"爱情片":0}
for s in KNN:
    label = movie_data[s[0]]
    labels[label[3]] += 1
labels =sorted(labels.items(),key=lambda l: l[1],reverse=True)
print(labels)
print("《唐人街探案》属于")
print(labels[0][0],sep='\n')

运行结果:

所有样本到唐人街探案的距离：
[['宝贝当家', 23.43], ['美人鱼', 18.55], ['澳门风云3', 32.14], ['功夫熊猫3', 21.47], ['谍影重重', 43.87], ['叶问3', 52.01], ['伦敦陷落', 43.42], ['我的特工爷爷', 17.49], ['奔爱', 47.69], ['夜孔雀', 39.66], ['代理情人', 40.57], ['新步步惊心', 34.44]]
距离最近的五个样本：
[['我的特工爷爷', 17.49], ['美人鱼', 18.55], ['功夫熊猫3', 21.47], ['宝贝当家', 23.43], ['澳门风云3', 32.14]]
[('喜剧片', 4), ('动作片', 1), ('爱情片', 0)]
《唐人街探案》属于
喜剧片

理论参考链接：https://stoic-shaw-839c64.netlify.app/ai/knn/

赏

谢谢你请我吃糖果

支付宝

微信