搜索
首页后端开发Python教程关于KNN算法详细介绍
关于KNN算法详细介绍Jun 20, 2017 pm 04:59 PM
介绍算法

KNN算法全名为k-Nearest Neighbor,就是K最近邻的意思。

算法描述

KNN是一种分类算法,其基本思想是采用测量不同特征值之间的距离方法进行分类。

算法过程如下:

1、准备样本数据集(样本中每个数据都已经分好类,并具有分类标签);
2、使用样本数据进行训练;
3、输入测试数据A;
4、计算A与样本集的每一个数据之间的距离;
5、按照距离递增次序排序;
6、选取与A距离最小的k个点;
7、计算前k个点所在类别的出现频率;
8、返回前k个点出现频率最高的类别作为A的预测分类。

主要因素

训练集(或样本数据)

训练集太小会误判,训练集太大时对测试数据分类的系统开销会非常大。

距离(或相似的衡量算法)

什么是合适的距离衡量?距离越近应该意味着这两个点属于一个分类的可能性越大。

距离衡量包括:

1、欧氏距离

欧几里得度量(euclidean metric)(也称欧氏距离)是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

适用于空间问题。

2、曼哈顿距离

出租车几何或曼哈顿距离(Manhattan Distance)是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ,是种使用在几何度量空间的几何学用语,用以标明两个点在标准坐标系上的绝对轴距总和。 曼哈顿距离是欧氏距离在欧几里得空间的固定直角坐标系上所形成的线段对轴产生的投影的距离总和。

图中红线代表曼哈顿距离,绿色代表欧氏距离,也就是直线距离,而蓝色和黄色代表等价的曼哈顿距离。 曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离,即d(i,j)=|xi-xj|+|yi-yj|。

适用于路径问题。

3、切比雪夫距离

在数学中,切比雪夫距离是向量空间中的一种度量,二个点之间的距离定义是其各坐标数值差绝对值的最大值。

切比雪夫距离会用在计算法网格中两点之间的距离,比如:棋盘、仓储物流等应用。

对一个网格,和一个点的切比雪夫距离为1的点为此点的Moore型邻居(英语:Moore neighborhood)。

使用于在网格中计算距离的问题。

4、闵可夫斯基距离(Minkowski Distance)

闵氏距离不是一种距离,而是一组距离的定义。

根据变参数的不同,闵氏距离可以表示一类的距离。

其公式中有一个变参p:
当p=1时,是曼哈顿距离;
当p=2时,是欧氏距离;
当p→∞时,就是切比雪夫距离。

5、标准化欧氏距离 (Standardized Euclidean distance )

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案,可以看成是一种加权欧氏距离。

标准欧氏距离的思路: 既然数据各维分量的分布不一样,那先将各个分量都“标准化”到均值、方差相等。

6、马氏距离(Mahalanobis Distance)

表示数据的协方差距离。

它是一种有效的计算两个未知样本集的相似度的方法。

量纲无关,可以排除变量之间的相关性的干扰。

7、巴氏距离(Bhattacharyya Distance) 在统计学中,巴氏距离用于测量两离散概率分布。它常在分类中测量类之间的可分离性。

8、汉明距离(Hamming distance)

两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。

例如字符串“1111”与“1001”之间的汉明距离为2。

应用:
信息编码(为了增强容错性,应使得编码间的最小汉明距离尽可能大)。

9、夹角余弦(Cosine)

几何中夹角余弦可用来衡量两个向量方向的差异,数据挖掘中可用来衡量样本向量之间的差异。

10、杰卡德相似系数(Jaccard similarity coefficient)

杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。
可将杰卡德相似系数用在衡量样本的相似度上。

11、皮尔森相关系数(Pearson Correlation Coefficient)

皮尔森相关系数,也称皮尔森积矩相关系数(Pearson product-moment correlation coefficient) ,是一种线性相关系数。 皮尔森相关系数是用来反映两个变量线性相关程度的统计量。

高维度对距离衡量的影响:
当变量数越多,欧式距离的区分能力就越差。

变量值域对距离的影响:
值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。

k的大小

