《Deep Learning Series》
  • 深耕系列之深度学习笔记
  • 第一章 Linux学习环境相关配置
    • 1.1 Ubuntu18下有道词典的配置
    • 1.2 Ubuntu18 安装Gitbook
    • 1.3 Ubuntu18 git命令使用总结
    • 1.4 Latex 排版使用笔记
    • 1.5 Ubuntu下常用工具软件配置安装
    • 1.6 win10+ubuntu双系统修复ubuntu启动引导
    • 1.7 gitbook 插件等相关设置
    • 1.8 深度学习环境搭建
    • 1.9 hexo 实现本地图片加载
    • 1.10 hexo网页定制
    • 1.11 sublime text3插件介绍
    • 1.12 vsftpd.conf文件配置
    • 1.13 mysql 笔记
    • 1.14 ubuntu16_18安装peek工具录制gif
    • 1.15 ubuntu下goldendict有道爬虫小程序
    • 1.16 ubuntu18升级后部分应用不能中文输入的问题
    • 1.17 ubuntu下安装有道词典
    • 1.18 opencv 安装
    • 1.19 gym_gazabe安装配置
    • 1.20 docker 基础
    • 1.21 docker_配置权限问题
    • 1.22 jupyternotebook使用
  • 第二章 深度学习相关基础算法
    • 2.1 马尔科夫链
      • 2.1.1 马尔科夫简单模型预测实战笔记
      • 2.1.2 最大熵模型
      • 2.1.3 隐马尔科夫HMM
    • 2.2 矩阵相关基础知识
    • 2.3 线性回归
    • 2.4 决策树
    • 2.5 梯度下降和最小二乘法
    • 2.6 递归算法与迭代算法
    • 2.7 神经网络浅学笔记
    • 2.8 强化学习经验回放
    • 2.9 K近邻算法
    • 2.10 朴素贝叶斯法
    • 2.11 极大似然估计
    • 2.12 logistic regression
  • 第三章 深度学习框架学习
    • 3.1 PyTorch 学习
      • 3.1.2 Pytorch 之MNIST手写字识别分类
    • 3.2 tensorflow学习笔记
      • 3.2.1 tensorflow之MNIST
    • 3.3 matplotlib函数
    • 3.4 numpy函数
  • 第四章 ROS机器人
    • ROS室内仿真环境.md
    • ros and gazebo and gym_gazebo安装
    • ubuntu16 安装gym-gazebo
    • gym-gazebo安装后的测试
    • 基于DQN的gym_gazebo运行代码演示
  • 项目开发
    • Library占座小工具使用手册
  • 附录
    • Python 相关笔记
      • Python 帮助文档检索方法
      • Module篇使用future
    • Git 相关配置
      • git-推送新的文章到github其他分支上
      • gitignre 配置
      • gitignre 配置
      • Hexo 每次写好后deploy博客
      • MFC Socket 通信
      • python之tkinter入坑Pack
      • ubuntu 中安装sublime_text3
      • ubuntu18-正确-安装ShadowSocket
      • vultr+freenom实现主机域名的绑定.md
      • 值得收藏的网站
      • 搜索技巧
      • 第一篇博文
      • 简单的方法,越过付费获取在线的log设计.md
      • 网页设计基础笔记.md
      • 解决Chrome67版本以后不能离线安装插件的情况.md
    • 嵌入式相关笔记
      • STM32串口通信配置
      • STM32复位及通过函数判断是何种条件出发的复位
Powered by GitBook
On this page
  • 摘要
  • KNN是通过测量不同特征值之间的距离进行分类
  • 例子
  • 欧氏距离:
  • 曼哈顿距离:
  • 接下来对KNN算法的思想总结一下
  • 参考

Was this helpful?

  1. 第二章 深度学习相关基础算法

2.9 K近邻算法

摘要

K近邻算法(K-nearest neighbor, k-NN)是一种基本的分类与回归的方法。

k近邻算法:

输入:训练数据集

T=(x1,y1),(x2,y2)...,(xN,yN)T={(x_{1},y_{1}), (x_{2},y_{2})..., (x_{N},y_{N})}T=(x1​,y1​),(x2​,y2​)...,(xN​,yN​)

其中

xiϵχ⊆Rnx_{i}\epsilon \chi \subseteq R^{n}xi​ϵχ⊆Rn

为实例的特征向量

