categoryhierarchy.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.Core;

import java.util.Vector;

import com.prudsys.pdm.Adapters.PmmlVersion20.ChildParent;
import com.prudsys.pdm.Adapters.PmmlVersion20.InlineTable;
import com.prudsys.pdm.Adapters.PmmlVersion20.Member;
import com.prudsys.pdm.Adapters.PmmlVersion20.Pargroup;
import com.prudsys.pdm.Adapters.PmmlVersion20.Row;
import com.prudsys.pdm.Adapters.PmmlVersion20.Taxonomy;
import com.prudsys.pdm.Utils.IntHashtable;
import com.prudsys.pdm.Utils.IntVector;

/**
  * Defines a hierarchy ordering (aka taxonomy) between groups
  * of items. <p>
  *
  * From CWM Data Mining. <p>
  *
  * Superclasses:
  * <ul>
  *   <li> Class
  * </ul>
  *
  * Extended for PDM. <p>
  *
  * The taxonomy is given as a Directed Acyclic Graph (DAG)
  * modeled by the MiningHierarchyNode nodes.
  *
  * In addition, functionality from PMML was added.
  * It corresponds to the PMML element Taxonomy.
  *
  * @see Category
  * @see CategoricalAttribute
  * @see MiningHierarchyNode
  * @see com.prudsys.pdm.Adapters.PmmlVersion20.Taxonomy
  */
public class CategoryHierarchy extends com.prudsys.pdm.Cwm.Core.Class implements PmmlPresentable
{
  // -----------------------------------------------------------------------
  //  Variables declarations
  // -----------------------------------------------------------------------
  /** Name of the category hierarchy. Now inherited from ModelElement. */
//  private String name = "categoryHierarchy";

  /** Vector of nodes of the DAG. Nodes are of the type MiningHierarchyNode. */
  protected Vector nodes = new Vector();

  /** Hashtable of nodes with categories as keys and node indexes as values. */
  protected IntHashtable nodesHash = new IntHashtable();

  /** Is the graph level-based? */
  protected boolean levelBased = false;

  // -----------------------------------------------------------------------
  //  Constructor
  // -----------------------------------------------------------------------
  /**
   * Empty constructor.
   */
  public CategoryHierarchy()
  {
    this.setName("categoryHierarchy");
  }

  // -----------------------------------------------------------------------
  //  Methods of taxonomy handling
  // -----------------------------------------------------------------------
  /**
   * Add is-a relationship to DAG.
   *
   * @param parent parent category
   * @param child child category
   * @exception MiningException parent is child's child (cycle!)
   */
  public void addRelationship(Category parent, Category child)
    throws MiningException {

    if (parent == null) throw new MiningException("parent is null");
    if (child == null)  throw new MiningException("child is null");

    // Look for parent and child nodes:
    MiningHierarchyNode par = findNodeOfCategory(parent);
    MiningHierarchyNode cld = findNodeOfCategory(child);

    // Parent and child exist. Make sure there will be no cycle:
    if (par != null && cld != null) {

      // Parent is already assigned to child:
      if (cld.getParentIndex(par) >= 0)
        return;

      // Parent equals child:
      if ( par.equals(cld) )
        throw new MiningException("Illegal relationship: parent and child are equal!");

      // Check for cycle:
      Vector grandpars = getAllParents( (Category)par.getNodeValue() );
      for (int i = 0; i < grandpars.size(); i++) {
        Category grandpa = (Category) grandpars.elementAt(i);
        if ( grandpa.equals(child) )
          throw new MiningException("Illegal relationship: parent is child's child!");
      };
    };

    // Child does not exist - create:
    if (cld == null) {
      cld = new MiningHierarchyNode();
      cld.setNodeValue(child);
      cld.setLeaf(true);
      cld.setRoot(false);
      nodes.addElement(cld);
      nodesHash.put( child, nodes.size()-1 );
    };

    // Parent does not exist - create:
    if (par == null) {
      par = new MiningHierarchyNode();
      par.setNodeValue(parent);
      par.setRoot(true);
      par.setLeaf(false);
      nodes.addElement(par);
      nodesHash.put( parent, nodes.size()-1 );
    };

    // Set relation:
    par.addChildNode(cld);
    par.setLeaf(false);
    par.setLevel(-1);

    cld.addParentNode(par);
    cld.setRoot(false);
    cld.setLevel(-1);

    levelBased = false;
  }

