[R] mapping functions down trees/ AIC for trees

Kevin Murphy murphyk at cs.berkeley.edu
Wed Jul 25 00:11:31 CEST 2001

Has anyone implemented AIC for trees? I realise that the tree growing
procedure does variable selection automatically - my goal is to learn
belief net structure where the local conditional probability
distributions (CPDs) are represented by trees (as in  e.g., Nir
Friedman, 1996 - ref below). For this, I need to properly penalize each
CPD. This is my current implementation for the tree class (I have
similar code for the rpart class - I am assuming this is a
classification tree for now.)

logLik.tree <- function(tr) {
  k <- length(attr(tr, "ylevels"))
  nparams.leaves  <- (k-1)*num.leaves(tr)
      # specify the params of the multinomials at the leaves
  nparams.struct <- 0   # ignore params needed to specify splits
  df <- nparams.leaves + nparams.struct # degrees of freedom
  structure(-2*deviance(tr), df=df, class="logLik")

num.leaves.tree <- function(tr) sum(as.numeric(tr$frame$var ==
num.leaves <- function(tr) UseMethod("num.leaves")

To compute the num. parameters used to specify the tree structure, one
can use the recursive encoding proposed by Quinlan and Rivest. To do
this, I need a way to map a function down a tree and to return a list of
the values.
I could then write something like

n <- num.inputs(tr)
f <- function(x) {
  if (is.leaf(x)) 1
  else 1 + log2(n-depth(x)) + sum(tree.apply(f, children(x)))
nparams.struct <- tree.apply(f, tr)

How can I implement tree.apply, children, is.leaf and depth?


  author = "N. Friedman and M. Goldszmidt",
  title = "Learning {B}ayesian Networks with Local Structure",
  booktitle = uai,
  year = 1996
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-help-request at stat.math.ethz.ch

More information about the R-help mailing list