CreateTreeStructure

 [Cliques] = CreateTreeStructure(MI)
 CreateTreeStructure: A maximum weighted tree is learned from the matrix of mutual information between the variables
 INPUTS
 MI: Matrix of mutual information
 OUTPUTS
    Cliques: Structure of the model in a list of cliques that defines the neighborhood 
    Each row of Cliques is a clique. The first value is the number of parents for variable i (1 in the case of a tree). 
    The second, is the number of new variables (one new variable, i).
    Then, parent variables are listed and  finally new variables (variable i) are listed

 Last version 5/6/2009. Roberto Santana (roberto.santana@ehu.es)

0001 function [Cliques] = CreateTreeStructure(MI)
0002 % [Cliques] = CreateTreeStructure(MI)
0003 % CreateTreeStructure: A maximum weighted tree is learned from the matrix of mutual information between the variables
0004 % INPUTS
0005 % MI: Matrix of mutual information
0006 % OUTPUTS
0007 %    Cliques: Structure of the model in a list of cliques that defines the neighborhood
0008 %    Each row of Cliques is a clique. The first value is the number of parents for variable i (1 in the case of a tree).
0009 %    The second, is the number of new variables (one new variable, i).
0010 %    Then, parent variables are listed and  finally new variables (variable i) are listed
0011 %
0012 % Last version 5/6/2009. Roberto Santana (roberto.santana@ehu.es)
0013  
0014 threshold = 10^-4;
0015 
0016 NumbVar = size(MI,1);
0017 Cliques = zeros(NumbVar,4);
0018 shuffle = randperm(NumbVar); % This is used to  avoid bias when the mutual information  is the same for many couple of variables
0019 
0020 Cliques(:,2) =  1;  % In every clique only a new variable is added;
0021 Tree = [1:NumbVar]; % Index of the parent for every variable
0022 
0023 
0024 %root = shuffle(fix(rand*NumbVar)+1);  % The root of the tree is randomly selected
0025 
0026 [a,b] = find(MI==max(max(MI)));
0027 root = a(1); % The root corresponds to the link with highest mutual information
0028 
0029 Cliques(root,:) = [0,1,root,-1]; % The root has zero parents
0030 Tree(root) = -1; 
0031 
0032                         
0033     for i=1:NumbVar-1  
0034         maxval=-10;
0035         for j=1:NumbVar
0036          for k=1:NumbVar
0037              auxm = MI(shuffle(j),shuffle(k));
0038              if(Tree(shuffle(j))==shuffle(j) && Tree(shuffle(k))~=shuffle(k) && auxm>maxval)
0039                       maxsonindex = shuffle(j);
0040                       maxfatherindex = shuffle(k);
0041                       maxval=auxm;
0042              end
0043          end
0044         end 
0045         if (maxval > threshold)
0046          Tree(maxsonindex)=maxfatherindex;
0047          Cliques(maxsonindex,:) = [1,1,maxfatherindex,maxsonindex];
0048          Weight(maxsonindex) = maxval;
0049         else
0050           Tree(maxsonindex) = -1;
0051           Cliques(maxsonindex,:) = [0,1,maxsonindex,-1];
0052           Weight(maxsonindex) = 0;
0053         end 
0054     end
0055      
0056   return;
0057