apriori.java

implementation of Apriori algorithm

  } //end public createcandidate(int n)

  
//-------------------------------------------------------------
//  Method Name: createcandidatehashtre
//  Purpose    : generate candidate hash tree
//  Parameter  : int n : n-itemset
//  Return     : hashtreenode : root of the hashtree
//-------------------------------------------------------------
  public hashtreenode createcandidatehashtree(int n) {  

    int i,len1;
    hashtreenode htn=new hashtreenode();

//System.out.println("Generating candidate "+n+"-itemset hashtree ....");
    if (n==1)
      htn.nodeattr=IL;
    else
      htn.nodeattr=HT;

    len1=((candidateelement)candidate.elementAt(n-1)).candlist.size();
    for (i=1;i<=len1;i++) {
      String cand1=new String();
      cand1=(String)((candidateelement)candidate.elementAt(n-1)).candlist.elementAt(i-1);
      genhash(1,htn,cand1);
    }

    return htn;

  } //end public createcandidatehashtree(int n)


//-------------------------------------------------------------
//  Method Name: genhash
//  Purpose    : called by createcandidatehashtree
//             : recursively generate hash tree node
//  Parameter  : htnf is a hashtreenode (when other method call this method,it is the root)
//             : cand : candidate itemset string
//             : int i : recursive depth,from i-th item, recursive
//  Return     : 
//-------------------------------------------------------------
  public void genhash(int i, hashtreenode htnf, String cand) {
    
    int n=itemsetsize(cand);
    if (i==n) {
      htnf.nodeattr=IL;
      htnf.depth=n;
      itemsetnode isn=new itemsetnode(cand,0);
      if (htnf.itemsetlist==null)
        htnf.itemsetlist=new Vector();
      htnf.itemsetlist.addElement(isn);
    }
    else {
      if (htnf.ht==null) 
        htnf.ht=new Hashtable(HT);
      if (htnf.ht.containsKey(Integer.toString(getitemat(i,cand)))) {
        htnf=(hashtreenode)htnf.ht.get(Integer.toString(getitemat(i,cand)));
        genhash(i+1,htnf,cand);
      }
      else {
        hashtreenode htn=new hashtreenode();
        htnf.ht.put(Integer.toString(getitemat(i,cand)),htn);
        if (i==n-1) {
          htn.nodeattr=IL;
          //Vector isl=new Vector();
          //htn.itemsetlist=isl;
          genhash(i+1,htn,cand);
        }
        else {
          htn.nodeattr=HT;
          //Hashtable ht=new Hashtable();
          //htn.ht=ht;
          genhash(i+1,htn,cand);
        }
      }
    }
  } //end public void genhash(int i, hashtreenode htnf, String cand)


//-------------------------------------------------------------
//  Method Name: createlargeitemset
//  Purpose    : find all itemset which have their counters>=minsup
//  Parameter  : int n : n-itemset
//  Return     : 
//-------------------------------------------------------------
  public void createlargeitemset(int n) {

    Vector candlist=new Vector();
    Vector lis=new Vector(); //large item set
    Vector perlist = new Vector();
    hashtreenode htn=new hashtreenode();
    int i;

//    System.out.println("Generating "+n+"-large item set ....");
    candlist=((candidateelement)candidate.elementAt(n-1)).candlist;
    htn=((candidateelement)candidate.elementAt(n-1)).htroot;
      
    getlargehash(0,htn,fullitemset,lis,perlist);

    largeitemset.addElement(lis);
    largeperlist.addElement(perlist);

  } // end public void createlargeitemset(int n)


