devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

机器学习————KNN算法_knn算法计算公式

作者：木道寻08 | 2024-06-28 19:37:33

赞

踩

knn算法计算公式

一、KNN算法介绍

1.1 KNN算法概述

KNN（K-Nearest Neighbor）算法是机器学习算法中最基础、最简单的算法之一，是一种分类和回归的统计方法，是监督学习。KNN通过测量不同特征值之间的距离来进行分类。所谓k近邻，就是k个最近的邻居的意思，说的是每个样本类别都可以用它最接近的k个邻居的类别来代表。 就比如：判断一个人的人品好坏，只需要观察与他来往最密切的几个人的人品好坏就可以得出，即“近朱者赤，近墨者黑"。

举个例子：

图中绿色的点是我们要预测的那个点，假设K=3。那么KNN算法就会找到与它距离最近的三个点，看看哪种类别多一些，例子中蓝色三角形有两个，红色圆有一个，那么新来的绿色点就归类到蓝三角了。

1.2 KNN算法的一般流程

1、收集数据：可以使用任何方法。
2、准备数据：距离计算所需要的数值，最好是结构化的数据格式。
3、分析数据：可以使用任何方法。
4、测试算法：计算错误率。
5、使用算法：
    5.1. 计算预测数据与训练数据之间的距离
    5.2. 将距离进行递增排序
    5.3. 选择距离最小的前K个数据
    5.4. 确定前K个数据的类别，及其出现频率
    5.5. 返回前K个数据中频率最高的类别（预测结果）

1.3 KNN算法的距离计算

KNN算法中对于距离的计算有好几种度量方式，比如欧式距离、曼哈顿距离、切比雪夫距离等等，最常用的就是欧式距离。

欧式距离计算公式：

\sqrt{\sum_{i=1}^{n}\left ( x_{i}-y_{i} \right )^{2}}

1.4 KNN算法的K值选择

K值的大小对算法的影响：

K值太大，会导致预测标签比较稳定，可能过平滑，容易欠拟合。

K值太小，会导致预测的标签比较容易受到样本的影响，容易过拟合。

所以对于K值的选取，我们通常使用交叉验证来验证，交叉验证：将样本数据按照一定比例，拆分出训练用的数据和验证用的数据，比如6：4拆分出部分训练数据和验证数据，从选取一个较小的K值开始，不断增加K的值，然后计算验证集合的方差，最终找到一个比较合适的K值。

二、实现KNN算法完成鸢尾花分类

2.1数据集介绍

鸢尾花数据集共收集了三类鸢尾花，即Setosa鸢尾花、Versicolour鸢尾花和Virginica鸢尾花，包括4个属性，分别为花萼的长、花萼的宽、花瓣的长和花瓣的宽。每个类别50个样本。

2.2代码介绍

2.2.1初始化数据集和数据集划分

读取数据集文件中的数据到列表中，因为数据集中单个数据特征是以,分隔开，所以按,分隔为一个样本数据再存到数组data_temp中

  1. # 初始化数据集
  2. def init(adder):
  3.     f = open(adder)  # 打开数据文件文件
  4.     lines = f.readlines()  # 把全部数据文件读到一个列表lines中
  5.     data_test = []
  6.     for line in lines:  # 把lines中的数据逐行读取出来
  7.         data_test.append(line.rstrip('\n').split(','))
  8.     data_temp = np.array(data_test)
  9.     return data_temp

使用numpy库把数据打乱，再按照指定比例把数据划分为数据集和验证集，用在确定模型准确率的时候使用

  1. # 将数据随机分为训练集和测试集
  2. def split_data(data, train_ratio):
  3.     np.random.shuffle(data)#打乱数据
  4.     train_size = int(len(data) * train_ratio)
  5.     train_data = data[:train_size]#按照比例划分
  6.     test_data = data[train_size:]
  7.     return train_data, test_data

