IT虾米网

KNN算法详解

flyfish 2018年07月04日 程序员 117 0


k近邻法(k-Nearest eighbor,K-NN)是一种基本分类和回归方法。K近邻法的输入为实例的特征向量,对应的特征空间的点:输出为实例的类别,可以取多类。
     k值的选择,距离度量,和分类决策规则是k近邻法的三个基本要素。

K近邻算法

给定一个训练数据集,对新的输入实例,在训练数据集中找到跟它最近的k个实例,根据这k个实例的类判断它自己的类(一般采用多数表决的方法)。

k近邻模型

模型

当3要素确定的时候,对任何实例(训练或输入),它所属的类都是确定的,相当于将特征空间分为一些子空间。

距离度量

对n维实数向量空间Rn,经常用Lp距离或曼哈顿Minkowski距离。

Lp距离定义如下:

当p=2时,称为欧氏距离:

当p=1时,称为曼哈顿距离:

当p=∞,它是各个坐标距离的最大值,即:

用图表示如下:

k值的选择

k较小,整体模型变得复杂,容易被噪声影响,发生过拟合。

k较大,较远的训练实例也会对预测起作用,容易发生错误。

在应用中,k一般取一个比较小的数值,通常采用交叉验证法来选取最优的k值。

分类决策规则

使用0-1损失函数衡量,那么误分类率是:

Nk是近邻集合,要使左边最小,右边的必须最大,所以多数表决=经验最小化。

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

感知机详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。