dic.java

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

      if (htn.ht.containsKey(Integer.toString(getitemat(c,transa))))
        checkcountedall((hashtreenode)htn.ht.get(Integer.toString(getitemat(c,transa))),transa,c);

  }


//-------------------------------------------------------------
//  Method Name: checkcounter
//  Purpose    : ( DC==>DS )
//             : travese hashtree to chech if an itemset node is stated DC and 
//             : it's counter>=minsup, then change its state to DS 
//  Parameter  : htn is a hashtreenode (when other method call this method,it is the root)
//             : transa : transaction
//             : startfrom : recursive depth
//  Return     : 
//-------------------------------------------------------------
  public void checkcounter(hashtreenode htn,String transa,int startfrom) { 

    if (htn.state==DC && htn.counter >= ((minsup*M)/100))
      htn.state=DS;

    if ( htn.ht.isEmpty())
      return;

    for (int c=startfrom+1;c<=N;c++)
      if (htn.ht.containsKey(Integer.toString(getitemat(c,transa)))) {
        checkcounter((hashtreenode)htn.ht.get(Integer.toString(getitemat(c,transa))),transa,c);
      }
  }


//-------------------------------------------------------------
//  Method Name: checkhashtree
//  Purpose    : traversal hashtree 
//             : for each of DS node's superset
//             : if all subset of it are SS/SC/DS
//             : generate new hashtreenode, and link it to its father
//             : e.g. tran="2 3 4 5", a=2, then, only "4 5" need traversal.
//  Parameter  : htn is a hashtreenode (when other method call this method,it is the root)
//             : transa : transaction
//             : transa: special transaction that includes all items
//             : startfrom : recursive depth, only check itemset_part after startfrom-th item
//  Return     : 
//-------------------------------------------------------------
  public void checkhashtree(hashtreenode htn,String transa,int startfrom) { 

    String superset=new String();
    String subset=new String();
    StringTokenizer stsuperset,stsubset;
    boolean dcfound;
 
    if ( htn.state==DS ) {
      superset=gensuperset(htn.itemset);
      if (superset!=null) {
        stsuperset=new StringTokenizer(superset,",");
        while (stsuperset.hasMoreTokens()) {
          String superset1=new String(stsuperset.nextToken());
          if (htn.ht.containsKey(Integer.toString(getitemat(itemsetsize(superset1),superset1))))
            continue ;
          subset=gensubset(superset1);
          stsubset=new StringTokenizer(subset,",");
          dcfound=false;
          while (stsubset.hasMoreTokens())
            if (circlefound(root,stsubset.nextToken(),0)) {
              dcfound=true;
              break;
            }
          if (!dcfound) {
            hashtreenode tmphtn=new hashtreenode(DC,superset1,0,tid,k);
            htn.ht.put(Integer.toString(getitemat(itemsetsize(superset1),superset1)),tmphtn);
          }
        }
      }
    }

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

    for (int c=startfrom+1;c<=N;c++)
      if (htn.ht.containsKey(Integer.toString(getitemat(c,transa))))
        checkhashtree((hashtreenode)htn.ht.get(Integer.toString(getitemat(c,transa))),transa,c);

  } //end public void checkhashtree(hashtreenode htn,String spetransa,int startfrom)


//-------------------------------------------------------------
//  Method Name: circlefound
//  Purpose    : called by checkhashtree
//  Parameter  : htn is a hashtreenode (when other method call this method,it is the root)
//             : transa : transaction
//             : transa: special transaction that includes all items
//             : startfrom : recursive depth, only check itemset_part after startfrom-th item
//  Return     : 
//-------------------------------------------------------------
  public boolean circlefound(hashtreenode htn,String itemset,int startfrom) {
    
    if (htn.state==DC || htn.state==SC)
      return true;

    for (int c=startfrom+1;c<=itemsetsize(itemset);c++)
      if (htn.ht.containsKey(Integer.toString(getitemat(c,itemset))))
        if (circlefound((hashtreenode)htn.ht.get(Integer.toString(getitemat(c,itemset))),itemset,c))
          return true;

    return false;
  }


