K近邻算法PPT
- 格式:pptx
- 大小:832.20 KB
- 文档页数:14
第6章k 近邻算法k 近邻算法(kNN 算法)由Thomas 等人在1967年提出[1]。
它基于以下朴素思想:要确定一个样本的类别,可以计算它与所有训练样本的距离,然后找出和该样本最接近的k 个样本,统计这些样本的类别进行投票,票数最多的那个类就是分类结果。
因为直接比较待预测样本和训练样本的距离,kNN 算法也被称为基于实例的算法。
6.1基本概念确定样本所属类别的一种最简单的方法是直接比较它和所有训练样本的相似度,然后将其归类为最相似的样本所属的那个类,这是一种模板匹配的思想。
k 近邻算法采用了这种思路,下图6.1是使用k 近邻思想进行分类的一个例子:图6.1k 近邻分类示意图在上图中有红色和绿色两类样本。
对于待分类样本即图中的黑色点,我们寻找离该样本最近的一部分训练样本,在图中是以这个矩形样本为圆心的某一圆范围内的所有样本。
然后统计这些样本所属的类别,在这里红色点有12个,绿色有2个,因此把这个样本判定为红色这一类。
上面的例子是二分类的情况,我们可以推广到多类,k 近邻算法天然支持多类分类问题。
6.2预测算法k 近邻算法没有要求解的模型参数,因此没有训练过程,参数k 由人工指定。
它在预测时才会计算待预测样本与训练样本的距离。
对于分类问题,给定l 个训练样本(),i i y x ,其中i x 为维特征向量,i y 为标签值,设定参数k ,假设类型数为c ,待分类样本的特征向量为x 。
预测算法的流程为:1.在训练样本集中找出离x 最近的k 个样本,假设这些样本的集合为N 。
2.统计集合N 中每一类样本的个数,1,...,i C i c =。
3.最终的分类结果为arg max i i C 。
在这里arg max i i C 表示最大的i C 值对应的那个类i 。
如果1k =,k 近邻算法退化成最近邻算法。
k 近邻算法实现简单,缺点是当训练样本数大、特征向量维数很高时计算复杂度高。
因为每次预测时要计算待预测样本和每一个训练样本的距离,而且要对距离进行排序找到最近的k 个样本。
K最近邻算法K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。
所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。
该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
kNN方法在类别决策时,只与极少量的相邻样本有关。
由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。
KNN算法的机器学习基础显示相似数据点通常如何彼此靠近存在的图像大多数情况下,相似的数据点彼此接近。
KNN算法就是基于这个假设以使算法有用。
KNN利用与我们童年时可能学过的一些数学相似的想法(有时称为距离、接近度或接近度),即计算图上点之间的距离。
例如,直线距离(也称为欧氏距离)是一个流行且熟悉的选择。
KNN通过查找查询和数据中所有示例之间的距离来工作,选择最接近查询的指定数字示例( K ),然后选择最常用的标签(在分类的情况下)或平均标签(在回归的情况下)。
在分类和回归的情况下,我们看到为我们的数据选择正确的K是通过尝试几个K并选择最有效的一个来完成的。
KNN算法的步骤1.加载数据2.将K初始化为你选择的邻居数量3.对于数据中的每个示例4.3.1 根据数据计算查询示例和当前示例之间的距离。
5.3.2 将示例的距离和索引添加到有序集合中6.按距离将距离和索引的有序集合从最小到最大(按升序)排序7.从已排序的集合中挑选前K个条目8.获取所选K个条目的标签9.如果回归,返回K个标签的平均值10.如果分类,返回K个标签的模式'为K选择正确的值为了选择适合你的数据的K,我们用不同的K值运行了几次KNN算法,并选择K来减少我们遇到的错误数量,同时保持算法在给定之前从未见过的数据时准确预测的能力。
第10章K近邻法第10-13章使用“非参数方法”(nonparametric approach)进行监督学习。
最简单的非参数方法就是K近邻法(K Nearest Neighbors,简记KNN),即以最近的K个邻居进行预测,由Fix and Hodges (1951)提出。
10.1 回归问题的K近邻法首先考虑回归问题。
假设响应变量y连续,而x为p维特征向量。
根据y x。
第4章命题4.1,能使均方误差最小化的函数为条件期望函数E(|)y x?问题是,在实践中应如何估计E(|)1如果对于任意给定x,均有很多不同的y观测值,则可对这些y值进行简单算术平均,参见图10.1。
图10.1 理想的数据2现实数据大多比较稀疏,比如图10.2。
给定x,可能只有很少的y观测值,甚至连一个y观测值也没有。
图10.2 现实的数据34一个解决方法是在特征空间(feature space)中,考虑离x 最近的K 个邻居。
记()K N x 为最靠近x 的K 个观测值i x 的集合。
K 近邻估计量 (K nearest neighbor estimator)以离x 最近的K 个邻居之y 观测值的平均作为预测值: ()1ˆ()i K KNN i N f y K ∈≡∑x x x (10.1)如果1K =,则为“最近邻法”(nearest neighbor),即以离x 最近邻居的y 观测值作为预测值。
5为了找到最近的K 个邻居,首先需要在特征空间中,定义一个距离函数。
通常以欧氏距离(即2L 范数)作为此距离函数,即2i x x 。
使用KNN 法的一个前提是,所有特征变量均为数值型;否则,将无法计算欧氏距离。
为避免某些变量对于距离函数的影响太大,一般建议先将所有变量标准化(standardization),即减去该变量的均值,再除以其标准差,使得所有变量的均值为0而标准差为1。
610.2 如何选择K在进行KNN 估计时,一个重要选择为如何确定K 。