ADTREE CODE TUTORIAL
                          (c) 1998, The Auton Lab.

                               Andrew W. Moore
          (awm@cs.cmu.edu, phone 412-268-7599, www.cs.cmu.edu/~awm)

  This very simple tutorial is by means of an example use of the software.
  The main text you will see is just what appeared on the screen during
  an example use of the program.

                    The heavily indented text (like this) are
                    commentary on what was going on during the
                    example. The example was based on the dataset
                    realmpg.csv, which you should be able to find in
                    the same place as this tutorial.

I TYPE: adtree
This is a data mining program. (c) 1997, 1998, The AUTON Laboratory.
Usage:
./adtree <datafile> [default_real {true|false}] [ignore_missing {true|false}]

                    If you just run the program without any arguments
                    you simply get the above message. Instead you need
                    to put a filename after the executable name.  For
                    example...

I TYPE: adtree realmpg.csv

              Welcome to the AUTON ADTREE DEMONSTRATION
                 (c) 1997, 1998, The AUTON Laboratory

    Andrew W. Moore (awm@cs.cmu.edu), http://www.cs.cmu.edu/~AUTON

                   Type help if you're new to this.
                        Type quit to finish.

Loading dataset (slow ASCII format) from realmpg.csv...
Datset load (pass 1) loaded 16 lines
Datset load (pass 1) loaded 256 lines
Datset load (pass 2) loaded 16 lines
Datset load (pass 2) loaded 256 lines
  ..loaded

                    At this point you get the following prompt, which
                    you will see after each command executes:

AUTON>

                    So, in this example I type the command "help"...

AUTON> help
inputs <attributes> : Define which attributes are to be used as inputs
output <attribute> : Define which attribute is to be used as output
add <attributes> : Add to the set of inputs
ignore <attributes> : Remove from the set of inputs
maketree [rmin <n>] [maxmegs <n>] : Build the adtree.
show : Display current inputs and outputs, and speed.
speed {fast|slow} : fast => use adtree for counting. slow => don't.
table : Display the contingency table for the current set of inputs.
matrix : Display joint contingency table between inputs and output.
features [numatts <n>] : Find best set of <n> features.
marginals [numatts <n>] : find and save best <n>-way correlations.
rules <val> [numatts n] [numrules n] [support n] [sigtest y|n]: Rule Finder.
net [iters <n>] [ordered {true|false}] : Learn a Bayes Net.
brief: Give a brief listing of details of each attribute.
info <attributes> : Give detailed attribute information.
symbolize <style> <num_levels> <attributes> : make numeric atts symbolic.
realize <attributes> : Convert certain symbolic attributes to real.
rename <attribute> <newname> : Rename.
delete <attributes> : Remove one or more attributes.
select <attributes> : delete all but the selected attributes.
swap <attnum1> <attnum2> : Reposition attributes by swapping columns.
sort [arity|entropy] [down|up] : Sort Attributes.
save {marked|unmarked} <filename>.
load <filename> [options] : Load new dataset from CSV or FDS file.
sortmissing : Display attributes sorted by number missing rows.
batchrename <filename> : Rename attributes from a file.
togglemarks : Make marked rows unmarked and vice versa.
showmarked <number> <attributes> : Show a subset of the data.
mark <constraint> : Set all rows matching constraint to be marked.
unmark <constraint> : Set all rows matching constraint to be unmarked.
shuffle : Randomly re-order the dataset rows.
(Help options: type help, or help all, or help <command>)

                    That gives me a list of commands. For more details
                    on a given command, just type help <commandname>

AUTON> brief
Dataset has 392 rows and 8 attributes.
         mpg real low 9, high 46.6, mean 23.4459
   cylinders symb 5 vals
displacement real low 68, high 455, mean 194.412
  horsepower real low 46, high 230, mean 104.469
      weight real low 1613, high 5140, mean 2977.58
acceleration real low 8, high 24.8, mean 15.5413
   modelyear symb 13 vals
       maker symb 3 vals asia europe usa

                    The brief command tells you about all the
                    attributes (columns) in the dataset. As you see,
                    some are symbolic (a set of discrete values) and
                    some are real-valued numbers.

AUTON> info cylinders
cylinders                 Attribute   1 (Symbolic)
    0 missing values
     3 (4) 4 (199) 5 (3) 6 (83) 8 (103)

                    The info command let us find a little more detail
                    about the cylinders attribute.

AUTON> info modelyear
modelyear                 Attribute   6 (Symbolic)
    0 missing values
     70 (29) 71 (27) 72 (28) 73 (40) 74 (26) 75 (30) 76 (34) 77 (28) 78 (36)
     79 (29) 80 (27) 81 (28) 82 (30)

                    ...and ditto for modelyear. Note how the data
                    reader saw a bunch of integer values when reading
                    modelyear, and decided to treat them as symbolic
                    instead of real. To over-ride that, you can use the
                    realize command...