2.2.2计算待测样本和数据集距离,并从距离最近的K个数据中来预测数据类别

通过数据特征来计算待测样本和数据集中每个数据的欧氏距离并存储，然后从存储的数据数组中按距离排序，再从最近的K个数据中找出出现次数最多的数据类别作为预测结果返回。

  1. # 计算两个样本之间的距离
  2. def distance_out(need_judge, source):
  3.     #类型转化
  4.     source = source.astype(float)
  5.     x = need_judge[0] - source[0]
  6.     y = need_judge[1] - source[1]
  7.     z = need_judge[2] - source[2]
  8.     r = need_judge[3] - source[3]
  9.     #计算欧氏距离
  10.     distance = math.sqrt((x ** 2 + y ** 2 + z ** 2 + r ** 2))
  11.     return distance
  12. # 计算待测样本与训练样本的距离
  13. def argue(need_judge, data_temp):
  14.     # 获取训练样本数量
  15.     times = data_temp.shape[0]
  16.     # 初始化一个数组来存储距离和类别信息
  17.     distance_all = np.zeros((1, 2))
  18.     for time in range(times):
  19.         #遍历样本，计算距离并存储距离和样本的类别
  20.         temp = data_temp[time]
  21.         temp_temp = temp[0:4]
  22.         distance_temp = distance_out(need_judge, temp_temp)
  23.         new_row = np.array((distance_temp, temp[4]), dtype=str)
  24.         new_row = np.array(new_row).reshape((1, 2))
  25.         #把包含距离和数据类别信息的新数组作为新的一行添加到distance_all中
  26.         distance_all = np.r_[distance_all, new_row]
  27.     return distance_all
  28. # 根据K近邻算法找到合适的类别
  29. def find_suitable(distance_all, K):
  30.     # 从距离数组中去除第一行（因为它是零行）
  31.     new_distance_all = distance_all[1:]
  32.     # 按距离对样本进行排序并获取索引
  33.     sorted_indices = np.argsort(new_distance_all[:, 0])
  34.     # 获取前K个最近的样本
  35.     min_k_rows = new_distance_all[sorted_indices[:K], :]
  36.     # 获取这些样本的类别
  37.     min_name = min_k_rows[:, 1]
  38.     # 统计类别出现的次数
  39.     counts = Counter(min_name.tolist())
  40.     # 找到出现次数最多的类别
  41.     most_common_str = max(counts, key=counts.get)
  42.     # 返回出现次数最多的类别
  43.     return most_common_str

2.2.3预测结果和使用验证集计算准确率

通过计算待测样本和数据样本之间的距离并找到最合适的类别，以及把数据集划分为训练集和验证集来计算准确率

  1. # 预测结果
  2. def train(need_judge, K, data):
  3.     # 计算待测样本与训练样本的距离并找到最合适的类别
  4.     distance_all = argue(need_judge, data)
  5.     kinds = find_suitable(distance_all, K)
  6.     return kinds
  7.  
  8. # 从样本数据中获取特征值
  9. def get_point(data):
  10.     #print("Data:", data)
  11.     #print("Data size:", len(data))
  12.     return data[0], data[1], data[2], data[3]
  13.  
  14. # 计算模型的准确率
  15. def ua(K, train_ratio):
  16.     # 初始化数据集
  17.     data = init(data_address)
  18.     # 划分训练集和测试集
  19.     train_data, test_data = split_data(data, train_ratio)
  20.     # 获取测试集的数量
  21.     data_number = test_data.shape[0]
  22.     right = 0
  23.     faid = 0
  24.     count = 0
  25.     # 对每个测试样本进行预测
  26.     for temp in test_data:
  27.         count += 1
  28.         print("正在进行第", count, "次验证")
  29.         # 获取特征值
  30.         x, y, z, r = get_point(temp)
  31.         need_judge = np.array([x, y, z, r], dtype=float)
  32.         # 预测样本类别
  33.         judge = train(need_judge, K, train_data)
  34.         # 统计预测正确和错误的样本数量
  35.         if judge == temp[4]:
  36.             right += 1
  37.         else:
  38.             faid += 1
  39.     # 计算准确率
  40.     right_faid = (float)((right) / (test_data.shape[0]))
  41.     print("当前模型的成功率是百分之", right_faid * 100)

