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