K近邻算法回顾
K近邻法模型的三要素:
距离度量:
K值的选取:K值的选取一般可以采用交叉验证法,且一般小于训练集样本量的平方根
分类决策规则:多数表决等价于误分类数最小
关于K近邻的问题:
1.简述K近邻算法的基本步骤
2.简述K近邻算法的三要素
答:距离度量、K值的选取、分类决策规则
3.简述距离的定义,以及欧氏距离、曼哈顿距离以及切比雪夫距离的定义
欧氏距离
曼哈顿距离:计算所有特征下的绝对距离,再求和
切比雪夫距离:找到所有特征下的绝对距离最大值
4.K值选取遵循的一般原则是什么?K值选择过大或者过小会对K近邻法的结果产生何种影响
答:K值的选取一般可以采用交叉验证法,且一般小于训练集样本量的平方根。
较小的k值,学习的近似误差减小,但估计误差会增大,敏感性增强,而且模型复杂,容易过拟合。较大的k值,减少学习的估计误差,但近似误差增大,而且模型简单。
正题切入:KD数
为什么要引入KD数:当数据集中的训练实例非常多且密集,并且一个实例也有很多的特征,那么就要计算出千上万个距离,运算量极大的,就需要一种快速的K近邻的搜索方法,提高搜索效率;一般考虑使用特殊的结构存储训练数据,以减少计算距离的次数。KD树就是一种这样的数据结构。1.KD树的概念
KD树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树型数据结构。
本质:二叉树,表示对k维空间的一个划分
构造过程:不断地用垂直于坐标轴的超平面将k维空间切分,形成k维超矩形区域
kd树的每个节点对应于一个K维超矩形区域
注意:KD树这里的K代表的是数据的特征维度,而k近邻中的k指的是距离新实例点最近的k个邻居。
最优切割特征选择的原则是什么?
要让数据划分成两部分之后,系统整体的信息熵降低。
𝒍 = 𝒋 𝒎𝒐𝒅 𝒌 + 𝟏怎么理解?问题暂留
绘制KD树
参考文献
[1]孙立东,吉孟宇.基于K近邻算法的平面结构变形场实时测量方法[J/OL].应用科技:1-7[-12-22].
[2]李航著.统计学习方法.北京:清华大学出版社.
如果觉得《机器学习 K近邻之KD树基本概念 绘制KD树》对你有帮助,请点赞、收藏,并留下你的观点哦!