k_tcherry_step: Determine a k'th order t-cherry tree from data

In nvihrs14/tcherry: Learning the structure of tcherry trees

Description

Determine the structure of a k'th order t-cherry tree from data based on a greedy stepwise approach.

Usage

k_tcherry_step(data, k, ...)

Arguments

data	The data the tree structure should be based on.
k	The order of the t-cherry tree.
...	Additional arguments passed to MIk.

Details

Notice that for k = 3 it is the same as using tcherry_step and for k = 2 it is the same as using ChowLiu.

The algorithm for constructing the t-cherry tree from data is based on an atempt to minimize the Kullback-Leibler divergence. The first cherry is chosen as the k variables with highest mutual information. This is the preliminary t-cherry tree. Then all possible new cherries are added stepwise to this tree and the weight

∑ MI(clique) - ∑ MI(separator)

is calculated. The first sum is over the cliques and the second over the separators of the junction tree of the preliminary t-cherry tree. The one with the highest weight is chosen as the new preliminary t-cherry tree, and the procedure is repeated untill all variables has 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))
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))

# smooth used in MIk
(tch <- k_tcherry_step(data, 3, smooth = 0.1))

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