文章目錄

• 思路
• 效果
• 代碼
• • mian
  • Kd_Tree_Create
  • recursive
  • Kd_Tree_Search

思路

第二個(gè)版本：鏈接

KD樹基本思路：
建立KD樹(Kd_Tree_Create)
遞歸搜索：回溯搜索的起點(diǎn)(Kd_Tree_Search)
回溯搜索：收斂到全局最近點(diǎn)(暫未實(shí)現(xiàn))

效果

僅用遞歸搜索效果如下：

代碼

mian

clear all; clc; %% 數(shù)據(jù)導(dǎo)入 Dataset=csvread("iris_dataset.csv"); rows=150; columns=5;%% 數(shù)據(jù)分割 Train_set=Dataset(1:120,:); Test_set=Dataset(121:150,:);%% kd樹生成 %1:columns列為屬性和類別, columns+1列節(jié)點(diǎn)存活狀態(tài) global Kd_Tree; Kd_Tree_Create(Train_set);%% 遞歸搜索 測(cè)試 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("遞歸搜索準(zhǔn)確率:"+scores/30);%% 遞歸 & 回溯搜索 測(cè)試

Kd_Tree_Create

function [] = Kd_Tree_Create(Dataset) %二叉樹數(shù)據(jù)結(jié)構(gòu)在c語(yǔ)言中容易表示,可在matlab中卻不那么容易 %但是c語(yǔ)言需要自己造輪子(sortrows()用c得寫死我), matlab有現(xiàn)成的, 所以思考一下如何在matlab中表示二叉樹呢 %參考大堆小堆利用數(shù)組表示二叉樹, 從而避開指針構(gòu)建kdtree(哇噢, 感覺自己就是個(gè)小機(jī)靈鬼誒) %給每個(gè)節(jié)點(diǎn)添加下標(biāo)以實(shí)現(xiàn)父子訪問 %提示:節(jié)點(diǎn)下標(biāo)為i, 左孩子下標(biāo)為2*i,左孩子下標(biāo)為2*i+1 %因?yàn)閗dtree不是完全二叉樹, 所以需要增加狀態(tài)信息欄表示某節(jié)點(diǎn)是否為空 %好了, 開整吧%Dataset共有rows行數(shù)據(jù),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) %Dataset:需要二分的數(shù)據(jù)集 %rows:需分類的個(gè)體數(shù) %columns:用于分類的屬性數(shù) %pos:Kd_Tree插入位置 %x_i:排序依據(jù) 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))%進(jìn)入右子節(jié)點(diǎn)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%進(jìn)入左子節(jié)點(diǎn)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

總結(jié)

以上是生活随笔為你收集整理的机器学习 KD树_递归搜索(matlab实现)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。