成都建设企业网站,乔拓云h5制作,被网站管理员设置拦截,麻将app开发公司1 引入原因
K近邻算法需要在整个数据集中搜索和测试数据x最近的k个点#xff0c;如果一一计算#xff0c;然后再排序#xff0c;开销过大 引入KD树的作用就是对KNN搜索和排序的耗时进行改进
2 KD树
2.1 主体思路
以空间换时间#xff0c;利用训练样本集中的样本点…1 引入原因
K近邻算法需要在整个数据集中搜索和测试数据x最近的k个点如果一一计算然后再排序开销过大 引入KD树的作用就是对KNN搜索和排序的耗时进行改进
2 KD树
2.1 主体思路
以空间换时间利用训练样本集中的样本点沿各维度依次对k维空间进行划分建立二叉树利用分治思想提高算法搜索效率二分查找的算法复杂度是O(logN)KD树的搜索效率与之接近取决于所构造kd-tree是否接近平衡树 上图为为训练样本对空间的划分以及对应的kd树绿色实心五角星为测试样本通过kd-tree的搜索算法快速找到与其最近邻的3个训练样本点空心五角星标注的点 2.2 KD树的建立
2.2.1 以一个例子引入
比如我有6个点(2,3),(4,7),(5,4),(7,2),(8,1),(9,6)1) 数据有两个维度分别计算xy方向上数据的方差 x方向上的方差最大——先沿着X轴方向进行split注这一步也可以不要因为KD树适用的问题大多是维度小于20的所以按照维度顺序一个一个来也没有问题2根据x轴方向的值2,5,9,4,8,7排序选出中位数为7 x≤7的和x 7的被分开了 3) 被分开的左半区和右半区分别选出y轴方向的中位数偶数选小的那个 4左上方三个点再根据x轴分一刀其他三个区域已经各只剩一个点了 最终得到的KD树
2.2.2 伪代码
def kd_tree_construct:input: x: 训练样本集dim: 当前节点的分割维度子节点的分割维度(dim1)%样本的维度output: node: 构造好的kd tree的根节点if 只有一个数据点:创建一个叶子结点node包含这一单一的点node.point x[0]node.son1 Nonenode.son2 Nonereturn nodeelse:记dim维度上的中位点为x对x中的数据按dim维排序取中位点偶数个则取较小的那个记xl为左集合(dim维小于p点的所有点)记xr为右集合(dim维大于p点的所有点)创建带有两个孩子的nodenode.point pnode.son1 fit_kd_tree(xl)node.son2 fit_kd_tree(xr)return node
2.3 KD树上的最近邻查找 2.3.1 伪代码
def kd_tree_searchglobal:Q, 缓存k个最近邻点初始时包含一个无穷远点q, 与Q对应保存Q中各点与测试点的距离input: k, 寻找k个最近邻t, 测试点node, 当前节点一开始时根节点dim, 当前节点的分割维度子节点的分割维度(dim1)%数据点的维度output: 无if distance(t, node.point) max(q)将node.point添加到Q并同步更新q若Q内超过k个近邻点则移出与测试点距离最远的那个点并同步更新qif t[dim]-max(q) node.point[dim]:kd_tree_search(k,t,node.son1)if t[dim]max(q) node.point[dim]:kd_tree_search(k,t,node.son2)2.3.1 以一个例子开始
2.3.1.1 例子1
搜索(2.1,3.1)
记k1 第1步将(7,2)加入Q中maxq5.02更新Q 2.1-5.02≤7 搜索左儿子第2步将5.4)加入Q中maxq3.04更新Q 3.1-3.04≤4 搜索下儿子第3步将23加入Q中maxq0.1414更新Q 已经是叶子节点了结束3.1-3.04≥4 搜索上儿子第4步将47加入Q中maxq4.3380.1414,不更新Q仍为0.1414 已经是叶子节点了结束2.1-5.02≥7 搜索右儿子第5步将96加入Q中maxq7.4840.1414,不更新Q仍为0.14143.17.4846 搜索上儿子没有上儿子结束算法结束最近的点是(2,3),q0.1414
2.3.1.2 例子2 回溯时改变最近邻点
假设我们要查询的点是24.5
同样记k1 第1步将(7,2)加入Q中maxq5.59更新Q 2-5.59≤7 搜索左儿子第2步将5.4)加入Q中maxq3.04更新Q 4.5-3.04≤4 搜索下儿子第3步将23加入Q中maxq1.5更新Q4.53.04≥4 搜索上儿子第4步将47加入Q中maxq3.201.5,不更新Q仍为1.525.59 7 搜索右儿子第5步将(9,6)加入Q中maxq7.161.5,不更新Q仍为1.5 4.57.166 搜索上儿子没有上儿子结束算法结束最近的点是(2,3)距离为1.5 参考内容KNN的核心算法kd-tree和ball-tree - 简书 (jianshu.com)
k-d tree算法 - J_Outsider - 博客园 (cnblogs.com)
