文章目錄

• 思路
• 效果
• 待優化
• 代碼
• • 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不是完全二叉樹, 所以需要增加狀態信息欄表示某節點是否為空 %好了, 開整吧%Dataset共有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) %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);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

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。