数据挖掘十大算法--K近邻算法

k-近邻算法是基于实例的学习方法中最基本的,先介绍基于实例学习的相关概念。

一、基于实例的学习。

1、已知一系列的训练样例,很多学习方法为目标函数建立起明确的一般化描述;但与此不同,基于实例的学习方法只是简单地把训练样例存储起来。

从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例,它分析这个新实例与以前存储的实例的关系,并据此把一个目标函数值赋给新实例。

2、基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上,很多技术只建立目标函数的局部逼近,将其应用于与新查询实例邻近的实例,而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂,但它可用不太复杂的局部逼近描述时,这样做有显著的优势。

3、基于实例方法的不足:

(1)分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时,而不是在第一次遇到训练样例时。所以,如何有效地索引训练样例,以减少查询时所需计算是一个重要的实践问题。

(2)当从存储器中检索相似的训练样例时,它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时,那么真正最“相似”的实例之间很可能相距甚远。

二、k-近邻法

基于实例的学习方法中最基本的是k-近邻算法。这个算法假定所有的实例对应于n维欧氏空间Ân中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲,把任意的实例x表示为下面的特征向量:

<a1(x),a2(x),...,an(x)>

其中ar(x)表示实例x的第r个属性值。那么两个实例xixj间的距离定义为d(xi,xj),其中:

说明:

1、在最近邻学习中,目标函数值可以为离散值也可以为实值。

2、我们先考虑学习以下形式的离散目标函数

。其中V是有限集合{v1,...vs}。下表给出了逼近离散目标函数的k-近邻算法。

3、正如下表中所指出的,这个算法的返回值f'(xq)为对f(xq)的估计,它就是距离xq最近的k个训练样例中最普遍的f值。

4、如果我们选择k=1,那么“1-近邻算法”就把f(xi)赋给(xq),其中xi是最靠近xq的训练实例。对于较大的k值,这个算法返回前k个最靠近的训练实例中最普遍的f值。

逼近离散值函数f: Ân_Vk-近邻算法

训练算法: 对于每个训练样例<x,f(x)>,把这个样例加入列表training_examples分类算法: 给定一个要分类的查询实例xq 在training_examples中选出最靠近xq的k个实例,并用x1....xk表示 返回 其中如果a=b那么d(a,b)=1,否则d(a,b)=0。

下图图解了一种简单情况下的k-近邻算法,在这里实例是二维空间中的点,目标函数具有布尔值。正反训练样例用“+”和“-”分别表示。图中也画出了一个查询点xq。注意在这幅图中,1-近邻算法把xq分类为正例,然而5-近邻算法把xq分类为反例。

图解说明:左图画出了一系列的正反训练样例和一个要分类的查询实例xq。1-近邻算法把xq分类为正例,然而5-近邻算法把xq分类为反例。

右图是对于一个典型的训练样例集合1-近邻算法导致的决策面。围绕每个训练样例的凸多边形表示最靠近这个点的实例空间(即这个空间中的实例会被1-近邻算法赋予该训练样例所属的分类)。

对前面的k-近邻算法作简单的修改后,它就可被用于逼近连续值的目标函数。为了实现这一点,我们让算法计算k个最接近样例的平均值,而不是计算其中的最普遍的值。更精确地讲,为了逼近一个实值目标函数

,我们只要把算法中的公式替换为:

三、距离加权最近邻算法

k-近邻算法的一个显而易见的改进是对k个近邻的贡献加权,根据它们相对查询点xq的距离,将较大的权值赋给较近的近邻。

例如,在上表逼近离散目标函数的算法中,我们可以根据每个近邻与xq的距离平方的倒数加权这个近邻的“选举权”。

方法是通过用下式取代上表算法中的公式来实现:

其中

为了处理查询点xq恰好匹配某个训练样例xi,从而导致分母为0的情况,我们令这种情况下的f '(xq)等于f(xi)。如果有多个这样的训练样例,我们使用它们中占多数的分类。

我们也可以用类似的方式对实值目标函数进行距离加权,只要用下式替换上表的公式:

其中wi的定义与之前公式中相同。

