# How to generate and use random trees?

I have the assignment to implement a random tree classifier in MATLAB.

The lecture says:

Input: observations and lables
While stopping criterion not reached:
1. Node optimization: - several split candidates are randomly generated
- the best splitting function is chosen according to some quality measure
2. Data splitting: observations are pushed to the left or right branch.
3. Move to next node

Stopping criteria:
Quality measure - Number of data points in the current node/leaf


My problem now is I do not understand how to get the randomly generated split candidates? Get them from the input values? But then I would get a decision tree (pick a random element and say >x right node, < x left node.) Also I do not understand what the difference between the random tree and the decision tree is in the end.

Also the lecture says:

Choosing the best candidates: according to a quality measures
Out-of-bag error (OOB)  -  Minimize error rate after splitting using a test set
Information gain  -  Maximize information gain after splitting


But what test set should I use? The test set already in the tree used for training?

Wikipedia and Google did not help me either. The code of the MATLAB stub can be found here: http://pastebin.com/iuzqF8gG

-
BTW, here you can find load of useful links, especially one on Friedman book, that contain whole chapter about random forests: stats.stackexchange.com/a/635/2401 – om-nom-nom Feb 5 '12 at 21:12

My problem now is I do not understand how to get the randomly generated split candidates? ... Also I do not understand what the difference between the random tree and the decision tree is in the end.

Randomly select a split point and choose to accept based on a quality measure like BIC, etc. It differs from a decision tree because the split point is generated randomly to generate several decision trees and you only keep the most useful (w.r.t some metric).

But what test set should I use? The test set already in the tree used for training?

Use cross-validation (e.g. leave-one-out-cross-validation).

Here, you take your data set and randomly split into two datasets : a test and training dataset (e.g. you have 100 data points and you randomly choose 50 for training and the rest for testing). Once you have trained your tree on the training data set, you can test it on the testing data set which will give you an insight on how well your trees perform with unseen data (testing error).

-
Thank you Jacob for your answer. I have a dedicated test set to test the full tree. I add the data set one node at a time. So do I create a random split point for every inset operation and test it once if it is better than the parent one? When do I walk up the tree to test the i.e. root? Or do I create more split points and pick the best one, but then when and how many? And a final question, how do I handle the constraints i.e. max 50 leaves per node and maximal depth of 5? Do I split when one node is at 50? – mmlac Jul 14 '11 at 21:22

I do not know about Matlab, but in general, you can use stochastic context free grammers (SCFG); see e.g. Weinberg, Nebel (2010).

Basic idea: represent trees with a CFG, train/define probabilities appropriately and generate trees top-down, following the grammar.

-