decisiontree.java

一个决策树的Applet（转载

      m_complete = true;

    // Inform any listeners that a node was added.
    Iterator i = m_treeChangeListeners.iterator();

    while( i.hasNext() )
      ((TreeChangeListener)i.next()).notifyNodeAdded( leaf );

    return leaf;
  }

  /**
   * Attaches a new internal node to the supplied node,
   * along the specified arc.
   *
   * @param parent The node in the current tree to attach
   *        the internal node to.  If the node is null, the
   *        new internal node becomes the root of the tree.
   *
   * @param arcNum The arc number (or attribute value
   *        index) along which to attach the new node.
   *
   * @param attributePosition The position of the
   *        attribute used to split at the new node, relative
   *        to the other attributes in the dataset.
   *
   * @param att The attribute used to split at the new
   *        node.
   *
   * @param mask The updated mask, with the additional
   *        arc to the new node <i>already</i> masked off.
   *
   * @return A reference to the new internal node.
   */
  public DecisionTreeNode addInternalNode( DecisionTreeNode parent,
      int arcNum,
      int attributePosition,
      Attribute att,
      AttributeMask mask,
      int numTrainingExamplesReachHere,
      int bestTrainingTargetIndex,
      int numTrainingEgsCorrectClassUsingBestTrainingIndex,
      int numTestingEgsCorrectClassUsingBestTrainingIndex,
      int numTestingExamplesReachHere,
      int bestTestingTargetIndex,
      int numTestingEgsCorrectClassUsingBestTestingIndex,
      int numTrainingEgsCorrectClassUsingBestTestingIndex )
  {
    // Create a new internal node.
    DecisionTreeNode internal =
      new DecisionTreeNode( parent, new String( att.getName() ),
                            att.getValueNames().toArray(), mask );

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

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

    // Update the tree statistics.
    m_internalNodes++;

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

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

    //--------------------- Debug ---------------------
    if( DEBUG_ON ) {
      System.out.print( "DecisionTree::addInternalNode: " +
        "Added internal node '" + att.getName() + "'" );

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

    // Inform any listeners that a node was added.
    Iterator i = m_treeChangeListeners.iterator();

    while( i.hasNext() )
      ((TreeChangeListener)i.next()).notifyNodeAdded( internal );

    return internal;
  }

  /**
   * Search through the current tree and return the first
   * node without a complete set of children.  The arc
   * number for the first missing child is returned in
   * position 0 of the arcNum array.
   *
   * @param node The node at which to begin the search.
   *
   * @param arcNum An integer array of size 1.  The arc
   *        number for the first missing child is
   *        returned in arcNum[0].
   *
   * @return A reference to the first incomplete node
   *         in the tree (farthest left).  The method
   *         returns null if the tree is already complete,
   *         or if the tree is empty.
   */
  public DecisionTreeNode
    findIncompleteNode( DecisionTreeNode node, int[] arcNum )
  {
    // The search is recursive - at some point, we
    // may want to change this to a non-recursive
    // algorithm (if we start dealing with extremely
    // large trees?)

    // Base cases.
    if( node == null || node.isLeaf() ) return null;

    // Recursive case. This node is not a leaf - so descend.
    for( int i = 0; i < node.getArcLabelCount(); i++ ) {
      DecisionTreeNode nextNode;

      if( (nextNode =
        findIncompleteNode( node.getChild(i), arcNum )) != null )
        return nextNode;
    }

    if( (arcNum[0] = node.getFirstMissingChild()) >= 0 ) {
      // We found a node with a missing child, which
      // is already stored in arcNum - so return this
      // node.

      //--------------------- Debug ---------------------
      if( DEBUG_ON ) {
        System.out.println( "DecisionTree::findIncompleteNode: " +
          "Found vacant branch (position " + (arcNum[0]+1) + ") at node '" +
          node.getLabel() + "'." );
        System.out.println();
      }

      return node;
    }

    // We searched all the subtrees attached to this
    // node, and didn't find anything, so return null.
    return null;
  }

  /**
   * Removes the most-recently added node from the tree.
   * Repeated calls to this method can be used to 'reverse'
   * the tree construction or pruning process.
   *
   * <p>
   * If the tree is empty, this method has no effect.
   */
  public void backup()
  {
    if( this.isEmpty() ) {
      //--------------------- Debug ---------------------
      if( DEBUG_ON ) {
        System.out.println( "DecisionTree:backup: Tree is " +
          "empty, can't backup any further." );
        System.out.println();
      }

      return;
    }

    pruneSubtree( (DecisionTreeNode)m_nodes.get( m_nodes.size() - 1 ) );
  }

  /**
   * Prunes off the subtree starting at the supplied root.
   *
   * @param pruneRoot The root of the subtree to remove.
   */
  public void pruneSubtree( DecisionTreeNode pruneRoot )
  {
    if( pruneRoot == null ) return;

    // Detach the root node of the subtree.
    pruneRoot.detach();

    // Once a node has been removed, the tree is no longer complete.
    m_complete = false;

    // Now, tell the tree to remove all the
    // node's children.
    recursiveRemoveSubtree( pruneRoot );
  }

  /**
   * Recursively descends through the tree, removing
   * the supplied node and any descendants from
   * the internal node list.
   *
   * @param node The root node of the subtree to remove.
   */
  public void recursiveRemoveSubtree( DecisionTreeNode node )
  {
    if( node == null ) return;

    // First, recursively remove all the node's children.
    // (This loop doesn't run if the node is a leaf node)
    for( int i = 0; i < node.getArcLabelCount(); i++ )
      if( node.getChild( i ) != null )
        recursiveRemoveSubtree( node.getChild( i ) );

    // Remove this node from the vector.
    m_nodes.remove( node );

    //--------------------- Debug ---------------------
    if( DEBUG_ON ) {
      System.out.println( "DecisionTree::recursiveRemoveSubtree: Removed " +
        "node '" + node.getLabel() + "' from tree." );
      System.out.println( "DecisionTree::recursiveRemoveSubtree: Tree now " +
        "contains " + m_nodes.size() + " nodes." );
      System.out.println();
    }

    // If the node was a leaf, then we have to update
    // the classification statistics.
    if( node.isLeaf() ) {
      m_trainingCorrect -=
        node.getTrainingEgsCorrectClassUsingBestTrainingIndex();
      m_testingCorrect  -=
        node.getTestingEgsCorrectClassUsingBestTrainingIndex();
    }
    else
      m_internalNodes--;

    // Inform any listeners that a node was removed.
    Iterator i = m_treeChangeListeners.iterator();

    while( i.hasNext() )
      ((TreeChangeListener)i.next()).notifyNodeRemoved( node );
  }

  /**
   * Sets the given node's flag value.  This method exist
   * here in order to allow the tree to notify
   * TreeChangeListeners that may be tracking the state of
   * the tree.
   */
  public void flagNode( DecisionTreeNode node, int flagValue )
  {
    node.setFlag( flagValue );

    // Inform any listeners that a node was modified.
    Iterator i = m_treeChangeListeners.iterator();

    while( i.hasNext() )
      ((TreeChangeListener)i.next()).notifyNodeModified( node );
  }
}