decisiontree.java

一个决策树的Applet（转载

package ai.decision.algorithm;

import java.util.*;
import ai.common.*;

/**
 * Implementation of a decision tree data structure.
 *
 * The DecisionTree class supports TreeChangeListeners, which
 * are notified whenever the tree is modified.
 *
 * <p>
 * <b>Change History:</b>
 *
 * <p><pre>
 * Name:            Date:            Change:
 * =============================================================
 * J. Kelly         Aug-22-2000      Ground-up rewrite.
 * J. Kelly         Nov-10-2000      Added pruning backup ability.
 * </pre>
 *
 * Copyright 2000 University of Alberta.
 *
 * <!--
 * This file is part of the Decision Tree Applet.
 *
 * The Decision Tree Applet is free software; you can redistribute it
 * and/or modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Foobar is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with the Decision Tree Applet; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * -->
 */
public class DecisionTree
{
  // Debug data members

  boolean DEBUG_ON = true;    // Turn on/off debugging info.

  // Instance data members

  Vector     m_nodes;               // Ordered list of tree nodes.
  LinkedList m_treeChangeListeners; // Tree change listeners.

  int     m_internalNodes;      // Count of internal nodes.
  int     m_trainingCorrect;    // Count of training examples
                                // correctly classified so far.
  int     m_testingCorrect;     // Count of testing examples
                                // correctly classified so far.
  boolean m_complete;           // Indicates tree is complete
                                // (all branches descend to leaves)

  // Constructors

  /**
   * Creates an empty decision tree.
   */
  public DecisionTree()
  {
    m_nodes = new Vector();
    m_treeChangeListeners = new LinkedList();
  }

  // Public methods

  /**
   * Registers a TreeChangeListener.  Whenever the tree
   * modified (e.g. a node is added or removed, or a subtree
   * is pruned) all TreeChangeListeners are notified.
   *
   * @param l The TreeChangeListener to add.
   */
  public void addTreeChangeListener( TreeChangeListener l )
  {
    if( l == null || m_treeChangeListeners.contains( l ) ) return;
    m_treeChangeListeners.add( l );
  }

  /**
   * Removes a TreeChangeListener from the listener list.
   *
   * @param l The TreeChangeListener to be removed.  If the
   *          supplied TreeChangeListener is null, or is
   *          not a member of the current list, no action
   *          is taken.
   */
  public void removeTreeChangeListener( TreeChangeListener l )
  {
    m_treeChangeListeners.remove( l );
  }

  /**
   * Returns true if the tree is empty (no nodes) or false
   * otherwise.
   *
   * @return true if the tree is empty, or false if it
   *         contains at least one node.
   */
  public boolean isEmpty()
  {
    return m_nodes.size() == 0;
  }

  /**
   * Returns true if the tree is complete (all branches
   * decend to leaves), or false otherwise.
   *
   * @return true if the tree is complete, or false otherwise.
   */
  public boolean isComplete()
  {
    return m_complete;
  }

  /**
   * Returns a reference to the root of the tree, or null if
   * the tree is empty.
   *
   * @return A reference to the current root node, or
   *         null if no nodes have been added to the tree.
   */
  public DecisionTreeNode getRoot()
  {
    if( m_nodes.size() == 0 ) return null;

    return (DecisionTreeNode)m_nodes.elementAt( 0 );
  }

  /**
   * Returns the number of nodes in the tree.
   *
   * @return The number of internal and leaf nodes currently in the tree.
   */
  public int getNumNodes()
  {
    return m_nodes.size();
  }

  /**
   * Returns the number of internal nodes in the tree.
   *
   * @return The number of internal nodes <b>only</b> currently in the tree.
   */
  public int getNumInternalNodes()
  {
    return m_internalNodes;
  }

  /**
   * Returns the number of training examples from the
   * dataset that are correctly classified by
   * the current tree.
   *
   * @return The number of training examples from the
   *         dataset that are correctly classified by the
   *         tree (which is equivalent to the number of
   *         examples that reach leaf nodes).
   */
  public int getNumTrainingEgCorrectClass()
  {
    return m_trainingCorrect;
  }

  /**
   * Returns the number of testing examples from the
   * dataset that are correctly classified by
   * the current tree.
   *
   * @return The number of testing examples from the
   *         dataset that are correctly classified by the
   *         tree (which is equivalent to the number of
   *         examples that reach leaf nodes).
   */
  public int getNumTestingEgCorrectClass()
  {
    return m_testingCorrect;
  }

  /**
   * Attaches a new leaf node to the supplied node, along
   * the specified arc.
   *
   * @param parent The node in the current tree to attach
   *        the new leaf node to.  If the node is null, the
   *        new leaf node becomes the root of the tree.
   *
   * @param arcNum The arc number (or attribute value
   *        index) along which to attach the new node.
   *
   * @param label The label for the new node - this
   *        should correspond to the name of the
   *        target attribute value for this leaf.  The
   *        String is copied and stored in the leaf.
   *
   * @param mask The updated mask, with the additional
   *        arc to the new node and the target attribute
   *        value <i>already</i> masked off.
   *
   * @return A reference to the new leaf.
   */
  public DecisionTreeNode addLeafNode( DecisionTreeNode parent,
      int arcNum,
      String label,
      AttributeMask mask,
      int numTrainingExamplesReachHere,
      int bestTrainingTargetIndex,
      int numTrainingEgsCorrectClassUsingBestTrainingIndex,
      int numTestingEgsCorrectClassUsingBestTrainingIndex,
      int numTestingExamplesReachHere,
      int bestTestingTargetIndex,
      int numTestingEgsCorrectClassUsingBestTestingIndex,
      int numTrainingEgsCorrectClassUsingBestTestingIndex )
  {
    // Create new leaf node.
    DecisionTreeNode leaf =
      new DecisionTreeNode( parent, new String( label ), null, mask );

    // Set the node statistics.
    leaf.setTrainingStats( numTrainingExamplesReachHere,
                           bestTrainingTargetIndex,
                           numTrainingEgsCorrectClassUsingBestTrainingIndex,
                           numTestingEgsCorrectClassUsingBestTrainingIndex );

    leaf.setTestingStats( numTestingExamplesReachHere,
                          bestTestingTargetIndex,
                          numTestingEgsCorrectClassUsingBestTestingIndex,
                          numTrainingEgsCorrectClassUsingBestTestingIndex );

    // Update the tree statistics.
    m_trainingCorrect += numTrainingEgsCorrectClassUsingBestTrainingIndex;
    m_testingCorrect  += numTestingEgsCorrectClassUsingBestTrainingIndex;

    // Now, attach the new leaf to the supplied node.
    if( parent != null )
      parent.setChild( arcNum, leaf );

    // Add a reference to the new node to the node list.
    m_nodes.add( leaf );

    //--------------------- Debug ---------------------
    if( DEBUG_ON ) {
      System.out.print( "DecisionTree::addLeafNode: " +
        "Added leaf node '" + label + "'" );

    if( parent == null )
      System.out.println( " as root of decision tree." );
    else
      System.out.println( " below internal node " +
        "'" + parent.getLabel() + "'." );
    }

    // Determine if the tree is complete.
    if( findIncompleteNode(
      (DecisionTreeNode)m_nodes.elementAt( 0 ), new int[1] ) == null )