dic.java

用JAVA编写的apriori中的动态项目集计数实现算法。采用Hash方法实现具体的划分

//
//  Author: Su Yibin, under the supervision of Howard Hamilton and
//          Mengchi Liu
//  Copyright: University of Regina and Su Yibin, April 2000
//  No reproduction in whole or part without maintaining this copyright
//  notice and imposing this condition on any subsequent users.

//---- dic.java

//---- input file need:
//----   1. config.txt 
//----      four lines, each line a integer
//----      item number, transaction number , minsup , step length
//----   2. transa.txt

import java.io.*;
import java.util.*;

//-------------------------------------------------------------
//  Class Name : dic
//  Purpose    : main program class
//-------------------------------------------------------------
public class dic {

  public static void main(String[] args) throws IOException {

    dicProcess process1=new dicProcess();
    System.exit(0);

  }
}


//-------------------------------------------------------------
//  Class Name : dicProcess
//  Purpose    : main processing class
//-------------------------------------------------------------
class dicProcess {

  private final int DC=1; // four states of tree node
  private final int DS=2;
  private final int SC=3;
  private final int SS=4;
  int N; // total item #
  int M; // total transaction #
  int stepm; // step increment
  int tid; // current line # of transaction
  int k; // current processing k-itemset
  int setnum; // item # in current transaction
  int minsup;
  hashtreenode root;
  String DSset,DCset,SCset,SSset;
  String transafile="transa.txt";
  String configfile="config.txt";


//-------------------------------------------------------------
//  Class Name : hashtreenode
//  Purpose    : object of node of hash tree
//-------------------------------------------------------------
  class hashtreenode {

    int state;         //  should be one of (DC,DS,SC,SS)
    String itemset;    //  itemset that this node stores
    int counter;       //  counte the number of occurrence in transactions
    int starting;      //  transaction id when this node starts to be counted
    int startingk;     //  k's value when this node starts to be counted
                       //  k : the number of <stepm>s that have been passed through
    boolean needcounting;  //  if this node should be counted later on
    Hashtable ht;      //  hash table stores this node's son-nodes

    // constructor 1
    public hashtreenode(int state,String itemset,int counter,int starting,int startingk) {
      this.state=state;
      if (itemset==null)
        this.itemset=new String();
      else
        this.itemset=new String(itemset);
      this.counter=counter;
      this.starting=starting;
      this.startingk=startingk;
      needcounting=true;
      ht=new Hashtable();
    }

