使用MATLAB实现基于KD树数据结构的K近邻算法，并写出详细代码

以下是使用MATLAB实现基于KD树数据结构的K近邻算法的详细代码：

classdef KDTree
    % KDTree class for K-Nearest Neighbor search
    properties
        point           % point coordinates in the tree
        split_var       % split variable for this node
        split_val       % split value for this node
        left_child      % left child node
        right_child     % right child node
    end
    
    methods
        function obj = KDTree(point, split_var, split_val, left_child, right_child)
            % Constructor for KDTree class
            obj.point = point;
            obj.split_var = split_var;
            obj.split_val = split_val;
            obj.left_child = left_child;
            obj.right_child = right_child;
        end
        
        function [idx, dist] = knnsearch(obj, X, k)
            % K-Nearest Neighbor search function
            n = size(X, 1);
            idx = zeros(n, k);
            dist = zeros(n, k);
            for i = 1:n
                [idx(i,:), dist(i,:)] = obj.search_knn(X(i,:), k);
            end
        end
        
        function [idx, dist] = search_knn(obj, x, k)
            % K-Nearest Neighbor search recursive function
            if isempty(obj.left_child) && isempty(obj.right_child)
                idx = 1;
                dist = norm(obj.point - x);
                return;
            end
            
            if x(obj.split_var) < obj.split_val
                if isempty(obj.left_child)
                    child = obj.right_child;
                else
                    child = obj.left_child;
                end
            else
                if isempty(obj.right_child)
                    child = obj.left_child;
                else
                    child = obj.right_child;
                end
            end
            
            if isempty(child)
                idx = [];
                dist = [];
                return;
            end
            
            [idx_temp, dist_temp] = child.search_knn(x, k);
            
            if isempty(idx_temp)
                idx = [];
                dist = [];
                return;
            end
            
            % Add current node into the result if necessary
            idx = [1, idx_temp];
            dist = [norm(obj.point - x), dist_temp];
            [~, idx_sort] = sort(dist);
            idx = idx(idx_sort);
            dist = dist(idx_sort);
            idx = idx(1:min(k,length(idx)));
            dist = dist(1:min(k,length(dist)));
            
            % Check if we need to search the other child node
            if length(idx) < k || abs(x(obj.split_var) - obj.split_val) < dist(end)
                if x(obj.split_var) < obj.split_val
                    other_child = obj.right_child;
                else
                    other_child = obj.left_child;
                end
                
                if ~isempty(other_child)
                    [idx_temp, dist_temp] = other_child.search_knn(x, k);
                    
                    if ~isempty(idx_temp)
                        % Merge the results from both child nodes
                        idx = [idx, idx_temp];
                        dist = [dist, dist_temp];
                        [~, idx_sort] = sort(dist);
                        idx = idx(idx_sort);
                        dist = dist(idx_sort);
                        idx = idx(1:min(k,length(idx)));
                        dist = dist(1:min(k,length(dist)));
                    end
                end
            end
        end
    end
end

使用方法示例：

% Create a random dataset
X = rand(100,2);

% Build a KDTree from the dataset
tree = build_kdtree(X);

% Perform K-Nearest Neighbor search on a query point
x = [0.5, 0.5];
k = 5;
[idx, dist] = tree.knnsearch(x, k);

其中，`build_kdtree` 函数用于构建KD树数据结构，代码如下：

function root = build_kdtree(X)
    % Recursive function to build KDTree
    n = size(X, 1);
    if n == 1
        root = KDTree(X, 1, X(1,1), [], []);
        return;
    end
    
    [~, split_var] = max(var(X));
    split_val = median(X(:,split_var));
    left_idx = X(:,split_var) < split_val;
    right_idx = X(:,split_var) >= split_val;
    left_child = build_kdtree(X(left_idx,:));
    right_child = build_kdtree(X(right_idx,:));
    root = KDTree([], split_var, split_val, left_child, right_child);
end