srchbbtknn.m

一个关于数据聚类和模式识别的程序,在生物化学,化学中因该都可以用到.希望对大家有用,谢谢支持

function [NNINDEX, NNDIST, DISTCOMPCOUNT] = srchbbtknn(vec, tree, alldata, k)
% BBTKNN Branch-and-bound tree search for k nearest neighbor

%	Roger Jang, 20000114

global NNINDEX		% Nearest neighbor index
global NNDIST		% Nearest neighbor distance
global DISTCOMPCOUNT	% No. of distance computation

NNINDEX = nan*ones(1, k);
NNDIST  = inf*ones(1, k);
DISTCOMPCOUNT = 0;

treesearch(vec, tree, 1, alldata);

% ====== Definition of treesearch() subfunction
function treesearch(vec, tree, index, alldata)
	global NNINDEX NNDIST DISTCOMPCOUNT
	% ====== According to rule 1
	if distance(vec, tree(index).mean) >= max(NNDIST)+tree(index).radius, 
	%	fprintf('Node %g is skipped.\n', index);
		return;
	end

	if ~isempty(tree(index).child),
		% ====== Recursion into the child nodes
		for i=tree(index).child,
			treesearch(vec, tree, i, alldata);
		end
	else
		% ====== Check each data item
		dataindex = tree(index).data;
		dist2mean = tree(index).dist2mean;
		for i = 1:length(dataindex),
			% ====== According to rule 2
			if distance(vec, tree(index).mean) < max(NNDIST)+dist2mean(i),
				temp = distance(vec, alldata(dataindex(i), :));
				if temp < max(NNDIST)	% Insert into NNDIST
					[NNINDEX, NNDIST] = insert(NNINDEX, NNDIST, dataindex(i), temp);
			
				end
				DISTCOMPCOUNT = DISTCOMPCOUNT + 1;
			end
		end
	end

% ====== Definition of distance() subfunction
function out = distance(vec1, vec2)
	out = norm(vec1-vec2);

% ====== Definition of insert() subfunction
function [nnindex, nndist] = insert(nnindex, nndist, index, dist);
%	Insert dist into nn dist, which is ordered increasingly
%	Also insert the index into nnindex accordingly.
%	dist must be smaller than max(nndist).
	index1 = find(nndist <= dist);
	index2 = 1:length(nndist);
	index2(index1) = [];
	nndist = [nndist(index1), dist, nndist(index2(1:end-1))];
	nnindex = [nnindex(index1), index, nnindex(index2(1:end-1))];