fptree.java

java platform java-growth algorithm

/* -------------------------------------------------------------------------- */
/*                                                                            */
/*                          FP   T R E E   C L A S S                          */
/*                                                                            */
/*                                 Frans Coenen                               */
/*                                                                            */
/*                                 25 May 2001                                */
/*                    (Revised 5 February 2003, 3 February 2006)              */ 
/*                                                                            */
/*                        Department of Computer Science                      */
/*                          The University of Liverpool                       */
/*                                                                            */
/* -------------------------------------------------------------------------- */

/* Structure:

AssocRuleMining
      |
      +-- TotalSupportTree	 
                  |
		  +-- FPtree		*/ 

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

/** Implementation of Han's FP-growth ARM algorithm. 
@author Frans Coenen
@version 5 February 2003 */
                             
public class FPtree extends TotalSupportTree {
    
    /* ------ FIELDS ------ */
    
    /** FP-tree node structure comprising a <TT>FPgrowthItemPrefixSubtreeNode</TT> in 
    which to store counts and a reference to a child branch. */
    
    protected class FPtreeNode {
        /** The FP tree node. */
        private FPgrowthItemPrefixSubtreeNode node = null;
	/** The reference to the child branch (levels in FP-tree branches are
	stored as a arrays of <TT>FPtreeNode</TT> structures. */ 
        private FPtreeNode[] childRefs = null;
        
	/** Default constructor. */

	protected FPtreeNode() {
	    }  
	    
	/** Single argument constructor. 
	@param newNode the reference to a new node to be included in the
	FP-tree.*/
	
	protected FPtreeNode(FPgrowthItemPrefixSubtreeNode newNode) {
	    node = newNode;
	    }
	}
    
    /** Prefix subtree structure. <P> A set enumeration tree in which to store
    itemsets together with support values. */
    
    private class FPgrowthItemPrefixSubtreeNode {
        /** The attribute identifier. */
        private short itemName;
	/** The support count. */
	private int itemCount;
	/** The backward link to the parent node in FP tree. */
	private FPgrowthItemPrefixSubtreeNode parentRef = null;
	/** The forward link to the next node in a linked list of nodes with
	same attribute identifier starting with an element in the header table
	(array). */
	private FPgrowthItemPrefixSubtreeNode nodeLink = null;
	
	/** Default constructor. */
	
	private FPgrowthItemPrefixSubtreeNode() {
	    }
	
	/** Three argument constructor. 
	@param name the itemset identifier. 
	@param support the support value for the itemset.
	@param backRef the backward link to the parent node. */
	
	private FPgrowthItemPrefixSubtreeNode(short name, int support, 
			FPgrowthItemPrefixSubtreeNode backRef) {
	    itemName = name;
	    itemCount = support;
	    parentRef = backRef;
	    }
	}
    
    /** Header table. <P> Array of these structures used to link into FP-tree.
    All FP-tree nodes with the same identifier are linked together starting
    from a node in a header table (made up of <TT>HeaderTasble</TT> structures).
    It is this "cross" linking that gives the FP-tree its most significant
    advantage. */
    
    protected class FPgrowthHeaderTable {
        /** The 1-itemset (attribute) identifier. */
	protected short itemName;
	/** The forward link to the next node in the link list of nodes. */
        protected FPgrowthItemPrefixSubtreeNode nodeLink = null;
        
	// Constructors

	protected FPgrowthHeaderTable (short columnNum) {
	    itemName = columnNum;
	    }  
        }
	
    /** Structure in which to store ancestor itemSets, i.e. nodes in an FP-tree
    that preceed the nodes identified by following a trail of links from a
    particular item in the header table. */
    
    private class FPgrowthSupportedSets {
        /** The itemSet label. */
        private short[] itemSet = null;
	/** The associated support value for the given itemset. */
        private int support;
	/** The reference to the next node in a linked list. */
	private FPgrowthSupportedSets nodeLink = null;
        
	/** Three argument constructor.
	@param newitemSet the given itemSet label.
	@param newSupport the associated support value for the given itemset. 
	@param newNodeLink the reference to the next node in a linked list. */
	
