机器学习 kd树-ag凯发k8国际

文章目录

• 思路
• 效果
• 待优化
• 代码
• • mian
  • kd_tree_create
  • recursive
  • kd_tree_search
  • kd_tree_recall_search

第一个版本：链接

kd树基本思路：
建立kd树(kd_tree_create)
递归搜索：回溯搜索的起点, 建立回溯栈(kd_tree_search)

回溯搜索：从起点向着根节点回溯(kd_tree_recall_search)

设
测试节点：test_x
当前最优节点：predicted_x_point
当前最短距离：predicted_x_distance
当前回溯节点：cuurent_point
测试节点与当前节点距离：dis_current_test
回溯规则：
若dis_current_test >= predicted_x_distance，说明当前节点并非当前最优节点
再判断以测试节点为球心形成的超球是否与当前节点形成的超面相交
若未相交且回溯栈非空
向上回溯(回溯栈顶弹出元素)
若相交
需向下遍历当前节点，寻找最优节点
若dis_current_test < predicted_x_distance，说明当前节点为当前最优节点
更新当前最优节点与当前最短距离
再判断以测试节点为球心形成的超球是否与当前节点形成的超面相交(此时一般来说都会相交, 因为当前最优节点处于超面)
若未相交且回溯栈非空
向上回溯(回溯栈顶弹出元素)
若相交
需向下遍历当前节点，寻找最优节点

1、当前代码仅实现向上回溯，超球与超面相交需向下遍历这一步被略去(因为目前我也没想到怎么去写)

mian

clear all; clc; %% 数据导入 dataset=csvread("iris_dataset.csv"); rows=150; columns=5;%% 数据分割 train_set=dataset(1:120,:); test_set=dataset(121:150,:);%% kd树生成 %1:columns列为属性和类别, columns 1列节点存活状态 global kd_tree; kd_tree_create(train_set); size_kd_tree=size(kd_tree);%% 方法1 递归搜索 测试 %{ global stack_point; scores=0; for i=1:30test_x=test_set(i,1:columns-1);kd_tree_search(1,size_kd_tree(1),columns-1,1,test_x);if (kd_tree(stack_point(1),columns)==test_set(i,columns))scores=scores 1;endstack_point=[]; end disp("递归搜索准确率:" scores/30); %} %% 方法2 递归 & 回溯搜索 测试global stack_point; global x_i_array; global predicted_x_point; global predicted_x_distance;scores=0; for i=1:30test_x=test_set(i,1:columns-1);kd_tree_search(1,size_kd_tree(1),columns-1,1,test_x);predicted_x_point=stack_point(1);predicted_x_distance=distant(kd_tree(predicted_x_point,1:columns-1),test_x);kd_tree_recall_search(stack_point(1),x_i_array(1),columns,test_x);if (kd_tree(predicted_x_point,columns)==test_set(i,columns))scores=scores 1;endstack_point=[];x_i_array=[]; end disp("递归 & 回溯搜索准确率:" scores/30);%% 方法3 递归 & 回溯 & 超球越界 搜索 测试

kd_tree_create

function [] = kd_tree_create(dataset) %二叉树数据结构在c语言中容易表示,可在matlab中却不那么容易 %但是c语言需要自己造轮子(sortrows()用c得写死我), matlab有现成的, 所以思考一下如何在matlab中表示二叉树呢 %参考大堆小堆利用数组表示二叉树, 从而避开指针构建kdtree(哇噢, 感觉自己就是个小机灵鬼诶) %给每个节点添加下标以实现父子访问 %提示:节点下标为i, 左孩子下标为2*i,左孩子下标为2*i 1 %因为kdtree不是完全二叉树, 所以需要增加状态信息栏表示某节点是否为空 %好了, 开整吧�taset共有rows行数据,1:columns-1列为属性,columns列为类别 size_dataset=size(dataset); recursive(dataset,1,1,size_dataset(1),size_dataset(2)-1); end

recursive

function [] = recursive(dataset,pos,x_i,rows,columns) �taset:需要二分的数据集 %rows:需分类的个体数 %columns:用于分类的属性数 %pos:kd_tree插入位置 %x_i:排序依据 global kd_tree; if(rows>1)%排序dataset=sortrows(dataset,mod(x_i-1,columns) 1);%二分divi_index=fix(rows/2);kd_tree(pos,1:columns 1)=dataset(divi_index 1,:);kd_tree(pos,columns 2)=1;%递归recursive(dataset(1:divi_index,:),2*pos,x_i 1,divi_index,columns);recursive(dataset(divi_index 2:rows,:),2*pos 1,x_i 1,rows-divi_index-1,columns); elseif(rows==1)kd_tree(pos,1:columns 1)=dataset;kd_tree(pos,columns 2)=1;elsekd_tree(pos,columns 2)=0;end endend

kd_tree_search

function [] = kd_tree_search(current_point,rows,x_dim,i_x,test_x) global kd_tree; global stack_point; stack_point=[current_point stack_point]; if(kd_tree(current_point,i_x)<=test_x(1,i_x))%进入右子节点if(2*current_point 1<=rows && kd_tree(2*current_point 1,x_dim 2)==1)kd_tree_search(2*current_point 1,rows,x_dim,mod(i_x,x_dim) 1,test_x)else%父与右子之间 && 右子为空end else%进入左子节点if(2*current_point<=rows && kd_tree(2*current_point,x_dim 2)==1)kd_tree_search(2*current_point,rows,x_dim,mod(i_x,x_dim) 1,test_x)else%父与左子之间 && 左子为空end endend

kd_tree_recall_search

function []= kd_tree_recall_search(current_x_point,x_i,columns,test_x) global kd_tree; global stack_point; global x_i_array; global predicted_x_point; global predicted_x_distance;size_stack_point=size(stack_point); size_x_i_array=size(x_i_array);stack_point=stack_point(1,2: size_stack_point(2));%待回溯节点 x_i_array=x_i_array(1,2: size_x_i_array(2));%待回溯节点所在x_idis_current_predicted=distant(kd_tree(current_x_point,1:columns-1),test_x); if(dis_current_predicted >= predicted_x_distance)%当前current距离 >= 最优predicted_x距离if(size_stack_point(2)>1)%未回溯到根节点kd_tree_recall_search(stack_point(1),x_i_array(1),columns,test_x);end%t1= (test(1,x_i) predicted_x_distance)-kd_tree(current_x_point,x_i);%t2= (test(1,x_i)-predicted_x_distance)-kd_tree(current_x_point,x_i);%if(t1*t2 > 0 && size_stack_point>1)%与当前节点所在超面无交点 && 未回溯到根节点%kd_tree_recall_search(stack_point(1),x_i_array(1),columns,test_x);%else% 与当前节点所在超面有交点%遍历current的另一子树%end else %当前current距离 < 最优predicted_x距离if(size_stack_point(2)>1)% 未回溯到根节点predicted_x_point=current_x_point;predicted_x_distance=distant(kd_tree(predicted_x_point,1:columns-1),test_x);%遍历current的另一子树kd_tree_recall_search(stack_point(1),x_i_array(1),columns,test_x);end end end

总结

以上是ag凯发k8国际为你收集整理的机器学习 kd树_递归_回溯_搜索(matlab实现)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。