  /**
   * Returns number of relationships of DAG.
   *
   * @return number of relationships of DAG
   */
  public int getNumberOfRelationships() {

    int nrel = 0;
    for (int i = 0; i < nodes.size(); i++) {
      MiningHierarchyNode chn = (MiningHierarchyNode) nodes.elementAt(i);
      nrel = nrel + chn.getParentsCount();
    };
    return nrel;
  }

  /**
   * Is current DAG level-based? If not, use method calcLevels to
   * create levels (if possible).
   *
   * @return true is level-based, false otherwise
   */
  public boolean isLevelBased() {

    return levelBased;
  }

  /**
   * Calculates all levels for the hierarchy nodes.
   *
   * @throws MiningException graph is not level-based
   */
  public void calcLevels() throws MiningException {

    calcLevels(false);
  }

  /**
   * Calculates all levels for the hierarchy nodes. If the parameter
   * 'anyway' is true, levels are calculated even if the graph is
   * not level-based. Otherwise, a corresponding exception is thrown.
   *
   * @param anyway calculate anyway
   * @throws MiningException graph is not level-based for false 'anyway'
   */
  public void calcLevels(boolean anyway) throws MiningException {

    // Init levels:
    Vector roots = new Vector();
    for (int i = 0; i < nodes.size(); i++) {
      MiningHierarchyNode node = (MiningHierarchyNode) nodes.elementAt(i);
      if ( node.isRoot() ) {
        node.setLevel(0);
        roots.addElement(node);
      }
      else
        node.setLevel(-1);
    }

    // Enter all roots and determine levels of their trees:
    for (int i = 0; i < roots.size(); i++) {
      MiningHierarchyNode root = (MiningHierarchyNode) roots.elementAt(i);
      calcNodeLevels(root, anyway);
    }

    levelBased = true;
  }

  /**
   * Determines levels of nodes by recursively calling this method.
   *
   * @param node parent node to traverse
   * @param anyway calculate anyway
   * @throws MiningException DAG is not level-based for false 'anyway'
   */
  private void calcNodeLevels(MiningHierarchyNode node, boolean anyway) throws MiningException {

     int nodeLevel = node.getLevel();
     for (int i = 0; i < node.getChildCount(); i++) {
       MiningHierarchyNode child = node.getChildAt(i);
       int childLevel = child.getLevel();
       if (childLevel == -1) {
         child.setLevel(nodeLevel + 1);
         calcNodeLevels(child, anyway);
       }
       else {
         if (!anyway && childLevel != nodeLevel + 1)
           throw new MiningException("graph is not level-based");
       }
     };
  }

  /**
   * Get direct parents of a given child category.
   *
   * @param child child category
   * @return vector of direct parent categories
   */
  public Vector getParents(Category child) {

    Vector parCats = new Vector();

    // Look for child node:
    MiningHierarchyNode cld = findNodeOfCategory(child);

    // Node not found => no parents:
    if (cld == null)
      return parCats;

    // Return parents:
    for (int i = 0; i < cld.getParentsCount(); i++)
      parCats.addElement( cld.getParentAt(i).getNodeValue() );

    return parCats;
  }

  /**
   * Get direct children of a given parent.
   *
   * @param parent parent category
   * @return vector of direct child categories
   */
  public Vector getChildren(Category parent) {

    Vector cldCats = new Vector();

    // Look for child node:
    MiningHierarchyNode par = findNodeOfCategory(parent);

    // Node not found => no children:
    if (par == null)
      return cldCats;

    // Return children:
    for (int i = 0; i < par.getChildCount(); i++)
      cldCats.addElement( par.getChildAt(i).getNodeValue() );

    return cldCats;
  }

