source: proiecte/Parallel-DT/R8/Doc/verbose.1 @ 24

.TH C4.5 1
.SH NAME
A guide to the verbose output of the C4.5 decision tree generator

.SH DESCRIPTION
This document explains the output of the program
.I C4.5
when it is run with the verbosity level (option
.BR v )
set to values from 1 to 3.

.SH TREE BUILDING

.B Verbosity level 1

To build a decision tree from a set of data items each of which belongs
to one of a set of classes,
.I C4.5
proceeds as follows:
.IP "    1." 7
If all items belong to the same class, the decision
tree is a leaf which is labelled with this class.
.IP "    2."
Otherwise,
.I C4.5
attempts to find the best attribute
to test in order to divide the data items into
subsets, and then builds a subtree from each subset
by recursively invoking this procedure for each one.
.HP 0
The best attribute to branch on at each stage is selected by
determining the information gain of a split on each of the attributes.
If the selection criterion being used is GAIN (option
.BR g ),
the best
attribute is that which divides the data items with the highest gain
in information, whereas if the GAINRATIO criterion (the default) is
being used (and the gain is at least the average gain across all
attributes), the best attribute is that with the highest ratio of
information gain to potential information.

For discrete-valued attributes, a branch corresponding to each value of
the attribute is formed, whereas for continuous-valued attributes, a
threshold is found, thus forming two branches.
If subset tests are being used (option
.BR s ),
branches may be formed
corresponding to a subset of values of a discrete attribute being tested.

The verbose output shows the number of items from which a tree is being
constructed, as well as the total weight of these items.  The weight
of an item is the probability that the item would reach this point in the
tree and will be less than 1.0 for items with an unknown value
of some previously-tested attribute.

Shown for the best attribute is:

    cut  -  threshold (continuous attributes only)
    inf  -  the potential information of a split
    gain -  the gain in information of a split
    val  -  the gain or the gain/inf (depending on the
selection criterion)

Also shown is the proportion of items at this point in the tree
with an unknown value for that attribute.  Items with an unknown value
for the attribute being tested are distributed across all values
in proportion to the relative frequency of these values in the
set of items being tested.

If no split gives a gain in information, the set of items is made
into a leaf labelled with the most frequent class of items reaching
this point in the tree, and the message:

        no sensible splits  
.IR r1 / r2

is given, where
.I r1
is the total weight of items reaching this point in the tree, and
.I r2
is the weight of these which don't belong to the class of this leaf.

If a subtree is found to misclassify
at least as many items as does replacing the subtree with a leaf, then
the subtree is replaced and the following message given:

        Collapse tree for
.I n
items to leaf
.I c

where
.I c
is the class assigned to the leaf.


.B Verbosity level 2

When determining the best attribute to test,
also shown are the threshold (continuous attributes only),
information gain and potential information for a split on
each of the attributes.
If a test on a continuous attribute has no gain or there are
insufficient cases
with known values of the attribute on which
to base a test, appropriate messages are given.
(Sufficient here means at least twice MINOBJS, an integer
which defaults to 2 but can be set with option
.BR m.)
The average gain across all attributes is also shown.

If subset tests on discrete attributes are being used,
for each attribute being examined, the combinations of
attribute values that are made (i.e. at each stage, the
combination with highest gain or gain ratio) and the
potential info, gain and gain or gain ratio are shown.


.B Verbosity level 3

When determining the best attribute to test,
also shown is the frequency distribution table showing
the total weight of items of each class with:

    - each value of the attribute (discrete attributes), or
    - values below and above the threshold (contin atts), or
    - values in each subset formed so far (subset tests).



.SH TREE PRUNING

.B Verbosity level 1

After the entire decision tree has been constructed,
.I C4.5
recursively
examines each subtree to determine whether replacing it with
a leaf or a branch would be beneficial.
(Note: the numbers treated below as counts of items actually
refer to the total weight of the items mentioned.)

Each leaf is shown as:

.IR        c ( r1 : r2 /
.IR r3 )

  with:
        \fIc\fR   -  the most frequent class at the leaf
        \fIr1\fR  -  the number of items at the leaf
        \fIr2\fR  -  misclassifications at the leaf
        \fIr3\fR  -  \fIr2\fR adjusted for additional errors

Each test is shown as:

.IR        att :[ n1 "%  N=" r4 tree=
.IR r5  leaf= r6 +
.IR r7  br[ n2 ]= r8 ]

  with:
        \fIn1\fR  -  percentage of egs at this subtree that are misclassified
        \fIr4\fR  -  the number of items in the subtree
        \fIr5\fR  -  misclassifications of this subtree
        \fIr6\fR  -  misclassifications if this was a leaf
        \fIr7\fR  -  adjustment to \fIr6\fR for additional errors
        \fIn2\fR  -  number of the largest branch
        \fIr8\fR  -  total misclassifications if subtree is replaced by largest branch

If replacing the subtree with a leaf or the largest branch
reduces the number of errors, then the subtree is replaced
by whichever of these results in the least number of errors.


.SH THRESHOLD SOFTENING

.B Verbosity level 1

In softening the thresholds of tests on continuous attributes
(option
.BR p ),
upper and lower bounds for each test are calculated.
For each such test, the following are shown:
.IP "  *" 4
Base errors - the number of items misclassified when the threshold has
its original value
.IP "  *"
Items - the number of items tested (with a known value for this
attribute)
.IP "  *"
se - the standard deviation of the number of errors
.HP 0
For each of the different attribute values, shown are:
.IP "  *" 4
Val <=   - the attribute value 
.IP "  *"
Errors   - the errors with this value as threshold
.IP "  *"
+Errors  - Errors - Base errors
.IP "  *"
+Items   - the number of items between this value and the original
threshold
.IP "  *"
Ratio    - Ratio of +Errors to +Items
.HP 0
The lower and upper bounds are then calculated so that the
number of errors with each as threshold would be one standard
deviation above the base errors.


.SH SEE ALSO

c4.5(1)