注意这个公式中的分母是一个常量,它将不同权值的贡献归一化(例如,它保证如果对所有的训练样例xif(xi)=c,那么(xq)<--c)。

注意以上k-近邻算法的所有变体都只考虑k个近邻以分类查询点。如果使用按距离加权,那么允许所有的训练样例影响xq的分类事实上没有坏处,因为非常远的实例对(xq)的影响很小。考虑所有样例的惟一不足是会使分类运行得更慢。如果分类一个新的查询实例时考虑所有的训练样例,我们称此为全局(global)法。如果仅考虑最靠近的训练样例,我们称此为局部(local)法。

四、对k-近邻算法的说明

按距离加权的k-近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪声有很好的鲁棒性,而且当给定足够大的训练集合时它也非常有效。注意通过取k个近邻的加权平均,可以消除孤立的噪声样例的影响。

1、问题一:近邻间的距离会被大量的不相关属性所支配。

应用k-近邻算法的一个实践问题是,实例间的距离是根据实例的所有属性(也就是包含实例的欧氏空间的所有坐标轴)计算的。这与那些只选择全部实例属性的一个子集的方法不同,例如决策树学习系统。

比如这样一个问题:每个实例由20个属性描述,但在这些属性中仅有2个与它的分类是有关。在这种情况下,这两个相关属性的值一致的实例可能在这个20维的实例空间中相距很远。结果,依赖这20个属性的相似性度量会误导k-近邻算法的分类。近邻间的距离会被大量的不相关属性所支配。这种由于存在很多不相关属性所导致的难题,有时被称为维度灾难(curse of dimensionality)。最近邻方法对这个问题特别敏感。

2、解决方法:当计算两个实例间的距离时对每个属性加权。

这相当于按比例缩放欧氏空间中的坐标轴,缩短对应于不太相关属性的坐标轴,拉长对应于更相关的属性的坐标轴。每个坐标轴应伸展的数量可以通过交叉验证的方法自动决定。

3、问题二:应用k-近邻算法的另外一个实践问题是如何建立高效的索引。因为这个算法推迟所有的处理,直到接收到一个新的查询,所以处理每个新查询可能需要大量的计算。

4、解决方法:目前已经开发了很多方法用来对存储的训练样例进行索引,以便在增加一定存储开销情况下更高效地确定最近邻。一种索引方法是kd-tree(Bentley 1975;Friedman et al. 1977),它把实例存储在树的叶结点内,邻近的实例存储在同一个或附近的结点内。通过测试新查询xq的选定属性,树的内部结点把查询xq排列到相关的叶结点。

python版本:

这里实现一个手写识别算法,这里只简单识别0~9熟悉,在上篇文章中也展示了手写识别的应用,可以参考:机器学习与数据挖掘-logistic回归及手写识别实例的实现

输入:每个手写数字已经事先处理成32*32的二进制文本,存储为txt文件。0~9每个数字都有10个训练样本,5个测试样本。训练样本集如下图:左边是文件目录,右边是其中一个文件打开显示的结果,看着像1,这里有0~9,每个数字都有是个样本来作为训练集。

第一步:将每个txt文本转化为一个向量,即32*32的数组转化为1*1024的数组,这个1*1024的数组用机器学习的术语来说就是特征向量。

[python] view plaincopy

  1. <span style="font-size:14px;">def img2vector(filename):
  2. returnVect = zeros((1,1024))
  3. fr = open(filename)
  4. for i in range(32):
  5. lineStr = fr.readline()
  6. for j in range(32):
  7. returnVect[0,32*i+j] = int(lineStr[j])
  8. return returnVect</span>

第二步:训练样本中有10*10个图片,可以合并成一个100*1024的矩阵,每一行对应一个图片,也就是一个txt文档。

