Last modified: Tue Nov 29 14:53:10 EST 2005 by Dean Foster

Admistrivia

• What to do with all those clusters?
• If clusters are "natural kinds" then additive models of clusters make sense.
• Can add them to a regression (as indicator variables)
• Not all that interesting if only one set of clusters
• But, if there are many sets of clusters, additive models could generate interesting models.
• Alternatively, can use clusters in a tree.
• Suppose there are cluster types A,B,...,C
• Draw tree built out of these.
• Trees of natural kinds is motivation for:
  • CART
  • ID3
  • C4.5 / C5.0
  • MARS
  • Context trees

Trees

• Too expensive to run clustering at every step?
• If the natural kinds are clean enough, maybe only one variable would be enough.
• Motivation for CART
• Build tree using splits on each X variable

Forecasting with a tree

• fits is the average in the node
• Draw picture: Note it is kinda bumpy
• In leaf nodes, use average (This is the description for CART)
• In leaf node, use most popular value in classification (This is the idea for C4.5)

How many trees are there

• p choices for top. n split points. So np total top nodes.
• Each child node (there are 2) has basically same picture.
• If depth is d, there are 2^d nodes each with pn choices.
• If d = log(p), this is same size as all regression models

Need heuristic search

• Heuristic function: current fit
• So pick best fit at each split
• where "Best" is defined to be LS for example

Pruning trees

• As a forester (3nd generation) I know pruning trees is important
• Easy to consider lots of comparisions
• Allows seperation of searching from purning
• All one needs is a good fitting function
• See for example: ( Variable Length Markov Chains. P. Buhlmann and A.J. Wyner, The Annals of Statistics, Vol. 27, No. 2, pp. 480-513, 1999.)

Random forests

• Suppose truth is additive model in k variables
• Requires k parameters in usual version of regression
• requires 2^k parameters (each based on only n2^-k data points) to fit a tree
• Our solution: drop a bunch of trees into a regression
• Existing solution: average over a bunch of trees: called random forests

---

dean@foster.net