tools.java

数据挖掘中的Aprior算法java实现

package datamining;

import java.util.*;

/**
 * A library class for basic actions in the algorithms. 
 * Actions that are simple and mostly just require traversing
 * the trie. 
 *
 * @author Michael Holler
 * @version 0.1, 16.03.2004
 */ 
public class Tools {

  // disable instantiation	
  private Tools() { }

  public static void print(Item root) {

  }
	
  private static void print(Item item, String str) {

  }

  /**
   * Zeroes the support of the items in the trie. Returns the
   * number of items in the trie.
   *
   * @return		number of items in the trie
   */ 
  public static int zeroSupport(Item item) {
    Vector v = item.getChildren(); 
    Item child;
    int items = 0;

    for (Enumeration e = v.elements(); e.hasMoreElements(); ) { 
      child = (Item)e.nextElement(); 
      child.setSupport(0);	      
      items++;
      items += zeroSupport(child);
    }
    return items;
  }

  /**
   * Method for counting the supports of the candidates
   * generated on this pass.
   *
   * !!!!I'm not sure if this is good to have here since it!!!!
   * !!!!sort of needs to overriden in a couple of methods.!!!!
   * 
   * @return 		the number of transactions from which 
   * 			the support was counted
   */
  public static int countSupport(Item root, DataHandler dh) {
    int rowcount = 0;
    int[] items;
    dh.open();
    for (items = dh.read(); items.length > 0; items = dh.read()) {
      rowcount++;
      countSupport(root, items, 0, 1);
    }
    return rowcount;
  }

  /**
   * Adds the support of the Item given as paramater and all the
   * Items in Trie below it.
   *
   * @param	item	the item the cover of which is to be counted
   * @param	items	the array of integer items from the database
   * @param	i 	the position in the array 
   * @param	depth	the depth of recursion 
   */
  private static void countSupport(Item item, int[] items, int i, int depth) {
    Vector v = item.getChildren(); 
    Item child;
    int tmp;
    Enumeration e = v.elements();

    // loop through the children to check
    while (e.hasMoreElements()) {
      child = (Item)e.nextElement();
     
      // break, if the whole transaction is checked
      if (i == items.length) { break; }
      
      // do a linear search for the child in the transaction starting from i
      tmp = i;
      while (tmp < items.length && items[tmp] < child.getLabel()) tmp++;
      
      // if the same item exists, increase support and go deaper
      if (tmp < items.length && child.getLabel() == items[tmp]) {
	child.incSupport();
        countSupport(child, items, tmp+1, depth+1);
	i = tmp+1;
      }
    }
  }

  /**
   * Method for pruning the candidates. Removes items that are
   * not frequent from the Trie.
   *
   * @param	item	the item the children of which will be pruned
   * @param	support	the minimal frequency threshold 
   * @return		the number of items pruned from the candidates
   */
  public static int pruneCandidates(Item item, int support) {
    Vector v = item.getChildren(); 
    Item child = item;
    int pruned = 0;
    
    for (Enumeration e = new Vector(v).elements(); e.hasMoreElements(); ) { 
      child = (Item)e.nextElement(); 

      if (child.getSupport() < support) {
	v.remove(child);
	pruned++;
      } else {
        pruned += pruneCandidates(child, support);
      }
    }
    return pruned;
  }

}