itemtree.java

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

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/**
 * Title:        prudsys basket analysis
 * Description:  Basket analysis algorithms
 * Copyright:    Copyright (c) 2001
 * Company:      PRUDENTIAL SYSTEMS SOFTWARE GmbH
 * @author Stefan Ludwig
 * @author Michael Thess
 * @version 1.0
 */
package com.prudsys.pdm.Models.Sequential.Algorithms.SeqSimple;

import java.util.Vector;

import com.prudsys.pdm.Models.AssociationRules.ItemSet;
import com.prudsys.pdm.Models.AssociationRules.RuleSet;

/**
 * n-ary tree to store all the temporary itemsets.
 * A itemset can only be added to the tree if a subset with only one item less is already in the tree.
 * This constraint (actually a property of the Apriori algorithm) allows it to store/search the itemsets efficiently
 *
 * Extended by the function largeItemSetList() by M. Thess.
 *
 * @author Stefan Ludwig
 * @author Michael Thess
 * @version 05. 07. 1999, 2001/05/07
 */
class ItemTree{

    static boolean dbg=false;


    ItemTreeElement tree;
    TransactionSet tset;
    boolean addedsth;
    ItemSet largeItemSet;
    ItemSetList largesetlist;

    /**
     * Construct an ItemTree from an ItemSetList.
     * The itemsets in the ItemSetList must contain only one item - all other items are ignored.
     *
     * @param isl ItemSetList with itemsets of only one item
     */

    ItemTree(ItemSetList isl) {
      int item;
      int count;
      tree=new ItemTreeElement(-1,-1);

      for (int i=0; i<isl.getSize(); i++)
       { item= ((ItemSet)isl.itemset.elementAt(i)).getIntegerAt(0);
         count=((ItemSet)isl.itemset.elementAt(i)).getSupportCount();
         tree.addItem(item,count);
       }

    }


    void setTransactionSet(TransactionSet transactionset) {tset=transactionset;}

    /**
     * Add an ItemSet to the ItemTree.
     * The ItemSet must already be sorted.
     *
     */


    void addItemSet(ItemSet is) {

      ItemTreeElement root=tree;
      int i,j;
      for (i=0; i<is.getSize()-1; i++) // go down tree up to second last item
        {
          for (j=0; j<root.next.size()
                   && ((ItemTreeElement)(root.next.elementAt(j))).item!=is.getIntegerAt(i);) j++;
          //System.out.println("j="+j);
          if (j<root.next.size()) {root=(ItemTreeElement)root.next.elementAt(j);
                                   //System.out.print("ROOT --> "); root.print(); System.out.println(" <--");
                                   }
                            else  {root=null; System.out.println("AIS:subset not in tree"); is.print();return;}
        }
      for (j=0; j<root.next.size()
                   && ((ItemTreeElement)(root.next.elementAt(j))).item!=is.getIntegerAt(is.getSize()-1);) j++;
      if (j<root.next.size()) {System.out.println("already in tree!"); return;}
      root.addItem(is.getIntegerAt(is.getSize()-1), is.getSupportCount());
    }

    /**
     * Delete an ItemSet from the ItemTree.
     * The ItemSet must already be sorted.
     *
     */

    void delItemSet(ItemSet is) {
      ItemTreeElement root=tree;
      ItemTreeElement oldroot=root;

      //System.out.print("ROOT --> "); root.print(); System.out.println(" <--");
      int i,j;
      for (i=0; i<is.getSize(); i++) // go down tree
        { for (j=0; j<root.next.size()
                   && ((ItemTreeElement)(root.next.elementAt(j))).item!=is.getIntegerAt(i);) j++;
          System.out.println("j="+j);
          if (j<root.next.size()) {oldroot=root; root=(ItemTreeElement)root.next.elementAt(j);
                                   //System.out.print("ROOT --> "); root.print(); System.out.println(" <--");
                                   }
                            else  {root=null; System.out.print("DIS:subset not in tree");is.print(); return;}
        }
      oldroot.next=new Vector(); //Delete this set and all subtrees under it
    }

    int getSupportCount(ItemSet is) {

      ItemTreeElement root=tree;
      //System.out.print("ROOT --> "); root.print(); System.out.println(" <--");
      int i,j;
      for (i=0; i<is.getSize(); i++) // go down tree
        { for (j=0; j<root.next.size()
                   && ((ItemTreeElement)(root.next.elementAt(j))).item!=is.getIntegerAt(i);) j++;
          //System.out.println("j="+j);
          if (j<root.next.size()) {root=(ItemTreeElement)root.next.elementAt(j);
                                   //System.out.print("ROOT --> "); root.print(); System.out.println(" <--");
                                   }
                            else  {root=null;
                                   //System.out.print("gsc:subset not in tree"); is.print();
                                   return -1;}
        }
      return root.count;
    }


    boolean contains(ItemSet is) {
        return (getSupportCount(is)>=0);
    }

    ItemSetList generateCandidates(int currSize) {
        ItemSetList isl=new ItemSetList();
        return isl;
    }

    void print() {
        System.out.println("root's next field contains:");
        for (int i=0; i<tree.next.size(); i++)
          {((ItemTreeElement)(tree.next.elementAt(i))).print();  System.out.println();}
    }

    boolean filltree(int depth) {
        addedsth=false;
        boolean r=filltree_rec(tree,new ItemSet(), 1,depth);
        if (dbg) System.out.println("filltree("+depth+") returns="+r);
        return r;
    }

    private boolean filltree_rec(ItemTreeElement root, ItemSet prefix,int depth,int pdepth) {
      if (root.next.size()==0) {prefix=new ItemSet(); return false;}
      if (depth==pdepth) {//System.out.println("\ndepth="+depth);
     // System.out.println("\np-item="+root.item+"\t");
      //prefix.print();
      ItemSet postfix=new ItemSet();
      for (int i=0; i<root.next.size(); i++) {
        ItemTreeElement ite= (ItemTreeElement)(root.next.elementAt(i));

        //System.out.print(ite.item+"-"+ite.count+"/"+ite.next.size()+"\t");
        if (depth>1) prefix=new ItemSet(prefix,root.item); else prefix=new ItemSet();
        postfix.addItem(ite.item);
      }
      ///prefix.print();
      ///postfix.print();
      ///System.out.println();
      // now generating & testing the candidates

      for (int i=0; i< postfix.getSize();i++)
        for (int j=0; j< postfix.getSize(); j++) {

          if (postfix.getIntegerAt(i)<postfix.getIntegerAt(j))
          {
           ItemSet candidate=new ItemSet(prefix,postfix.getIntegerAt(i));
           candidate.addItem(postfix.getIntegerAt(j));

           // are all subsets of candidate in itemtree ?
           boolean match=true;
           for (int k=0; k<candidate.getSize() && match;k++) { //leave out k-th element
             ItemSet candsub=new ItemSet();
             for (int l=0; l<candidate.getSize(); l++)
               if (l!=k) candsub.addItem(candidate.getIntegerAt(l));
             match=this.contains(candsub);
           }
           if (match){ //all subsets are already in tree, check if candidate has minsuppcount in transSet

            int suppcount=tset.getSupportCount(candidate);
            candidate.setSupportCount(suppcount);
            if (tset.getMinSuppCount()<=suppcount)
              {//System.out.print("*"); candidate.print();
               this.addItemSet(candidate); addedsth=true;}
           }
          }
        }
      prefix=new ItemSet();
      return addedsth;}
      else {

        for (int i=0; i<root.next.size(); i++) {
          if (depth>1) prefix=new ItemSet(prefix,root.item);
          filltree_rec(((ItemTreeElement)(root.next.elementAt(i))),prefix, depth+1,pdepth);
        }
      }
      return  addedsth;
    }


  void printtree(ItemTreeElement root) {
   largeItemSet=new ItemSet();
   print_tree(root);

  }

 private void print_tree(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);
    largeItemSet.print();
    print_tree(currItem);
    largeItemSet.delItemAt(largeItemSet.getSize()-1);
   }
  }