-------------------------------------------------------------------------------
                                       
                                       
                       B O S T O N   U N I V E R S I T Y
                                       
                          Computer Science Department
                                       
                              C O L L O Q U I U M
                                       
			     Tuesday March 1, 1994
                                       
                                    3:30pm
                            (Tea served at 3:00pm)
                                       
                            Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------


	     Algorithms for Inducing Decision Trees from Examples

				      by

				Steven Salzberg
			   Johns Hopkins University


      This talk describes several recent algorithms we have developed for
      generating decision tree  classifiers from examples.  First I  will
      describe  OC1, a method  for   constructing {\it oblique}  decision
      trees.  Oblique   trees    classify examples  by   testing   linear
      combinations of the features  at each  non-leaf  node of the  tree.
      Each test  is equivalent to  a hyperplane at an oblique orientation
      to   the axes  defined by  the  features.   Because  the problem of
      finding an  optimal   orientation for  an  oblique  hyperplane   is
      NP-Complete, we   have  developed heuristic  methods  to find  good
      hyperplanes.  The OC1  system combines deterministic and randomized
      procedures in its search for good trees.  Next I will describe KS1,
      an efficient algorithm  for finding  multi-way splits for  decision
      trees.  Unlike standard decision trees whose nodes have only binary
      splits, KS1 allows nodes  to split an interval  into any  number of
      subintervals up to $k$.  For  each value from  1 to $k$ it computes
      the optimal split, and then chooses the best  of those according to
      a pre-defined goodness measure.

      I will also describe experiments using  both OC1 and KS1 on several
      different   real-world and  artificial   data sets.    Some of  the
      real-world  data comes from a  joint project with the Department of
      Physics  and  Astronomy at Johns  Hopkins  and the  Space Telescope
      Science Institute.   The problems there involve  identifying stars,
      galaxies, cosmic rays, and other   astronomical objects in   images
      collected by the Hubble Space Telescope  and other telescopes.  The
      classification accuracy of the trees found  using our methods often
      equals or exceeds the best known results  of other machine learning
      methods on these problems.


      Hosts: Abdelsalam Heddaya and Azer Bestavros

-------------------------------------------------------------------------------
    For more information contact Prof. Azer Bestavros <bestavros@cs.bu.edu>
-------------------------------------------------------------------------------