赞
踩
@创建于:2020.04.09
@修改于:2020.04.09
kNN是一个基本而简单的分类算法,作为监督学习,那么KNN模型需要的是有标签的训练数据,对于新样本的类别由与新样本距离最近的k个训练样本点按照分类决策规则决定。k近邻法1968年由Cover和Hart提出。
k近邻法(k-nearest neighbor, kNN)是一种基本的分类与回归方法;是一种基于有标签训练数据的模型;是一种监督学习算法。
基本做法的三个要点是:
第一,确定距离度量;
第二,k值的选择(找出训练集中与带估计点最靠近的k个实例点);
第三,分类决策规则。
k近邻法不具有显式的学习过程。它是懒惰学习(lazy learning)的著名代表,此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为零,待收到测试样本后再进行处理。
参考链接:
距离度量、k值的选择及分类决策规则是k近邻法的三个基本要素。
如下图,根据欧氏距离,选择k=4个离测试实例最近的训练实例(红圈处),再根据多数表决的分类决策规则,即这4个实例多数属于“-类”,可推断测试实例为“-类”。
参考链接:机器学习(二):k近邻法(kNN)
特征空间中的两个实例点的距离是两个实例点相似程度的反映。K近邻法的特征空间一般是n维实数向量空间
R
n
R_n
Rn。度量的距离是其他
L
p
L_p
Lp范式距离,一般为欧式距离。
L
p
(
x
i
,
x
j
)
=
(
∑
l
n
∣
x
i
(
l
)
−
x
j
(
l
)
∣
p
)
1
p
(1)
L_p(x_i, x_j) = (\sum_l^n|x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p} \tag1
Lp(xi,xj)=(l∑n∣xi(l)−xj(l)∣p)p1(1)
常用的方法:
(1)从k=1开始,使用检验集估计分类器的误差率。
(2)重复该过程,每次K增值1,允许增加一个近邻。
(3)选取产生最小误差率的K。
注意:
(1)一般k的取值不超过20,上限是n的开方,随着数据集的增大,K的值也要增大。
(2)一般k值选取比较小的数值,并采用交叉验证法选择最优的k值。
说明:
参考链接:
kNN的分类决策规则就是对输入新样本的邻域内所有样本进行统计数目。
邻域的定义就是,以新输入样本点为中心,离新样本点距离最近的k个点所构成的区域。
参考链接:KNN
k近邻法最简单的实现方法是线性扫描(linear scan),这时要计算输入实例与每一个训练实例的距离,当训练集很大时,计算非常耗时。
kNN的时间复杂度为O(n),一般适用于样本数较少的数据集,当数据量大时,可以将数据以树的形式呈现,能提高速度,常用的有kd-tree和ball-tree。
下面介绍其中的kd树方法(平衡二叉树)。kd树是存储k维空间数据的树结构,这里的k与k近邻法的k意义不同。
依次选择坐标轴对空间切分,选择训练实例点在选定坐标轴上的中位数(一组数据按大小顺序排列起来,处于中间的一个数或最中间两个数的平均值。本文在最中间有两个数时选择最大值作中位数)为切分点,这样得到的kd树是平衡的。注意,平衡的kd树搜索时未必是最优的。
参考链接:
sklearn中的K近邻分类器在sklearn库中,可以使sklearn.neighbors.KNeighborsClassifier 创建一个K近邻分类器 。
主要参数有:
from sklearn.neighbors import KNeighborsClassifier
# 设置最近的3个邻居作为分类的依据
neigh = KNeighborsClassifier(n_neighbors = 3, weights = 'uniform', algorithm = 'auto')
详细代码请参考链接:监督学习-分类(KNN算法)
1、优点
2、缺点
参考链接:数据挖掘十大算法——kNN
1、k值设定为多大?
2、类别如何判定最合适?
3、如何选择合适的距离衡量?
4、训练样本是否要一视同仁?
5、性能问题?
6、能否大幅减少训练样本量,同时又保持分类精度?
参考链接:数据挖掘十大算法——kNN
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。