	private FPgrowthSupportedSets(short[] newitemSet, int newSupport, 
			FPgrowthSupportedSets newNodeLink) {
	    itemSet = newitemSet;
            support = newSupport;
	    nodeLink = newNodeLink;
	    } 
	} 
    
    /** Structure in which to store counts. */
    
    private class FPgrowthColumnCounts {
        /** The column/attribute ID number. */
        private short columnNum;
	/** The associated support value. */
        private int support=0;
        
	/** One argument constructor.
	@param column the column/attribute ID number. */

	private FPgrowthColumnCounts(int column) {
	    columnNum = (short) column;
	    }  
        
	/** Two argument constructor.
	@param column the column/attribute ID number. 
	@param sup the associatec support value. */
	
	private FPgrowthColumnCounts(int column, int sup) {
	    columnNum = (short) column;
	    support = sup;
	    }  
	}   
	
    // Data structures
    
    /** Start reference for FP-tree. */
    protected FPtreeNode rootNode = null;
    /** Start reference for header table. */
    protected FPgrowthHeaderTable[] headerTable; 
    /** Start reference for supportedSets linked list (temporary storage 
    only).*/
    private static FPgrowthSupportedSets startTempSets = null;
    
    // Other fields 
    
    /** Temporary storage for an index into an array of FP-tree nodes. </P>
    Used when reassigning child reference arrays. */
    private int tempIndex  = 0;    	
    /** Number of nodes created. */
    private int numberOfNodes;
    
    /* ------ CONSTRUCTORS ------ */
    
    /** Constructor to process command line argument.
    @param args the command line arguments. */
    
    public FPtree(String[] args) {
	super(args);
	
	// Initialise root node
	rootNode = new FPtreeNode();
	
	// Create header table	
	headerTable = new FPgrowthHeaderTable[numOneItemSets+1];
	
	// Populate header table	
	for (int index=1;index<headerTable.length;index++) {
	    headerTable[index] = new FPgrowthHeaderTable((short) index);
	    }
	}	
    
    /* ------ METHODS ------ */
    
    /*-------------------------------------------------------------------*/
    /*                                                                   */
    /*                             GENERATE FP-TREE                      */
    /*                                                                   */
    /*-------------------------------------------------------------------*/  
    
    /* CREATE FP-TREE */   
    /** Top level method to commence the construction of the FP-Tree. */
    
    public void createFPtree() {      
	//System.out.println("GENERATING FP-TREE\n------------------");
	
	// Create header table	
	headerTable = new FPgrowthHeaderTable[numOneItemSets+1];
	
	// Populate header table	
	for (int index=1;index<headerTable.length;index++) {
	    headerTable[index] = new FPgrowthHeaderTable((short) index);
	    }
	    
	// Process datatable, loop through data table (stored in data array)
	// For each entry add the entry to the FP-tree.

	for (int index=0;index<dataArray.length;index++) {
	    // Non null record (if initial data set has been reordered and
	    // pruned some records may be empty
	    if (dataArray[index] != null) 
	    	addToFPtree(rootNode,0,dataArray[index],1,headerTable);
	    }         	                                                  
	}

    /* ADD TO FP-TREE */   
    /** Searches through current list of child refs looking for given item set.
    <P> If reference for current itemset found increments support count and 
    proceed down branch, otherwise adds to current level. 
    @param ref the current location in the FP-tree (<TT>rootNode</TT> at start).
    @param place the current index in the given itemset.
    @param itemSet the given itemset.
    @param support the associated support value for the given itemset.
    @param headerRef the link to the appropriate place in the header table. */
    
    private void addToFPtree(FPtreeNode ref, int place, short[] itemSet, 
    				int support, FPgrowthHeaderTable[] headerRef) {  
	if (place < itemSet.length) {
	    if (!addToFPtree1(ref,place,itemSet,support,headerRef)) 
	    		addToFPtree2(ref,place,itemSet,support,headerRef);
	    }
	}
	
    /* ADD TO FP TREE 1 */    
    /** Searches through existing branch and if itemset found updates the 
    support count and returns true, otherwise return false. 
    @param ref the current FP-tree node reference.
    @param place the current index in the given itemset.
    @param itemSet the given itemset.
    @param support the associated support value for the given itemset.
    @param headerRef the link to the appropriate place in the header table. 
    @return true if given itemset exists in FP-tree, and false otherwise. */
    
