apriori.java

this is apriori algo code for datamining

//http://www2.cs.uregina.ca/~dbd/cs831/notes/itemsets/itemset_prog1.html
//  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.
//

//---- apriori.java

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

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

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

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

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

  }
}


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

  private final int HT=1; // state of tree node (hash table or
  private final int IL=2; // itemset list)
  int N; // total item #
  int M; // total transaction #
  Vector largeitemset=new Vector();
  Vector candidate=new Vector();
  int minsup;
  String fullitemset;
  String configfile="config.txt";
  String transafile="transa.txt";


//-------------------------------------------------------------
//  Class Name : candidateelement
//  Purpose    : object that will be stored in Vector candidate
//             : include 2 item
//             : a hash tree and a candidate list
//-------------------------------------------------------------
  class candidateelement {
    hashtreenode htroot;
    Vector candlist;
  }


//-------------------------------------------------------------
//  Class Name : hashtreenode
//  Purpose    : node of hash tree
//-------------------------------------------------------------
  class hashtreenode {
    int nodeattr; //  IL or HT
    int depth;
    Hashtable ht;
    Vector itemsetlist;

    public void hashtreenode() {
      nodeattr=HT;
      ht=new Hashtable();
      itemsetlist=new Vector();
      depth=0;
    }

    public void hashtreenode(int i) {
      nodeattr=i;
      ht=new Hashtable();
      itemsetlist=new Vector();
      depth=0;
    }
  }  


//-------------------------------------------------------------
//  Class Name : itemsetnode
//  Purpose    : node of itemset
//-------------------------------------------------------------
  class itemsetnode {
    String itemset;
    int counter;
    
    public itemsetnode(String s1,int i1) {
      itemset=new String(s1);
      counter=i1;
    }

    public itemsetnode() {
      itemset=new String();
      counter=0;
    }

    public String toString() {
      String tmp=new String();
      tmp=tmp.concat("<\"");
      tmp=tmp.concat(itemset);
      tmp=tmp.concat("\",");
      tmp=tmp.concat(Integer.toString(counter));
      tmp=tmp.concat(">");
      return tmp;
    }
  }


//-------------------------------------------------------------
//  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) {
    if (htn.nodeattr == IL ) {
      System.out.println("Node is an itemset list");
      System.out.println("	depth :<"+htn.depth+">");
      System.out.println("	iteset:<"+htn.itemsetlist+">");
    }
    else { // HT
      System.out.println("Node is a hashtable");
      if (htn.ht==null)
        return;
      for (int b=a+1;b<=N;b++)
        if (htn.ht.containsKey(Integer.toString(getitemat(b,transa)))) {
          System.out.println("	key:<"+getitemat(b,transa));
          printhashtree((hashtreenode)htn.ht.get(Integer.toString(getitemat(b,transa))),transa,b);
        }
    }
  }


//-------------------------------------------------------------
//  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("config.txt");
      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();
      System.out.print("\nInput configuration: "+N+" items, "+M+" transactions, ");
      System.out.println("minsup = "+minsup+"%");
      System.out.println();
    } 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);
    StringTokenizer st=new StringTokenizer(itemset);
    int j;

    if (i > st.countTokens())
      System.out.println("eRRor! in getitemat, !!!!");

    for (j=1;j<=i;j++)
      str1=st.nextToken();

    return(Integer.valueOf(str1).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: gensubset
//  Purpose    : generate all subset given an itemset
//  Parameter  : itemset
//  Return     : a string contains all subset deliminated by ","
//             : e.g. "1 2,1 3,2 3" is subset of "1 2 3"
//-------------------------------------------------------------
  public String gensubset(String itemset) {

    int len=itemsetsize(itemset);
    int i,j;
    String str1;
    String str2=new String();
    String str3=new String();

    if (len==1)
      return null;
    for (i=1;i<=len;i++) {
      StringTokenizer st=new StringTokenizer(itemset);
      str1=new String();
      for (j=1;j<i;j++) {
        str1=str1.concat(st.nextToken());
        str1=str1.concat(" ");
      }
      str2=st.nextToken();
      for (j=i+1;j<=len;j++) {
        str1=str1.concat(st.nextToken());
        str1=str1.concat(" ");
      }
      if (i!=1)
        str3=str3.concat(",");
      str3=str3.concat(str1.trim());
    }

    return str3;

  } //end public String gensubset(String itemset)


//-------------------------------------------------------------
//  Method Name: createcandidate
//  Purpose    : generate candidate n-itemset
//  Parameter  : int n : n-itemset
//  Return     : Vector : candidate is stored in a Vector
//-------------------------------------------------------------
  public Vector createcandidate(int n) { 

    Vector tempcandlist=new Vector();
    Vector ln_1=new Vector();
    int i,j,length1;
    String cand1=new String();
    String cand2=new String();
    String newcand=new String();
    
//System.out.println("Generating "+n+"-candidate item set ....");
    if (n==1)
      for (i=1;i<=N;i++)
        tempcandlist.addElement(Integer.toString(i));
    else {
      ln_1=(Vector)largeitemset.elementAt(n-2);
      length1=ln_1.size();
      for (i=0;i<length1;i++) {
        cand1=(String)ln_1.elementAt(i);
        for (j=i+1;j<length1;j++) {
          cand2=(String)ln_1.elementAt(j);
          newcand=new String();
          if (n==2) {
            newcand=cand1.concat(" ");
            newcand=newcand.concat(cand2);
            tempcandlist.addElement(newcand.trim());
          }
          else {
            int c,i1,i2;
            boolean same=true;

            for (c=1;c<=n-2;c++) {
              i1=getitemat(c,cand1);
              i2=getitemat(c,cand2);
              if ( i1!=i2 ) {
                same=false;
                break;
              }