K近邻算法.pptx
《K近邻算法.pptx》由会员分享,可在线阅读,更多相关《K近邻算法.pptx(52页珍藏版)》请在咨信网上搜索。
1、K-近邻算法目录一、K-近邻算法优缺点二、K-近邻算法工作原理及示例三、K-近邻算法的一般流程四、准备:使用Python导入数据五、实施kNN分类算法六、示例1:改进约会网站的配对结果七、示例2:手写识别系统八、小结K-近邻算法优缺点 简单地说,K-近邻算法近邻算法(又称KNN)采用测量不同特征值之间的距离方法进行分类。其优缺点及适用数据范围如下:优点:精度高、对异常值不敏感、无数据输入假定。缺点:计算复杂度高、空间复杂度高。适用数据范围:数值型和标称型。K-近邻算法工作原理1.工作原理:存在一个样本数据集合(1)(也称为训练样本集),并且样本集中每个数据都存在标签(即我们知道样本集中每一数据
2、与所属分类的对应关系(2)。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提供样本集中特征最相似数据(最近邻)的分类标签(3)。一般来说,我们只选择样本数据集中前k 个最相似的数据(4),这便是算法中k的出处(通常k20)。最后,选择k个最相似数据中出现次数最多的分类,作为新标签的分类。K-近邻算法示例2.示例(1)问题描述:电影的分类可以按照题材来,然而题材本身是如何定义的?也就是说同一题材的电影具有哪些共同特征?这些都是电影分类时必须要考虑的因素。现在有一种简单的方法,例如在爱情片中会出现打斗场面,动作片亦会出现轻吻镜头,但是很明显两者的频率是不同的,
3、因此接下来将讲述K-近邻算法关于此的简单应用。K-近邻算法示例(2)下图示例了六部电影的打斗和接吻镜头数。K-近邻算法示例(3)假如有一部未看过的电影,如何确定它是爱情片还是动作片呢?接下来将展示如何使用KNN来解决这个问题。首先我们需要知道需分类电影的打斗镜头和接吻镜头数量,下图给出了一个详细示例:K-近邻算法示例即使不知道待分类电影属于哪种类型,我们也可以通过某种方法计算方法。下图展示的是待分类电影与样本集中其他电影的距离计算结果:(此处暂时不关心如何计算得到的这些距离值,稍后会具体讲解。)K-近邻算法示例现在我们得到了样本集中所有电影与未知电影的距离,按照距离递增排序,可以找到k个距离最
4、近的电影。假定k=3,则三个最靠近的电影依次是Hes Not Really into Dudes、Beautiful Woman和California Man。结果:K-近邻算法按照距离最近的三部电影的类型,决 定待分类电影的类型,而这三部电影均为爱情片,因此我们判定待分类电影为爱情片。K-近邻算法的一般流程接下来主要讲解如何在实际中应用K-近邻算法,同时涉及如何使用Python工具和相关的机器学习术语,以下为该算法的一般流程:(1)收集数据:可以使用任何方法。(2)准备数据:距离计算所需要的数值,最好是结构化的数据格式。(3)分析数据:可以使用任何方法。(4)测试算法:计算错误率。(5)使用
5、算法:首先需要输入样本数据和结构化的输输入样本数据和结构化的输出结果出结果,然后运行运行k-近邻算法判定近邻算法判定输入数据属于哪个分类,最后应用对计算出的分类执行后续的处理。准备:使用Python导入数据1.创建名为kNN.py的Python模块注:接下来所有的代码均保存于这个文件夹中,读者可以按照自己的习惯在自己创建的文件夹中编写代码,也可以去网上查找源代码,但笔者建议读者按照本PPT的顺序去创建模块并编写代码。(1)首先编写一些基本的通用函数,将下列代码保存在创建好的kNN.py文件中:from numpy import*import operatordef createDataSet(
6、):group=array(1.0,1.1,1.0,1.0,0,0,0,0.1)labels=A,A,B,B return group,labels准备:使用Python导入数据 在上述代码中,我们导入了两个模块:科学计算包Numpy以及运算符模块,k-近邻算法执行排序操作时将使用这个模块提供的参数,后面我们将进一步介绍。为了方便使用createDataSet()函数,它创建数据集和标签,我们需进入Python开发环境并输入以下命令:(1)import kNN 上述命令导入kNN模块。准备:使用Python导入数据 (2)为了确保输入相同的数据集,继续输入以下命令:group,labels=k
7、NN.createDataSet()该命令创建了变量group和labels。(3)输入变量的名字以检验是否正确的定义变量:group 准备:使用Python导入数据 labels 结果显示,这里有四组数据,每组数据有两个我们已知的属性或特征值。上面的group矩阵每行包含一个不同的数据,我们可以将其想象成某个日志文件中不同的测量点或者入口。由于人类大脑的限制,我们通常只能可视化处理三维以下的实务。因此为了简单地实现数据可视化,对于每个数据点我们通常只使用两个特征。向量labels包含了每个数据点的标签信息,labels包含的元素个数等于group矩阵行数。这里我们将数据点(1,1.1)定义为
8、A类,数据点(0,0.1)定义为B类。为了方便说明,例子中的数值是任意选择的,并没有给出轴标签。实施kNN分类算法现在我们已经知道Python如何解析数据,如何加载数据,以及kNN算法的工作原理,接下来我们将使用这些方法完成分类任务。(1)以下为K-近邻算法的伪代码对未知类别属性的数据集中的每个点依次执行以下操作:计算已知类别数据集中点与当前点之间的距离;按照距离递增次序排序;选取与当前点距离最小的k个点;确定前k个点所在类别出现的频率;返回前k个点出现频率最高的类别作为当前点的预测分类。实施kNN分类算法(2)以下为kNN近邻算法代码,将其保存于kNN.py中def classify0(in
9、X,dataSet,labels,k):dataSetSize=dataSet.shape0 diffMat=tile(inX,(dataSetSize,1)-dataSet sqDiffMat=diffMat*2 sqDistances=sqDiffMat.sum(axis=1)distances=sqDistances*0.5 sortedDistIndicies=distances.argsort()classCount=for i in range(k):voteIlabel=labelssortedDistIndiciesi classCountvoteIlabel=classCou
10、nt.get(voteIlabel,0)+1 sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)return sortedClassCount00实施kNN分类算法classify0()函数有四个参数:用于分类的输入向量inX,输入的样本训练集为dataSet,标签向量为labels,最后的参数k表示用于选择最近邻居的数目,其中标签向量和矩阵dataSet的行数相同;代码中下划线部分用于距离计算,使用的是欧式距离公式;倾斜字体部分为对距离计算完毕后的数据按照从小到大的次序
11、排序并确定前k个距离最小元素所在的主要分类(k总为正整数);实施kNN分类算法倾斜+下划线部分为使用运算符模块的itemge-tter方法,按照第二个元素的次序对元组进行排序,此处的排序为逆序,最后返回发生频率最高的元素标签。(3)为了预测数据所在分类,在Python提示符中输入以下命令:kNN.classify0(0,0,group,labels,3)实施kNN分类算法显然输出结果为B,当然也可以输入其他值例如0.5,0.5,结果如下:到目前为止,我们已经构建了一个分类器,接下来我们将从实例出发进行讲解:(4)关于分类器分类器并不会得到100%正确的结果,我们可以通过错误率来进行评估。示例:
12、使用k-近邻算法改进约会网站的配对结果1.问题描述:我都朋友佩琪一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选,但是她并不是喜欢每一个人。经过一番总结,她发现曾交往过三种类型的人:p不喜欢的人p魅力一般的人p极具魅力的人示例:使用k-近邻算法改进约会网站的配对结果尽管发现了上述规律,但佩琪依然无法将约会网站推荐的匹配对象归入恰当的类别。她觉得可以在周一至约会那些魅力一般的人,而周末则更喜欢与那些极具魅力的人为伴。佩琪希望我们的分类软件可以更好的帮助她将匹配到的对象划分到确切的分类中。此外,佩琪还收集了一些约会网站未曾记录的数据信息并保存在了文本文件datingTest
13、Set2.txt中。示例:使用k-近邻算法改进约会网站的配对结果(2)佩琪保存的样本具有以下3个特征:p每年获得的飞行常客里程数p玩视频游戏所耗时间百分比p每周消费的冰淇淋公升数在将上述特征数据输入到分类器之前,必须将待处理数据的格式改变为分类器可以接受的格式。在kNN.py文件中添加名为file2matrix的函数,以此来处理该问题。示例:使用k-近邻算法改进约会网站的配对结果(3)file2matrix()代码如下,即将文本记录转换为Numpy的解析程序:def file2matrix(filename):fr=open(filename)arrayOLines=fr.readlines(
14、)numberOfLines=len(arrayOLines)returnMat=zeros(numberOfLines,3)classLabelVector=index=0 for line in arrayOLines:line=line.strip()listFromLine=line.split(t)returnMatindex,:=listFromLine0:3 classLabelVector.append(int(listFromLine-1)index+=1 return returnMat,classLabelVector示例:使用k-近邻算法改进约会网站的配对结果该函数的输
15、入为文件名字符串,输出为训练样本矩阵和类标签向量。下划线部分为得到文件行数。倾斜部分为创建以0填充的矩阵Numpy。下划线+倾斜字体部分循环处理文件中的每行数据,首先使用函数line.strip()截掉所有回车字符,然后使用t字符将上一步得到的整行数据分割成一个元素列表。接着我们选取前3个元素,将他们存储到特征矩阵中。示例:使用k-近邻算法改进约会网站的配对结果Python语言可以使用索引值-1表示列表中的最后一列元素,利用这种索引,我们可以很方便地将列表的最后一行储存到向量classLabel-Vector中。值得注意的是,我们必须明确告诉解释器列表中存储的元素是整型。继续输入以下命令:re
16、load(kNN)datingDataMat,datingLabels=kNN.file2matrix(datingTestSet2.txt)示例:使用k-近邻算法改进约会网站的配对结果 datingDataMat datingLabels0:20 接下来我们将采用图形化的方法直观地显示数据。示例:使用k-近邻算法改进约会网站的配对结果2.首先我们使用Matplotlib制作原始数据的散点图,继续输入以下命令:import matplotlib import matplotlib.pyplot as plt fig=plt.figure()ax=fig.add_subplot(111)ax.s
17、catter(datingDataMat:,1,datingDataMat:,2)plt.show()输出结果如图:示例:使用k-近邻算法改进约会网站的配对结果上述散点图使用datingDataSet矩阵的第二、第三列数据,分别表示特征值“玩视频游戏所耗时间百分比”和“每周所消耗的冰淇淋公升数”。由于没有使用样本分类的特征值,我们很难从上图中看出任何有用的数据模式信息。一般来说,我们会采用彩色或其他的记号来标记不同样本分类,以便更好地理解数据信息。Matplotlib库提供的scat-ter函数支持个性化标记散点图上的点。重新输入上面代码,调用scatter函数时使用下列函数:ax.scatt
18、er(datingDataMat:,1,datingDataMat:,2,15.0*array(datingLabels),15.0*array(datingLabels),其结果如图:该图为选取每年获取的飞行常客里程数与玩视频游戏所耗时间百分比所得的散点图:示例:使用k-近邻算法改进约会网站的配对结果3.准备数据:归一化数值(1)下表给出了提取的四组数据如果想要计算样本3和样本4之间的距离,可以采用下面的方法:示例:使用k-近邻算法改进约会网站的配对结果(2)发现问题:我们很容易发现,上面方程中数字差异最大的属性对计算结果的影响最大,也就是说,每年获取的飞行常客里程数对于计算结果的影响将远远
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 近邻 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。