COMMAND(1)

NAME
tgen - generate a decision tree

SYNOPSIS
tgen [options] attribute_file example_file tree_file

DESCRIPTION

tgen takes a data set (see attr(1) for a description of the data file formats and /IND/Data/thyroid for a sample data set) and builds a decision tree. Options allow CART style cost-complexity pruning by test set or by cross validation, and a wide variety of splitting rules such as Bayesian, information gain and gini methods. Subsetting is implemented, as well as handling pre- and post-pruning rules. Various hacks exist for handling missing values. Lookahead can be programmed with the -B option, and early stopping (pre-pruning) with the -J1 option or the -n option. Interactive mode (the -o option) also displays plots using gnuplot under X.11 of the cut-point profiles, if you wish to control the growing operation more closely.

Lookahead during search for trees is best controlled using mktree(1) with the preset styles "-s bayes -s look" or "-s mml -s look".

Bayesian option trees with averaging is best controlled using mktree(1) with the preset styles "-s bayes -s opt" or "-s mml -s opt". This will in general allow better estimates of class probabilities than other methods, particularly when samples are small, but will require an order of magnitude more computation and the trees produced cannot be displayed or "read" easily. However, they can be used for classification with tclass(1) or tquest(1). Option trees allow alternative tests to be specified at nodes so that the tree structure now represents a whole space of possible optional trees. Since optional tests can exist recursively, this has a potential exponential explosion in the number of nodes in the tree, and the generation mechanisms control this explosion.

To control the generation of option trees from tgen requires use of the -B, -J, -K and -L options. The -A and -P options should be combined as well. This is a simple beam search that retains all good trees found in an and-or structure. The -B option allows n-ply lookahead during splitting (all other splitting rules use 1-ply lookahead). Use 2 or 3-ply to get better performance on small problems. Option trees are initiated with the -J option. Options are repeatedly added to the tree until the system either runs out of space or time, or no more "reasonable" options are found. The -K option is for post-pruning of option trees only. The -L option is critical to keep the system from running out of resources prematurely. A typical option combination might be:
        tgen -t -B2,4 -J4 -K4 -L0.9 -d5 -s4 ...

Decision graphs are grown by using the -DD option. This is best done with preset styles of mktree(1). The -t and -P options must be used to grow decision graphs. Using the -P option the user may give a value for P_Join, or may specify to search for a value of P_Join. Two other options are provided for use with decision graphs, the -I option and the -w option. The -A, -B, -d, -s and -U options are compatible with decision graphs. A typical option combination for decision graphs would be:
        tgen -DD -t -Pwall -A1
If you wished to grow a graph with a particular value of P_Join (say 0.15) then you might use the option combination:
        tgen -DD -t -Pwall,0.15 -A1
Decision graphs may be grown using lookahead, e.g.,
        tgen -DD -t -Pwall -A1 -B2,4

OPTIONS

-A alpha

-A classes[,alpha]