k太小,分类结果易受噪声点影响,误差会增大;
k太大,近邻中又可能包含太多的其它类别的点(对距离加权,可以降低k值设定的影响);
k=N(样本数),则完全不足取,因为此时无论输入实例是什么,都只是简单的预测它属于在训练实例中最多的类,模型过于简单,忽略了训练实例中大量有用信息。

在实际应用中,K值一般取一个比较小的数值,例如采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。

经验规则:k一般低于训练样本数的平方根。

优缺点

1、优点
简单,易于理解,易于实现,精度高,对异常值不敏感。

2、缺点

KNN是一种懒惰算法,构造模型很简单,但在对测试数据分类的系统开销大(计算量大,内存开销大),因为要扫描全部训练样本并计算距离。

适用范围

数值型和标称型(具有有穷多个不同值,值之间无序)。
比如客户流失预测、欺诈侦测等。

算法实现

这里以python为例描述下基于欧氏距离的KNN算法实现。

欧氏距离公式:

以欧氏距离为例的示例代码:

#! /usr/bin/env python#-*- coding:utf-8 -*-# E-Mail : Mike_Zhang@live.comimport mathclass KNN:    def __init__(self,trainData,trainLabel,k):
        self.trainData = trainData
        self.trainLabel = trainLabel
        self.k = k       def predict(self,inputPoint):
        retLable = "None"arr=[]for vector,lable in zip(self.trainData,self.trainLabel):
            s = 0for i,n in enumerate(vector) :
                s += (n-inputPoint[i]) ** 2arr.append([math.sqrt(s),lable])
        arr = sorted(arr,key=lambda x:x[0])[:self.k]           
        dtmp = {}for k,v in arr :if not v in dtmp : dtmp[v]=0
            dtmp[v] += 1retLable,_ = sorted(dtmp.items(),key=lambda x:x[1],reverse=True)[0]        return retLable

data = [
    [1.0, 1.1],
    [1.0, 1.0],
    [0.0, 0.0],
    [0.0, 0.1],
    [1.3, 1.1],
]

labels = ['A','A','B','B','A']
knn = KNN(data,labels,3)print knn.predict([1.2, 1.1])  
print knn.predict([0.2, 0.1])

上面的实现比较简单,在开发中可以使用现成的库,比如scikit-learn :


算法应用

  • 识别手写数字


以上是关于KNN算法详细介绍的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
wapi是什么东西详细介绍wapi是什么东西详细介绍Jan 07, 2024 pm 09:14 PM

wapi这个名词用户们可能在使用网络得时候见到过,但是对于一部分人来说肯定都不知道wapi是什么,下面就带来了详细介绍,帮助不知道小伙伴去了解。wapi是什么东西:答:wapi是无线局域网鉴别和保密的基础结构。这就像红外线和蓝牙等功能一样,一般都覆盖在办公楼等地方的附近。基本都是为一个小部门所有的,所以这个功能涉及的范围只有几公里。wapi相关介绍:1、wapi是无线局域网里面的一种传输协议。2、这款技术是可以去避免窄频带通信的问题,可以更好的去进行传播。3、仅仅只需要一个代码就可以去传送信号了

详解win11能否运行PUBG游戏详解win11能否运行PUBG游戏Jan 06, 2024 pm 07:17 PM

pubg又称绝地求生,是一款非常经典的射击大逃杀类型游戏,从2016年火爆以来一直拥有非常多的玩家。在最近的win11系统推出后,就有不少玩家想要在win11上游玩它,下面就跟着小编来看看win11是否可以玩pubg吧。win11能玩pubg吗:答:win11可以玩pubg。1、在win11推出之初,因为win11需要开启tpm的缘故,所以导致很多玩家被pubg封号处理了。2、不过后来根据玩家的反馈,蓝洞方面已经解决了这个问题,目前已经可以在win11中正常玩pubg了。3、如果大家遇到了pub

Python函数介绍:exec函数的介绍及示例Python函数介绍:exec函数的介绍及示例Nov 03, 2023 pm 02:09 PM