//-------------------------------------------------------------
//  Method Name: getlargehash
//  Purpose    : recursively traverse candidate hash tree 
//             : to find all large itemset
//  Parameter  : htnf is a hashtreenode (when other method call this method,it is the root)
//             : cand : candidate itemset string
//             : int i : recursive depth
//             : Vector lis : Vector that stores large itemsets
//  Return     : 
//-------------------------------------------------------------
  public void getlargehash(int i,hashtreenode htnf,String transa,Vector lis,Vector perlist) {

    Vector tempvec=new Vector();
    int j;	   
    if (htnf.nodeattr==IL) {
      tempvec=htnf.itemsetlist;
	  for (j = 1; j <= tempvec.size(); j++)
          {
		perlist.addElement(((itemsetnode)tempvec.elementAt(j - 1)).itemset + "$#"+((itemsetnode)tempvec.elementAt(j - 1)).counter +"%"); 
              if (((itemsetnode)tempvec.elementAt(j - 1)).counter >= ((minsup * M) / 100))
		  
             // String tep=;
			  lis.addElement(((itemsetnode)tempvec.elementAt(j - 1)).itemset);//+"$#"+((itemsetnode)tempvec.elementAt(j - 1)).counter +"%" );
			  
		 // }
                          
                  }		  
			
    }
    else {
      if (htnf.ht==null)
        return;
      for (int b=i+1;b<=N;b++)
        if (htnf.ht.containsKey(Integer.toString(getitemat(b,transa)))) 
          getlargehash(b,(hashtreenode)htnf.ht.get(Integer.toString(getitemat(b,transa))),transa,lis,perlist);
    }
  }


//-------------------------------------------------------------
//  Method Name: transatraverse
//  Purpose    : read each transaction, traverse hashtree, 
//               incrment approporiate itemset counter.
//  Parameter  : int n : n-itemset
//  Return     : 
//-------------------------------------------------------------
  public void transatraverse(int n) {

    FileInputStream file_in;
    DataInputStream data_in;
    String oneline=new String();
    int i=0,j=0,len=0;
    String transa;
    hashtreenode htn=new hashtreenode();
    StringTokenizer st;
    String str0;
    int numRead=0;

    //System.out.println("Traverse "+n+"-candidate hashtree ... ");
    htn=((candidateelement)candidate.elementAt(n-1)).htroot;
    try {
      file_in = new FileInputStream(transafile);
      data_in = new DataInputStream(file_in);

      while ( true ) {
        transa=new String();
        oneline=data_in.readLine();
	numRead++;
        if ((oneline==null)||(numRead > M))
          break;
        st=new StringTokenizer(oneline.trim());
	j=0;
        while ((st.hasMoreTokens()) && j < N) {
	  j++;
	  str0=st.nextToken();
          i=Integer.valueOf(str0).intValue();
          if (i!=0) {
            transa=transa.concat(" ");
            transa=transa.concat(Integer.toString(j));
            len++;
          }
        } 
        transa=transa.trim();
        transatrahash(0,htn,transa);
      }
    } catch (IOException e) {
      System.out.println(e);
    }
  }


//-------------------------------------------------------------
//  Method Name: transatrahash
//  Purpose    : called by transatraverse
//             : recursively traverse hash tree
//  Parameter  : htnf is a hashtreenode (when other method call this method,it is the root)
//             : cand : candidate itemset string
//             : int i : recursive depth,from i-th item, recursive
//  Return     : 
//-------------------------------------------------------------
  public void transatrahash(int i,hashtreenode htnf,String transa) {

    String stris=new String();
    Vector itemsetlist=new Vector();
    int j,lastpos,len,d;
    itemsetnode tmpnode=new itemsetnode();

    if (htnf.nodeattr==IL) {
      itemsetlist=(Vector)htnf.itemsetlist;
      len=itemsetlist.size();
      for (j=0;j<len;j++) {
	tmpnode=(itemsetnode)itemsetlist.elementAt(j);
	d=getitemat(htnf.depth,tmpnode.itemset);
        lastpos=transa.indexOf(Integer.toString(d));
        if (lastpos!=-1) 
          ((itemsetnode)(itemsetlist.elementAt(j))).counter++;
      }
      return;
    }
    else  //HT
      for (int b=i+1;b<=itemsetsize(transa);b++) 
        if (htnf.ht.containsKey(Integer.toString(getitemat(b,transa)))) 
          transatrahash(i,(hashtreenode)htnf.ht.get(Integer.toString(getitemat(b,transa))),transa);

  } // public transatrahash(int ii,hashtreenode htnf,String transa)


