gentreealgorithm.java

一个数据挖掘软件ALPHAMINERR的整个过程的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.
 */

/**
 * Title: XELOPES Data Mining Library
 * Description: The XELOPES library is an open platform-independent and data-source-independent library for Embedded Data Mining.
 * Copyright: Copyright (c) 2002 Prudential Systems Software GmbH
 * Company: ZSoft (www.zsoft.ru), Prudsys (www.prudsys.com)
 * @author Valentine Stepanenko ([e-mail])
 * @author Michael Thess
 * @version 1.0
 */

package com.prudsys.pdm.Models.Classification.DecisionTree.Algorithms.GenTree;

import com.prudsys.pdm.Core.CategoricalAttribute;
import com.prudsys.pdm.Core.IterativeMiningAlgorithm;
import com.prudsys.pdm.Core.MiningException;
import com.prudsys.pdm.Models.Classification.DecisionTree.DecisionTreeAlgorithm;
import com.prudsys.pdm.Models.Supervised.Classifier;

/**
 * Realization of general tree algorithm.
 */
public class GenTreeAlgorithm extends DecisionTreeAlgorithm implements IterativeMiningAlgorithm
{
    // Impurity measures:
    public static final int FS_InfGain      = 0;
    public static final int FS_InfGain_MC   = 1;
    public static final int FS_GainRatio    = 2;
    public static final int FS_GainRatio_MC = 3;
    public static final int FS_Chi2         = 4;  // not supported
    public static final int FS_Chi2_MC      = 5;  // not supported
    public static final int FS_Chi2Prob     = 6;  // not supported
    public static final int FS_Chi2Prob_MC  = 7;  // not supported
    public static final int FS_Gini         = 8;  // not supported
    public static final int FS_Gini_MC      = 9;  // not supported

    // Discretization type of numeric attributes:
    public static final int D_InfGain       = 0;
    public static final int D_MDLP          = 1;  // not supported

    /** Type of impurity measure. */
    protected int impurityMeasureType       = FS_InfGain;

    /** Discretization type of numeric attributes. */
    protected int discreteType              = D_InfGain;

    /** Root node. */
    private GenTreeNode root                = null;

    /** Iterative mode. Splits one node in every step. */
    private boolean iterativeMode           = false;

    /** Iterative mode. Are new iterations neccessary? */
    private boolean iterationImprovement    = true;

    /** Iterative mode. Current level of nodes. */
    private int level                       = 0;

    /** Debug. 0 - no debugging. */
    private int debug = 0;

    /**
     * Empty constructor.
     */
    public GenTreeAlgorithm()
    {
    }

    /**
     * Runs general tree algorithm.
     *
     * @throws MiningException
     */
    protected void runAlgorithm() throws MiningException
    {
        // Create root node:
        if (!iterativeMode || root == null) {
          root = new GenTreeNode( this, miningInputStream, metaData, target );
          root.calculateScore();
        };

        // Build complete tree:
        if (!iterativeMode) {
          root.buildTree();
          return;
        };

        // Iterative mode:
        GenTreeNode node = root;
        int iniLevel     = level;

        // Find next node to split:
        boolean foundSplitNode = false;
        while (! foundSplitNode) {
          if (debug > 0) System.out.println("level: " + level);

          // Root node in first step:
          if (node.getChildCount() == 0 && node.getLevel() == 0) {
            foundSplitNode = true;
            level = 1;
            continue;
          };

          // Switch to higher level if not root:
          if (node.currChild == node.getChildCount() && node.getChildCount() > 0) {
            // Root:
            if (node == root) {
              // No further splitting node found => break:
              if (iniLevel < level) break;

              // Grow tree to new level:
              level = level + 1;
              node.currChild = 0;
              continue;
            };

            // Not root:
            node.currChild = 0;
            node = (GenTreeNode) node.getParent();
            node.currChild = node.currChild + 1;
            continue;
          };

          // Intermediate node:
          if (node.getLevel() < level) {
            GenTreeNode tNode = (GenTreeNode) node.getChildAt( node.currChild );
            if (tNode.isLeaf()) node.currChild = node.currChild + 1;
            else node = tNode;
          }
          // Final node level:
          else {
            foundSplitNode = true;
            ((GenTreeNode) node.getParent()).currChild++;
          };

        };

        // Split new node:
        if (foundSplitNode) node.buildTree();
        else{
          if (debug > 0) System.out.println("No node for splitting found");
        };
        iterationImprovement = foundSplitNode;

        if (debug > 0) System.out.println("--------------------------------------");
    }

    /**
     * Returns decision tree classifier.
     *
     * @return decision tree classifier
     */
    protected Classifier getClassifier()
    {
        return root;
    }

    /**
     * Returns type of impurity measure.
     *
     * @return type of impurity measure
     */
    public int getImpurityMeasureType()
    {
      return impurityMeasureType;
    }

    /**
     * Sets new type of impurity measure.
     *
     * @param impurityMeasureType new type of impurity measure
     */
    public void setImpurityMeasureType(int impurityMeasureType)
    {
      this.impurityMeasureType = impurityMeasureType;
    }

    /**
     * Returns discretization type of numeric attributes.
     *
     * @return discretization type of numeric attributes
     */
    public int getDiscreteType()
    {
      return discreteType;
    }

    /**
     * Sets discretization type of numeric attributes.
     *
     * @param discreteType new discretization type of numeric attributes
     */
    public void setDiscreteType(int discreteType)
    {
      this.discreteType = discreteType;
    }

    /**
     * Is iterative mode?
     *
     * @return true if iterative mode, otherwise false
     */
    public boolean isIterativeMode()
    {
      return iterativeMode;
    }

    /**
     * Sets iterative mode.
     *
     * @param iterativeMode new iterative mode
     */
    public void setIterativeMode(boolean iterativeMode)
    {
      this.iterativeMode = iterativeMode;
    }

    /**
     * Will further iterations improve the results? If false,
     * you can finish the iteration process.
     *
     * @return true if improvement expected, otherwise false
     */
    public boolean isIterationImprovement() {

      return iterationImprovement;
    }

    /**
     * Resets iteration process before first iteration step.
     *
     * @exception MiningException cannot reset iteration process
     */
    public void resetIterations() throws MiningException {

      root = null;
      level = 0;
      iterationImprovement = true;
    }

    /**
     * Checks mining algorithm for completeness by calling verify method
     * of superclass. Adiitionally, it checks whether the target attribute
     * is categorical.
     *
     * @throws IllegalArgumentException if some algorithm attributes are incorrect
     */
    public void verify() throws IllegalArgumentException
    {
      super.verify();

      if (! (target instanceof CategoricalAttribute))
        throw new IllegalArgumentException("GenTree requires categorical target attribute");
    }
}