k_tcherry_p_lookahead: Determine a k'th order t-cherry tree from data by adding p...

In nvihrs14/tcherry: Learning the structure of tcherry trees

Description

Determine the structure of a k'th order t-cherry tree from data with realisations of n variables based on a greedy stepwise approach. In each step p new cliques are added.

Usage

k_tcherry_p_lookahead(data, k, p, ...)

Arguments

data	The data the tree structure should be based on.
k	The order of the t-cherry tree.
p	The number of new cliques considered in one step.
...	Additional arguments passed to MIk.

Details

Notice that for p = 1 it is the same as using k_tcherry_step and for p = n - (k - 1) it is the same as using tcherry_complete_search. Note that for p = 1 it is faster to use k_tcherry_step

The algorithm for constructing the t-cherry tree from data is based on an atempt to minimize the Kullback-Leibler divergence by maximizing the weight

∑ MI(clique) - ∑ MI(separator).

The first sum is over the cliques and the second over the separators of the junction tree of the t-cherry tree. In each step all possibilities of p new cliques are added to the preliminary tree. The one with the highest weight is chosen as the new preliminary t-cherry tree, and the procedure is repeated untill all variables have been added.

Value

A list containing the following components:

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

• weight The weight of the final k'th order t-cherry tree.

• cliques A list containing the cliques of the k'th order t-cherry tree.

• separators A list containing the separators of a junction tree for the k'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))

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

# smooth used in MIk
(tch <- k_tcherry_p_lookahead(data, k = 3, p = 2, smooth = 0.1))

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