Matlab笔记――KNN算法022

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

22.KNN算法KNN算法又称为k近邻分类(k-nearestneighborclassification)算法,是从训练集中找到和新数据最接近的k条记录,然后根据他们的主要分类来决定新数据的类别。该算法涉及3个主要因素:训练集、距离或相似的衡量、k的大小。一、算法要点1.指导思想其指导思想是“近朱者赤,近墨者黑”,由你的邻居来推断出你的类别。2.算法步骤:1)算距离:计算已知类别数据集合汇总的点与当前点的距离,按照距离递增次序排序;2)找邻居:选取与当前点距离最近的K个点;3)做分类:确定距离最近的前K个点所在类别的出现频率,返回距离最近的前K个点中频率最高的类别作为当前点的预测分类。3.k值设定为多大?k太小,分类结果易受噪声点影响;k太大,近邻中又可能包含太多的其它类别的点。(对距离加权,可以降低k值设定的影响)k值通常是采用交叉检验来确定(以k=1为基准)经验规则:k一般低于训练样本数的平方根2.距离或相似度的衡量什么是合适的距离衡量?距离越近应该意味着这两个点属于一个分类的可能性越大。常用的距离衡量包括欧氏距离、夹角余弦等。对于文本分类来说,使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。高维度对距离衡量的影响:众所周知当变量数越多,欧氏距离的区分能力就越差。变量值域对距离的影响:值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。3.类别的判定投票决定:少数服从多数,近邻中哪个类别的点最多就分为该类。加权投票法:根据距离的远近,对近邻的投票进行加权,距离越近则权重越大(权重为距离平方的倒数)。投票法没有考虑近邻的距离的远近,距离更近的近邻也许更应该决定最终的分类,所以加权投票法更恰当一些。4.优缺点1)优点简单,易于理解,易于实现,无需估计参数,无需训练。适合对稀有事件进行分类(例如当流失率很低时,比如低于0.5%,构造流失预测模型)。特别适合于多分类问题(multi-modal,对象具有多个类别标签),例如根据基因特征来判断其功能分类,kNN比SVM(支持向量机)的表现要好。2)缺点懒惰算法,对测试样本分类时的计算量大,内存开销大,评分慢。可解释性较差,无法给出决策树那样的规则。二、Matlab实现KNN.mfunctionrelustLabel=KNN(test,train,trainlabels,k,type)%%test为一条输入测试数据,train为样本数据,trainlabels为样本标签,选取k个临近值row=size(train,1);forj=1:rowswitchtypecase1%求test到每个样本的欧氏距离distanceMat(j)=sum((test-train(j,:)).^2);case2求test到每个样本的夹角余弦distanceMat(j)=(train(j,:)*test')/(norm(train(j,:),2)*norm(test,2));ifdistanceMat(j)0distanceMat(j)=(distanceMat(j)+1)/2;endendenddistanceMat=distanceMat';[B,IX]=sort(distanceMat,'ascend');%距离从小到大排序len=min(k,length(B));%选k个邻近值,当然k不能超过训练样本个数relustLabel=mode(trainlabels(IX(1:len)));%取众数(即出现频率最高的label)作为返回结果end测试数据(部分):主程序:loaddata;dataMat=data(:,1:3);labels=data(:,4);len=size(dataMat,1);k=4;error=0;%观察可视化数据label1=find(data(:,4)==1);label2=find(data(:,4)==2);label3=find(data(:,4)==3);plot3(data(label1,1),data(label1,2),data(label1,3),'ro');holdonplot3(data(label2,1),data(label2,2),data(label2,3),'go');plot3(data(label3,1),data(label3,2),data(label3,3),'bo');gridon%归一化处理maxV=max(dataMat);minV=min(dataMat);range=maxV-minV;newdataMat=(dataMat-repmat(minV,[len,1]))./(repmat(range,[len,1]));%测试数据比例Ratio=0.1;numTest=Ratio*len;%100条测试,900条训练%训练数据和测试数据TrainData=newdataMat(numTest+1:end,:);TrainLabels=labels(numTest+1:end,:);TestData=newdataMat(1:numTest,:);TestLabels=labels(1:numTest,:);%测试,欧氏距离type=1,夹角余弦type=2type=1;fori=1:numTestclassifyresult=KNN(TestData(i,:),TrainData,TrainLabels,k,type);%fprintf('第%d条记录,测试结果为:%d真实结果为:%d\n',[iclassifyresult(i)labels(i)])[classifyresultlabels(i)])if(classifyresult~=labels(i))error=error+1;endendclassifyresult=classifyresult';fprintf('分类错误的记录标签为:')Index=find(classifyresult~=TestLabels)fprintf('准确率为:%f\n',1-error/(numTest))运行结果:分类错误的记录标签为:Index=337592准确率为:0.970000注:1)若用夹角余弦距离,分类准确率只有11%;2)将样本数据分为两部分:训练集和测试集,调用分类算法,将测试集的分类结果与已知标签做比较,观察分类准确率。若准确率满足要求,则可以用该方法去分类标签未知的数据了,预测其类别。

1 / 6
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功