source: branches/MetisMQI/src/main/java/weka/classifiers/rules/part/C45PruneableDecList.java

/*
 *    This program 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.
 *
 *    This program 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 this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    C45PruneableDecList.java
 *    Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.classifiers.rules.part;

import weka.classifiers.trees.j48.Distribution;
import weka.classifiers.trees.j48.ModelSelection;
import weka.classifiers.trees.j48.NoSplit;
import weka.classifiers.trees.j48.Stats;
import weka.core.Instances;
import weka.core.RevisionUtils;
import weka.core.Utils;

/**
 * Class for handling a partial tree structure pruned using C4.5's
 * pruning heuristic.
 *
 * @author Eibe Frank (eibe@cs.waikato.ac.nz)
 * @version $Revision: 1.9 $
 */
public class C45PruneableDecList
  extends ClassifierDecList{

  /** for serialization */
  private static final long serialVersionUID = -2757684345218324559L;
    
  /** CF */
  private double CF = 0.25;
  
  /**
   * Constructor for pruneable tree structure. Stores reference
   * to associated training data at each node.
   *
   * @param toSelectLocModel selection method for local splitting model
   * @param cf the confidence factor for pruning
   * @param minNum the minimum number of objects in a leaf
   * @exception Exception if something goes wrong
   */
  public C45PruneableDecList(ModelSelection toSelectLocModel, 
                             double cf, int minNum) 
       throws Exception {
                               
    super(toSelectLocModel, minNum);
    
    CF = cf;
  }
 
  /**
   * Builds the partial tree without hold out set.
   *
   * @exception Exception if something goes wrong
   */
  public void buildDecList(Instances data, boolean leaf) throws Exception {
    
    Instances [] localInstances,localPruneInstances;
    int index,ind;
    int i,j;
    double sumOfWeights;
    NoSplit noSplit;
    
    m_train = null;
    m_test = null;
    m_isLeaf = false;
    m_isEmpty = false;
    m_sons = null;
    indeX = 0;
    sumOfWeights = data.sumOfWeights();
    noSplit = new NoSplit (new Distribution((Instances)data));
    if (leaf)
      m_localModel = noSplit;
    else
      m_localModel = m_toSelectModel.selectModel(data);
    if (m_localModel.numSubsets() > 1) {
      localInstances = m_localModel.split(data);
      data = null;
      m_sons = new ClassifierDecList [m_localModel.numSubsets()];
      i = 0;
      do {
        i++;
        ind = chooseIndex();
        if (ind == -1) {
          for (j = 0; j < m_sons.length; j++) 
            if (m_sons[j] == null)
              m_sons[j] = getNewDecList(localInstances[j],true);
          if (i < 2) {
            m_localModel = noSplit;
            m_isLeaf = true;
            m_sons = null;
            if (Utils.eq(sumOfWeights,0))
              m_isEmpty = true;
            return;
          }
          ind = 0;
          break;
        } else 
          m_sons[ind] = getNewDecList(localInstances[ind],false);
      } while ((i < m_sons.length) && (m_sons[ind].m_isLeaf));
      
      // Check if all successors are leaves
      for (j = 0; j < m_sons.length; j++) 
        if ((m_sons[j] == null) || (!m_sons[j].m_isLeaf))
          break;
      if (j == m_sons.length) {
        pruneEnd();
        if (!m_isLeaf) 
          indeX = chooseLastIndex();
      }else 
        indeX = chooseLastIndex();
    }else{
      m_isLeaf = true;
      if (Utils.eq(sumOfWeights, 0))
        m_isEmpty = true;
    }
  }
 
  /**
   * Returns a newly created tree.
   *
   * @exception Exception if something goes wrong
   */
  protected ClassifierDecList getNewDecList(Instances data, boolean leaf) 
       throws Exception {
         
    C45PruneableDecList newDecList = 
      new C45PruneableDecList(m_toSelectModel,CF, m_minNumObj);
    
    newDecList.buildDecList((Instances)data, leaf);
    
    return newDecList;
  }

  /**
   * Prunes the end of the rule.
   */
  protected void pruneEnd() {
    
    double errorsLeaf, errorsTree;
    
    errorsTree = getEstimatedErrorsForTree();
    errorsLeaf = getEstimatedErrorsForLeaf();
    if (Utils.smOrEq(errorsLeaf,errorsTree+0.1)) { // +0.1 as in C4.5
      m_isLeaf = true;
      m_sons = null;
      m_localModel = new NoSplit(localModel().distribution());
    }
  }
  
  /**
   * Computes estimated errors for tree.
   */
  private double getEstimatedErrorsForTree() {

    if (m_isLeaf)
      return getEstimatedErrorsForLeaf();
    else {
      double error = 0;
      for (int i = 0; i < m_sons.length; i++) 
        if (!Utils.eq(son(i).localModel().distribution().total(),0))
          error += ((C45PruneableDecList)son(i)).getEstimatedErrorsForTree();
      return error;
    }
  }
  
  /**
   * Computes estimated errors for leaf.
   */
  public double getEstimatedErrorsForLeaf() {
  
    double errors = localModel().distribution().numIncorrect();

    return errors+Stats.addErrs(localModel().distribution().total(),
                                errors,(float)CF);
  }
  
  /**
   * Returns the revision string.
   * 
   * @return            the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 1.9 $");
  }
}