KNN算法课案

KNN:K最近邻分类算法K-NearestNeighborClassification数据挖掘十大算法KNNC4.5K-MeansSVMAprioriEMPageRankAdaBoostNaiveBayesCART分类输入数据是记录的集合。每条记录也称为样本或样例，用元组（x，y）表示。x是属性集合，y是类标号（分类属性或目标属性）。类标号是离散的。（回归的目标属性y是连续的）分类：通过学习得到一个目标函数（分类函数）f，把每个属性集x映射到一个预先定义的类标号y。分类任务：确定对象属于哪个预定义的目标类。脊椎动物的数据表名字体温冬眠有腿胎生类标号人类恒温否是是哺乳类蝙蝠恒温是是是哺乳类青蛙冷血是是否两栖类蟒蛇冷血是否否爬行类分类分类分类性能预测的类类=1类=0实际的类类=1f11f10类=0f01f00使用性能度量来衡量分类模型性能的信息，如准确率和错误率。准确率=正确预测数/预测总数=（f11+f00）/（f11+f10+f01+f00）错误率=错误预测数/预测总数=（f10+f01）/（f11+f10+f01+f00）表1二类问题的混淆矩阵KNN算法怎么来的？KNN算法是怎么来的电影名称打斗次数接吻次数电影类型CaliforniaMan3104RomanceHe’sNotReallyintoDudes2100RomanceBeautifulWoman181RomanceKevinLongblade10110ActionRoboSlayer3000995ActionAmpedII982Action未知1890Unknown猜猜看：最后一行未知电影属于什么类型的电影。KNN算法是怎么来的点X坐标Y坐标点类型A点3104RomanceB点2100RomanceC点181RomanceD点10110ActionE点995ActionF点982ActionG点1890Unknown猜猜看：最后一行未知点属于什么类型的点。最近邻算法由此，我们引出最近邻算法的定义：为了判定未知样本的类别，以全部训练样本作为代表点，计算未知样本与所有训练样本的距离，并以最近邻者的类别作为决策未知样本类别的唯一依据。最近邻算法的缺陷——对噪声数据过于敏感，为了解决这个问题，我们可以把未知样本周边的多个最近样本计算在内，扩大参与决策的样本量，以避免个别数据直接决定决策结果。由此，引进K-近邻（knearestneighbor）算法。KNN算法是用来干什么的K-最近邻算法是最近邻算法的一个延伸。基本思路是：选择距离未知样本最近的K个样本，该K个样本大多数属于某一类型，则未知样本判定为该类型。问题：有一个未知形状X(图中绿色的圆点)，如何判断X是什么形状?右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。KNN算法基本描述k-近邻法:基本规则是，在所有N个样本中,找到测试样本的k(k=N)个最近邻者，当k=1时，knn问题就变成了最近邻问题。其中各类别所占个数表示成ki,i＝1，…，c。定义判别函数为：gi(x)=ki,i=1,2,…,c。k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。多数表决决策规则为：argmax(),1,...,iijgicx计算步骤如下：1）算距离：给定测试对象，计算它与训练集中的每个对象的距离2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类距离度量KNN算法中，距离如何定义？就是如何度量邻居之间的相识度，也就是如何选取邻居的问题，我们知道相似性的度量方式在很大程度上决定了选取邻居的准确性，也决定了分类的效果，因为判定一个样本点的类别是要利用到它的邻居的，如果邻居都没选好，准确性就无从谈起。因此我们需要用一个量来定量的描述邻居之间的距离，也可以形象的表述为邻居之间的相似度，具体的距离度量方式有很多，不同的场合使用哪种需要根据不同问题具体探讨，如文本类型，一般用余弦相似度。距离度量曼哈顿距离(ManhattanDistance)从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(CityBlockdistance)。两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的曼哈顿距离距离度量欧氏距离(EuclideanDistance)欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的欧氏距离：距离度量切比雪夫距离(ChebyshevDistance)国际象棋的玩法。国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走试试。你会发现最少步数总是max(|x2-x1|,|y2-y1|)步。有一种类似的一种距离度量方法叫切比雪夫距离。两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的切比雪夫距离这个公式的另一种等价形式是距离度量闵可夫斯基距离(MinkowskiDistance)闵氏距离不是一种距离，而是一组距离的定义。闵氏距离的定义两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：其中p是一个变参数。当p=1时，就是曼哈顿距离当p=2时，就是欧氏距离当p→∞时，就是切比雪夫距离根据变参数的不同，闵氏距离可以表示一类的距离。KNN算法的实现步骤算法步骤：1：令k是最近邻数目，D是训练样例的集合2：for每个测试样例zdo3：计算z和每个训练样例之间的距离d4：对d进行升序排序5：取前k个训练样例的集合6：统计K个最近邻样本中每个类别出现的次数7：选择出现频率最大的类别作为未知样本的类别8：endforKNN算法MATLAB%KNNclassifiers,%trainingistrainingset,testingistestset,%Disthedistance,D=1is曼哈顿距离;D=2is欧氏距离；D=3是切比雪夫%距离%Kisthenumberofselectedneighborsfunctionlabel=KNN(training,testing,D,K)[row,column]=size(training)；%%%row行（样本），column列（属性）[row1,column1]=size(testing);%计算测试集与训练集的距离KNN算法MATLAB%数据标准化Tr_m=min(training);%%%每列（属性）取最小值，得到一个行向量Tr_s=max(training);%%%每列（属性）取最大值，得到一个行向量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多一列类标号KNN算法MATLAB%%%%%计算距离%%D=1曼哈顿距离%%%%%%%%%%%%%%%%distance=[];ifD==1fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)]‘;%%变为两个列向量d=mandist(temp);%%%mandist函数求曼哈顿距离distance(i,j)=d(1,2);%%两个列向量求mandist，得出endendendKNN算法MATLAB%%%%%计算欧几里得距离%%%%%%%%%%%%%%%%%%ifD==2fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)]';d=dist(temp);%%%%dist函数计算距离distance(i,j)=d(1,2);endendendKNN算法MATLAB%%%%%计算切比雪夫距离%%%%%%%%%%%%%%%%%%ifD==3fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)];%%两个行向量d=max(abs(temp(1,:)-temp(2,:)));%%两个行向量求距离distance(i,j)=d;endendendKNN算法MATLAB%%%%寻找k个近邻%%%%算法核心部分%%%%%%%%%%%%%%label=[];fori=1:row1[a,b]=sort(distance(i,:));%%针对第i个测试样本与所有训练样本的距离，进行升序排序，距离越小，离的越近，a返回排序后的距离，b返回排序后的下标neighbors=b(1:K)‘;%%选取前k个下标neighbors_D=training(neighbors,column);%%对应下标找到k个类标号[x,y]=sort(neighbors_D);%对K个类标号排序，x返回类标号，y返回下标temp=find(diff(x)~=0);nei_d=[x(1);x(temp+1)];%对前k个样本的标签进行分类KNN算法MATLABNum_D=[];forj=1:length(nei_d)num=length(find(neighbors_D==nei_d(j)));Num_D=[Num_D,num];end%%%%%计算样本的类别号%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%[a,b]=max(Num_D);%取标签较多的那个类作为测试样本的类别label(i)=nei_d(b);end%label=label';KNN算法的缺陷观察下面的例子，我们看到，对于未知样本X，通过KNN算法，我们显然可以得到X应属于红点，但对于未知样本Y，通过KNN算法我们似乎得到了Y应属于蓝点的结论，而这个结论直观来看并没有说服力。KNN算法的具体实现由上面的例子可见：该算法在分类时有个重要的不足是，当样本不平衡时，即：一个类的样本容量很大，而其他类样本数量很小时，很有可能导致当输入一个未知样本z=(x’,y’)时，该样本的K个邻居中大数量类的样本占多数。但是这类样本并不接近目标样本，而数量小的这类样本很靠近目标样本。这个时候，我们有理由认为该未知样本属于数量小的样本所属的一类，但是，KNN却不关心这个问题，它只关心哪类样本的数量最多，而不去把距离远近考虑在内，因此，我们可以采用权值的方法来改进。和该样本距离小的邻居权值大，和该样本距离大的邻居权值则相对较小，由此，将距离远近的因素也考虑在内，避免因一个样本过大导致误判的情况。距离加权表决：argmax(),1,...,iiijwgicx21/(',)iiwdxxKNN算法的缺陷从算法实现的过程大家可以发现，该算法存两个严重的问题，第一个是需要存储全部的训练样本，第二个是需要进行繁重的距离计算量。对此，提出以下应对策略。两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种则是在原有样本集中挑选出对分类计算有效