increase_order1: Determine a (k + 1)'th order t-cherry tree from a k'th order...

In nvihrs14/tcherry: Learning the structure of tcherry trees

Description

Determine the structure of a (k + 1)'th order t-cherry tree from a k'th order t-cherry tree.

Usage

increase_order1(tch_cliq, data, ...)

increase_order2(tch_cliq, data, ...)

Arguments

tch_cliq	A list containing the cliques of the k'th order t-cherry tree.
data	The data the tree structure should be based on.
...	Additional arguments passed to MIk.

Details

The algorithms for constructing the (k + 1)'th order t-cherry tree from a k'th order t-cherry tree are greedy algorithms. increase_order1 attempts to maximize the sum of mutual information of the cliques and increase_order2 attempts to maximize the weight of the junction tree. increase_order2 is also a faster implementation and a faster alternative to creating a (k + 1)'th order t-cherry tree directly from data with k_tcherry_step. It is therefore recommended to use this one, and increase_order1 is primarily kept for historical reasons.

In increase_order1 the procedure is:

• Starting from the k'th order t-cherry tree, make a complete set of the (k + 1) variables with highest mutual information which satisfies that this only adds one edge to the original graph. Remove these (k + 1) variables from later consideration.

• Make a complete set of the (k + 1) variables with highest mutual information which satisfies that this only adds one edge to the graph and that k of the variables are in earlier created cliques of size (k + 1). Remove these (k + 1) variables from later consideration.

• Continue until all variables are in a clique of size (k + 1).

For increase_order2 the procedure is: Start with the k'th order t-cherry tree T_k and set T_(k + 1) = T_k. Choose the set of (k + 1) variables with highest mutual information which satisfies that making the set complete in T_(k + 1) adds only one edge. Let this set be the first cherry/clique and make it complete in T_(k + 1). Consider all possible new cherries of size (k + 1). A new cherry is possible if k of the variables are already in an existing cherry, and making the set complete only adds one edge in T_(k + 1). For each new cherry, calculate the weight

MI(clique) - MI(separator)

for the new clique and separator of the junction tree for the preliminary (k + 1)'th order t-cherry tree. Add the cherry with the highest weight to T_(k + 1). Repeat the procedure until T_(k + 1) is a (k + 1)'th order t-cherry tree.

Value

A list containing the following components:

• adj_matrix The adjacency matrix for the (k + 1)'th order t-cherry tree.

• weight Weight of the junction tree (only for increase_order2)

• cliques A list containing the cliques (cherries) of the (k + 1)'th order t-cherry tree.

• separators A list containing the separators of a junction tree for the (k + 1)'th order t-cherry tree.

• n_edges The number of edges in the resulting graph.

Author(s)

Katrine Kirkeby, [e-mail]

Maria Knudsen, [e-mail]

Ninna Vihrs, [e-mail]

See Also

MIk for mutual information of k variables.

Examples

set.seed(43)
var1 <- c(sample(c(1, 2), 100, replace = TRUE))
var2 <- var1 + c(sample(c(1, 2), 100, replace = TRUE))
var3 <- var1 + c(sample(c(0, 1), 100, replace = TRUE,
                        prob = c(0.9, 0.1)))
var4 <- c(sample(c(1, 2), 100, replace = TRUE))
var5 <- var2 + var3
var6 <- var1 - var4 + c(sample(c(1, 2), 100, replace = TRUE))
var7 <- c(sample(c(1, 2), 100, replace = TRUE))

data <- data.frame("var1" = as.character(var1),
                   "var2" = as.character(var2),
                   "var3" = as.character(var3),
                   "var4" = as.character(var4),
                   "var5" = as.character(var5),
                   "var6" = as.character(var6),
                   "var7" = as.character(var7))

ChowLiu_cliques <- list(c("var1", "var5"),
                        c("var2", "var5"),
                        c("var3", "var5"),
                        c("var3", "var7"),
                        c("var4", "var6"),
                        c("var5", "var6"))
                        
# smooth used in MIk
(tch <- increase_order1(ChowLiu_cliques, data, smooth = 0.1))
(tch2 <- increase_order2(ChowLiu_cliques, data, smooth = 0.1))

nvihrs14/tcherry documentation built on Aug. 1, 2020, 6:25 p.m.