    private boolean addToFPtree1(FPtreeNode ref, int place, short[] itemSet,
    			int support, FPgrowthHeaderTable[] headerRef) {	
			
	// Loop	
	if (ref.childRefs != null) {
	    for (int index=0;index<ref.childRefs.length;index++) {
	        // If item is already in list of child refs
	        // increment count and proceed down branch.
	        if (itemSet[place] == ref.childRefs[index].node.itemName) {
	            ref.childRefs[index].node.itemCount =
		                 ref.childRefs[index].node.itemCount + support;
		    numUpdates++;
		    addToFPtree(ref.childRefs[index],place+1,itemSet,support,
		    		headerRef);
		    return(true);
		    }
	        // Child refs ordered lexicographically so break when passed
		// point where item should be
		if (itemSet[place] < ref.childRefs[index].node.itemName) 
					return(false);
		}
	    }	
        
	// Default
	
	return(false);
	}

    /* ADD TO FP TREE 2 */
    
    /** Adds new node to FP-tree. <P> Adds first attribute in itemSet and then 
    rest of sequence. 
    @param ref the current FP-tree node reference.
    @param place the current index in the given itemset.
    @param itemSet the given itemset.
    @param support the associated support value for the given itemset.
    @param headerRef the link to the appropriate place in the header table. */
    
    private void addToFPtree2(FPtreeNode ref, int place, short[] itemSet,
    				int support, FPgrowthHeaderTable[] headerRef) {	
	
	// Create new Item Prefix Subtree Node
	FPgrowthItemPrefixSubtreeNode newPrefixNode = new 
	    		FPgrowthItemPrefixSubtreeNode(itemSet[place],support,ref.node);
	// Create new FP tree node incorporating new Item Prefix Subtree Node
	FPtreeNode newFPtreeNode = new FPtreeNode(newPrefixNode);
	// Add link from header table
	addRefToFPgrowthHeaderTable(itemSet[place],newPrefixNode,headerRef);
	// Add into FP tree
	ref.childRefs = reallocFPtreeChildRefs(ref.childRefs,newFPtreeNode);
	// Proceed down branch with rest of itemSet
	addRestOfitemSet(ref.childRefs[tempIndex],newPrefixNode,place+1,itemSet,
				support,headerRef);
	}
    
    /* ADD REST OF ITEMSET */
    
    /** Continues adding attributes in current itemset to FP-tree. 
    @param ref the current FP-tree node reference.
    @param backRef the backwards link to the previous node.
    @param place the current index in the given itemset.
    @param itemSet the given itemset.
    @param support the associated support value for the given itemset.
    @param headerRef the link to the appropriate place in the header table. */
    
    private void addRestOfitemSet(FPtreeNode ref, FPgrowthItemPrefixSubtreeNode backRef, 
    				int place, short[] itemSet, int support, 
						FPgrowthHeaderTable[] headerRef) {
        
	// Process if more items in item set.
	if (place<itemSet.length) {
	    // Create new Item Prefix Subtree Node
	    FPgrowthItemPrefixSubtreeNode newPrefixNode = new
	    		FPgrowthItemPrefixSubtreeNode(itemSet[place],support,backRef);
	    // Create new FP tree node incorporating new Item Prefix Subtree 
	    // Node
	    FPtreeNode newFPtreeNode = new FPtreeNode(newPrefixNode);
	    // Add link from header table
	    addRefToFPgrowthHeaderTable(itemSet[place],newPrefixNode,headerRef);
	    ref.childRefs = reallocFPtreeChildRefs(ref.childRefs,newFPtreeNode);
	    // Add into FP tree
	    addRestOfitemSet(ref.childRefs[tempIndex],newPrefixNode,place+1,
	    					itemSet,support,headerRef);
	    }
	}
	    
    /* ADD REF TO HEADER TABLE */
    
    /** Adds reference to new FP-tree node to header table moving old reference 
    so that it becomes a link from the new FP-tree node.
    @param columnNumber the given attribute.
    @param newNode the newly created FP-tree node.
    @param headerRef the reference to the header table (array). */