//-------------------------------------------------------------
//  Method Name: aprioriProcess()
//  Purpose    : main processing method
//  Parameters :
//  Return     : 
//-------------------------------------------------------------
  public aprioriProcess(int s)  throws IOException {

    candidateelement cande;
    int k=0;
    Vector large=new Vector();
    Date d=new Date();
    long s1,s2;

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

    System.out.println();
    System.out.println("Algorithm apriori starting now.....");
    System.out.println();
	String[] itemArray = {"butter","milk","torch","soap",
                          "pot","coil","iron","coke",
                          "fruits","towel","Tshirt","jeans",
                          "belt","cell","perfume","comb",
                          "purse","box","books","headphone"};

	String index="";
	String index1="";

    getconfig(s);

    fullitemset=new String();
    fullitemset=fullitemset.concat("1");
    for (int i=2;i<=N;i++) {
      fullitemset=fullitemset.concat(" ");
      fullitemset=fullitemset.concat(Integer.toString(i));
    }

    d=new Date();
    s1=d.getTime();

    while (true) {
      k++;
      cande=new candidateelement();
      cande.candlist=createcandidate(k);

	System.out.println("C"+k+"("+k+"-candidate-itemset): "+cande.candlist);

      if (cande.candlist.isEmpty())
	break;

      cande.htroot=null;
      candidate.addElement(cande);

      ((candidateelement)candidate.elementAt(k-1)).htroot=createcandidatehashtree(k);

//System.out.println("Now reading transactions, increment counters of itemset");
      transatraverse(k);

      createlargeitemset(k);
      System.out.println("Frequent "+k+"-itemsets:");
      fn.append("Frequent "+k+"-itemsets:");
     // System.out.println((Vector)(largeitemset.elementAt(k-1)));
	  Vector tempStr = (Vector)(largeitemset.elementAt(k - 1));
          Vector secondtempstr = (Vector)(largeperlist.elementAt(k - 1));
	  if (tempStr!=null)
	  {
		  
		  
		  //index = tempStr.toString().trim().substring(1,2);
                    index =secondtempstr.toString().trim();
                    //System.out.println("sachin "+index +" end");
                    StringTokenizer st2 = new StringTokenizer(index,"[ ]$");
                    while (st2.hasMoreTokens())
		  {
                     // System.out.print(st2.nextToken()+"  ");
                      String intstr =st2.nextToken();
                       if (intstr.indexOf('#') != -1)
			  {
                           intstr=intstr.replace('#', ' ');
                           all.append(intstr+" ");
                       }
                       else
                       {
                        all.append(" " + itemArray[Integer.parseInt(intstr.trim())-1]);
                       }
                      
                    }
                    all.append("\n");
                    
		  index1 = tempStr.toString().trim();
		  StringTokenizer st = new StringTokenizer(index1,"[ ]");
		  System.out.print("Items are [ ");
                  fn.append("Items are [ ");
		  while (st.hasMoreTokens())
		  {
			  //itemArray[];
			  //System.out.println(st.nextToken());
			  String str = st.nextToken();
			  
			  if (str.indexOf(',') != -1)
			  {
				  str=str.replace(',', ' ');				  
				  System.out.print(" " + itemArray[Integer.parseInt(str.trim())-1]+",");
                                  fn.append(" " + itemArray[Integer.parseInt(str.trim())-1]+",");
			  }
                          else if(str.indexOf('#') != -1)
                          {
                              str=str.replace('#', ' ');
                            System.out.print(str);
                            fn.append(str);
                          }
			  else
                          {	  System.out.print(" " + itemArray[Integer.parseInt(str.trim())-1]);
                          fn.append(" " + itemArray[Integer.parseInt(str.trim())-1]);
                          }
		  }
		  System.out.print(" ]");
                  fn.append("]\n");
		  //System.out.println("@@@" +index.trim());
		 // System.out.println("???"+index1.trim());
		}
		//int i1 = Integer.valueOf(index.trim());
	//	int i2  = Integer.valueOf(index1.trim());
		//System.out.println("$$$$$$"+i1+" "+i2);
	//	

		//System.out.print("or any other key to continue.  ");
		/*try {
		   response = reader.readLine();
		 } catch (Exception e) {
		   System.out.println(e);
		 }
*/

    }

    hashtreenode htn=new hashtreenode();
  //  htn=((candidateelement)candidate.elementAt(k-2)).htroot;

	//printhashtree(htn, "", 3);
    d=new Date();
    s2=d.getTime();
    System.out.println();
    System.out.println("Execution time is: "+((s2-s1)/1000) + " seconds.");

//System.out.println("End.");

  }
}