KNN算法讲解及其实现

2016-03-19 17:27:55

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议

这次讲的是比较简单的分类办法,主要是最近从谷歌上的资料,《机器学习实战》和《集体编程智慧》上学习的KNN方法。

这个方法讲解简单易学,逻辑很清楚。

他的优点是:

  • 精度高
  • 对异常值不敏感
  • 无数据输入假定

当然,他也有一些缺点,主要是:

  • 计算复杂度高
  • 空间复杂度高

其实简单说,就是这个算法,当所使用的计算资源够多时能提供高质量的结果。

算法原理


其实他的算法非常简单。

可以从这个图看出来:

pic

或者,这张图也是比较清晰的写出了算法:

pic

步骤如下:

  • 首先你先有一堆已经知道类型的数据,例如:

pic

  • 从这里我们可以看到一堆的值,表达了这个电影的一些量化数据,有接吻次数,打斗次数,和票房,最后给出他的分类
  • 那么我们的问题就是,现在有一个电影,我们有了这些数据,我们要怎么样自动的给这个电影分类呢?
  • 首先我们需要一点数学知识,我们唯一需要的数学知识,就是欧式距离啦:

pic

  • 那么就是这个东西啦,欧式算法把多维的数量值建立联系,使我们能够比较他们,就和一维量一样
  • 好了,来看看我们的KNN 算法吧,首先我们现在有一个数据,我们想知道他的类型,这时候我需要一个K
  • 然后我们开始计算,这个数据到每一个已知数据的欧式距离,最后对这个距离值进行排序
  • 然后我们得到一列排序值,我们选择前K个数据,看这个 K个数据里面,类型最多出现的类型,就是我们的数据的类型了

类似上面的图,首先是图一,绿点是属于红点还说蓝点的?

如果我们的 K3,那么根据我们的算法,现在有两个红点,一个蓝点,那么这个绿点属于占多数的红点

但是,如果我们把K设为5,那么绿点就要属于占多数的蓝点

代码实现


这里我是使用numpy写的一组最简单的实现:

def KNNClassify(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]

    #计算欧式距离

    diffMat=tile(inX,(dataSetSize,1))-dataSet
    sqDiffMat=diffMat**2
    sqDistances=sqDiffMat.sum(axis=1)
    distances=sqDistances**0.5

    #对欧式距离list进行排序

    sortedDistUndicies=distances.argsort()

    #计算出现k个值前,出现数最多的类型

    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistUndicies[i]]
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1

    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)

    #返回第一个类型

    return sortedClassCount[0][0]

通过这个算法,你就可以计算很多东西,像《机器学习实战》中,拿来模拟手写智能输入法,KNN的思路简单,用的好,非常有用。

##常见问题


最常见的问题就是未归一化的问题

我拿之前的那张表举例子,因为亲吻次数和票房的的标准不一样,所以使用欧式距离算法时,会面临,全部被票房带着走,其他数据面临忽略

我们最常用的解决这个办法是 归一化:

pic

他的numpy 代码实现:

 def autoNorm(dataSet):

    #获得最大最小值,进行计算

    minVals=dataSet.min(0)
    maxVals=dataSet.max(0)
    ranges=maxVals-minVals
    normDataSet=zeros(shape(dataSet))
    m=dataSet.shape[0]
    normDataSet=dataSet-tile(minVals,(m,1))
    normDataSet=normDataSet/tile(ranges,(m,1))

    #返回的是一个介于(0,1)的值

    return normDataSet,ranges,minVals

本文参考:

  • andrew ng的machine learning公开课
  • 《机器学习实战》
  • 《集体编程智慧》
  • 《数据科学实战》
  • 《统计学习方法》
  • 维基百科

机器学习 返回首页

Designed and built with all the love in the world by the Mr.ALJUN.

@SERVER BY NGINX AND POWER BY DIGITALOCEAN.

© COPYRIGHT BY GAGASALAMER 2015