  /**
   * Get all parents of a given child category.
   *
   * @param child child category
   * @return vector of all parent categories
   */
  public Vector getAllParents(Category child) {

    Vector parCats = new Vector();

    // Look for child node:
    MiningHierarchyNode cld = findNodeOfCategory(child);

    // Node not found => no parents:
    if (cld == null)
      return parCats;

    // Get all parents recursively:
    Vector allPars     = new Vector();
    MiningHierarchyNode node = cld;
    IntVector parup    = new IntVector();
    IntVector childown = new IntVector();
    parup.addElement(-1);
    childown.addElement(-1);
    int lev        = 0;
    boolean newpar = true;
    while (newpar) {
      int ipar = parup.IntegerAt(lev);
      if (ipar < node.getParentsCount() - 1) {
        ipar = ipar + 1;
        parup.setElementAt(ipar, lev);
        MiningHierarchyNode par = node.getParentAt(ipar);
        if (allPars.indexOf(par) < 0) allPars.addElement(par);
        lev = lev + 1;
        if (parup.size() <= lev) {
          parup.addElement(-1);
          childown.addElement( par.getChildIndex(node) );
        }
        else {
          parup.setElementAt(-1, lev);
          childown.setElementAt( par.getChildIndex(node), lev );
        }
        node = par;
      }
      else {
        ipar = -1;
        parup.setElementAt(ipar, lev);
        if (lev > 0) {
          cld = node.getChildAt(childown.IntegerAt(lev));
          lev = lev - 1;
          node = cld;
        }
        else
          newpar = false;
      };
    }

    // Extract parent categories:
    for (int i = 0; i < allPars.size(); i++) {
      Category parCat = (Category) ((MiningHierarchyNode) allPars.elementAt(i)).getNodeValue();
      if (parCats.indexOf(parCat) < 0) parCats.addElement(parCat);
    };

    return parCats;
  }

  /**
   * Get all children of a given parent.
   *
   * @param parent parent category
   * @return vector of all child categories
   */
  public Vector getAllChildren(Category parent) {

    Vector cldCats = new Vector();

    // Look for child node:
    MiningHierarchyNode par = findNodeOfCategory(parent);

    // Node not found => no children:
    if (par == null)
      return cldCats;

    // Get all children recursively:
    Vector allClds     = new Vector();
    MiningHierarchyNode node = par;
    IntVector childown = new IntVector();
    IntVector parup    = new IntVector();
    childown.addElement(-1);
    parup.addElement(-1);
    int lev        = 0;
    boolean newcld = true;
    while (newcld) {
      int icld = childown.IntegerAt(lev);
      if (icld < node.getChildCount() - 1) {
        icld = icld + 1;
        childown.setElementAt(icld, lev);
        MiningHierarchyNode cld = node.getChildAt(icld);
        if (allClds.indexOf(cld) < 0) allClds.addElement(cld);
        lev = lev + 1;
        if (childown.size() <= lev) {
          childown.addElement(-1);
          parup.addElement( cld.getParentIndex(node) );
        }
        else {
          childown.setElementAt(-1, lev);
          parup.setElementAt( cld.getParentIndex(node), lev );
        }
        node = cld;
      }
      else {
        icld = -1;
        childown.setElementAt(icld, lev);
        if (lev > 0) {
          par = node.getParentAt( parup.IntegerAt(lev) );
          lev = lev - 1;
          node = par;
        }
        else
          newcld = false;
      };
    };

    // Extract child categories:
    for (int i = 0; i < allClds.size(); i++) {
      Category cldCat = (Category) ((MiningHierarchyNode) allClds.elementAt(i)).getNodeValue();
      if (cldCats.indexOf(cldCat) < 0) cldCats.addElement(cldCat);
    };

    return cldCats;
  }

  /**
   * Return all root nodes of the DAG.
   *
   * @return vector Categories of all root nodes
   */
  public Vector getAllRoots() {

    Vector allRoots = new Vector();

    for (int i = 0; i < nodes.size(); i++) {
      MiningHierarchyNode chn = (MiningHierarchyNode) nodes.elementAt(i);
      if (chn.isRoot())