itemtree.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

  /**
   * Returns list of large itemsets.
   * Added by M. Thess.
   *
   * @param root root element of item tree
   * @return list of large itemsets
   */
  ItemSetList getLargeItemSetList(ItemTreeElement root) {

    ItemSetList largeItemSetList = new ItemSetList();
    largeItemSet                 = new ItemSet();
    getLargeItemSetList(largeItemSetList, root);
    return largeItemSetList;
  }

  /**
   * Returns list of large itemsets recursively.
   * Added by M. Thess.
   *
   * @param largeItemSetList list of large itemsets
   * @param r current item tree element
   */
  private void getLargeItemSetList(ItemSetList largeItemSetList, ItemTreeElement r) {

    for (int i = 0; i < r.next.size(); i++) {
      ItemTreeElement currItem = ((ItemTreeElement) r.next.elementAt(i));
      largeItemSet.addItem(currItem.item);
      largeItemSet.setSupportCount(currItem.count);
      ItemSet cpLargeItemSet = new ItemSet(largeItemSet);
      largeItemSetList.addItemSet(cpLargeItemSet);
      getLargeItemSetList(largeItemSetList, currItem);
      largeItemSet.delItemAt(largeItemSet.getSize()-1);
    };
  }


  ItemSetList genrules2 (TransactionSet tset, RuleSetList rulesetlist, double minconf) {
   largeItemSet=new ItemSet();
   largesetlist=new ItemSetList();
   gen_rules2(this.tree, tset, rulesetlist, minconf);
   return largesetlist;
  }

  private void gen_rules2(ItemTreeElement r,TransactionSet tset, RuleSetList rulesetlist,double minconf ) {
   for (int i=0; i<r.next.size();i++) {
    ItemTreeElement currItem=((ItemTreeElement)r.next.elementAt(i));
    largeItemSet.addItem(currItem.item);
    largeItemSet.setSupportCount(currItem.count);
    if (dbg) largeItemSet.print();
    largesetlist.addItemSet(new ItemSet(largeItemSet));
    if (largeItemSet.getSize()>1) // now have the current large ItemSet l_k
           genrules2(largeItemSet, largeItemSet, tset, rulesetlist, minconf);
    gen_rules2(currItem, tset, rulesetlist,  minconf);
    largeItemSet.delItemAt(largeItemSet.getSize()-1);
   }
  }


