java.lang.Object
de.uka.ipd.sdq.dsexplore.bayesnets.searchers.ChowLiuTree

public class ChowLiuTree extends Object
ChowLiuTree is another algorithm for searching the space of Bayesian networks quickly. It gives reasonable networks that model the data quite well in shorter time than other algorithms like Hill Climber etc. However, it only models Bayesian networks which have a tree structure.

Here is the algorithm : Calculate the mutual info. between all pairs of nodes in the network. Start with the pair of nodes having the highest mutual info value and add an (undirected) edge between them. Look for the next highest mutual info pair of nodes, and add an (undirected) edge between them iff adding the edge does not produce cycles in the network. Carry on the process till you can add no more edges. In the end, you get a Maximum Spanning Tree structure, which has all edges which are undirected. In order to make the network/graph directed, just choose a node at random in the structure, and assign directions to all edges in such a way that they go away from the chosen node.

  • Constructor Summary

    Constructors
    Constructor
    Description
    ChowLiuTree(int[][] Data)
    Constructor for the class.
  • Method Summary

    Modifier and Type
    Method
    Description
    static void
    main(String[] args)
     
    double
    mutualInfo(int Node1, int Node2)
    This method calculates the mutual information between a pair of nodes Node1 and Node2.
    int[][]
    This method searches the best bayesian networks in the search space using the chow liu algortihm.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • ChowLiuTree

      public ChowLiuTree(int[][] Data)
      Constructor for the class.
      Parameters:
      Data - - The matrix containing the data. Each row represents a data instance.
  • Method Details

    • main

      public static void main(String[] args)
    • search

      public int[][] search()
      This method searches the best bayesian networks in the search space using the chow liu algortihm. It returns the best Bayesian network (as an adjacency matrix) it has found over its search.
      Parameters:
      None -
      Returns:
      An Adjacency matrix of the best learnt Bayesian network.
    • mutualInfo

      public double mutualInfo(int Node1, int Node2)
      This method calculates the mutual information between a pair of nodes Node1 and Node2.
      Parameters:
      Node1 - - First node of the pair of nodes.
      Node2 - - Second node of the pair of nodes.
      Returns:
      The mutual information as a double.