2.2.4交互界面

写了一点简单交互，让用户选择是进行预测还是进行计算准确率以及是否退出，在进行预测和准确率计算时都有让用户输入K值，并且在计算准确率时还有让用户指定训练集和验证集的比例。

  1. if __name__ == '__main__':
  2.     while True:
  3.         choose = input("1.查看准确率\n"
  4.                        "2.开始预测\n"
  5.                        "3.退出\n")
  6.  
  7.         if choose == '1':
  8.             K = int(input("输入K: "))
  9.             train_ratio = float(input("输入训练集比例(例如0.8表示80%): "))
  10.             ua(K, train_ratio)
  11.         elif choose == '2':
  12.             K = int(input("输入K: "))
  13.             x = float(input("输入特征值1: "))
  14.             y = float(input("输入特征值2: "))
  15.             z = float(input("输入特征值3: "))
  16.             r = float(input("输入特征值4: "))
  17.             need_judge = np.array([x, y, z, r], dtype=float)
  18.             data = init(data_address)
  19.             kinds = train(need_judge, K, data)
  20.             print("根据您输入的预测值，模型猜测结果是", kinds)
  21.         elif choose == '3':
  22.             break
  23.         else:
  24.             print("输入错误")
  25.     print("欢迎下次使用")

2.2.5遇到的问题

在写train函数时，考虑的是在预测时的使用，所以一开始写的下面这个样子

  1. # 预测结果
  2. def train(need_judge, K):
  3.     # 初始化数据集
  4.     data = init(data_address)
  5.     # 计算待测样本与训练样本的距离并找到最合适的类别
  6.     distance_all = argue(need_judge, data)
  7.     kinds = find_suitable(distance_all, K)
  8.     return kinds

导致在计算准确率中的验证时会有冲突，所以最后使用这个版本，而在预测时选择重新初始化一次数据来传参。

  1. # 预测结果
  2. def train(need_judge, K, data):
  3.     # 计算待测样本与训练样本的距离并找到最合适的类别
  4.     distance_all = argue(need_judge, data)
  5.     kinds = find_suitable(distance_all, K)
  6.     return kinds

2.3结果截图展示

查看准确率

预测

三、总结

3.1KNN算法的优点

1. 简单易实现：KNN算法的原理简单，易于理解和实现，无需训练过程

2.适用于多分类问题：KNN算法可以应用于多分类问题，并且对样本分布的假设较少。

3.对异常值不敏感：KNN算法对异常值不敏感，因为它是通过距离计算来确定最近邻样本，即使某个样本是异常值，也不会对整体结果产生很大影响

3.2KNN算法的缺点

1.计算复杂度高：KNN算法需要计算测试样本与所有训练样本之间的距离，计算复杂度较高，尤其是在大规模数据集上。

2.高度数据相关：KNN算法依赖于特征空间中的距离度量，如果特征空间中的距离度量不合理或者特征权重不准确，可能会导致预测性能下降。

3.决策边界不规则：KNN算法的决策边界通常是不规则的，因为它只考虑了局部样本的信息，而没有对全局进行建模。
4.对内存要求较高，因为该算法存储了所有训练数据。
5.预测阶段可能很慢：如果数据样本过多的话，需要全部遍历就会耗时间。

3.3思考

3.3.1KNN算法是否可以用于DNA检测等任务中

应该是可以。但是效率应该会很低，因为大多数的DNA序列数据巨大，数据特征的高维度再加上组合的多样性会导致计算效率很低，从而导致预测效率很低。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号