最邻近规则分类 KNN (K-Nearest Neighbor)算法及python实现

简介: 最邻近规则分类 KNN (K-Nearest Neighbor)算法及python实现

我的微信公众号名称深度学习与先进智能决策

微信公众号ID:MultiAgent1024

公众号介绍:主要研究强化学习、计算机视觉、深度学习、机器学习等相关内容,分享学习过程中的学习笔记和心得!期待您的关注,欢迎一起学习交流进步!

KNN算法是学者Cover和Hart早在1968年提出的算法,最初的最邻近规则分类算法最早也是被用来处理分类的问题,是基于实例的学习(instance-based learning),也叫做懒惰学习(lazy learning),之所以这么说呢,是因为最开始我们并不设计算法的模型,而是基于实例来给他归类。

假设我们有一个电影集,我们有一个任务,来给电影分类。电影有很多类型,如浪漫的,动作片。对于每个电影我们可以把它想象成实例,我们的任务是给他归类,在实例中我们可以提取不同的特征值,在下面的这张图片中我们提取了两个特征值:打斗次数,接吻次数。最终实现对未知电影根据特征值分类。

首先我们如何将电影这个例子表达得更像一个数学模型,我们可以表达地如下图所示:

也就是我们可以把每部电影表达为每个实例点,每个点相当于空间中的多维向量,我们的目的是为了将其归类。

KNN算法祥述

为了判断未知实例的类别,以所有已知类别的实例作为参考,选择参数K,计算未知实例与所有已知实例的距离,选择最近K个已知实例,根据少数服从多数的投票法则(majority-voting),让未知实例归类为K个最邻近样本中最多的类别。举个例子来说呢就是:

假设我们有一个豆子A,我们不知道他是哪一类的,我们根据已知的这三类豆子给他进行分类。我们选择最近的K个豆子,假设K=3,那么我们就看这最近的三个豆子属于哪一类,并根据少数服从多数的投票法则来判断这个豆子A的类别。

细节

K如何选取?我们可以依据训练时候的准确度来选取。

关于距离的衡量方法:

Euclidean Distance(欧几里得距离

其他距离衡量:余弦值(cos),相关度(correlation),曼哈顿距离(Manhanttan distance)

以上面所讲的电影的数据集为例,介绍一下具体的算法工作流程:

1. 算G点到A、B、C、D、E、F,点的距离,程序计算欧几里得距离如下(以A和G点之间的距离为例):

 import math
 def ComputeEuclideanDistance(x1, y1, x2, y2):
     d = math.sqrt(math.pow((x1 - x2), 2) + math.pow((y1- y2), 2))
 return d
 d_ag = ComputeEuclideanDistance(18, 90, 3, 104)
 print(d_ag)

2. 之后的话我们选取三个距离最小的三个临近豆子,看这三个临近豆子属于哪一类,用少数服从多数的原则判别出这个豆子的种类。

KNN的算法对K的选择非常敏感,如下图所示:

算法优点:简单;易于理解;容易实现;通过对K的选择可具备丢噪音数据的健壮性。

算法缺点:需要大量空间存储所有已知实例;算法复杂度高(需要比较所有已知实例与要分类的实例);当其样本分布不平衡时,比如其中一类样本过大(实例数量过多)占主导的时候,新的未知实例容易被归为这个主导样本,因为这类样本实例的数量过大,但这个新的未知实例并不接近目标样本。

对于样本点,其silhouette值定义为:

为样本点与当前所属类别的差异度(dissimilarity),用与所有样本点的平均距离度量。为样本点与其他类别差异度最小值。由此可知,接近1表示样本点更倾向于当前类,接近0表示样本点更在两类之间,接近-1表示样本点更倾向于其他类。


Python实现:

 from sklearn import neighbors
 from sklearn import datasets
 # 调用KNN的分类器
 knn = neighbors.KNeighborsClassifier()
 # 加载数据库
 iris = datasets.load_iris()
 # 打印数据集 包含一个四维的特征值和其对应的标签
 print(iris)
 knn.fit(iris.data, iris.target)
 # 预测[0.1, 0.2, 0.3, 0.4]属于哪一类
 predictedLabel = knn.predict([[0.1, 0.2, 0.3, 0.4]])
 # 打印出预测的标签
 print(predictedLabel)


相关文章
|
2月前
|
Python
Python办公自动化:xlwings对Excel进行分类汇总
Python办公自动化:xlwings对Excel进行分类汇总
55 1
|
20天前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
36 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
4天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
12 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
8天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
16天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
38 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
2月前
|
机器学习/深度学习 算法 TensorFlow
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
交通标志识别系统。本系统使用Python作为主要编程语言,在交通标志图像识别功能实现中,基于TensorFlow搭建卷积神经网络算法模型,通过对收集到的58种常见的交通标志图像作为数据集,进行迭代训练最后得到一个识别精度较高的模型文件,然后保存为本地的h5格式文件。再使用Django开发Web网页端操作界面,实现用户上传一张交通标志图片,识别其名称。
86 6
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
|
2月前
|
机器学习/深度学习 人工智能 算法
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
文本分类识别系统。本系统使用Python作为主要开发语言,首先收集了10种中文文本数据集("体育类", "财经类", "房产类", "家居类", "教育类", "科技类", "时尚类", "时政类", "游戏类", "娱乐类"),然后基于TensorFlow搭建CNN卷积神经网络算法模型。通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型,并保存为本地的h5格式。然后使用Django开发Web网页端操作界面,实现用户上传一段文本识别其所属的类别。
79 1
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
|
25天前
|
算法 安全 Go
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
56 1
|
25天前
|
存储 算法 安全
Python 加密算法详解与应用
Python 加密算法详解与应用
15 1
|
1月前
|
安全 Python
Python脚本实现IP按段分类
【10月更文挑战第04天】
24 7