flatrulesalgorithm.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

/**
 * 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 Michael Thess
 * @version 1.2
 */

package com.prudsys.pdm.Models.AssociationRules.Algorithms.FlatRules;

import java.util.*;
import java.lang.Math;

import com.prudsys.pdm.Core.*;
import com.prudsys.pdm.Core.Event.AlgorithmStatusMessage;
import com.prudsys.pdm.Core.Event.Status.*;
import com.prudsys.pdm.Input.*;
import com.prudsys.pdm.Models.AssociationRules.*;
import com.prudsys.pdm.Models.AssociationRules.Event.CreationModelEndMessageAssociationRules;
import com.prudsys.pdm.Utils.*;

/**
 * Flat association rules algorithm. Finds only one-to-one rules:
 * item1 => item2. In addition, minimum support and confidence
 * can be set to zero without computational problems. <p>
 *
 * This is a very simple association rules algorithm that determines
 * similarity between all pairs of items that share at least one
 * common transaction. Unlike classic association rules algorithms
 * it first finds the rules and than adds the itemsets (if desired). <p>
 *
 * The advantage of this algorithm is that it delivers rules for all
 * items that are included in at leaest one transaction. This makes
 * this algorithm well suited for recommendation engines.
 */
public class FlatRulesAlgorithm extends AssociationRulesAlgorithm implements MiningListener
{
    // -----------------------------------------------------------------------
    //  Constants of order type of rule ordering
    // -----------------------------------------------------------------------
    /** Order rules by descreasing support. */
    public static final int ORDER_SUPP = 0;

    /** Order rules by decreasing confidence. */
    public static final int ORDER_CONF = 1;

    /** Order rules by decreasing support*confidence. */
    public static final int ORDER_SUPP_CONF = 2;

    /** Order rules by decreasing lift. */
    public static final int ORDER_LIFT = 3;

    // -----------------------------------------------------------------------
    //  Variables declarations
    // -----------------------------------------------------------------------
    /** Minimum support count. User-defined. */
    private int minimumSupportCount = 0;

    /** Minimum support count. */
    private int minimumSuppCount = 1;

    /** Minimum number of rules for a premise item. */
    private int minimumItemSize = 1;

    /** Maximum number of rules for a premise item. */
    private int maximumItemSize = -1;

    /** Type of decreasing ordering of rules (supp, conf, supp*conf, lift). */
    private int rulesOrderType = ORDER_LIFT;

    /** Debug level. */
    private int debug = 1;

    /** Vector of association rules. */
    private Vector associationRules;

    /** Vector of large itemsets. */
    private Vector largeItemSets;

    /** Do also create large itemsets (beside association rules). */
    private boolean createLargeItemSets = true;

    /** Number of different items. */
    private int nItems = 0;

    /** Number of transactions. */
    private int nTransact = 0;

    /** Hashtable of items. Points to itemTrans, itemNeighb, and itemSims. */
    private IntHashtable itemHash = new IntHashtable();

    /** Vector of vectors of all transactions containing the item. */
    private Vector itemTrans      = new Vector();

    /** Vector of hashtables of all neighbouring items of the item. */
    private Vector itemNeighb     = new Vector();

    /** Vector of vectors of similarities to neighbouring items of the item. */
    private Vector itemSims       = new Vector();

    /** Hashtable of large itemsets. */
    private IntHashtable lits     = new IntHashtable();

    // -----------------------------------------------------------------------
    //  Constructor
    // -----------------------------------------------------------------------
    /**
     * Empty constructor.
     */
    public FlatRulesAlgorithm()
    {
      this.addMiningListener(this);
    }

    public void processMiningEvent(MiningEvent e) {
    }

    // -----------------------------------------------------------------------
    //  Getter and setter methods
    // -----------------------------------------------------------------------
    /**
     * 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;
    }

    /**
     * Sets minimum number of rules for a premise item.
     *
     * @param minimumItemSize new minimum number of rules for a premise item
     */
    public void setMinimumItemSize(int minimumItemSize)
    {
        this.minimumItemSize = minimumItemSize;
    }

    /**
     * Sets maximum number of rules for a premise item.
     *
     * @param maximumItemSize new maximum number of rules for a premise item
     */
    public void setMaximumItemSize(int maximumItemSize)
    {
        this.maximumItemSize = maximumItemSize;
    }

    /**
     * Return type of decreasing ordering of rules (supp, conf, supp*conf).
     *
     * @return rule type
     */
    public int getRulesOrderType()
    {
      return rulesOrderType;
    }

    /**
     * Sets type of decreasing ordering of rules (supp, conf, supp*conf).
     *
     * @param rulesOrderType new rule type
     */
    public void setRulesOrderType(int rulesOrderType)
    {
      this.rulesOrderType = rulesOrderType;
    }

    /**
     * Sets debug value.
     *
     * @param debug new debug value
     */
     public void setDebug(int debug)
     {
         this.debug = debug;
     }

