KNN算法讲解及其实现

2016-03-19 17:27:55

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

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

他的优点是：

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

当然，他也有一些缺点，主要是：

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

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

算法原理

其实他的算法非常简单。

可以从这个图看出来：

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

步骤如下：

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

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

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

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

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

但是，如果我们把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的思路简单，用的好，非常有用。

##常见问题

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

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

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

他的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公开课
• 《机器学习实战》
• 《集体编程智慧》
• 《数据科学实战》
• 《统计学习方法》
• 维基百科