-A nonsym,alpha
    With the first option class probabilities at nodes are calculated using the symmetric Laplace formula:

        (#this-class + alpha/#classes)/(#total + alpha).

    where
          #this-class = count for this class at this node
          #total = total count at this node
          #classes = number of classes
    Note the class probabilities sum to 1. The default is alpha=1. With the "classes" option, alpha is first multiplied by the number of classes, #classes, before using the formula above. With the "nonsym" option, class probabilities at nodes are calculated using the non-symmetric Laplace formula:

        (#this-class + #class-base-rate*alpha)/(#total + alpha).

    where
        #class-base-rate = class proportion in population
    The base rates are estimated from the class counts in the entire training sample, using a symmetric Laplace formula with alpha set to the number of classes. This option also effects the operation of the -t option because alpha is used as a prior parameter. See also the -P options. By default, alpha is 1.0 and the "classes" and "nonsym" options are switched off. If you use both the "classes" and "nonsym" options then they will overlay their effects.

-B depth,breadth[,fact[,c_breadth,c_fact]]
    When tree growing there is an initial beam-search n-ply lookahead phase to evaluate the quality of each test. At each step when doing this, choose the best breadth choices for each test that are within fact of the best, and add these as options on the search beam. Lookahead to depth depth. Only supported with the -t option. Default values are 1,1,0.00001,breadth,0.00001. When initializing beam search, each node is expanding into a set of optional tests by using the standard 1-ply lookahead splitting rule. To make the root of this beam search broader, make c_depth greater than depth, and c_fact is the corresponding factor at the root.

-c prop[,cseed]
    Build tree from a proportion prop of the examples selected at random; prune tree using cost-complexity pruning with test set on remainder. See discussion on costs with the -C option. A typical value to use is prop=0.7. See the -p option below for setting the standard errors. cseed initializes the random number generator using the seed, so you can reproduce the train/test partition.

-C folds[,cseed]
    Build tree using folds-fold cross-validation cost-complexity pruning using costs from the utility matrix, or assuming minimum errors costs. CART recommended value is 10-fold. See the -G option in tclass for displaying the error estimate, and the -p option below for setting the standard errors. With the verbose (-v) option used, additional information will be printed giving details of cost-complexity parameters, tree sizes and tree "costs", which are CART's variation of utilities. Costs are the negative of utilities normalized to be in the range 0-1. The minimum errors cost matrix has zeros on the diagonal and ones everywhere else. cseed initializes the random number generator using the seed, so you can reproduce the train/test partitions.

-d depth
    Stops growing tree beyond depth depth. By default is set to 200. The root node is depth 0 and its children are depth 1.

-DD Build a decision graph rather than a decision tree. Requires the use of the -P and -t options. Also see the -I option and -w option.

-e  By default tgen assumes the example file is encoded and to be sampled automatically (see enc(1) and encsmpl(1)). This option makes tgen read in the example file as a text file complete.

-F  Totally randomize the evaluation of tests at the initial growing (1-ply lookahead) phase. Without lookahead, this means the tree will be grown randomly, just in case you wanted a random tree.

-G subsize
    When growing a node by choosing a test to make a split, if there are more than 1.2*subsize data at the node, then (psuedo-)randomly choose a subsample of size subsize to evaluate the potential tests. Default is 1000. Really only useful if there are a lot of real valued attributes and the training set is 5,000 or more.

-i purflg
    Use the splitting rule indicated by purflg when growing a node. purflg can be one of "i" (information gain), "g" (GINI index of diversity), "t" (twoing), or "r" (Quinlan's gain ratio).

-I  This option is only available when building decision graphs (-DD). This option allows the user to create a smaller decision graph that is more suited to interpretation by a person. Graphs generated with this option will not always perform as well as graphs tailored for smoothing by tprune (see -b option in tprune).

-J breadth[,fact[,add_fact[,leaf_fact]]]
    Sets the post-lookahead growing options. Does option tree growing with magic numbers to alter the search strategy, and requires use of the -B option (at the very least, -B1,2). After initial lookahead has found a candidate set of tests nodes, grow as distinct optional sub-trees the best breadth test nodes within fact (default = 0.005) factor of the best. The last two magic numbers modulate early stopping or pre-pruning. Only grow the node if the non-leaf probability is within a factor leaf_fact of leaf probability (default = 0.00001, make this closer to 1.0 to stop earlier) and if the non-leaf probability is not greater than a factor add_fact of the best test to grow (default=0.75, make this smaller to stop earlier). This option is only supported with the -t option. Should be used with options -d and -s to help limit search and option -K to save memory.

-K breadth[,fact]
    Does post-pruning on option trees with magic numbers to alter the search. Keep only the best breadth (default = 1) option branches and only choose those within a fact (default = 0.005) factor of the best. Only supported with the -t option.

-L fact
    Thuis is an esoteric search control parameter you shouldn't need to know about. Used in conjunction with the -J option. With the -J option in use, tgen starts producing optional tests at each node, in order of their estimated quality. Better optional tests are added first. Each optional test produces a full subtree, which itself my generate more good optional tests recursively. tgen keeps adding optional tests until it runs out of space, or no more "reasonable" ones exist according to the -J arguments. In the initial generation of the first tree, however, only the "best" tests are explored, but some tests may be indistinguishable so the first tree grown may contain a few optional tests. Two tests are indistinguishable according to tgen if their log posteriors are within a factor fact. By default, fact=0.9.

-n factor
    Do prepruning during initial growing. The larger the factor, the stronger the prepruning. This prevents an ungrown tree node from being extended at the 1-ply lookahead phase if the gain doesn't exceed the factor factor. This takes effect before the -B lookahead facility kicks in. By default the factor is a very large negative number. With the -t option in use, the factor should be something like 0.01, and this prevents extension if the posterior probability of the children is not within 0.01 of the leaf. Without the -t option, this should be set to something like 0 (to prevent extension when there is no gain) or -.01 (to allow extension even if the best gain is slightly negative).

-N  When using the -t or -J options the Bayes splitting rules, etc., are in effect. For these, a "log posterior" measure is computed and used as a rating for the tree (see -g option in tclass). For some priors this is out by a constant because the tree prior, as specified with the -P option, has not been normalized. The -N option does the extra calculation necessary to compute this normalizing constant, which can then be displayed with the -Q option in tclass. The computation can be exponential in nature if there are mixed continuous or discrete attributes of several different arities. The calculation is approximate if subsetting is used. Help avoid computational problems with the -d option, for instance, try smaller depths first.

-o  Manual override option. Allows the user to manually choose which attribute to split on, and print all sorts of debugging information while building, thus overriding the automatic selection made. A menu of interactive options is available (via the "h" command) to guide the manual tree building process. Setting the "x" toggle can spawn gnuplot processes giving cut point profiles.

-p factor
    When cost-complexity pruning, number of standard deviations to use. Default is 1.0. CART methodology suggests 0.0 for larger trees and (sometimes) greater accuracy.

-P optarg
    This option sets the format for the tree prior. The command line arguments will be overridden by any prior commands embedded in the attribute file. This affects whether large, small, stringy or bushy trees are preferred. The options are:

    weight,n_weight[,l_weight]
        Leaves are penalized by a probability l_weight and nodes (tests) by n_weight. This makes small trees much more likely, but also tends to penalize high arity attributes.

    choices
        Divide the node probability above by the number of test choices at the node. Use in conjunction with the "weight" option above or the "mml" option below.

    nochoices
        Switch off the above option.

    null
        Makes the prior null. i.e. is equivalent to "-Pweight,0,0 -A0.000001".

    mml This is the Wallace tree prior described in the manual. For the full Wallace prior also use the "-Pchoices" option. The full prior roughly says to stop subtrees from branching too much so approximately one outcome of a test should lead to a non-leaf. This is an incredibly strong preference for smaller trees so the "-s mml" style option in mktree just uses the "-Pmml" prior option alone.

-s min-set[,min-set-split]
    Turn node to leaf (stop growing) if there are less examples than min-set or only one class has more than min-set/2 examples. Don't allow splitting if all but one nodes in the split have less than min-set-split examples. Default to 1 and 0.5 respectively (effectively ignored) but should be set to higher values to speed up search in noisy data. When using a non-Bayesian splitting rule, cut points are prevented from occuring at the extreme ends of the ranges.

-S type
    Allow binary tests on multi-valued discrete attributes which split the attribute values into two parts. Note subsetting can else by set for individual attributes using attribute qualifiers, see attr(1). This is "subsetting" implemented in a simple greedy manner. type is one of the following:

    full
        Regular subsetting of multi-valued attributes. i.e. do splits testing if the attribute is in a certain subset or not. Disallows the usual multi-way splits.

    one Do binary encoding of the multi-valued attributes. i.e. do splits testing if the attribute is a certain value or not. Disallows the usual multi-way splits.

-t  Bayes splitting rule. On by default.

-U n
    How to handle unknowns when splitting training set. The available methods are:

    1   The default. Send the unknown down each branch with proportion as found in the training set at that node. Not yet convinced the implementation is OK.

    3   Send unknown down the most common branch.

    4   Send unknown down a single branch chosen with probability proportional to that found in the training set at that node.

-v  Increment the verbose level. It starts at one, and each time you use this option it increases by one. Level one reports details of all options currently in operation, and feedback on basic statistics computed during cost complexity pruning with cross validation. Only one level is really supported at the moment.

-w  This option is only available when building decision graphs (-DD). Build a decision graph and then perform a "Markov Chain" like wander through graph and tree space searching for superior graphs and/or trees.
    Warning this option takes considerable time and space.

BUGS
When growing option trees ("tgen -J" or "mktree -s opt"), if tgen quits with a message like "memory limit exceeded" or "time limit exceeded" then it still produces a tree, but has stopped search prematurely. This is not really an error termination.

SEE ALSO
attr(1), tprune(1), tclass(1), tquest(1), mktree(1), tprint(1).