Assignment 7 information

Code and other information

• Testing program for this assignment. See comments for instructions. UPDATED 11/18 --- now does decision tree comparison correctly.

• Decision tree support code updated 11/16; see Addenda and Eratta section below.

• The data sets (now includes census-test1 and census-test2) Data set documentation (for your information).

• This will be a 140 point assignment. The tentative plan is for problem 1 to be about 120 points and problem 2 to be about 20 points. I'll finalize this soon.

Addenda & eratta

• 11/16: I have corrected a small error in the test-dt function, and I have also added the following functions to help with problem 2

  • (learn-disc-dt discretize-fn training-data)

    This will automaticall run your discretize function on the training data and then call your learn-dt procedure.

  • (test-disc-dt discretize-fn dt test-data

    Akin to the test-dt procedure, this function runs your discretize function on the test data and then tests it with the given decision tree.

  Here's an example of using these functions. (Note that you can do the some thing with the non "discretize" versions.)

  (define cdt (learn-disc-dt discretize census-tdata))
  ;Value: cdt
  
  (test-disc-dt discretize cdt census-test1)
  Out of 50 examples, 34 were correctly classified,
  7 were incorrectly classified, and
  9 had attribute values not seen before.
  
  ;No value
  

• The support code now does error checking on inputs to split-td, tally-td, and print-dt

• I have added two more functions to the support code:
  • (pick-majority tally).

    This function takes a tally (such as that produced by the tally-td procedure) and returns the "majority" attribute value. For example:

    (tally-td play-tennis-tdata)
    ;Value: ((no 2) (yes 3))
    
    (pick-majority (tally-td play-tennis-tdata))
    ;Value: yes
    

  • (print-dt decision-tree attribute-names)

    This function prints out a decision tree in a nice format. The second argument, a list of the names of the attributes is optional. See the section below (on outputs for the sample data sets) for examples of using this function. There should now be no need for you to use the make-readable-dt procedure.

• For problem 2, the data set is specified by the variables: census-tdata and census-anames.

Hints

• (learn-dt training-data)

  You can basically follow the procedure given in figure 18.7 of our text, except don't use a default value or handle the case where the examples (training data) is empty. This case will never occur because split-td will only create a "split" if there is at least one training example with the given attribute value.

  If there are "unknown" attribute values encountered while classifying an example, the classify procedure will return a default value.

• The log function computes natural logarithms. To get logarithms to base two, divide by the natural log of two.

• The procedures split-td and tally-td will in a large part determine how you go about writing the learn-td procedure. Make sure you understand the output format of these functions.

• I suggest that you create a function that computes the information given a tally, for example:

  (calc-info '((yes 3) (no 2)))
  ;Value: .9709505944546686
  

• You may also want to write a function that computes the amount of information after a split, i.e. after the training data have been split by some attribute.

Results on sample data sets

(print-dt (learn-dt play-tennis-tdata))
(1 (normal yes)
   (high (0 (overcast yes)
            (sunny no)
            (rain no))))
;No value

(print-dt (learn-dt play-tennis-tdata) play-tennis-anames)
(humidity (normal yes)
          (high (outlook (overcast yes)
                         (sunny no)
                         (rain no))))
;No value

(print-dt (learn-dt restaurant-tdata) restaurant-anames)
(patrons (none no)
         (full (hungry (no no)
                       (yes (type (burger yes)
                                  (italian no)
                                  (thai (fri (no no)
                                             (yes yes)))))))
         (some yes))
;No value

(print-dt (learn-dt mushroom-tdata) mushroom-anames)
(odor (c p)
      (p p)
      (l e)
      (a e)
      (f p)
      (n (cap-color (p e)
                    (b p)
                    (c e)
                    (y p)
                    (e e)
                    (n e)
                    (w (cap-shape (f e)
                                  (c p)
                                  (x e)))
                    (g e))))
;No value