itemset.java

实现APRIORI算法

/*
  Itemset.java
   
  (P)1999-2001 Laurentiu Cristofor
*/

/*

laur.dm.ar - A Java package for association rule mining 
Copyright (C) 2002  Laurentiu Cristofor


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., 59 Temple Place, Suite 330, Boston, MA 02111-1307
USA


The laur.dm.ar package was written by Laurentiu Cristofor ([e-mail]).

*/

package laur.dm.ar;

import java.util.ArrayList;

/**

   An itemset is an ordered list of integers that identify items
   coupled with a double value representing the support of the itemset
   as a percentage.
   
   @version 1.0
   @author Laurentiu Cristofor

*/
public class Itemset 
  implements java.io.Serializable, CriteriaComparable
{
  /**
   * Specifies sorting should be performed according to itemset size.
   */
  public static final int BY_SIZE    = 0;

  /**
   * Specifies sorting should be performed according to itemset support.
   */
  public static final int BY_SUPPORT = 1;


  private static final int SIZE_INCR = 7;

  /** 
   * The capacity of the itemset.
   *
   * @serial
   */
  private int capacity;

  /** 
   * The number of items in the itemset.
   *
   * @serial
   */
  private int size;

  /** 
   * The itemset.
   *
   * @serial
   */
  private int[] set;

  /** 
   * The support of the itemset.
   *
   * @serial
   */
  private double support;

  /** 
   * The weight of the itemset.
   *
   * @serial
   */
  private long weight;

  /** 
   * The mark of the itemset. Can be used to mark the itemset for
   * various purposes
   *
   * @serial
   */
  private boolean mark;

  /**
   * Create a new empty itemset of specified capacity.
   *
   * @param c   the capacity of the itemset
   * @exception IllegalArgumentException   <code>c</code> is negative or zero
   */
  public Itemset(int c)
  {
    if (c < 1)
      throw new IllegalArgumentException("initial capacity must be a positive value");

    capacity = c;

    set = new int[capacity];
    size = 0;
    support = 0;
    weight = 0;
    mark = false;
  }

  /**
   * Creates a new empty itemset.
   */
  public Itemset()
  {
    this(SIZE_INCR);
  }

  /**
   * Create a new itemset by copying a given one.
   *
   * @param itemset   the itemset to be copied
   * @exception IllegalArgumentException   <code>itemset</code> is null
   */
  public Itemset(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("null itemset");

    capacity = itemset.capacity;
    set = new int[capacity];
    size = itemset.size;
    for (int i = 0; i < size; i++)
      set[i] = itemset.set[i];
    support = itemset.support;
    weight = itemset.weight;
    mark = itemset.mark;
  }

  /**
   * Return support of itemset.
   */
  public double getSupport()
  {
    return support;
  }

  /**
   * Set the support of the itemset.
   *
   * @param newSupport   the support of the itemset
   * @exception IllegalArgumentException   <code>newSupport</code> is < 0
   * or > 100
   */
  public void setSupport(double newSupport)
  {
    if (newSupport < 0 || newSupport > 1)
      throw new IllegalArgumentException("support must be between 0 and 1");

    support = newSupport;
  }

  /**
   * Return weight of itemset.
   */
  public long getWeight()
  {
    return weight;
  }

  /**
   * Set the weight of the itemset.
   *
   * @param newWeight   the weight of the itemset
   * @exception IllegalArgumentException   <code>newWeight</code> is < 0
   */
  public void setWeight(long newWeight)
  {
    if (newWeight < 0)
      throw new IllegalArgumentException("weight must be >= 0");

    weight = newWeight;
  }

  /**
   * Increment the weight of the itemset.
   */
  public void incrementWeight()
  {
    weight++;
  }

  /**
   * Return size of itemset.
   *
   * @return   size of itemset
   */
  public int size()
  {
    return size;
  }

  /**
   * Return i-th item in itemset. The count starts from 0.
   *
   * @param i   the index of the item to get
   * @exception IndexOutOfBoundsException   <code>i</code> is an invalid index
   * @return   the <code>i</code>-th item
   */
  public int get(int i)
  {
    if (i < 0 || i >= size)
      throw new IndexOutOfBoundsException("invalid index");

    return set[i];
  }

  /**
   * Add a new item to the itemset.
   *
   * @param item   the item to be added
   * @exception IllegalArgumentException   <code>item</code> is <= 0
   * @return   true if item was added, false if it wasn't added (was
   * already there!)
   */
  public boolean add(int item)
  {
    if (item <= 0)
      throw new IllegalArgumentException("item must be a positive value");

    if (size == 0)
      set[0] = item;
    else
      {
	// look for place to insert item
	int index;
	for (index = 0; index < size && item > set[index]; index++)
	  ;

	// if item was already in itemset then return
	if (index < size && item == set[index])
	  return false;

	// if set is full then allocate new array
	if (size == capacity)
	  {
	    capacity = size + SIZE_INCR;
	    int[] a = new int[capacity];

	    int i;
	    for (i = 0; i < index; i++)
	      a[i] = set[i];
	    // insert new item
	    a[i] = item;
	    for ( ; i < size; i++)
	      a[i + 1] = set[i];

	    set = a;
	  }
	// otherwise make place and insert new item
	else
	  {
	    int i;
	    for (i = size; i > index; i--)
	      set[i] = set[i - 1];

	    set[i] = item;
	  }
      }

    // update size
    size++;
    return true;
  }

  /**
   * Removes a given item from the itemset.
   *
   * @param item   the item to remove
   * @exception IllegalArgumentException   <code>item</code> is <= 0
   * @return   true if item was removed, false if it wasn't removed (was
   * not found in itemset!)
   */
  public boolean remove(int item)
  {
    if (item <= 0)
      throw new IllegalArgumentException("item must be a positive value");

    int index;
    for (index = 0; index < size && item != set[index] ; index++)
      ;

    if (item == set[index])
      {
	for (++index; index < size; index++)
	  set[index - 1] = set[index];
	size--;
	return true;
      }
    else 
      return false;
  }

  /**
   * Removes last item (which has the greatest value) from the itemset. 
   *
   * @return   true if item was removed, false if it wasn't removed (the
   * itemset was empty)
   */
  public boolean removeLast()
  {
    if (size > 0)
      {
	size--;
	return true;
      }
    else
      return false;
  }

  /**
   * Compare two Itemset objects on one of several criteria.
   *
   * @param is   the Itemset object with which we want to compare this
   * object
   * @param criteria   the criteria on which we want to compare, can 
   * be one of SIZE or SUPPORT.
   * @exception IllegalArgumentException   <code>obj</code> is not
   * an Itemset or criteria is invalid
   * @return   a negative value if this object is smaller than 
   * <code>is</code>, 0 if they are equal, and a positive value if this
   * object is greater.
   */
  public int compareTo(Object obj, int criteria)
  {
    if (!(obj instanceof Itemset))
      throw new IllegalArgumentException("not an itemset");

    Itemset is = (Itemset)obj;

    double diff;

    if (criteria == BY_SIZE)
      return size() - is.size();
    else if (criteria == BY_SUPPORT)
      diff = support - is.support;
    else
      throw new IllegalArgumentException("invalid criteria");

    if (diff < 0)
      return -1;
    else if (diff > 0)
      return 1;
    else 
      return 0;
  }

  /**
   * Checks equality with another object.
   *
   * @param o   the object against which we test for equality
   * @return true if object is equal to our itemset, false otherwise
   */
  public boolean equals(Object o)
  {
    if (o == this)
      return true;

    if (!(o instanceof Itemset))
      return false;

    Itemset itemset = (Itemset)o;

    if (size != itemset.size())
      return false;

    for (int i = 0; i < size; i++)
      if (set[i] != itemset.set[i])
	return false;

    return true;
  }

  /**
   * Checks inclusion in a given itemset.
   *
   * @param itemset   the itemset against which we test for inclusion
   * @exception IllegalArgumentException   <code>itemset</code> is null
   */
  public boolean isIncludedIn(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("null itemset");

    if (itemset.size() < size)
      return false;

    int i, j;

    for (i = 0, j = 0; 
	 i < size && j < itemset.size() && set[i] >= itemset.set[j]; 
	 j++)
      if (set[i] == itemset.set[j])
	i++;

    if (i == size)
      return true;
    else 
      return false;
  }