KNN算法课案

《KNN算法课案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、KNN:K最近邻分类算法K-NearestNeighborClassification数据挖掘十大算法KNNC4.5K-MeansSVMAprioriEMPageRankAdaBoostNaiveBayesCART分类输入数据是记录的集合。每条记录也称为样本或样例，用元组（x，y）表示。x是属性集合，y是类标号（分类属性或目标属性）。类标号是离散的。（回归的目标属性y是连续的）分类：通过学习得到一个目标函数（分类函数）f，把每个属性集x映射到一个预先定义的类标号y。分类任务：确定对象属于哪个预定义的目标类

2、。脊椎动物的数据表名字体温冬眠有腿胎生类标号人类恒温否是是哺乳类蝙蝠恒温是是是哺乳类青蛙冷血是是否两栖类蟒蛇冷血是否否爬行类分类分类分类性能预测的类类=1类=0实际的类类=1f11f10类=0f01f00使用性能度量来衡量分类模型性能的信息，如准确率和错误率。准确率=正确预测数/预测总数=（f11+f00）/（f11+f10+f01+f00）错误率=错误预测数/预测总数=（f10+f01）/（f11+f10+f01+f00）表1二类问题的混淆矩阵KNN算法怎么来的？KNN算法是怎么来的电影名称打斗次数接吻

3、次数电影类型CaliforniaMan3104RomanceHe’sNotReallyintoDudes2100RomanceBeautifulWoman181RomanceKevinLongblade10110ActionRoboSlayer3000995ActionAmpedII982Action未知1890Unknown猜猜看：最后一行未知电影属于什么类型的电影。KNN算法是怎么来的点X坐标Y坐标点类型A点3104RomanceB点2100RomanceC点181RomanceD点10110Acti

4、onE点995ActionF点982ActionG点1890Unknown猜猜看：最后一行未知点属于什么类型的点。最近邻算法由此，我们引出最近邻算法的定义：为了判定未知样本的类别，以全部训练样本作为代表点，计算未知样本与所有训练样本的距离，并以最近邻者的类别作为决策未知样本类别的唯一依据。最近邻算法的缺陷——对噪声数据过于敏感，为了解决这个问题，我们可以把未知样本周边的多个最近样本计算在内，扩大参与决策的样本量，以避免个别数据直接决定决策结果。由此，引进K-近邻（knearestneighbor）算法。K

5、NN算法是用来干什么的K-最近邻算法是最近邻算法的一个延伸。基本思路是：选择距离未知样本最近的K个样本，该K个样本大多数属于某一类型，则未知样本判定为该类型。问题：有一个未知形状X(图中绿色的圆点)，如何判断X是什么形状?右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。KNN算法基本描述k-近邻法:基本规则是，在所有N个样本中,找到测试样本的k(k

6、<=N)个最近邻者，当k=1时，knn问题就变成了最近邻问题。其中各类别所占个数表示成ki,i＝1，…，c。定义判别函数为：gi(x)=ki,i=1,2,…,c。k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。多数表决决策规则为：计算步骤如下：1）算距离：给定测试对象，计算它与训练集中的每个对象的距离2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类距离度量KNN算法中，距离如何定义？就是如何度量邻居之间的相识度，也

7、就是如何选取邻居的问题，我们知道相似性的度量方式在很大程度上决定了选取邻居的准确性，也决定了分类的效果，因为判定一个样本点的类别是要利用到它的邻居的，如果邻居都没选好，准确性就无从谈起。因此我们需要用一个量来定量的描述邻居之间的距离，也可以形象的表述为邻居之间的相似度，具体的距离度量方式有很多，不同的场合使用哪种需要根据不同问题具体探讨，如文本类型，一般用余弦相似度。距离度量曼哈顿距离(ManhattanDistance)从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十

8、字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(CityBlockdistance)。两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的曼哈顿距离距离度量欧氏距离(EuclideanDistance)欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。两个n维向量