     /**
      * Are large itemsets also created (beside association rules).
      *
      * @return true if created, no otherwise
      */
     public boolean isCreateLargeItemSets()
     {
       return createLargeItemSets;
     }

     /**
      * Set create large itemsets (beside association rules).
      *
      * @param createLargeItemSets set create large itemsets
      */
     public void setCreateLargeItemSets(boolean createLargeItemSets)
     {
       this.createLargeItemSets = createLargeItemSets;
     }

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

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

    /**
     * Returns number of transactions. Overwrites same method from
     * AssociationRulesAlgorithm because here the transactions are
     * really counted what also works for transaction ID attributes
     * of 'unstoredCategories' type.
     *
     * @return number of transactions, -1 if unknown
     */
    public int getNumberOfTransactions() {

      return nTransact;
    }

    /**
     * Checks mining algorithm for completeness by calling verify method
     * of superclass. Aditionally, it checks whether minimumSupportCount,
     * minimumItemSize, and maximumItemSize are admissible.
     *
     * @throws IllegalArgumentException if some algorithm attributes are incorrect
     */
    public void verify() throws IllegalArgumentException
    {
      super.verify();
      if (minimumSupportCount < 0)
        throw new IllegalArgumentException("minimumSupportCount can't be negative");
      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");
      if (rulesOrderType < 0)
        throw new IllegalArgumentException("rulesOrderType can't be negative");
    }

    // -----------------------------------------------------------------------
    //  Run flat rules algorithm
    // -----------------------------------------------------------------------
    /**
     * Implements the algorithm. 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
    {
       // Initializations:
       if (debug > 0) System.out.println("Flat Rules:");
       associationRules = new Vector();
       largeItemSets    = new Vector();
       nItems           = 0;
       nTransact        = 0;
       itemHash.clear();
       itemTrans.clear();
       itemNeighb.clear();
       itemSims.clear();
       lits.clear();

       // Fill item data:
       if (debug > 0) System.out.println("filling data...");
       fillItemData();
       if (debug == 2) printItemData();

       fireMiningEvent(new CreationModelBeginMessage(getAlgorithmLevel()));
       
       // Calculate similarities between all neighbouring items:
       if (debug > 0) System.out.println("calculating similarities...");
       fireMiningEvent(new AlgorithmStatusMessage(getAlgorithmLevel(), "CalculatingSimilarities", null));
       calcItemSimilarities();

       // Order neighbouring items by descending similarities:
       if (debug > 0) System.out.println("sorting neighbours...");
       fireMiningEvent(new AlgorithmStatusMessage(getAlgorithmLevel(), "SortingNeighbours", null));
       sortItemSimilarities();

       // Create rules and large itemsets:
       if (debug > 0) System.out.println("creating rules...");
       fireMiningEvent(new AlgorithmStatusMessage(getAlgorithmLevel(), "RulesGenerationStarted", null));
       saveResults();

       fireMiningEvent(new CreationModelEndMessageAssociationRules(associationRules.size(), largeItemSets.size(), getAlgorithmLevel()));
       
       if (debug > 0) System.out.println("done.");
    }

    /**
     * Read mining input stream and fill itemHash, itemTrans, and
     * intemNeighb with item information.
     *
     * @throws MiningException cannot fill item data
     */
    private void fillItemData() throws MiningException {

      fireMiningEvent(new ReadingBeginMessage(getAlgorithmLevel()));
      
      ItemSet itemSet      = new ItemSet();    // current itemset
      boolean firstItem    = true;             // first line
      Category prevTransId = new Category(""); // previous transaction ID
      
      int rows = 0;
      
      while ( miningInputStream.next() ) {
        // Read vector:
        MiningVector vector = miningInputStream.read();

        // Empty line => ignore line:
        if (vector == null)
          continue;
        // Get transaction and item IDs (keys):
        double transId = vector.getValue(categoryTransactId);
        double itemId  = vector.getValue(categoryItemId);
        Category currTransId = categoryTransactId.getCategory(transId);
        // Missing value => ignore line:
        if ( Category.isMissingValue(itemId) || currTransId == null )
          continue;

        // First item:
        if (firstItem) {
          prevTransId = currTransId;
          firstItem   = false;
        };
        // New transaction:
        if ( !currTransId.equals(prevTransId) ) {

          // Process previous transaction:
          processTransaction(itemSet, nTransact);

          // Init new transaction:
          itemSet     = new ItemSet();
          prevTransId = currTransId;
          nTransact   = nTransact + 1;
        };

        // Add item to itemset:
        itemSet.addItem( (int) itemId );
        
        rows++;
      }
      // Last transaction:
      if (!firstItem) {
        processTransaction(itemSet, nTransact);
        nTransact   = nTransact + 1;
      }
      
      fireMiningEvent(new ReadingEndMessage(rows, getAlgorithmLevel()));

      // Calculate minimum support count:
      minimumSuppCount = minimumSupportCount;
      if (minimumSuppCount <= 0)
        minimumSuppCount = (int) Math.ceil( minimumSupport * nTransact );