apriori.java

implementation of Apriori algorithm

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package samparproriapp;



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

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


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

  public static void main1(int s) throws IOException {

   // aprioriProcess process1=new aprioriProcess(s);
   

  }

    static void main1(int parseInt, int parseInt0) {
        //throw new UnsupportedOperationException("Not yet implemented");
    }

    static StringBuffer main1(int s, int parseInt0,StringBuffer nall) throws IOException {
         aprioriProcess process1=new aprioriProcess(s);
    //System.exit(0);
     //   throw new UnsupportedOperationException("Not yet implemented");
       
         System.out.println(process1.all.toString());
      nall.append(process1.all.toString());
      
         return process1.fn;  
    }
}
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 largeperlist=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
//-------------------------------------------------------------
StringBuffer fn =new StringBuffer();  
StringBuffer all =new StringBuffer();
        //-------------------------------------------------------------
  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) {
    
    InputStreamReader input = new InputStreamReader(System.in);
    BufferedReader reader = new BufferedReader(input);
    String response = "";
    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));	

	System.out.println("press any key to see next entry");
    try {
      response = reader.readLine();
    } catch (Exception e) {
      System.out.println(e);
    }	
          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(int s) 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");
	int res=1;
    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=s;//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;
              }
              else {
                newcand=newcand.concat(" ");
                newcand=newcand.concat(Integer.toString(i1));
              }
            }
            if (same) {
              i1=getitemat(n-1,cand1);
              i2=getitemat(n-1,cand2);
              newcand=newcand.concat(" ");
              newcand=newcand.concat(Integer.toString(i1));
              newcand=newcand.concat(" ");
              newcand=newcand.concat(Integer.toString(i2));
              tempcandlist.addElement(newcand.trim());
            }
          } //end if n==2 else
        } //end for j
      } //end for i
    } //end if n==1 else

    if (n<=2) 
      return tempcandlist;

    Vector newcandlist=new Vector();
    for (int c=0; c<tempcandlist.size(); c++) {
      String c1=(String)tempcandlist.elementAt(c);
      String subset=gensubset(c1);
      StringTokenizer stsubset=new StringTokenizer(subset,",");
      boolean fake=false;
      while (stsubset.hasMoreTokens())
	if (!ln_1.contains(stsubset.nextToken())) {
          fake=true;
	  break;
        }
      if (!fake)
	newcandlist.addElement(c1);
    }

    return newcandlist;