aggclust.m

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

function level = aggclust(distance, method)
%aggClust: Hierarchical (agglomerative) clustering
%	Usage: level = aggclust(distance, method)
%		distance: 2D distance matrix of data points, with diagonal elements of "INF"
%		method: "single" for single-linkage, "complete" for complete-linkage
%		level: data structure for a hierarchical clustering result
%		level(i).distance: distance matrix at level i
%		level(i).height: the minimum distance measure to form level i 
%		level(i).merged: the two clusters (of level i-1) being merged to form level i 
%		level(i).cluster{j}: a vector denotes the data points in j-th cluster of level i 
%
%	Type "aggclust" to see a demo of a hierarchical clustering
%	(single-linkage) of 50 random patterns of dimensionality 2.
%
%	See also DENDRO, LINKCLU.

% Roger Jang, 19981027, 20080117

if nargin<1, selfdemo; return; end
if nargin<2, method = 'single'; end

dataNum = size(distance, 1);
level(1).distance = distance;
level(1).height = 0;
level(1).merged = [];
for i = 1:dataNum,
	level(1).cluster{i} = [i];
end

for i = 2:dataNum,
	level(i) = merge(level(i-1), method);
end

% ====== Merge clusters
function levelOutput = merge(level, method)
% MERGE Merge a level of n clusters into n-1 clusters

[minI, minJ, minValue] = minxy(level.distance);
if minI>minJ, temp=minI; minI=minJ; minJ=temp; end	% Reorder to have minI < minJ
levelOutput = level;
levelOutput.height = minValue;		% Update height
levelOutput.merged = [minI minJ];	% Update merged cluster
% Update cluster
levelOutput.cluster{minI} = [levelOutput.cluster{minI} levelOutput.cluster{minJ}];
levelOutput.cluster(minJ) = [];	% delete cluster{minJ}

% New distance matrix
distance2 = level.distance;
% "min" for single-linkage; "max" for complete-linkage
if strcmp(method, 'single'),
	distance2(:, minI) = min(distance2(:, minI), distance2(:, minJ)); 
	distance2(minI, :) = min(distance2(minI, :), distance2(minJ, :)); 
elseif strcmp(method, 'complete'),
	distance2(:, minI) = max(distance2(:, minI), distance2(:, minJ)); 
	distance2(minI, :) = max(distance2(minI, :), distance2(minJ, :)); 
else
	error(sprintf('Unsupported method in %s!', mfilename));
end

distance2(minJ, :) = [];
distance2(:, minJ) = [];
distance2(minI, minI) = inf;

levelOutput.distance = distance2;

% ====== Find the minimum value in a matrix
function [i, j, minValue] = minxy(A)
[valueRow, indexRow] = min(A);
[minValue, j] = min(valueRow);
i = indexRow(j);

% ====== Self demo ======
function selfdemo
dataNum = 50;
dimension = 2;
points = rand(dataNum, dimension);
for i = 1:dataNum,
	for j = 1:dataNum,
		distance(i, j) = norm(points(i,:)-points(j,:));
	end
end

% Diagonal elements should always be inf.
for i = 1:dataNum, distance(i, i) = inf; end

level = aggclust(distance);

% Plot heights w.r.t. levels
figure;
plot([level.height], 'r:o');
xlabel('Level');
ylabel('Height');
title('Height vs. level');

% Plot the dendrogram
figure;
dendro(level);

% View the formation of clusters
%figure;
%linkclu(points, distance, level);