apriori.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:        prudsys basket analysis
 * Description:  Basket analysis algorithms
 * Copyright:    Copyright (c) 2001
 * Company:      PRUDENTIAL SYSTEMS SOFTWARE GmbH
 * @author Stefan Ludwig
 * @author Michael Thess
 * @version 1.0
 */
package com.prudsys.pdm.Models.AssociationRules.Algorithms.AprioriSimple;

import java.util.Hashtable;
import java.util.Iterator;
import java.util.Vector;

import com.prudsys.pdm.Core.Category;
import com.prudsys.pdm.Core.MiningException;
import com.prudsys.pdm.Input.MiningInputStream;
import com.prudsys.pdm.Input.MiningVector;
import com.prudsys.pdm.Models.AssociationRules.AssociationRulesAlgorithm;
import com.prudsys.pdm.Models.AssociationRules.ItemSet;
import com.prudsys.pdm.Utils.IntVector;

/**
 * Apriori - Data Mining Algorithm. Old implementation of 1999
 * by Stefan Ludwig. New implementation in AprioriOptimized
 * by Alexej Grinyuk is magnitudes faster.
 *
 * @author Stefan Ludwig
 * @author Michael Thess
 * @version 1.3, 2002/08/12
 */
public class Apriori extends AssociationRulesAlgorithm {

  static boolean dbg = false;

  /** Minimum number of supporting transactions, only used if >0. */
  private int minimumSupportCount = 0;

  /** Minimum item site. */
  private int    minimumItemSize = 1;

  /** Maximum item size. */
  private int    maximumItemSize = -1;

  /** Generate association rules after large itemsets. */
  private boolean generateRules = true;

  /** Transaction set. */
  private TransactionSet transSet = null;

  /** Association rules. */
  private Vector associationRules;

  /** Large itemsets. */
  private Vector largeItemSets;

  /**
   * Returns vector of association rules.
   *
   * @return vector of associaltion rules (RuleSet)
   */
  public Vector getAssociationRules()
  {
     return associationRules;
  }

  /**
   * Returns vector of large itemsets.
   *
   * @return vector of large itemsets (ItemSet)
   */
  public Vector getLargeItemSets()
  {
     return largeItemSets;
  }

  /**
   * Sets minimum item size.
   *
   * @param minimumItemSize minimum item size
   */
  public void setMinimumItemSize(int minimumItemSize)
  {
    this.minimumItemSize = minimumItemSize;
  }

  /**
   * Sets maximum item size (-1: unbounded).
   *
   * @param maximumItemSize maximum item size
   */
  public void setMaximumItemSize(int maximumItemSize)
  {
    this.maximumItemSize = maximumItemSize;
  }

  /**
   * Sets generate association rules.
   *
   * @param generateRules generate association rules
   */
  public void setGenerateRules(boolean generateRules)
  {
    this.generateRules = generateRules;
  }

  /**
   * Returns minimum number of transactions containing item pairs.
   * The relative minimum support value is defined by the minimumSupport
   * parameter.
   *
   * @return minimum support count
   */
  public int getMinimumSupportCount()
  {
    return minimumSupportCount;
  }

  /**
   * Sets minimum number of transactions containing item pairs.
   * The relative minimum support value is defined by the minimumSupport
   * parameter.
   *
   * @param minimumSupportCount new minimum support count
   */
  public void setMinimumSupportCount(int minimumSupportCount)
  {
    this.minimumSupportCount = minimumSupportCount;
  }

  /**
   * Checks mining algorithm for completeness by calling verify method
   * of superclass. Adiitionally, it checks whether minimumItemSize and
   * maximumItemSize are admissible.
   *
   * @throws IllegalArgumentException if some algorithm attributes are incorrect
   */
  public void verify() throws IllegalArgumentException
  {
    super.verify();
    if (minimumItemSize < 0)
      throw new IllegalArgumentException("minimumItemSize can't be negative");
    if (maximumItemSize > -1 && minimumItemSize > maximumItemSize)
      throw new IllegalArgumentException("minimumItemSize can't be larger than maximumItemSize");
  }

  /**
   * Implements the Algorithm Apriori. If a transactionId or itemId
   * has a missing value, the (transactionId, itemId)-pair is ignored.
   *
   * @exception MiningException cannot run algorithm
   */
  public void runAlgorithm() throws MiningException
  {
    // Convert input stream to transaction set when called for first time:
    if (transSet == null)
    {
       transSet = convertMiningInputStream( miningInputStream );
    };

    // Run algorithm:
    AprioriResult apRes = AprioriAlg();

    // Transform result:
    associationRules = new Vector();
    RuleSetList rsl  = apRes.getAssociationRules();
    for (int i = 0; i < rsl.getSize(); i++)
      if (rsl.getRuleSetAt(i).getSize() >= minimumItemSize)
        associationRules.add( rsl.getRuleSetAt(i) );

    largeItemSets = new Vector();
    ItemSetList isl  = apRes.getLargeItemSets();
    for (int i = 0; i < isl.getSize(); i++)
    {
        // Add all itemset
        //if (isl.getItemSetAt(i).getSize() >= minimumItemSize)
        largeItemSets.add( isl.getItemSetAt(i) );
    }
  }

  /**
   * Implements the Algorithm Apriori (by Rakesh Agrawal).
   *
   * @return result as list of association rules
   */
  public AprioriResult AprioriAlg() {

    // Init transaction set:
    transSet.init();

    // Get tree of large itemsets:
    ItemTree itree = getItemTree(transSet);

    // Find association rules:
    ItemSetList largeItemSetList = null;
    RuleSetList ruleSetList = new RuleSetList();
    if (generateRules) {
      if (dbg) System.out.println("Now generating association rules...");
      largeItemSetList = itree.genrules(transSet, ruleSetList, minimumConfidence);
    }
    else
      largeItemSetList = itree.getLargeItemSetList(itree.tree);

    // Create and return result:
    return new AprioriResult(ruleSetList, largeItemSetList);
 }

  /**
   * Implements the part of finding large itemsets of
   * Algorithm Apriori (by Rakesh Agrawal).
   *
   * @param transSet transaction set
   * @return result as list of large itemsets
   */
  protected ItemSetList AprioriAlgLITS(TransactionSet transSet) {

    // Init transaction set:
    transSet.init();

    // Get tree of large itemsets:
    ItemTree itree = getItemTree(transSet);

    // Copy large itemsets:
    ItemSetList largeItemSetList = itree.getLargeItemSetList(itree.tree);
    if (dbg) System.out.println("L A R G E  Itemset list:");
    if (dbg) largeItemSetList.print();

    return largeItemSetList;
 }

 /**
  * Create tree of large itemsets.
  *
  * @param transSet transaction set
  * @return tree of large itemsets
  */
  private ItemTree getItemTree(TransactionSet transSet) {

    // Create list of large itemsets:
    ItemSetList largeItemSetList = new ItemSetList();

    // Determine minimal support: