KNN算法课案-算法课案

KNN:K最近邻分类(fēnlèi)算法K-NearestNeighborClassification第一页，共44页。数据挖掘十大算法(suànfǎ)KNNC4.5K-MeansSVMAprioriEMPageRankAdaBoostNaiveBayesCART第二页，共44页。分类(fēnlèi)输入数据是记录的集合。每条记录也称为样本或样例，用元组（x，y）表示。x是属性集合，y是类标号（分类属性或目标属性）。类标号是离散的。（回归的目标属性y是连续(liánxù)的）分类：通过学习得到一个目标函数（分类函数）f，把每个属性集x映射到一个预先定义的类标号y。分类任务：确定对象属于哪个预定义的目标类。脊椎动物的数据表名字体温冬眠有腿胎生类标号人类恒温否是是哺乳类蝙蝠恒温是是是哺乳类青蛙冷血是是否两栖类蟒蛇冷血是否否爬行类第三页，共44页。分类(fēnlèi)第四页，共44页。分类(fēnlèi)第五页，共44页。分类(fēnlèi)性能预测的类类=1类=0实际的类类=1f11f10类=0f01f00使用性能度量来衡量分类模型性能的信息，如准确率和错误率。准确率=正确预测数/预测总数(zǒngshù)=（f11+f00）/（f11+f10+f01+f00）错误率=错误预测数/预测总数(zǒngshù)=（f10+f01）/（f11+f10+f01+f00）表1二类问题(wèntí)的混淆矩阵第六页，共44页。KNN算法(suànfǎ)怎么来的？第七页，共44页。KNN算法(suànfǎ)是怎么来的电影名称打斗次数接吻次数电影类型CaliforniaMan

3104RomanceHe’sNotReallyintoDudes

2100RomanceBeautifulWoman

181RomanceKevinLongblade

10110ActionRoboSlayer3000

995ActionAmpedII

982Action未知1890Unknown猜猜看：最后(zuìhòu)一行未知电影属于什么类型的电影。第八页，共44页。KNN算法(suànfǎ)是怎么来的点X坐标Y坐标点类型A点

3104RomanceB点

2100RomanceC点

181RomanceD点

10110ActionE点

995ActionF点

982ActionG点1890Unknown猜猜看：最后一行(yīxíng)未知点属于什么类型的点。第九页，共44页。最近(zuìjìn)邻算法由此，我们引出最近邻算法的定义：为了(wèile)判定未知样本的类别，以全部训练样本作为代表点，计算未知样本与所有训练样本的距离，并以最近邻者的类别作为决策未知样本类别的唯一依据。最近邻算法的缺陷——对噪声数据过于敏感，为了(wèile)解决这个问题，我们可以把未知样本周边的多个最近样本计算在内，扩大参与决策的样本量，以避免个别数据直接决定决策结果。由此，引进K-近邻（knearestneighbor）算法。第十页，共44页。KNN算法(suànfǎ)是用来干什么的K-最近邻算法是最近邻算法的一个延伸。基本思路是：选择距离未知样本最近的K个样本，该K个样本大多数属于某一类型，则未知样本判定为该类型。问题：有一个未知形状X(图中绿色(lǜsè)的圆点)，如何判断X是什么形状?右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于(yóuyú)红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于(yóuyú)蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。第十一页，共44页。KNN算法基本(jīběn)描述k-近邻法:基本规则是，在所有N个样本中,找到测试样本的k(k<=N)个最近邻者，当k=1时，knn问题就变成了最近邻问题。其中各类别所占个数表示成ki,i＝1，…，c。定义判别函数为：

gi(x)=ki,i=1,2,…,c。k-近邻一般(yībān)采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。多数表决决策规则为：计算步骤如下：

1）算距离：给定测试对象，计算它与训练(xùnliàn)集中的每个对象的距离

2）找邻居：圈定距离最近的k个训练(xùnliàn)对象，作为测试对象的近邻

3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类

第十二页，共44页。距离(jùlí)度量KNN算法中，距离如何定义？就是如何度量邻居之间的相识度，也就是如何选取邻居的问题，我们知道相似性的度量方式在很大程度上决定了选取邻居的准确性，也决定了分类的效果(xiàoguǒ)，因为判定一个样本点的类别是要利用到它的邻居的，如果邻居都没选好，准确性就无从谈起。因此我们需要用一个量来定量的描述邻居之间的距离，也可以形象的表述为邻居之间的相似度，具体的距离度量方式有很多，不同的场合使用哪种需要根据不同问题具体探讨，如文本类型，一般用余弦相似度。

第十三页，共44页。距离(jùlí)度量曼哈顿距离(ManhattanDistance)

从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际(shíjì)驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(CityBlockdistance)。两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的曼哈顿距离

第十四页，共44页。距离(jùlí)度量

欧氏距离(EuclideanDistance)

欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间(kōngjiān)中两点间的距离公式。

两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的欧氏距离：第十五页，共44页。距离(jùlí)度量切比雪夫距离

(ChebyshevDistance)

国际象棋的玩法。国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走试试。你会发现最少步数总是max(|x2-x1|,|y2-y1|)步。有一种类似的一种距离度量方法(fāngfǎ)叫切比雪夫距离。

两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的切比雪夫距离

这个公式的另一种等价形式是

第十六页，共44页。距离(jùlí)度量闵可夫斯基距离(MinkowskiDistance)闵氏距离不是一种距离，而是一组距离的定义。闵氏距离的定义

两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：其中p是一个变参数。当p=1时，就是曼哈顿距离当p=2时，就是欧氏距离当p→∞时，就是切比雪夫距离

根据变参数的不同，闵氏距离可以(kěyǐ)表示一类的距离。第十七页，共44页。KNN算法的实现(shíxiàn)步骤算法(suànfǎ)步骤：1：令k是最近邻数目，D是训练样例的集合2：for每个测试样例zdo3：计算z和每个训练样例之间的距离d4：对d进行升序排序5：取前k个训练样例的集合6：统计K个最近邻样本中每个类别出现的次数7：选择出现频率最大的类别作为未知样本的类别8：endfor第十八页，共44页。KNN算法(suànfǎ)MATLAB%KNNclassifiers,%trainingistrainingset,testingistestset,%Disthedistance,D=1is曼哈顿距离;D=2is欧氏距离；D=3是切比雪夫%距离%Kisthenumberofselectedneighborsfunctionlabel=KNN(training,testing,D,K)[row,column]=size(training)；%%%row行（样本），column列（属性(shǔxìng)）[row1,column1]=size(testing);%计算测试集与训练集的距离第十九页，共44页。KNN算法(suànfǎ)MATLAB%数据标准化Tr_m=min(training);%%%每列（属性(shǔxìng)）取最小值，得到一个行向量Tr_s=max(training);%%%每列（属性(shǔxìng)）取最大值，得到一个行向量Tr=[];Te=[];fori=1:(column-1)%%%最后一列是类标号Tr_mi=(training(:,i)-Tr_m(i))/Tr_s(i);%%每列中的数据减该列最小值，再除以该列最大值Te_mi=(testing(:,i)-Tr_m(i))/Tr_s(i);Tr=[Tr,Tr_mi];Te=[Te,Te_mi];endtraining=[Tr,training(:,column)];%%%加上类标号testing=Te;%%%training比testing多一列类标号第二十页，共44页。KNN算法(suànfǎ)MATLAB%%%%%计算距离%%D=1曼哈顿距离%%%%%%%%%%%%%%%%distance=[];ifD==1fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)]‘;%%变为两个列向量d=mandist(temp);%%%mandist函数(hánshù)求曼哈顿距离distance(i,j)=d(1,2);%%两个列向量求mandist，得出endendend第二十一页，共44页。KNN算法(suànfǎ)MATLAB%%%%%计算(jìsuàn)欧几里得距离%%%%%%%%%%%%%%%%%%ifD==2fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)]';d=dist(temp);%%%%dist函数计算(jìsuàn)距离distance(i,j)=d(1,2);endendend第二十二页，共44页。KNN算法(suànfǎ)MATLAB%%%%%计算(jìsuàn)切比雪夫距离%%%%%%%%%%%%%%%%%%ifD==3fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)];%%两个行向量d=max(abs(temp(1,:)-temp(2,:)));%%两个行向量求距离distance(i,j)=d;endendend第二十三页，共44页。KNN算法(suànfǎ)MATLAB%%%%寻找k个近邻%%%%算法核心部分%%%%%%%%%%%%%%label=[];fori=1:row1[a,b]=sort(distance(i,:));%%针对第i个测试样本与所有训练样本的距离，进行升序排序，距离越小，离的越近，a返回(fǎnhuí)排序后的距离，b返回(fǎnhuí)排序后的下标neighbors=b(1:K)‘;%%选取前k个下标neighbors_D=training(neighbors,column);%%对应下标找到k个类标号[x,y]=sort(neighbors_D);%对K个类标号排序，x返回(fǎnhuí)类标号，y返回(fǎnhuí)下标temp=find(diff(x)~=0);nei_d=[x(1);x(temp+1)];%对前k个样本的标签进行分类第二十四页，共44页。KNN算法(suànfǎ)MATLABNum_D=[];forj=1:length(nei_d)num=length(find(neighbors_D==nei_d(j)));Num_D=[Num_D,num];end%%%%%计算(jìsuàn)样本的类别号%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%[a,b]=max(Num_D);%取标签较多的那个类作为测试样本的类别label(i)=nei_d(b);end%label=label';

第二十五页，共44页。KNN算法(suànfǎ)的缺陷观察下面的例子，我们看到，对于未知样本X，通过KNN算法，我们显然可以(kěyǐ)得到X应属于红点，但对于未知样本Y，通过KNN算法我们似乎得到了Y应属于蓝点的结论，而这个结论直观来看并没有说服力。第二十六页，共44页。KNN算法的具体(jùtǐ)实现由上面的例子可见：该算法在分类时有个重要的不足是，当样本不平衡时，即：一个类的样本容量很大，而其他类样本数量很小时，很有可能导致当输入一个未知样本z=(x’,y’)时，该样本的K个邻居中大数量类的样本占多数。但是这类样本并不接近目标样本，而数量小的这类样本很靠近目标样本。这个时候，我们有理由认为该未知样本属于数量小的样本所属的一类，但是，KNN却不关心这个问题，它只关心哪类样本的数量最多，而不去把距离远近考虑在内，因此(yīncǐ)，我们可以采用权值的方法来改进。和该样本距离小的邻居权值大，和该样本距离大的邻居权值则相对较小，由此，将距离远近的因素也考虑在内，避免因一个样本过大导致误判的情况。距离加权表决：第二十七页，共44页。KNN算法(suànfǎ)的缺陷 从算法实现的过程大家可以发现，该算法存两个严重的问题，第一个是需要存储全部(quánbù)的训练样本，第二个是需要进行繁重的距离计算量。对此，提出以下应对策略。两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。

第二十八页，共44页。KNN算法(suànfǎ)的改进：分组快速搜索近邻法 其基本思想是：将样本集按近邻关系分解成组，给出每组质心的位置，以质心作为代表点，和未知样本计算距离(jùlí)，选出距离(jùlí)最近的一个或若干个组，再在组的范围内应用一般的knn算法。由于并不是将未知样本与所有样本计算距离(jùlí)，故该改进算法可以减少计算量。第二十九页，共44页。KNN算法的改进：压缩(yāsuō)近邻算法 利用现在的样本集，采取一定(yīdìng)的算法产生一个新的样本集，该样本集拥有比原样本集少的多的样本数量，但仍然保持有对未知样本进行分类的能力。 基本思路：定义两个存储器，一个用来存放生成的样本集，称为output样本集；另一个用来存放原来的样本集，称为original样本集。 1.初始化：output样本集为空集，原样本集存入original样本集，从original样本集中任意选择一个样本移动到output样本集中； 2.在original样本集中选择第i个样本，并使用output样本集中的样本对其进行最近邻算法分类，若分类错误，则将该样本移动到output样本集中，若分类正确，不做任何处理； 3.重复2步骤，直至遍历完original样本集中的所有样本，output样本集即为压缩后的样本集。 通过这种方式也能减少算法的计算量。第三十页，共44页。KNN算法(suànfǎ)几大问题1、k值设定为多大？

k太小，分类结果易受噪声(zàoshēng)点影响；k太大，近邻中又可能包含太多的其它类别的点。k值通常是采用交叉检验来确定。经验规则：k一般低于训练样本数的平方根

第三十一页，共44页。KNN算法(suànfǎ)几大问题2、类别如何判定最合适？

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。3、如何选择合适的距离衡量？

高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

4、训练样本是否要一视同仁？

在训练集中，有些样本可能是更值得依赖的。可以给不同的样本施加不同的权重，加强(jiāqiáng)依赖样本的权重，降低不可信赖样本的影响。

第三十二页，共44页。分类学习(xuéxí)算法的种类积极学习法(决策树归纳)：先根据训练集构造出分类(fēnlèi)模型，根据分类(fēnlèi)模型对测试集分类(fēnlèi)。5、性能问题？

kNN是一种懒惰算法，平时不好好学习，考试(kǎoshì)（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。消极学习法(基于实例的学习法):推迟建模，当给定训练元组时，简单地存储训练数据(或稍加处理)，一直等到给定一个测试元组。消极学习法在提供训练元组时只做少量工作，而在分类或预测时做更多的工作。懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。

第三十三页，共44页。Multi-LabelLearning(MLL)Multi-labelobjectsareubiquitous!第三十四页，共44页。KNN算法(suànfǎ)的扩展：ML-KNN（Multi-labelKNN）Min-LingZhang,Zhi-HuaZhou.ML-KNN:AlazylearningapproachtoMulti-labellearning.PatternRecognition,40(2007):2038-2048.第三十五页，共44页。KNN算法(suànfǎ)的扩展：ML-KNN（Multi-labelKNN）未知样本(yàngběn)dt的3个最近邻是d4，d5，d6.则nt=<0,1,0>+<0,1,1>+<1,1,0>=<1,3,1>.运用maximumaposteriori(MAP）那么(nàme)对于此例子，对类1：P（H1=1|E=1）？P（H1=0|E=1）对类2：P（H2=1|E=3）？P（H2=0|E=3）对类3：P（H3=1|E=1）？P（H3=0|E=1）第三十六页，共44页。KNN算法(suànfǎ)的扩展：ML-KNN（Multi-labelKNN）由贝叶斯公式(gōngshì)：第一步：先求出先验概率：第三十七页，共44页。KNN算法(suànfǎ)的扩展：ML-KNN（Multi-labelKNN）设平滑参数s=1.则P（H1=1）=（1+4）/（2*1+6）=0.625.第二步：求条件(tiáojiàn)概率和将训练集中的每一个样本看成是一个测试样本，找其最近邻。第三十八页，共44页。KNN算法(suànfǎ)的扩展：ML-KNN（Multi-labelKNN）然后计算(jìsuàn)概率：设平滑(pínghuá)参数s