itemset.java

数据挖掘的工具代码（包含fp-tree,appriory

	  }
      }

    // 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 removeItem(int item)
  {
    if (item <= 0)
      throw new IllegalArgumentException("negative or zero value for item not allowed");

    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 removeLastItem()
  {
    if (size > 0)
      {
	size--;
	return true;
      }
    else
      return false;
  }

  /**
   * 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(float newSupport)
  {
    if (newSupport < 0 || newSupport > 1)
      throw new IllegalArgumentException("support must be between 0 and 1");

    support = newSupport;
  }

  /**
   * 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 positive");

    weight = newWeight;
  }

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

  /**
   * Checks equality with a given itemset.
   *
   * @param itemset   the itemset against which we test for equality
   * @exception IllegalArgumentException   <code>itemset</code> is null
   */
  public boolean isEqualTo(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("itemset required as argument");

    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("itemset required as argument");

    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;
  }

  /**
   * Mark the itemset.
   *
   * @return   true if itemset was already marked, false otherwise
   */
  public boolean mark()
  {
    boolean old_mark = mark;
    mark = true;
    return old_mark;
  }

  /**
   * Unmark the itemset.
   *
   * @return   true if itemset was marked, false otherwise
   */
  public boolean unmark()
  {
    boolean old_mark = mark;
    mark = false;
    return old_mark;
  }

  /**
   * Return itemset mark.
   *
   * @return   true if itemset is marked, false otherwise
   */
  public boolean isMarked()
  {
    return mark;
  }

  /**
   * Return a String representation of the Itemset.
   *
   * @return   String representation of Itemset
   */
  public String toString()
  {
    String s = "{";

    for (int i = 0; i < size; i++)
      s += set[i] + " ";
    s += "}/[" + support + "/" + weight + "] (" + size + ")";

    return s;
  }

  /**
   * Check whether two itemsets can be combined. Two itemsets can be
   * combined if they differ only in the last item.
   *
   * @param itemset   itemset with which to combine
   * @exception IllegalArgumentException   <code>itemset</code> is null
   * @return   true if the itemsets can be combined, false otherwise
   */
  public boolean canCombineWith(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("itemset required as argument");

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

    if (size == 0)
      return false;

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

    return true;
  }

  /**
   * Combine two itemsets into a new one that will contain all the
   * items in the first itemset plus the last item in the second
   * itemset.
   *
   * @param itemset   itemset with which to combine
   * @exception IllegalArgumentException   <code>itemset</code> is null
   * @return   an itemset that combines the two itemsets as described
   * above 
   */
  public Itemset combineWith(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("itemset required as argument");

    Itemset is = new Itemset(this);
    is.support = 0;
    is.weight = 0;

    is.addItem(itemset.set[itemset.size - 1]);

    return is;
  }

  /**
   * Remove all non-maximal itemsets from the vector v
   *
   * @param v   the collection of itemsets
   */
  public static synchronized void pruneNonMaximal(Vector v)
  {
    int i, j;
    int size = v.size();

    for (i = 0; i < size; i++)
      {
	// see if anything is included in itemset at index i
	for (j = i + 1; j < size; j++)
	  if (((Itemset)v.get(j)).isIncludedIn((Itemset)v.get(i)))
	      {
		// replace this element with last, delete last,
		// and don't advance index
		v.set(j, v.lastElement());
		v.remove(--size);
		j--;
	      }

	// see if itemset at index i is included in another itemset
	for (j = i + 1; j < size; j++)
	  if (((Itemset)v.get(i)).isIncludedIn((Itemset)v.get(j)))
	      {
		// replace this element with last, delete last,
		// and don't advance index
		v.set(i, v.lastElement());
		v.remove(--size);
		i--;
		break;
	      }
      }
  }

  /**
   * Remove all duplicate itemsets from the vector v
   *
   * @param v   the collection of itemsets
   */
  public static synchronized void pruneDuplicates(Vector v)
  {
    int i, j;
    int size = v.size();

    for (i = 0; i < size; i++)
      {
	// see if anything is equal to itemset at index i
	for (j = i + 1; j < size; j++)
	  if (((Itemset)v.get(j)).isEqualTo((Itemset)v.get(i)))
	      {
		// replace this element with last, delete last,
		// and don't advance index
		v.set(j, v.lastElement());
		v.remove(--size);
		j--;
	      }
      }
  }

  /** 
   * for testing purposes only !!! 
   */
  public static void main(String[] args)
  {
    Itemset is1 = new Itemset();
    Itemset is2 = new Itemset();

    is1.addItem(7);
    is1.addItem(3);
    is1.addItem(15);
    is1.addItem(5);
    is1.addItem(12);
    is1.addItem(12);

    System.out.println("is1: " + is1);

    is2.addItem(12);
    is2.addItem(15);
    is2.addItem(7);
    is2.addItem(5);
    is2.addItem(3);
    is2.addItem(8);

    System.out.println("is2: " + is2);

    System.out.println("do is1 and is2 share items: " 
		       + is1.doesIntersect(is2));
    System.out.println("do is2 and is1 share items: " 
		       + is2.doesIntersect(is1));

    Itemset is3 = is1.subtract(is2);
    System.out.println("is3 <= subtracting is2 from is1:" + is3);

    System.out.println("do is1 and is3 share items: " 
		       + is1.doesIntersect(is3));
    System.out.println("do is3 and is1 share items: " 
		       + is3.doesIntersect(is1));

    is3 = is2.subtract(is1);
    System.out.println("is3 <= subtracting is1 from is2:" + is3);

    System.out.println("do is1 and is3 share items: " 
		       + is1.doesIntersect(is3));
    System.out.println("do is3 and is1 share items: " 
		       + is3.doesIntersect(is1));

    System.out.println("do is3 and is2 share items: " 
		       + is3.doesIntersect(is2));
    System.out.println("do is2 and is3 share items: " 
		       + is2.doesIntersect(is3));

    System.out.println("adding is2 to is1:" + is1.add(is2));
    System.out.println("adding is1 to is2:" + is2.add(is1));

    System.out.println("is1 equal to is2: " + is1.isEqualTo(is2));
    System.out.println("is1 included in is2: " + is1.isIncludedIn(is2));
    System.out.println("is2 included in is1: " + is2.isIncludedIn(is1));

    is1.addItem(8);

    System.out.println("is1: " + is1);

    System.out.println("is1 equal to is2: " + is1.isEqualTo(is2));
    System.out.println("is1 included in is2: " + is1.isIncludedIn(is2));
    System.out.println("is2 included in is1: " + is2.isIncludedIn(is1));

    is1.addItem(1);

    System.out.println("is1: " + is1);

    System.out.println("is1 equal to is2: " + is1.isEqualTo(is2));
    System.out.println("is1 included in is2: " + is1.isIncludedIn(is2));
    System.out.println("is2 included in is1: " + is2.isIncludedIn(is1));

    is1.addItem(50);

    System.out.println("is1: " + is1);

    System.out.println("is1 equal to is2: " + is1.isEqualTo(is2));
    System.out.println("is1 included in is2: " + is1.isIncludedIn(is2));
    System.out.println("is2 included in is1: " + is2.isIncludedIn(is1));

    is1.addItem(100);

    System.out.println("is1: " + is1);

    System.out.println("is1 equal to is2: " + is1.isEqualTo(is2));
    System.out.println("is1 included in is2: " + is1.isIncludedIn(is2));
    System.out.println("is2 included in is1: " + is2.isIncludedIn(is1));

    System.out.println("adding 70 to is2: " + is2.addItem(70));
    System.out.println("adding 70 to is2: " + is2.addItem(70));

    System.out.println("is2: " + is2);

    System.out.println("is1 equal to is2: " + is1.isEqualTo(is2));
    System.out.println("is1 included in is2: " + is1.isIncludedIn(is2));
    System.out.println("is2 included in is1: " + is2.isIncludedIn(is1));

    System.out.println("removing 1 from is1: " + is1.removeItem(1));
    System.out.println("removing 1 from is1: " + is1.removeItem(1));
    System.out.println("is1: " + is1);
    System.out.println("removing 50 from is1: " + is1.removeItem(50));
    System.out.println("is1: " + is1);
    System.out.println("removing 70 from is1: " + is2.removeItem(70));
    System.out.println("is2: " + is2);

    System.out.print("going through items of is1:");
    while (is1.hasMoreItems())
      System.out.print(" " + is1.getNextItem());
    System.out.println("");

    System.out.print("going through items of is2:");
    while (is2.hasMoreItems())
      System.out.print(" " + is2.getNextItem());
    System.out.println("");

    System.out.println("is1 first item: " + is1.getFirstItem());
    System.out.println("is1 next item: " + is1.getNextItem());
    System.out.println("is2 first item: " + is2.getFirstItem());
    System.out.println("is2 next item: " + is2.getNextItem());

    while (is2.removeLastItem())
      ;
    System.out.println("is2: " + is2);

    System.out.println("mark is1, previous state: " + is1.mark());
    System.out.println("mark is1, previous state: " + is1.mark());
    System.out.println("is1 mark state: " + is1.isMarked());
    System.out.println("unmark is1, previous state: " + is1.unmark());
    System.out.println("unmark is1, previous state: " + is1.unmark());
  }
}