tsrchbbt.m

来自「一个关于数据聚类和模式识别的程序,在生物化学,化学中因该都可以用到.希望对大家有」· M 代码 · 共 50 行

close all
clear all

data = rand(1000,2);		% Generate data
clusterNum = 3;		% No. of children for each tree node
levelNum = 4;		% No. of levels of the BB tree
mytree = genBBT(data, clusterNum, levelNum);	% Generate a search tree
testNum = 500;
testVec = rand(testNum, size(data,2));	% Each row is a test points
k = 1;

fprintf('Data size = %g\n', size(data,1));
fprintf('Data dimension = %g\n', size(data,2));
fprintf('No. of tree nodes = %g\n', length(mytree));
fprintf('No. of test points = %g\n', testNum);

evalcount = zeros(testNum, 1);
nnindex1 = zeros(testNum, k);
nnindex2 = zeros(testNum, k);
nndist1 = zeros(testNum, k);
nndist2 = zeros(testNum, k);

% Compute KNN via exhaustive method
tic;
for i = 1:testNum,
	dist = vecdist(testVec(i,:), data);
	[a, b] = sort(dist);
	nnindex1(i, :) = b(1:k);
	nndist1(i, :) = a(1:k);
end
t1 = toc;

% Compute KNN via branch-and-bound tree
tic;
for i = 1:testNum,
	[nnindex2(i,:), nndist2(i,:), evalcount(i)] = srchBBT(testVec(i,:), mytree, data');
end
t2 = toc;

fprintf('Max. dist. comp. count = %g\n', max(evalcount));
fprintf('Min. dist. comp. count = %g\n', min(evalcount));
fprintf('Ave. dist. comp. count = %g\n', mean(evalcount));
fprintf('Total search time for brutal-force search = %g seconds ', t1);
fprintf('(Average time = %g seconds)\n', t1/testNum);
fprintf('Total search time for BB-tree search = %g seconds ', t2);
fprintf('(Average time = %g seconds)\n', t2/testNum);
fprintf('Speedup factor = %g\n', t1/t2);
fprintf('Index difference = %g\n', max(abs(nnindex1(:)-nnindex2(:))));
fprintf('Dist. difference = %g\n', max(abs(nndist1(:)-nndist2(:))));