Home > Mateda2.0 > learning > CreateTreeStructure.m

# CreateTreeStructure

## PURPOSE

[Cliques] = CreateTreeStructure(MI)

## SYNOPSIS

function [Cliques] = CreateTreeStructure(MI)

## DESCRIPTION

     [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)

## CROSS-REFERENCE INFORMATION

This function calls:

This function is called by:

- LearnTreeModel [model] = LearnTreeModel(k,NumbVar,Card,SelPop,AuxFunVal,learning_params)

## SOURCE CODE

    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