Python函数介绍:exec函数的介绍及示例引言:在Python中,exec是一种内置函数,它用于执行存储在字符串或文件中的Python代码。exec函数提供了一种动态执行代码的方式,使得程序可以在运行时根据需要生成、修改和执行代码。本文将介绍exec函数的使用方法,并给出一些实际的代码示例。exec函数的使用方法:exec函数的基本语法如下所示:exec

i5处理器是否能装win11详细介绍i5处理器是否能装win11详细介绍Dec 27, 2023 pm 05:03 PM

i5是英特尔旗下的一系列处理器,拥有到现在11代i5的各种不同版本,每一代都有着不同性能。因此对于i5处理器是否能够安装win11,还需要看是第几代的处理器,下面就跟着小编一起来分别了解一下吧。i5处理器能装win11吗:答:i5处理器能装win11。一、第八代及之后的i51、第八代及后续的i5处理器是能够满足微软的最低配置需求的。2、因此我们只需要进入微软网站,下载一个“win11安装助手”3、下载完成后,运行该安装助手,根据提示进行操作就可以安装win11了。二、第八代之前的i51、第八代之

edge快捷键的介绍edge快捷键的介绍Jul 12, 2023 pm 05:57 PM

在如今快捷的生活,为了提高工作效率,快捷键是必不可少的工作需求。快捷键是指按键或按键组合,可提供另一种方式来执行通常使用鼠标执行的操作。那么edge快捷键有哪些呢?edge快捷键的功能又有哪些呢?下面小编整理了一份edge快捷键的介绍,感兴趣的朋友们快来看看吧!Ctrl+D:将当前页面添加到收藏夹或阅读列表Ctrl+E:在地址栏中执行搜索查询Ctrl+F:在页面上查找Ctrl+H:打开历史记录面板Ctrl+G:打开阅读列表面板Ctrl+I:打开收藏夹列表面板(测试好像不起作用)Ctrl+J:打开

详细介绍电脑中的打印机驱动程序位置详细介绍电脑中的打印机驱动程序位置Jan 08, 2024 pm 03:29 PM

很多用户在电脑上安装了打印机驱动程序,但却不知道如何找到它们。因此,今天我为大家带来了详细介绍打印机驱动程序在电脑中的位置,对于还不了解的用户,快来看看吧打印机驱动在电脑哪里找重新撰写内容而不改变原义时,需要将语言改写为中文,不需要出现原句首先,建议使用第三方软件进行搜索2、在右上角找到"工具箱"3、在下方找到并点击“设备管理器”。改写后的句子:3、在底部找到并点击“设备管理器”4、然后打开“打印队列”,然后找到你的打印机设备。此次是你的打印机名称型号。5、右键打印机设备,就能够去更新或者卸载我

Python函数介绍:zip函数的介绍及示例Python函数介绍:zip函数的介绍及示例Nov 03, 2023 pm 02:02 PM

Python函数介绍:zip函数的介绍及示例Python是一种高级语言,它提供了许多有用的函数来帮助开发人员快速地编写程序。其中一个函数就是zip函数。Zip函数是Python中的内置函数之一,它可以接受一组可迭代对象(包括列表、元组、集合和字典等),并返回一个由这些可迭代对象中的元素按顺序成对组成的元组。Zip函数可以用于多种情况,例如:1.将两个列表的元

玩游戏最好的win10版本介绍玩游戏最好的win10版本介绍Jan 08, 2024 am 10:41 AM

在微软公司发布了win10系统之后,我们所知的就有好几种版本:家庭版、教育版、专业版、旗舰版等等。小编认为这些版本在性能上没什么差别,只是有些针对性的功能不同。那么小编今天就来跟大家聊一聊玩游戏用win10哪个版本最好吧~希望可以帮助到你。玩游戏用win10哪个版本最好答:玩游戏来说,这几个版本其实区别并不大。如果只是想要拿来打游戏的话,推荐win10家庭版。因为家庭版没有其他花里胡哨的功能,能够让性能主要集中在游戏方面。这个问题,首先要说的就是win10几个版本之间的区别。1、win10主要版

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境