function tree(objectorder,heights)
%TREE creates a tree in which the leaves represent
% objects. The vertical coordinate of the junction
% of two branches is the dissimilarity between the
% corresponding clusters (maximal 30 objects allowed).
%
% The algorithm is fully described in:
% Kaufman, L. and Rousseeuw, P.J. (1990),
% "Finding groups in data: An introduction to cluster analysis",
% Wiley-Interscience: New York (Series in Applied Probability and
% Statistics), ISBN 0-471-87876-6.
%
% Required input arguments:
% objectorder : order of objects
% heights : diameter of cluster before dividing it
% (=length of banner)
%
% I/O:
% tree(objectorder,heights)
%
% Example (subtracted from the referenced book)
% load agricul.mat
% result = diana(agricul,[4 4],0,0,1);
% tree(result.objectorder,result.heights)
%
% The output of TREE is a figure containing the
% agglomerative (agnes) or divise (diana) tree.
%
% This function is part of LIBRA: the Matlab Library for Robust Analysis,
% available at:
% http://wis.kuleuven.be/stat/robust.html
%
% Written by Wai Yan Kong (May 2006)
% Last Revision: 28/09/2006
clf reset
whitebg([1 1 1]);
if (nargin<2)
error('Two input arguments required')
elseif (nargin>2)
error('Too many input arguments')
end
if(size(objectorder,2)~=size(heights,2)+1)
error('Missing values in objectorder or heights')
end
Heights=H(heights);
number=size(objectorder,2);
if (number>30)
error('Only 30 objects allowed')
end
%midden=[];
middle(1)=0;
Maxi=0;
Mini=0;
PrevMID=middle(1);
lengt=[]; %length
high=[]; %height
indices=[];
L=[];
[maxim,index]=max(Heights);
if(1<=index-1)
[Prevmax,Previndex]=max(Heights(1:(index-1)));
else
Prevmax=maxim;
Previndex=index;
end
if(index+1<=number-1)
[Postmax,Postindex]=max(Heights((index+1):(number-1)));
Postindex=Postindex+index+1-1;
else
Postmax=maxim;
Postindex=index;
end
if(Postindex+1<=number-1)
[Post2max,Post2index]=max(Heights(Postindex+1:number-1));
Post2index=Post2index+Postindex+1-1;
else
Post2max=Postmax;
Post2index=Postindex;
end
if(Postindex+1<=Post2index-1)
[Betweenmax,Betweenindex]=max(Heights(index+1:Postindex-1));
Betweenindex=Betweenindex+index+1-1;
else
Betweenmax=Postmax;
Betweenindex=Postindex;
end
L=cat(2,L,maxim);
high=cat(2,high,[Post2max,Postmax,Betweenmax,maxim,Prevmax]);
indices=cat(2,indices,[Post2index,Postindex,Betweenindex,index,Previndex]);
M=0;
extra=number/2;
lengt(1)=Postindex-Previndex+extra+2;
PrevLEN=lengt(1);
rectangle('Position',[middle(1)-(lengt(1)/2),maxim,lengt(1),0.0001]);
NbanFirst=1;
k=1;
branch=0;
over=0;
Element=0;
Special=0;
Spec=0;
Sp=0;
S=0;
ww=0;
if(maxim<20)
extrawaystick=0.8;
extrawaytext=1.5;
else
extrawaytext=0;
extrawaystick=0;
end
right=0;
direct11=0;
direct111=0;
righttree=0;
if(index==1)
direct1=1;
else
direct1=0;
end
Last=size(lengt,2);
LastM=size(middle,2);
LastL=size(lengt,2);
while(k<=number)
w=0;
LastH=size(high,2);
if((high(LastH)~=high(LastH-1)) & Element==0)
while(branch==0)
S=0;
w=w+1;
ww=ww+1;
if(over==0)
middle=cat(2,middle,middle(LastM)-(lengt(LastL)/2));
end
if(righttree==1)
middle=cat(2,middle,middle(LastM)-(lengt(LastL)/2));
righttree=0;
end
if(Sp==1)
LastM=size(middle,2);
LastL=size(lengt,2);
middle(LastM)=middle(LastM)+lengt(LastL)/2;
Sp=0;
S=1;
end
LastM=size(middle,2);
Output=maxim-Prevmax;
rectangle('Position',[middle(LastM),Prevmax,0.0001,Output]);
if(Betweenmax==Postmax | over==0)
Post2max=Postmax;
Post2index=Postindex;
end
if((Betweenmax==Postmax | over==0) & (right~=1 | over==0))
Postmax=maxim;
Postindex=index;
end
maxim=Prevmax;
index=Previndex;
if(NbanFirst<=(index-1))
[Prevmax,Previndex]=max(Heights(NbanFirst:(index-1)));
Previndex=Previndex+NbanFirst-1;
else
Prevmax=maxim;
Previndex=index;
end
if(index+1<=Postindex-1)
[Betweenmax,Betweenindex]=max(Heights(index+1:Postindex-1));
Betweenindex=Betweenindex+index+1-1;
else
Betweenmax=Postmax;
Betweenindex=Postindex;
end
if(right==1 & over~=0)
high=cat(2,high,[Prevmax Prevmax]);
indices=cat(2,indices,[Previndex Previndex]);
else
high=cat(2,high,Prevmax);
indices=cat(2,indices,Previndex);
end
if(Postindex-Previndex<=0)
lengt=cat(2,lengt,1);
else
if(Postindex-Previndex-direct111>0)
if(ww==1)
lengt=cat(2,lengt,Postindex-Previndex-direct111+2);
else
lengt=cat(2,lengt,Postindex-Previndex-direct111);
end
else
if(ww==1)
lengt=cat(2,lengt,Postindex-Previndex+2);
else
lengt=cat(2,lengt,Postindex-Previndex);
end
end
end
L=cat(2,L,maxim);
if(direct111~=0)
direct111=0;
end
LastH=size(high,2);
LastL=size(lengt,2);
LastM=size(middle,2);
rectangle('Position',[middle(LastM)-(lengt(LastL)/2),maxim,lengt(LastL),0.0001]);
if(over~=0)
over=0;
end
if(right~=0)
right=0;
end
if(NbanFirst==index)
branch=1;
end
end
rectangle('Position',[middle(LastM)-(lengt(LastL)/2),maxim-1+extrawaystick,0.0001,1-extrawaystick]);
if(objectorder(k)>10)
text(middle(LastM)-(lengt(LastL)/2)-0.25,maxim-2.0+extrawaytext,num2str(double(objectorder(k))));
T=middle(LastM)-(lengt(LastL)/2-0.25);
else
text(middle(LastM)-(lengt(LastL)/2)-0.1,maxim-2.0+extrawaytext,num2str(double(objectorder(k))));
T=middle(LastM)-(lengt(LastL)/2-0.1);
end
Maxi=max(Maxi,T);
Mini=min(Mini,T);
if(Betweenmax~=Postmax)
high=high(1:LastH-2);
indices=indices(1:LastH-2);
Prevmax=Betweenmax;
Previndex=Betweenindex;
high=cat(2,high,Prevmax);
indices=cat(2,indices,Previndex);
LastH=size(high,2);
LastL=size(lengt,2);
middle(LastM)=middle(LastM)+lengt(LastL)/2;
over=1;
end
direct1=0;
Special=0;
Spec=0;
else
if(Special==1)
Special=0;
Spec=1;
end
if(Sp==1)
Sp=0;
end
if(S==1)
S=2;
end
direct111=0;
LastH=size(high,2);
LastM=size(middle,2);
LastL=size(lengt,2);
if(direct1==0)
rectangle('Position',[middle(LastM)+(lengt(LastL)/2),high(LastH)-1+extrawaystick,0.0001,1-extrawaystick]);
text(middle(LastM)+lengt(LastL)/2-0.1,high(LastH)-2.0+extrawaytext,num2str(double(objectorder(k))));
T=middle(LastM)+lengt(LastL)/2-0.1;
Maxi=max(Maxi,T);
Mini=min(Mini,T);
else
rectangle('Position',[middle(LastM)-(lengt(LastL)/2),high(LastH)-1+extrawaystick,0.0001,1-extrawaystick]);
text(middle(LastM)-lengt(LastL)/2-0.1,high(LastH)-2.0+extrawaytext,num2str(double(objectorder(k))));
T=middle(LastM)-lengt(LastL)/2-0.1;
Maxi=max(Maxi,T);
Mini=min(Mini,T);
direct1=0;
direct11=1;
end
if(high(LastH-1)==high(LastH))
high=high(1:LastH-2);
indices=indices(1:LastH-2);
else
high=high(1:LastH-1);
indices=indices(1:LastH-1);
end
LastH=size(high,2);
maxim=high(LastH);
index=indices(LastH);
if(LastH-1>=1)
Postmax=high(LastH-1);
Postindex=indices(LastH-1);
end
if(LastH-2>=1)
Post2max=high(LastH-2);
Post2index=indices(LastH-2);
end
if(index+1<=Postindex-1)
[Betweenmax,Betweenindex]=max(Heights(index+1:Postindex-1));
Betweenindex=Betweenindex+index+1-1;
else
Betweenmax=Postmax;
Betweenindex=Postindex;
end
if(Betweenmax~=Postmax)
Prevmax=Betweenmax;
Previndex=Betweenindex;
else
Prevmax=maxim;
Previndex=index;
end
if(high(LastH)>high(LastH-1))
righttree=1;
end
high(LastH)=Prevmax;
indices(LastH)=Previndex;
LastM=size(middle,2);
LastL=size(lengt,2);
Last=size(L,2);
if(LastM-1>=1)
middle=middle(1:LastM-1);
end
if(LastL-1>=1)
lengt=lengt(1:LastL-1);
end
if(Last-1>=1)
L=L(1:Last-1);
end
LastM=size(middle,2);
LastL=size(lengt,2);
Last=size(L,2);
if(Last>0)
while(maxim>L(Last))
lengt=lengt(1:Last-1);
L=L(1:Last-1);
Last=size(L,2);
end
end
LastL=size(lengt,2);
middle(LastM)=middle(LastM)+(lengt(LastL)/2);
if(Betweenmax~=Postmax)
Element=0;
else
Element=1;
middle(LastM)=middle(LastM)-(lengt(LastL)/2);
end
if(righttree==1 | direct11==1)
if(Spec==1)
Sp=1;
end
PrevMAX=L(1);
[maxim,index]=max(Heights(NbanFirst+1:number-1));
index=index+NbanFirst+1-1;
if(NbanFirst+1<=index-1)
[Prevmax,Previndex]=max(Heights(NbanFirst+1:index-1));
Previndex=Previndex+NbanFirst+1-1;
else
Prevmax=maxim;
Previndex=index;
end
if(index+1<=number-1)
[Postmax,Postindex]=max(Heights(index+1:number-1));
Postindex=Postindex+index+1-1;
else
Postmax=maxim;
Postindex=index;
end
if(index+1<=Postindex-1)
[Betweenmax,Betweenindex]=max(Heights(index+1:Postindex-1));
Betweenindex=Betweenindex+index+1-1;
else
Betweenmax=Postmax;
Betweenindex=Postindex;
end
if(Postindex+1<=number-1)
[Post2max,Post2index]=max(Heights(Postindex+1:number-1));
Post2index=Post2index+Postindex+1-1;
else
Post2max=Postmax;
Post2index=Postindex;
end
rectangle('Position',[PrevMID+(PrevLEN/2),maxim,0.0001,PrevMAX-maxim]);
LastM=size(middle,2);
LastMID=PrevMID+(PrevLEN/2);
PrevMID=LastMID;
middle=[];
middle(1)=LastMID;
LastM=size(middle,2);
high=[];
indices=[];
high=cat(2,high,[Post2max,Postmax,Betweenmax,maxim,Prevmax]);
indices=cat(2,indices,[Post2index,Postindex,Betweenindex,index,Previndex]);
LastH=size(high,2);
L=[];
L=cat(2,L,maxim);
Last=size(L,2);
lengt=[];
if(Postindex>Previndex)
if(M<extra)
M=M+1;
end
lengt(1)=Postindex-Previndex+(extra-M);
rectangle('Position',[LastMID-lengt(1)/2,maxim,lengt(1),0.0001]);
direct1=1;
elseif(Postindex<=Previndex & Betweenmax==Postmax)
lengt(1)=1;
rectangle('Position',[LastMID-1/2,maxim,1,0.0001]);
%%%%%%%
rectangle('Position',[LastMID-1/2,maxim-1+extrawaystick,0.0001,1-extrawaystick]);
if(objectorder(k+1)>10)
text(LastMID-1/2-0.25,maxim-2.0+extrawaytext,num2str(double(objectorder(k+1))));
Mini=min(Mini,LastMID-1/2-0.25);
else
text(LastMID-1/2-0.1,maxim-2.0+extrawaytext,num2str(double(objectorder(k+1))));
Mini=min(Mini,LastMID-1/2-0.1);
end
rectangle('Position',[LastMID+1/2,maxim-1+extrawaystick,0.0001,1-extrawaystick]);
text(LastMID+1/2-0.1,maxim-2.0+extrawaytext,num2str(double(objectorder(k+2))));
Maxi=max(Maxi,LastMID+1/2-0.1);
k=k+2;
end
PrevLEN=lengt(1);
LastL=size(lengt,2);
if(Element==1)
Element=0;
end
if(direct11==1)
if(NbanFirst+1<index)
middle=cat(2,middle,middle(LastM)-lengt(LastL)/2);
LastM=size(middle,2);
direct111=1;
over=1;
end
direct11=0;
end
Special=1;
PrevMAX=maxim;
end
if(S==2 && k+1==number)
rectangle('Position',[LastMID+lengt(1)/2,PrevMAX-1+extrawaystick,0.0001,1-extrawaystick]);
text(LastMID+lengt(1)/2-0.1,PrevMAX-2.0+extrawaytext,num2str(double(objectorder(k+1))));
Maxi=max(Maxi,LastMID+lengt(1)/2-0.1);
Mini=min(Mini,LastMID+lengt(1)/2-0.1);
k=k+1;
end
over=1;
end
branch=0;
k=k+1;
NbanFirst=NbanFirst+1;
end
axis([Mini-1,Maxi+1,min(Heights)-5,max(Heights)+1]);
XT=[];
set(gca,'XTick',XT);
set(gca,'XTickLabel',[]);
%---
function res=H(vector)
lengt=size(vector,2);
Nvector=vector;
i=1;
for i=1:lengt
for j=i+1:lengt
if (vector(i)==vector(j))
Nvector(j)=vector(j)+i*0.0001;
i=i+1;
end
end
end
res=Nvector;