yiϵY=c1,c2......,cK,y_{i} \epsilon Y={c_{1}, c_{2}......, c_{K}, }yi​ϵY=c1​,c2​......,cK​,

为实例的类别,i=1,2,...,N

输出:给定实例x,要能输出新给的特征向量所属y中的类

(1). 根据给定的距离度量,在训练集T中找出与x最邻近的k个点,涵盖这k个点的x的邻域基座 $N_{k} (x)$ ;

(2). 在 $N{k} (x)$ 中根据分类决策规则(如多数表决表,对$N{k} (x)$ 进行排序,然后取出现频率最高的第k个点的类)决定x的类别y:

y=arg max⁡cj ∑xi⊆Nk(x) I(yi=cj)y=arg\, \max_{c_{j}}^{\ } \sum_{x_{i}\subseteq N_{k}(x)}^{\ } I(y_{i}=c_{j})y=argcj​max ​xi​⊆Nk​(x)∑ ​I(yi​=cj​)

其中I为指示函数,为yi=cjy_{i}=c_{j}yi​=cj​情况下, I = 1 否则I = 0

更通俗的理解可以为如下:

KNN是通过测量不同特征值之间的距离进行分类

  • 它的思路是:

如果选择一个待分类的样本,其在特征空间中有k个最相似的样本值(即特征空间中和这个待分类的点为最邻近点集)。

这k个样本集中的绝大多数属于某一类别,则该待分类的样本也属于这个绝大多数的同一类别。

其中K通常是不大于20的整数。

KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

例子

下面通过一个简单的例子说明一下:如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如下图所示

  • 如果K=3,最小的圆, 由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类。

  • 如果K=5,虚线内,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。

由此也说明了KNN算法的结果很大程度取决于K的选择。

在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:

欧氏距离:

d(x,y)=∑k=1n(xk−yk)2d(x,y)=\sqrt{\sum_{k=1}^{n}(x_{k}-y_{k})^{2}}d(x,y)=k=1∑n​(xk​−yk​)2​

曼哈顿距离:

d(x,y)=∑k=1n∣xk−yk∣d(x,y)=\sqrt{\sum_{k=1}^{n}|x_{k}-y_{k}|}d(x,y)=k=1∑n​∣xk​−yk​∣​

同时,KNN通过依据k个对象中占优的类别进行决策,而不是单一的对象类别决策。这两点就是KNN算法的优势。

接下来对KNN算法的思想总结一下

就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:

  • 1)计算测试数据与各个训练数据之间的距离;

  • 2)按照距离的递增关系进行排序;

  • 3)选取距离最小的K个点;

  • 4)确定前K个点所在类别的出现频率;

  • 5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

python 代码实现:

#coding:utf-8

from numpy import *
import operator

##给出训练数据以及对应的类别
def createDataSet():
    group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
    labels = ['A','A','B','B']
    return group,labels

###通过KNN进行分类
def classify(input,dataSe t,label,k):
    dataSize = dataSet.shape[0]
    ####计算欧式距离
    diff = tile(input,(dataSize,1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff,axis = 1)###行向量分别相加,从而得到新的一个行向量
    dist = squareDist ** 0.5

    ##对距离进行排序
    sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序,返回下标

    classCount={}
    for i in range(k):
        voteLabel = label[sortedDistIndex[i]]
        ###对选取的K个样本所属的类别个数进行统计
        classCount[voteLabel] = classCount.get(voteLabel,0) + 1
    ###选取出现的类别次数最多的类别
    maxCount = 0
    for key,value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key

    return classes

测试代码如下:

#-*-coding:utf-8 -*-
import sys
sys.path.append("...文件路径...")
import KNN
from numpy import *
dataSet,labels = KNN.createDataSet()
input = array([1.1,0.3])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("测试数据为:",input,"分类结果为:",output)

回车之后的结果为:

测试数据为: [ 1.1 0.3] 分类为: A

答案符合我们的预期,要证明算法的准确性,势必还需要通过处理复杂问题进行验证,之后另行说明。

【提示】python版本为3.7

具体的KNN视频教程地址为:

参考

Previous2.8 强化学习经验回放Next2.10 朴素贝叶斯法

Last updated 5 years ago

Was this helpful?

参考文档来源1:

参考文档来源2:

Yabea-博客
李航-统计学习方法
knn算法例子