//-------------------------------------------------------------
//  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: gensuperset
//  Purpose    : generate all superset given an itemset 
//  Parameter  : itemset
//  Return     : a string contains all superset deliminated by ","
//             : e.g. "1 2,1 3,1 4" is superset of "1"
//-------------------------------------------------------------
  public String gensuperset(String itemset) {
    
    String str1,str2;
    int c;
    int i1=itemset.lastIndexOf(" ");

    if (i1==-1)
      str1=new String(itemset);
    else
      str1=new String(itemset.substring(i1+1));
    c=Integer.valueOf(str1).intValue();
    if (c==N)
      return null;
    else  {
      str2=new String();
      for (int b=c+1;b<N;b++) {
        str2=str2.concat(itemset);
        str2=str2.concat(" ");
        str2=str2.concat(Integer.toString(b));
        str2=str2.concat(",");
      }
      str2=str2.concat(itemset);
      str2=str2.concat(" ");
      str2=str2.concat(Integer.toString(N));
    }
    return str2;
  }


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

    String fullitemset=new String();
    String transa=new String();
    int j;
    String str0;
    FileInputStream file_in;
    DataInputStream data_in;
    String oneline=new String();
    StringTokenizer st;
    int lineprocessed;
    boolean qiaole=false;
    Date d=new Date();
    long s1,s2;
    String ss1,ss2;
    int numRead=0;

    System.out.println("\nAlgorithm DIC starting now.....\n");
    getconfig();

    // generating 1-itemset in root.
    root=new hashtreenode(SS,null,0,1,0);
    for (int i=1;i<=N;i++) {
      String str=new String(Integer.toString(i));
      hashtreenode htn=new hashtreenode(DC,str,0,1,0);
      if (root.ht==null) {
        Hashtable ht=new Hashtable();
        root.ht=ht;
      }
      root.ht.put(str,htn);
    }

    file_in = new FileInputStream(transafile);
    data_in = new DataInputStream(file_in);

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

    k=0;
    tid=1;
    lineprocessed=0;

    d=new Date();
    s1=d.getTime();
    System.out.print("Processing step M number: ");

    while (true) {
      k++;
      System.out.print(k+"..");
      // if no dashed item exsits, program ends.
      if (!dashfound(root))
        break;
      lineprocessed=0;
      while (true) {
        oneline=data_in.readLine();
        numRead++;
        if ((oneline==null) || (numRead > M)) {
	  numRead=0;
          file_in = new FileInputStream(transafile);
          data_in = new DataInputStream(file_in);
          if (qiaole) {
            oneline=data_in.readLine();
            tid=1;
          }
          else {
            tid=1;
            break;
          }
        }
        st=new StringTokenizer(oneline.trim());
        j=0;
	str0=new String();
	transa=new String();
        while (st.hasMoreTokens()) {
          j++;
          str0=st.nextToken();
          int i=Integer.valueOf(str0).intValue();
          if (i!=0) {
            transa=transa.concat(" ");
            transa=transa.concat(Integer.toString(j));
          }
        }
        transa=transa.trim();
        transatrahashtree(transa,root,0);
        lineprocessed++;
        tid++;
        if (lineprocessed>=stepm && tid>M)
            qiaole=true;
        else
	    qiaole=false;

        if (tid>M) 
          tid=1;

        if (lineprocessed>=stepm)
            break;
      }

//System.out.println("Now checking counter to find those whose counter>minsup...");
      checkcounter(root,fullitemset,0);
//System.out.println("Now checking hashtree to find those whose superset should be generated...");
      checkhashtree(root,fullitemset,0);
//System.out.println("Now checking those count all through and not need counting any more...");
      checkcountedall(root,fullitemset,0);

    }

    DSset=new String();
    DCset=new String();
    SCset=new String();
    SSset=new String();
    printhashtree(root,fullitemset,0);
    System.out.println("\n");

    StringTokenizer sss;
      int i=1;
      j=1;
      boolean found=false, first=true;
      while (true) {
	first=true;
        sss=new StringTokenizer(SSset,",");
        found=false;
        while (sss.hasMoreTokens()) {
          String superset1=new String(sss.nextToken());
          if ((superset1.length()==i) && (superset1.length() > 0)) {
	    if(first) {
	      System.out.println("Frequent "+j+"-itemsets:");
	      first=false;
	      System.out.print("["+superset1);
	    }
	    else
	      System.out.print(", "+superset1);
            found=true;
          }
        }
	if (found == true)
	  System.out.print("]");
	System.out.println();
        if (!found)
          break;
        i=i+2;
        j++;
      }

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

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

  }
}