AUTON> realize modelyear
modelyear will be converted.
AUTON> info modelyear
modelyear                 Attribute   6 (Real)
    0 missing values
    mean 75.9796 sdev 3.68374 min 70 max 82
    First 8 vals... 70 70 70 70 70 70 70 70

                    ..and as you see above, it changes.

AUTON> mark maker == usa
245 rows are currently marked

                    The mark and unmark facilities are useful if you
                    want to "mark" or "flag" some subset of the
                    records. Type help mark for more details.

AUTON> unmark modelyear < 77
101 rows are currently marked

                    So now the only marked rows are ones after 1976
                    and made in America.

AUTON> showmarked 5 mpg maker modelyear weight
   Row        mpg     weight  modelyear      maker
   215         30       2155         77        usa
   217       25.5       2300         77        usa
   219       17.5       3880         77        usa
   220         17       4060         77        usa
   221       15.5       4140         77        usa
I showed you the first 5 of the 101 marked rows.

                    That allowed us to see the values of the specified
                    attributes amongst the 5 earliest marked rows in
                    the dataset.

                    Now, let's cut to the chase and make us an ADTREE
                    so we can do some data-mining...

AUTON> maketree
I can't build the tree because there are real-valued
attributes. I suggest using the symbolize command to
convert them to symbolic form.

                    AUTON complained because the version of ADtrees in
                    this software can only cope with datasets where
                    all attributes are symbolic. Type help symbolize
                    to see how to convert numeric to symbolic.

AUTON> symbolize equal 3 all
mpg will be changed
cylinders unchanged---already symbolic
displacement will be changed
horsepower will be changed
weight will be changed
acceleration will be changed
modelyear will be changed
maker unchanged---already symbolic

                    So now all attributes are symbolic, in three
                    buckets.  Suppose we want to save this processed
                    dataset for future use.  Just use the save
                    command.

AUTON> save symbolmpg.csv
*** Note, I'm saving all rows, whether marked
*** unmarked. To save only the marked rows,
*** enter
***           save marked symbolmpg.csv
*** and to save only the unmarked rows, enter
***           save unmarked symbolmpg.csv
Saving dataset (slow ASCII format) to symbolmpg.csv...  ..saved

                    Notice the starred comments. That was AUTON
                    reminding you that if you had wanted to only save
                    your marked rows you were in for a disappointment.
                    But we don't care. We *wanted* to save all rows.

AUTON> save symbolmpg.fds
Saving dataset (fast "fds" binary format) to symbolmpg.fds...  ..saved

                    ..what we just did was save in the fast .fds
                    format. This format is used automatically for any
                    input or output file that end in .fds . These
                    files are much faster to load and save and usually
                    save space for large files.  Type help save for
                    more info.

AUTON> maketree
Enter rmin (0 to 392) [default 30]>
Enter maxmegs (1 to 64000) [default 20]>

                    We were allowed to build it this time! Those extra
                    requests for input are quite common in the AUTON
                    code, and you can always just hit return in order
                    to get the default.

Building ADTREE
   (8 attributes, 392 rows, rmin 30 maxmegs 20)...
The ADTREE uses 9492 bytes and contains 123 snodes
That took 0 second(s).

AUTON> output mpg
Inputs:
Output: mpg
AUTON> inputs acceleration maker
Inputs: acceleration maker
Output: mpg

                    The last two commands are important commands to
                    define the "current set of inputs" and "the
                    current output". These objects are used by many of
                    the data mining operations. See also the add
                    command for adding to the current set of
                    inputs. See ignore for removing inputs. You can
                    also type "inputs all" to add all attributes
                    except for the current output into the set of
                    inputs.

AUTON> table
acceleration     maker
     ----      ----      ----
   v0:14-      asia        12
   v0:14-    europe        11
   v0:14-       usa        95
   v1:14+      asia        66
   v1:14+    europe        45
   v1:14+       usa       141
   v2:20+      asia         1
   v2:20+    europe        12
   v2:20+       usa         9
ctab entropy = 2.41701

                    The above command listed out each of the possible
                    combinations of values of acceleration and
                    maker. And in each case it told us how many
                    records in the dataset matched the given
                    combination.

AUTON> matrix
                            |          mpg=          mpg=          mpg=
 acceleration         maker |        v0:22-        v1:22+        v2:36+
