# [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 ==
"<leaf>"))
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?

Kevin

@inproceedings{Friedman96,
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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

```