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

文章目录

• 思路
• 效果
• 代码
• • mian
  • kd_tree_create
  • recursive
  • kd_tree_search

第二个版本：链接

kd树基本思路：
建立kd树(kd_tree_create)
递归搜索：回溯搜索的起点(kd_tree_search)
回溯搜索：收敛到全局最近点(暂未实现)

仅用递归搜索效果如下：

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);%% 递归搜索 测试 global stack_point; size_kd_tree=size(kd_tree); 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);%% 递归 & 回溯搜索 测试

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

总结

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

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