----------------------------------------------------------------
       v0:14-          asia |             4             7             1
       v0:14-        europe |             3             8             0
       v0:14-           usa |            85            10             0
       v1:14+          asia |             5            48            13
       v1:14+        europe |            10            32             3
       v1:14+           usa |            82            55             4
       v2:20+          asia |             0             1             0
       v2:20+        europe |             1             7             4
       v2:20+           usa |             3             6             0
Prediction Accuracy = 0.704082 (default accuracy 0.492347)
Entropy(mpg) = 1.27667
IG( mpg | acceleration maker ) = 0.322338
RIG = 100 * IG/Entropy =  25.2484

                    The above command brings the current output into
                    the picture. For example it tells us there are 3
                    records where acceleration==v2:20+, maker=usa and
                    mpg=v0:22- (see the bottom left number in the
                    matrix). For copious extra details, type help
                    matrix.

                    The bottom line of the above output told us that
                    the Relative Information Gain (RIG) was 25.2%
                    (which meant that a quarter of the entropy of mpg
                    is "explained" by the combination of acceleration
                    and maker. But maybe there are a pair of
                    attributes out there with even more predictive
                    power?  Lets find out.

AUTON> inputs all
Inputs: cylinders displacement horsepower weight acceleration modelyear maker
Output: mpg

                    What we just did was tell AUTON that it are
                    allowing it to consider all possible inputs in its
                    search for the best two inputs. Now let's run this
                    search (called features, standing for Feature
                    Selection)...

AUTON> features
Enter numatts (0 to 8) [default 2]> 2

                    ...that "2" is where we specify we're looking for
                    the best 2 attributes...


Time to compute best probtab = 0 seconds (loops = 1)
[Hit Return] (or h for other options)
                            |          mpg=          mpg=          mpg=
    cylinders     modelyear |        v0:22-        v1:22+        v2:36+
----------------------------------------------------------------
            3        v0:74- |             2             0             0
            3        v1:74+ |             1             0             0
            3        v2:78+ |             0             1             0
            4        v0:74- |            13            46             0
            4        v1:74+ |             6            48             4
            4        v2:78+ |             0            63            19
            5        v1:74+ |             1             0             0
            5        v2:78+ |             0             1             1
            6        v0:74- |            25             1             0
            6        v1:74+ |            37             2             0
            6        v2:78+ |             8             9             1
            8        v0:74- |            63             0             0
            8        v1:74+ |            29             0             0
            8        v2:78+ |             8             3             0
Prediction Accuracy = 0.852041 (default accuracy 0.492347)
Entropy(mpg) = 1.27667
IG( mpg | cylinders modelyear ) = 0.74497
RIG = 100 * IG/Entropy =  58.3527

                    ...so it turns out that the combination of
                    cylinders and modelyear is best, explaining almost
                    60% of the entropy.

                    The next operation is used to allow us to see, for
                    all pairs of attributes, how helpful is one of the
                    attributes in predicting the other. The
                    interesting thing is that it goes beyond simple
                    correlations, but instead searches among a very
                    wide space of high-dimensional correlations to
                    find if there are *any* circumstances in which
                    attribute A contributes something useful in
                    predicting attribute B.

AUTON> marginals
Enter numatts (2 to 8) [default 2]> 4
Predictor (attname or all)>all
Predictee (attname or all)>all
predictor_attnums = { mpg cylinders displacement horsepower weight acceleration modelyear maker }
predictee_attnums = { mpg cylinders displacement horsepower weight acceleration modelyear maker }
use_attnums = { mpg cylinders displacement horsepower weight acceleration modelyear maker }
maxatts = 4
[Hit Return] (or h for other options)
Searching...    ...finished
I just searched among 1232 conditional probability tables
[Hit Return] (or h for other options)

                    ...at this point you will see lots and lots of
                    output tables. I will pick just one here and
                    explain it....

************************************************

Predictee modelyear, Arity 3, Entropy 1.57575

Best predicted (RIG  22.7147) by: mpg weight maker

RANK    PREDICTOR    RIGI     RIG INPUTS
----    ---------    ----     --- ------
   1          mpg  14.728  16.238 mpg maker
   2    cylinders   7.558  14.238 cylinders acceleration maker
   3       weight   7.230  13.909 weight acceleration maker
   4 displacement   6.725   6.725 displacement
   5   horsepower   6.516   8.025 horsepower maker
   6 acceleration   5.647  13.909 weight acceleration maker
   7        maker   4.867  20.872 mpg acceleration maker
[Hit Return] (or h for other options)

                    This table is concerned with how useful are each
                    of the other attributes for predicting
                    "modelyear". It mentions at the top that the very
                    best set of three attributes for doing so are a
                    combination of mpg weight and maker. But the main
                    table tells us other stuff.

   1          mpg  14.728  16.238 mpg maker

                    This, for example, tells us that when mpg and
                    maker are used together to predict modelyear, they
                    explain 16.238% of the entropy.  (that's the RIG
                    value). More importantly if you were to take "mpg"
                    away from this team of (mpg,maker), you would lose
                    a huge bite of that RIG value...in fact you'd lose
                    14.728% of the original entropy. Thus RIGI is the
                    Relative Information Gain INCREASE of adding
                    attribute mpg into a collaboration with maker. The
                    reason this is useful is that it is often possible
                    to have attributes which are not especially well
                    correlated with the output by themselves, but
                    which given the right "catalyst" in the form of
                    some other set of one or more attributes, they can
                    really shine.  And "marginals" does an exhaustive
                    search to find where the attribute shines the
                    most.

                    So far we have talked mostly about generally
                    predicting one attribute from a bunch of other
                    attributes. Rule learning, which we'll do next, is
                    a nice thing if you are very obsessed wih one
                    particular value of the output attributes. For
                    example...

AUTON> rules
You must supply a desired value for output attribute mpg.
The legal values are:
   0 : v0:22-
   1 : v1:22+
   2 : v2:36+
You may use either the text name, or the small integer number.

                    ...when I just type rules it complains that it
                    needs to know which of the possible three values
                    of "mpg" I am obsessed with.

AUTON> rules 0

                    ...I could have equally legally typed "rules
                    v0:22-"...

Enter numatts (0 to 8) [default 2]> 3
Enter numrules (1 to 1000) [default 10]>
Enter support (1 to 392) [default 20]>
Enter choice sigtest [default y]>

Time to compute rulequeue = 0 seconds

Number of rules considered = 310
[Hit Return] (or h for other options)
** Result of searching for rules that match a high ratio
** of records in which mpg = v0:22-
** The full dataset has 392 records, 193 of which have
** mpg = v0:22-, meaning general fraction is 0.492347.

The queue contains 10 rules (maximum possible = 10)
Rule 0: score = 0.964, fraction = 1.000 (81/81), cylinders = 8, acceleration = v0:14-
Rule 1: score = 0.959, fraction = 1.000 (70/70), horsepower = v1:120+, acceleration = v0:14-, maker = usa
Rule 2: score = 0.955, fraction = 1.000 (64/64), weight = v2:4000+
Rule 3: score = 0.954, fraction = 1.000 (63/63), cylinders = 8, modelyear = v0:74-
Rule 4: score = 0.947, fraction = 0.989 (87/88), horsepower = v1:120+, maker = usa
Rule 5: score = 0.947, fraction = 1.000 (54/54), horsepower = v1:120+, modelyear = v0:74-
Rule 6: score = 0.946, fraction = 0.989 (86/87), cylinders = 8, horsepower = v1:120+
Rule 7: score = 0.946, fraction = 0.989 (86/87), cylinders = 8, horsepower = v1:120+, maker = usa
Rule 8: score = 0.936, fraction = 0.986 (72/73), horsepower = v1:120+, acceleration = v0:14-
Rule 9: score = 0.934, fraction = 1.000 (43/43), displacement = v1:200+, horsepower = v1:120+

                    The above should be fairly self-explanatory. Type
                    help rules for more information.

                    The final thing we can do is learn Bayes Net
                    structures. Feel free to do so....

AUTON> net
Enter iters (1 to 10000000) [default 500]> 50000
Enter choice ordered [default n]>

                    ...If you answer yes to the choice "ordered"
                    (which you'd do by typing y instead of hitting
                    return to achieve the default of n) then we would
                    add an extra major constraint to the kinds of nets
                    we could grow...we'd insist that whatever partial
                    ordering on nodes that the search found, it would
                    not contradict the natural ordering of attributes
                    by column number....



BAYES NET SEARCH (50000 iterations) COMPLETED
cylinders sc=  1.59869 , np=    4 , pars = <no parents>
      mpg sc= 0.699766 , np=   10 , pars = cylinders
displacement sc= 0.457153 , np=   10 , pars = cylinders
horsepower sc= 0.272198 , np=   10 , pars = cylinders
   weight sc= 0.561208 , np=   10 , pars = cylinders
    maker sc= 0.941794 , np=    6 , pars = displacement
modelyear sc=  1.37312 , np=    6 , pars = mpg
acceleration sc=  0.84129 , np=    6 , pars = horsepower
Score is 2911.18
The search took 11 seconds.
AUTON> quit

                    ...That command quits the application.

                    Comments: for researchers doing academic research
                    within the AUTON lab, source code for this is
                    available, which includes a C-language API for
                    accessing the above functionality
                    embedded within your own C programs.