[python] view plaincopy

  1. def handwritingClassTest():
  2. hwLabels = []
  3. trainingFileList = listdir('trainingDigits')
  4. print trainingFileList
  5. m = len(trainingFileList)
  6. trainingMat = zeros((m,1024))
  7. for i in range(m):
  8. fileNameStr = trainingFileList[i]
  9. fileStr = fileNameStr.split('.')[0]
  10. classNumStr = int(fileStr.split('_')[0])
  11. hwLabels.append(classNumStr)
  12. #print hwLabels
  13. #print fileNameStr
  14. trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
  15. #print trainingMat[i,:]
  16. #print len(trainingMat[i,:])
  17. testFileList = listdir('testDigits')
  18. errorCount = 0.0
  19. mTest = len(testFileList)
  20. for i in range(mTest):
  21. fileNameStr = testFileList[i]
  22. fileStr = fileNameStr.split('.')[0]
  23. classNumStr = int(fileStr.split('_')[0])
  24. vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
  25. classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
  26. print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
  27. if (classifierResult != classNumStr): errorCount += 1.0
  28. print "\nthe total number of errors is: %d" % errorCount
  29. print "\nthe total error rate is: %f" % (errorCount/float(mTest))

第三步:测试样本中有10*5个图片,同样的,对于测试图片,将其转化为1*1024的向量,然后计算它与训练样本中各个图片的“距离”(这里两个向量的距离采用欧式距离),然后对距离排序,选出较小的前k个,因为这k个样本来自训练集,是已知其代表的数字的,所以被测试图片所代表的数字就可以确定为这k个中出现次数最多的那个数字。

[python] view plaincopy

  1. def classify0(inX, dataSet, labels, k):
  2. dataSetSize = dataSet.shape[0]
  3. #tile(A,(m,n))
  4. print dataSet
  5. print "----------------"
  6. print tile(inX, (dataSetSize,1))
  7. print "----------------"
  8. diffMat = tile(inX, (dataSetSize,1)) - dataSet
  9. print diffMat
  10. sqDiffMat = diffMat**2
  11. sqDistances = sqDiffMat.sum(axis=1)
  12. distances = sqDistances**0.5
  13. sortedDistIndicies = distances.argsort()
  14. classCount={}
  15. for i in range(k):
  16. voteIlabel = labels[sortedDistIndicies[i]]
  17. classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
  18. sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
  19. return sortedClassCount[0][0]

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-07-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

教程 | 如何使用贪婪搜索和束搜索解码算法进行自然语言处理

2495
来自专栏计算机视觉

基于图的分割 Efficient Graph-Based Image Segmentation 论文详解

输入图片 不同参数下的分割结果 原图片 产生superpixel的方法 1. How to segment an image into regions?    ...

3588
来自专栏量化投资与机器学习

从Encoder到Decoder实现Seq2Seq模型(算法+代码)

知乎专栏:机器不学习 作者:天雨栗 | 蚂蚁金服 | 数据算法 已授权刊登 前言 好久没有更新专栏,今天我们来看一个简单的Seq2Seq实现,我们将使用Tens...

4236
来自专栏云霄雨霁

算法设计策略----动态规划法

1160
来自专栏灯塔大数据

每周学点大数据 | No.16平面图直径

No.16期 平面图直径 小可:好的,关于图的基本内容我听懂了。 Mr. 王:很好,图能够对很多现实问题进行数学抽象,方便通过计算机的手段进行抽象。而平面图指...

3054
来自专栏机器之心

入门 | 通过 Q-learning 深入理解强化学习

选自Medium 作者:Thomas Simonini 机器之心编译 参与:Geek AI、刘晓坤 本文将带你学习经典强化学习算法 Q-learning 的相关...

2465
来自专栏机器学习原理

深度学习——RNN(2)双向RNN深度RNN几种变种

4003
来自专栏jeremy的技术点滴

机器学习课程_笔记02

2947
来自专栏生信小驿站

黑箱方法-神经网络①人工神经网络

今天,主要使用人工神经网络的进行建模分析,涉及的R包是neuralnet和nnet两个包,函数名和包名是一样的。

903
来自专栏程序员的碎碎念

分享几个我经常用到的函数

同上一个推送一样,为了提高php开发的效率,在学习完一些零零碎碎的知识外,我们要学会的那就是总结与分享,学会封装类和函数,方便下次你再次敲此功能代码。在...

3526

扫描关注云+社区