private void genrules2(ItemSet is1, ItemSet is2,TransactionSet tset,
                     RuleSetList rulelist,  double minconf) //the "real" genrules part
{
 ItemSet a;
 ItemSet b;
 RuleSet rule;
 ItemSetList H=new ItemSetList();
 double confidence;

 for (int i=0; i<is2.getSize(); i++) // don't add the i-th item to current a
 {
 	a=new ItemSet();
 	for (int j=0; j<is2.getSize(); j++) if (j!=i) a.addItem(is2.getIntegerAt(j));
 	confidence=(double)is1.getSupportCount()/this.getSupportCount(a);
 	if (confidence>=minconf)
 	{
 	 ItemSet is=new ItemSet(); is.addItem(is1.getIntegerAt(i));
 	 H.addItemSet(is);
 	 // consequent of rule derived from l_k w/ one item in the consequent


 	 //for (int k=0; k<is1.getSize(); k++)
 	 // if ( !a.contains(is1.getIntegerAt(k))) b.addItem(is1.getIntegerAt(k));

 	 rule=new RuleSet(a,is,(double)is1.getSupportCount()/tset.getSize(),confidence);
 	 if (!rulelist.contains(rule)) rulelist.addRule(rule);
 	 //if (a.getSize()>1) genrules(is1,a,tset,rulelist,minconf);
 	}
 }
 //////System.out.println("H_1:"); H.print();
 //rulelist.print();

 ap_genrules(is1,H,rulelist,minconf);
}


 private void ap_genrules(ItemSet l, ItemSetList h,RuleSetList rulelist, double minconf) {
   RuleSet rule;
    // ap-genrules(...)
    //System.out.println("---"+h.getSize());
    ///////if (h.getSize()==0) return;
    if (l.getSize()>h.getItemSetAt(0).getSize()+1) {
      ItemSet p,q;
      ItemSetList c=new ItemSetList();

      //apriori-gen(...)
      for (int pi=0; pi<h.getSize(); pi++) {
        for (int qi=0; qi<h.getSize(); qi++) if (pi!=qi) {

          p=h.getItemSetAt(pi);
          q=h.getItemSetAt(qi);
          boolean failed=false;
         /// System.out.println("p & q");
         /// p.print();           q.print();

          for (int i=0; i<p.getSize()-1 && !failed; i++)
            if (p.getIntegerAt(i)!=q.getIntegerAt(i)) failed=true;
         ///System.out.println("#"+failed);
          if (!failed) if (p.getIntegerAt(p.getSize()-1)<q.getIntegerAt(p.getSize()-1)){
           ItemSet is=new ItemSet(p);
           //is.delItemAt(is.getSize()-1);
           is.addItem(q.getIntegerAt(p.getSize()-1));
           c.addItemSet(is);
           //System.out.println("add item"); is.print();
          }
        }
      }

      // now the prune step
      //System.out.println("before prune"+c.getSize());
      //c.print();
      //if (c.getSize()>0)
      for (int i=0; i<c.getSize(); i++) {
        //System.out.println("before"+c.getSize());
        ItemSet is=c.getItemSetAt(i);
        //System.out.println("after");is.print();

        boolean found=true;
        for (int j=0; j<is.getSize() && found; j++) {
          ItemSet sub=new ItemSet(is);
          sub.delItemAt(j);
          //System.out.println("is="); is.print();
          //System.out.println("sub="); sub.print();
          if (!this.contains(sub)) {found=false; break;}
        }
        if (!found) c.delItemSetAt(i--);
      }


      // done with apriori-gen
      //System.out.println("nach apriori-gen"); c.print();
      for (int i=0; i<c.getSize(); i++) { // forall h_m+1 \in H_m+1
        ItemSet conseq=new ItemSet();

        ItemSet is=c.getItemSetAt(i); // ..==h_m+1

        for (int j=0; j<l.getSize(); j++)
          if (!is.contains(l.getIntegerAt(j))) conseq.addItem(l.getIntegerAt(j));
        /// conseq==l_k - h_m+1
        //System.out.println("D"+c.getSize());
        double conf=(double)this.getSupportCount(l)/this.getSupportCount(conseq);
        //System.out.println("conf="+conf+" minconf="+tset.getMinSuppCount()+
          //                 "   "+this.getSupportCount(l) +"   "+this.getSupportCount(conseq));

        if (conf>=minconf) {
           rule=new RuleSet(conseq,is,(double)l.getSupportCount()/tset.getSize(),conf);
 	       if (!rulelist.contains(rule)) rulelist.addRule(rule);
 	       //System.out.println("RULELIST:");
 	      // rulelist.print();
        }
        else {
          //System.out.println("vorher:");
            //c.print();
         c.delItemSetAt(c.indexOf(is));
         i--;
         //System.out.println("delete:"); is.print();
         //c.print();
        }
      }
      //System.out.println("E"+c.getSize());
      ap_genrules(l, c,rulelist,minconf);

    }
 }




 ItemSetList genrules(TransactionSet tset, RuleSetList rulesetlist,double minconf) {
   largeItemSet=new ItemSet();
   largesetlist=new ItemSetList();
   gen_rules(this.tree, tset, rulesetlist, minconf);
   return largesetlist;
  }

 private void gen_rules(ItemTreeElement r,TransactionSet tset, RuleSetList rulesetlist,double minconf ) {
   for (int i=0; i<r.next.size();i++) {
    ItemTreeElement currItem=((ItemTreeElement)r.next.elementAt(i));
    largeItemSet.addItem(currItem.item);
    largeItemSet.setSupportCount(currItem.count);
    if (dbg) largeItemSet.print();
    /* changed from Holm */
    ItemSet is = new ItemSet(largeItemSet);
    is.setSupportCount(largeItemSet.getSupportCount());
    largesetlist.addItemSet(is);
    /* end of changes */
    if (largeItemSet.getSize()>1) // now have the current large ItemSet l_k
      genrules(largeItemSet, largeItemSet, tset, rulesetlist, minconf);
    gen_rules(currItem, tset, rulesetlist,  minconf);
    largeItemSet.delItemAt(largeItemSet.getSize()-1);
   }
  }



  private void genrules(ItemSet is1, ItemSet is2,TransactionSet tset,
                     RuleSetList rulelist,  double minconf)
{
 ItemSet a;
 ItemSet b;
 RuleSet rule;
 double confidence;

 for (int i=0; i<is2.getSize(); i++)
 {
 	a=new ItemSet();
 	for (int j=0; j<is2.getSize(); j++) if (j!=i) a.addItem(is2.getIntegerAt(j));
 	confidence=(double)is1.getSupportCount()/this.getSupportCount(a);
 	if (confidence>=minconf)
 	{
     b=new ItemSet();
 	 for (int k=0; k<is1.getSize(); k++)
 	  if ( !a.contains(is1.getIntegerAt(k))) b.addItem(is1.getIntegerAt(k));
 	 rule=new RuleSet(a,b,(double)is1.getSupportCount()/tset.getSize(),confidence);
 	 if (!rulelist.contains(rule)) rulelist.addRule(rule);
 	 if (a.getSize()>1) genrules(is1,a,tset,rulelist,minconf);
 	}
 }
}




}