    // constructor 2
    public hashtreenode() {
      this.state=DC;
      this.itemset=new String();
      this.counter=0;
      this.starting=0;
      this.startingk=0;
      needcounting=true;
      ht=new Hashtable();
    }
  }  
 

//-------------------------------------------------------------
//  Method Name: getconfig
//  Purpose    : open file config.txt
//             : get the total number of items of transaction file
//             : and the total number of transactions
//             : and minsup
//-------------------------------------------------------------
  public void getconfig() throws IOException {

    FileInputStream file_in;
    DataInputStream data_in;
    String oneline=new String();
    int i=0;

    InputStreamReader input = new InputStreamReader(System.in);
    BufferedReader reader = new BufferedReader(input);
    String response = "";

    System.out.println("Press 'C' to change the default configuration and transaction files");
    System.out.print("or any other key to continue.  ");
    try {
      response = reader.readLine();
    } catch (Exception e) {
      System.out.println(e);
    }
    int res=response.compareTo("C") * response.compareTo("c");

    if(res == 0) {
      System.out.print("\nEnter new transaction filename: ");
      try {
        transafile = reader.readLine();
      } catch (Exception e) {
        System.out.println(e);
      }
      System.out.print("Enter new configuration filename: ");
      try {
        configfile = reader.readLine();
      } catch (Exception e) {
        System.out.println(e);
      }
      System.out.println("Filenames changed");
    }

    try {
      file_in = new FileInputStream(configfile);
      data_in = new DataInputStream(file_in);

      oneline=data_in.readLine();
      N=Integer.valueOf(oneline).intValue();
      oneline=data_in.readLine();
      M=Integer.valueOf(oneline).intValue();
      oneline=data_in.readLine();
      minsup=Integer.valueOf(oneline).intValue();
      oneline=data_in.readLine();
      stepm=Integer.valueOf(oneline).intValue();

      String user = "";
      while(stepm < 5) {
	System.out.println("\nThe value of step M must be at least 5 (it is currently "+stepm+")");
	System.out.print("Enter a larger value for step M: ");
        try {
          user = reader.readLine();
        } catch (Exception e) {
          System.out.println(e);
        }

	stepm = Integer.valueOf(user).intValue();
      }

      System.out.print("\nInput configuration: " + N + " items, " + M + " transactions, ");
      System.out.println("minsup = " + minsup + "%, step M = " + stepm + "\n");

    } catch (IOException e) {
      System.out.println(e);
    }
  }


//-------------------------------------------------------------
//  Method Name: getitemat
//  Purpose    : get an item from an itemset
//             : get the total number of items of transaction file
//  Parameter  : int i : i-th item ; itemset : string itemset
//  Return     : int : the item at i-th in the itemset 
//-------------------------------------------------------------
  public int getitemat(int i,String itemset) {

    String str1=new String(itemset);

    int pos1,pos2;
    pos1=0;
    pos2=0;
    for (int a=1;a<i;a++) {
      pos1=itemset.indexOf(" ",pos1);
      pos1++;
    }    
    pos2=itemset.indexOf(" ",pos1+1);
    if (pos2==-1) 
      pos2=itemset.length();
    str1=itemset.substring(pos1,pos2);

    return(Integer.valueOf(str1.trim()).intValue());

  }


//-------------------------------------------------------------
//  Method Name: itesetsize
//  Purpose    : get item number of an itemset
//  Parameter  : itemset : string itemset
//  Return     : int : the number of item of the itemset 
//-------------------------------------------------------------
  public int itemsetsize(String itemset) {

    StringTokenizer st=new StringTokenizer(itemset);

    return st.countTokens();

  }


//-------------------------------------------------------------
//  Method Name: dashfound
//  Purpose    : check the hashtree to see if there exsits a dashed node
//             : if no dashed circle or dashed squire exsits in hash tree
//             : program will end
//  Parameter  : htn : hash tree root 
//  Return     : boolean : if a dashed node found, return true, otherwise, false
//-------------------------------------------------------------
  boolean dashfound(hashtreenode htn) {
  
    if (htn.state==DS || htn.state==DC)
      return true;
    for (Enumeration e=htn.ht.elements();e.hasMoreElements(); )
      if (dashfound((hashtreenode)e.nextElement()))
        return true;
    return false;
  }


//-------------------------------------------------------------
//  Method Name: printhashtree
//  Purpose    : print the whole hash tree
//  Parameter  : htn is a hashtreenode (when other method call this method,it is the root)
//             : transa : special transaction with all items occurr in it.
//             : a : recursive depth
//  Return     : 
//-------------------------------------------------------------
  public void printhashtree(hashtreenode htn,String transa,int a) {
    String state=new String();
    switch (htn.state) {
      case DC: 
	state="DC" ; 
	DCset=DCset.concat(htn.itemset);
	DCset=DCset.concat(",");
//	DCset=DCset.concat("[");
//	DCset=DCset.concat(htn.itemset);
//	DCset=DCset.concat("]");
	break;
      case DS: 
	state="DS" ; 
	DSset=DSset.concat(htn.itemset);
	DSset=DSset.concat(",");
//	DSset=DSset.concat("[");
//	DSset=DSset.concat(htn.itemset);
//	DSset=DSset.concat("]");
	break;
      case SC: 
	state="SC" ; 
	SCset=SCset.concat(htn.itemset);
	SCset=SCset.concat(",");
//	SCset=SCset.concat("[");
//	SCset=SCset.concat(htn.itemset);
//	SCset=SCset.concat("]");
	break;
      case SS: 
	state="SS" ; 
	SSset=SSset.concat(htn.itemset);
	SSset=SSset.concat(",");
//	SSset=SSset.concat("[");
//	SSset=SSset.concat(htn.itemset);
//	SSset=SSset.concat("]");
	break;
    }
//    System.out.print("Itemset:<"+htn.itemset+">");
//    System.out.print(" state:<"+state+">");
//    System.out.print(" counter:<"+htn.counter+">");
//    System.out.print(" starting:<"+htn.starting+">");
//    System.out.print(" startingk:<"+htn.startingk+">");
//    System.out.println(" needcounting:<"+htn.needcounting+">");

    if (htn.ht==null)
      return;
    for (int b=a+1;b<=itemsetsize(transa);b++)
      if (htn.ht.containsKey(Integer.toString(getitemat(b,transa))))
        printhashtree((hashtreenode)htn.ht.get(Integer.toString(getitemat(b,transa))),transa,b);

  }


//-------------------------------------------------------------
//  Method Name: transatrahashtree
//  Purpose    : recursive transaction traversal through hash tree 
//  Parameter  : htn is a hashtreenode (when other method call this method,it is the root)
//             : transa : transaction
//             : a : recursive depth,only traversal itemset_part after a-th item
//             : e.g. tran="2 3 4 5", a=2, then, only "4 5" need traversal.
//  Return     : 
//-------------------------------------------------------------
  public void transatrahashtree(String transa,hashtreenode htn,int a) {

    if (htn.needcounting)
      htn.counter++;
    if (htn.ht==null)
      return;
    else
      for (int b=a+1;b<=itemsetsize(transa);b++)
        if (htn.ht.containsKey(Integer.toString(getitemat(b,transa))))
          transatrahashtree(transa,(hashtreenode)htn.ht.get(Integer.toString(getitemat(b,transa))),b);

  }


//-------------------------------------------------------------
//  Method Name: checkcountedall
//  Purpose    : travese hashtree to chech if an itemset has been counted 
//             : through all transactions, stop counting it.
//  Parameter  : htn is a hashtreenode (when other method call this method,it is the root)
//             : transa : transaction
//             : startfrom : recursive depth
//  Return     : 
//-------------------------------------------------------------
  public void checkcountedall(hashtreenode htn,String transa,int startfrom) { 

    if ( htn.starting==tid && k!=htn.startingk ) {
      if (htn.state==DS) {
        htn.state=SS;
      }
      else if (htn.state==DC) {
        htn.state=SC;
      }
      htn.needcounting=false;
    }

    if (htn.ht==null || htn.ht.isEmpty())
      return;

    for (int c=startfrom+1;c<=N;c++)