专栏首页Flaneur的文章分享KNN算法及python实现

KNN算法及python实现

前言

        KNN算法即K-Nearest Neighbor,也是机器学习十大经典算法之一。前文讲解了K-means算法,今天我们就继续讲KNN算法,两者看起来挺相似的,但区别还是很大的,看完本片文章你就会明白了。

一、引入

问题:确定绿色圆是属于红色三角形、还是蓝色正方形?

KNN的思想:         从上图中我们可以看到,图中的数据集是良好的数据,即都打好了label,一类是蓝色的正方形,一类是红色的三角形,那个绿色的圆形是我们待分类的数据。         如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形         如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形         即如果一个样本在特征空间中的k个最相邻的样本中,大多数属于某一个类别,则该样本也属于这个类别。我们可以看到,KNN本质是基于一种数据统计的方法!其实很多机器学习算法也是基于数据统计的。

二、KNN算法

1.介绍

        KNN即K-最近邻分类算法(K-Nearest Neighbor),是一种memory-based learning,也叫instance-based learning,属于lazy learning。即它没有明显的前期训练过程,而是程序开始运行时,把数据集加载到内存后,不需要进行训练,就可以开始分类了。         KNN也是一种监督学习算法,通过计算新数据与训练数据特征值之间的距离,然后选取K(K>=1)个距离最近的邻居进行分类判(投票法)或者回归。若K=1,新数据被简单分配给其近邻的类。

2.步骤

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

(计算距离的方式前文讲k-means时说过,不清楚的可以去查看以下➡传送门)

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

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

K值是由自己来确定的

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

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

说明:对于步骤5的预测分类有以下两种方法

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

特点

1) 非参数统计方法:不需要引入参数 2) K的选择:         K = 1时,将待分类样本划入与其最接近的样本的类。         K = |X|时,仅根据训练样本进行频率统计,将待分类样本划入最多的类。 K需要合理选择,太小容易受干扰,太大增加计算复杂性。 3) 算法的复杂度:维度灾难,当维数增加时,所需的训练样本数急剧增加,一般采用降维处理。

三、算法优缺点

优点

  1. 简单、有效。
  2. 重新训练的代价较低(类别体系的变化和训练集的变化,在Web环境和电子商务应用中是很常见的)。
  3. 计算时间和空间线性于训练集的规模(在一些场合不算太大)。
  4. 由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
  5. 该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。

缺点

  1. KNN算法是懒散学习方法(lazy learning),而一些积极学习的算法要快很多。
  2. 需要存储全部的训练样本
  3. 输出的可解释性不强,例如决策树的可解释性较强。
  4. 该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。该算法只计算最近的邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。
  5. 计算量较大。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。

四、KNN与K-means的区别

        废话不多说,咱直接上图:

相似点:         虽然两者有很大且别,但两者也有共同之处。都包含了一个过程:给定一个点,在数据集找离它最近的点,即都用到了NN(Nearest Neighbor)算法。

五、python实例实现

        下面引入一个实例,通过python代码具体看下KNN算法的流程。

from numpy import *
import operator

dataSet = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']

def classify0(inX,dataSet,labels,k):

    #求出样本集的行数,也就是labels标签的数目
    dataSetSize = dataSet.shape[0]

    #构造输入值和样本集的差值矩阵
    diffMat = tile(inX,(dataSetSize,1)) - dataSet

    #计算欧式距离
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5

    #求距离从小到大排序的序号
    sortedDistIndicies = distances.argsort()

    #对距离最小的k个点统计对应的样本标签
    classCount = {}
    for i in range(k):
        #取第i+1邻近的样本对应的类别标签
        voteIlabel = labels[sortedDistIndicies[i]]
        #以标签为key,标签出现的次数为value将统计到的标签及出现次数写进字典
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

    #对字典按value从大到小排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

    #返回排序后字典中最大value对应的key
    return sortedClassCount[0][0]
if __name__ == '__main__':
    print(classify0([1.1,0],dataSet,labels,3))

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅谈机器学习-分类和聚类的区别

            机器学习中有两类的大问题,一个是分类,一个是聚类。在我们的生活中,我们常常没有过多的去区分这两个概念,觉得聚类就是分类,分类也差不多就是聚类,下...

    Flaneur
  • 人工神经网络(ANN)

            初学人工智能不久,今天碰上了人工神经网(ANN),开始学的时候很懵,一大堆理论、公式、推导…..作为一名小白,还是很痛苦的,不过经过摸索,大概了...

    Flaneur
  • K-means算法及python实现

            K-means(Thek-meansalgorithm)是机器学习十大经典算法之一,同时也是最为经典的无监督聚类(Unsupervised Cl...

    Flaneur
  • 把vcf文件转换为maf格式,肿瘤外显子上游分析教程到此为止

    可能还有一些教程我漏掉了,毕竟这些年发布了近万篇教程了,大家直接我去我博客,生信菜鸟团就可以搜索,去我们的论坛,生信技能树里面也可以搜到。

    生信技能树
  • 多进程web动态服务器

    self.tcp_server = socket.socket(socket.AF_INET,socket.SOCK_STREAM)

    不断折腾
  • 《统计学习方法》第 14 章 聚类方法 KMeans

    iOSDevLog
  • 物料价格小数点问题解决思路

    现阶段在业务过程中物料的价格保留到了小数点后4位,同时财务承认的价格也是小数点后四位,而以后在SAP系统中价格只支持到小数点后两位,即精确到“分”。

    用户5495712
  • 投身区块链,或许也救不了ofo

    如果用一个词来形容当前的ofo,那么用“迷茫”再合适不过了。这就像是一个在战场上经常打仗的士兵,等到仗打完了,突然不知道应该做什么了。这种境遇在ofo的身上同样...

    孟永辉
  • 用scikit-learn研究局部线性嵌入(LLE)

        在局部线性嵌入(LLE)原理总结中,我们对流形学习中的局部线性嵌入(LLE)算法做了原理总结。这里我们就对scikit-learn中流形学习的一些算法做...

    刘建平Pinard
  • Valid Perfect Square

    Tyan

扫码关注云+社区

领取腾讯云代金券