knn算法 教学课件.pptx

浅谈K-NN算法

目录

一算法简介

一算法思想

一算法实现

一算法应用场面或场景一算法的应用案例

一、算法简介

一何谓K近邻算法，即K-NearestNeighboralgorithm,简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：分析一个人时，我们不妨观察和他最亲密的几个人。同理的，在判定一个未知事物时，可以观察离它最近的几个样本，这就是kNN(k最近邻)的方法。

■如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。

一问题：图中的绿色的圆属于哪一类?

■如果K=3,绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

一如果K=5,绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

二、算法思想

三、算法实现

一产生训练集，使得训练集按照已有的分类标准划分成离散型数值类，或者是连续型数值类输出。

一以训练集的分类为基础，对测试集每个样本寻找K个近邻，采用欧式距离作为样本间的相似程度的判断依据，相似度大的即为最近邻。一般近邻可以选择1个或者多个。

●当类为连续型数值时，测试样本的最终输出为近邻的平均值；当类为离散型数值时，测试样本的最终为近邻类中个数最多的那一类。

算法步骤

step.1---初始化距离为最大值

step.2---计算未知样本和每个训练样本的距离dist

step.3---得到目前K个最临近样本中的最大距离maxdist

step.4---如果dist小于maxdist,则将该训练样本作为K-最近邻样本step.5---重复步骤2、3、4,直到未知样本和所有训练样本的距离都

算完

step.6---统计K个最近邻样本中每个类别出现的次数

step.7---选择出现频率最大的类别作为未知样本的类别

算法三个基本要素

●K值的选择

一距离度量

一分类决策规则

内容补充：K值的选择

(a)Neighborhoodtoo(b)Neighborhoodjust(c)Neighborhoodtoo

small.right.large.

内容补充：距离度量之欧式距离

马氏距离：马氏距离能够缓解由于属性的线性组合带来的距离失真，Z是数据的协方差矩阵。

dmahx,y=x-yz-1(x-y)⁷

曼哈顿距离：

切比雪夫距离：

dchex,y=max(lx一yI)

闵氏距离：r取值为2时：曼哈顿距离；r取值为1时：欧式距离。

平均距离：

弦距离：ll·Il₂表示2-范数，即

测地距离：

K近邻算法的优点

一简单，易于理解，易于实现，无需估计参数，无需训练

一适合对稀有事件进行分类

一特别适合于多分类问题(multi-modal,对象具有多个类别标签)

K近邻算法的缺点

一当样本不平衡时(如一个类的样本容量很大，而其他类样本容量很小时)有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

一需要存储全部训练样本，计算量较大

●可解释性较差，无法给出决策树那样的规则。

针对K近邻缺点的改进方案

一缺点一解决方案：1、权值的方法(和该样本距离小的邻居权值大);2、事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

一缺点二解决方案：选取质点

K近邻算法带来的问题

一应用K-近邻算法来进行预测的时候，经常会遇到很多现实问题。包括：

维度灾害问题

近邻索引问题

近邻大小问题

计算效率问题

归纳偏置问题

K近邻算法改进：压缩近邻算法

一定义两个存储器，一个用来存放生成的样本集，称为output样本集；另一个用来存放原来的样本集，称为original样本集。

●1、初始化：output样本集为空集，原样本集存入original样本集，从original样本集中任意选择一个样本移动到output样本集中。

■2、在original样本集中选择第i个样本，并使用output样本集中的样本对其进行最近邻算法分类，若