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

以下是使用MATLAB实现基于KD树数据结构的K近邻算法的详细代码： ```matlab 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 ``` 使用方法示例： ```matlab % 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树数据结构，代码如下： ```matlab 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 ```