k近邻算法是机器学习算法中最简单基础的算法,大意是给你一个样本a,计算出和它距离最近的k个样本,这k个样本也即与a最相似的样本,它们组成了a的K近邻域.k的取值通常是一个不大于20的整数.
具体做法是,对于未知类别的样本a,我们计算a样本与每个训练样本的距离,然后对距离排序,得到前k个距离最小的样本,这k个样本中哪个类别的样本多,我们就说a可以分到该类别中.
样本间的距离,也即特征向量间的距离 定义的方式比较多,常见的有最简单的欧氏距离,还有其他的一些距离计算方式也需要了解,比如余弦距离,pearson距离,CityBlock距离,Minkowski距离等等等等,不同距离的选择会对相似度计算产生不同的影响,在实际的项目中,可以多做尝试,来选取最好的距离公式.距离的计算在很多机器学习算法中都有用到,比如以后会提到的相似度计算,k均值聚类等等等.
###优缺点
优点:
最简单最有效,对异常值不敏感
缺点:
当训练数据量很大时,必须有非常大的空间来存储训练数据,此外必须对数据集中的每个数据计算距离值,回非常耗时.另一个缺陷是他无法给出任何数据的 基础结构信息,因此我们无法知晓平均实例样本和典型实例样本具有什么特征.后续的概率测量方法处理分类会解决这个问题
#encoding:utf8 from numpy import * import operator def createDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ['A','A','B','B'] return group, labels def classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape[0] #dataSet的行数,等于labels向量的元素数目 diffMat = tile(inX, (dataSetSize, 1)) - dataSet #print diffMat sqDiffMat = diffMat**2 #print sqDiffMat sqDistances = sqDiffMat.sum(axis=1) #计算每行的和 #print sqDistances distances = sqDistances**0.5 #计算欧式距离 #print distances sortedDistIndicies = distances.argsort()#返回矩阵中每个元素的排序序号->来自原矩阵的序号:升序排列!!! #print sortedDistIndicies classCount = {}#建立一个空字典/哈希表/映射:键值为label;值为每个label出现的频率 for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#统计每个label出现的频率 #D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None. sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True) #D.iteritems() -> an iterator over the (key, value) items of D #key = operator.itemgetter(1)->获取函数key第一个域的值 #reverse = True->逆序排序 #将字典分解为列表, return sortedClassCount[0][0]
group, labels = createDataSet() print classify0([0,0], group, labels, 3)
运行结果:
Python 2.7.6 (default, Nov 10 2013, 19:24:18) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ >>> B >>>