机器学习 KD树生成(matlab实现)_kd树matlab简单实现

一、思路

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

二、效果

三、代码

1、mian

%% 数据导入
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);
1
2
3
4
5
6
7
8
9
10
11
12
13

2、Kd_Tree_Create

function [] = Kd_Tree_Create(Dataset)
%Dataset共有rows行数据,1:columns-1列为属性,columns列为类别
size_Dataset=size(Dataset);
recursive(Dataset,1,1,size_Dataset(1),size_Dataset(2)-1);
end
1
2
3
4
5

3、recursive

function [] = recursive(Dataset,pos,x_i,rows,columns)
disp("kd树深度:"+x_i);
%Dataset:需要二分的数据集
%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)+1;%加1去掉也不影响
    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);
else
    if(rows==1)
        Kd_Tree(pos,1:columns+1)=Dataset;
        Kd_Tree(pos,columns+2)=1;
    else
        Kd_Tree(pos,columns+2)=0;
    end
end

end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28