当前位置: 代码迷 >> 数据仓库 >> 数据挖掘学习笔记之KNN算法(一)
  详细解决方案

数据挖掘学习笔记之KNN算法(一)

热度:80   发布时间:2016-05-05 15:52:56.0
数据挖掘学习札记之KNN算法(一)

参考:

1. KNN算法介绍,Python程序和一个简单算例

2. k-nearest neighbor algorithm


基本想法:

在距离空间里,如果一个样本的最接近的k个邻居里,绝大多数属于某个类别,则该样本也属于这个类别。俗话叫,“随大流”。


算法描述:

1. 依公式计算 Item 与 D1、D2 … …、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)。2. 将Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)排序,若是超过相似度阈值t则放入邻居案例集合NN。3. 自邻居案例集合NN中取出前k名,依多数决,得到Item可能类别。


参数K的选取:

如何选择一个最佳的K值取决于数据。一般情况下,在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。比如下图,

待测样本(绿色圆圈)既可能分到红色三角形类,也可能分到蓝色正方形类。如果k取3,从图可见,待测样本的3个邻居在实线的内圆里,按多数投票结果,它属于红色三角形类,票数1:2.但是如果k取5,那么待测样本的最邻近的5个样本在虚线的圆里,按表决法,它又属于蓝色正方形类,票数2(红色三角形):3(蓝色正方形)。


其它问题:

计算两者间距离,用哪种距离会更好呢?计算量太大怎么办?假设样本中,类型分布非常不均,该怎么办呢?



例子(电影分类):

电影名称打斗次数接吻次数电影类型
California Man 
 
3104Romance
He’s Not Really into Dudes 
 
2100Romance
Beautiful Woman 
 
181Romance
Kevin Longblade 
 
10110Action
Robo Slayer 3000 
 
995Action
Amped II 
 
982Action
未知1890Unknown

这个数据用打斗次数和接吻次数来界定电影类型,接吻多的是Romance类型的,而打斗多的是动作电影。现在有一部名字未知的电影,打斗次数为18次,接吻次数为90次的电影(这里名字未知是为了防止能从名字中猜出电影类型),它到底属于哪种类型的电影呢?


下面调用Python的sklearn模块求解:(转自KNN算法介绍)

import numpy as npfrom sklearn import neighborsknn = neighbors.KNeighborsClassifier() #取得knn分类器data = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]) # data对应着打斗次数和接吻次数labels = np.array([1,1,1,2,2,2]) #labels则是对应Romance和Actionknn.fit(data,labels) #导入数据进行训练'''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,和直觉相符。


问题是:在这个例子中,k是多少呢?


  相关解决方案