KNN算法介绍 | 沙湖王

KNN算法介绍 | 沙湖王

KNN算法介绍

作者: rickey 日期: 2012 年 8 月 14 日 发表评论 (0) 查看评论

   KNN算法是机器学习里面比较简单的一个分类算法了，整体思想比较简单：计算一个点A与其他所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则点A属于该分类。这样讲可能还有点迷糊，下面用一个例子来说明一下：

 

 

	好书推荐
	公众风潮:互联网海啸 (美)查伦・李 (平装 - … ￥ 35.70 大数据技术丛书：新机器的灵魂 基德尔(Tracy Kidd… ￥ 33.80 精益创业:新创企业的成长思维 埃里克•莱斯(Eric Ri… ￥ 35.28 未来是湿的:无组织的组织力量(互联网界人人必读) 克莱·舍基 (平装 - M… ￥ 28.26 1 2 3 4 5 > 隐私
	获得Widget

Amazon.cn Widgets

 

电影名称	打斗次数	接吻次数	电影类型
California Man	3	104	Romance
He’s Not Really into Dudes	2	100	Romance
Beautiful Woman	1	81	Romance
Kevin Longblade	101	10	Action
Robo Slayer 3000	99	5	Action
Amped II	98	2	Action
未知	18	90	Unknown

简单说一下这个数据的意思：这里用打斗次数和接吻次数来界定电影类型，如上，接吻多的是Romance类型的，而打斗多的是动作电影。还有一部名字未知（这里名字未知是为了防止能从名字中猜出电影类型），打斗次数为18次，接吻次数为90次的电影，它到底属于哪种类型的电影呢？

KNN算法要做的，就是先用打斗次数和接吻次数作为电影的坐标，然后计算其他六部电影与未知电影之间的距离，取得前K个距离最近的电影，然后统计这k个距离最近的电影里，属于哪种类型的电影最多，比如Action最多，则说明未知的这部电影属于动作片类型。

在实际使用中，有几个问题是值得注意的：K值的选取，选多大合适呢？计算两者间距离，用哪种距离会更好呢（欧几里得距离等等几个）？计算量太大怎么办？假设样本中，类型分布非常不均，比如Action的电影有200部，但是Romance的电影只有20部，这样计算起来，即使不是Action的电影，也会因为Action的样本太多，导致k个最近邻居里有不少Action的电影，这样该怎么办呢？

没有万能的算法，只有在一定使用环境中最优的算法，所以，要懂得合适利用算法。

光是介绍算法，没有实现出来也没有意思。我这里用的是scikit-learn这个Python的机器学习包，感觉它的文档写得特别好，对于文档写得好的开源软件就是有爱呀。下面是简单的代码：

 

 

1 2 3 4 5 6 7

import numpy as np from sklearn import neighbors knn = neighbors.KNeighborsClassifier() #取得knn分类器 data = np.array([[ 3 , 104 ],[ 2 , 100 ],[ 1 , 81 ],[ 101 , 10 ],[ 99 , 5 ],[ 98 , 2 ]]) labels = np.array([ 1 , 1 , 1 , 2 , 2 , 2 ]) knn.fit(data,labels) #导入数据进行训练，data对应着打斗次数和接吻次数，而labels则是对应Romance和Action，因为这里只能接受整数类型的数组 knn.predict([ 18 , 90 ])

上面的代码这里简单解释一下：

首先，我用labels数组中的1和2代表Romance和Aciton，因为sklearn不接受字符数组作为标志，只能用1,2这样的int型数据来表示，后面处理可以将1和2映射到Romance和Action上来。

fit则是用data和labels进行训练，data对应的是打斗次数和接吻次数构成的向量，称之为特征向量。labels则是这个数据所代表的电影所属的类型。

predict则是进行预测了，将未知电影的特征向量代入，则能分析出该未知电影所属的类型。这里的结果是1,也就是该未知电影属于Romance。