Exact Algorithms: Clustering algorithm

From DSL

Clustering algorithm is the fastest known exact algorithm for belief updating in Bayesian networks. It was originally proposed by Lauritzen and Spiegelhalter (1988) and improved by several researchers, e.g., Jensen et al.(1990) or Dawid (1992).

The clustering algorithm works in two phases: (1) compilation of a directed graph into a junction tree, and (2) probability updating in the junction tree. It has been a common practice to compile a network and then perform all operations in the compiled version. Our research in relevance reasoning (Lin & Druzdzel 1997, 1998) has challenged this practice and has shown that it may be advantageous to preprocess the network before transferring it into a junction tree. Genie does not include the compilation phase in its user interface, something that we believe might have been confusing for users.

The clustering algorithm is GeNIe default algorithm and should be sufficient for most applications. Only when networks become very large and complex, the clustering algorithm may not be fast enough. In that case, it is suggested that the user choose an approximate algorithm, such as one of the stochastic sampling algorithms.