做网站要学会什么语言,国外网页设计,主机一键wordpress,教育平台oss做视频网站1 KD树的问题
算法笔记#xff1a;KD树_UQI-LIUWJ的博客-CSDN博客
在kd树中#xff0c;导致性能下降的最核心因素是因为kd-tree中被分割的子空间是一个个的超方体#xff0c;而求最近邻时使用的是欧式距离#xff08;超球#xff09;。超方体与超球体相交的可能性是极高…1 KD树的问题
算法笔记KD树_UQI-LIUWJ的博客-CSDN博客
在kd树中导致性能下降的最核心因素是因为kd-tree中被分割的子空间是一个个的超方体而求最近邻时使用的是欧式距离超球。超方体与超球体相交的可能性是极高的如上图所示凡是相交的子空间都需要进行检查大大的降低运行效率
2 球树
如果划分区域也是超球体则相交的概率大大降低——ball-tree通过超球体划分空间去掉棱角划分超球体和搜索超球体相交的概率大大降低 特别在数据维度很高时算法效率得到大大提升 3 构建球树
def fit_ball_tree:input: x 数据点output: node构造好的ball tree的根节点if 只有一个数据点:创建一个叶子结点node包含这一单一的点node.pivot x[0]node.son1 Nonenode.son2 Nonenode.radius 0 #球树半径return nodeelse:让c为最宽的维度让p1,p2为该维度最两端的点让p为这个维度的中心点 (p1p2)/2让radius为p到x上最远点的距离让xl为左集合(距离p1更近的所有点)让xr为右集合(距离p2更近的所有点)创建带有两个孩子的nodenode.pivot pnode.label Nonenode.son1 fit_balltree(xl)node.son2 fit_balltree(xr)node.radius radiusreturn node4 球树K近邻搜索 def ball_tree_searchglobal:Q, 缓存k个最近邻点初始时包含一个无穷远点q, 与Q对应保存Q中各点与测试点的距离input: k, 寻找k个最近邻t, 测试点node, 当前节点output: 无三角不等式若测试点到当前球的最近距离大于到Q中最远点的距离则当前球中不可能包含待搜索的近邻点if distance(t, node.pivot) - node.radius ≥ max(q)returnif node为叶节点将node.pivot添加到Q并同步更新q若Q内超过k个近邻点则移出与测试点距离最远的那个点并同步更新qelse:递归搜索当前节点的左儿子和右儿子ball_tree_search(k,t,node.son1)ball_tree_search(k,t,node.son2)参考内容KNN的核心算法kd-tree和ball-tree - 简书 (jianshu.com)
