partialsupporttree.java

多关联分类算法

/* -------------------------------------------------------------------------- */
/*                                                                            */
/*                   P A R T I A L   S U P P O R T   T R E E                  */
/*                                                                            */
/*                               Frans Coenen                                 */
/*                                                                            */
/*                          Wednesday 9 January 2003                          */
/*                             (Revised 5/7/2003)                             */
/*                                                                            */
/*                       Department of Computer Science                       */
/*                        The University of Liverpool                         */
/*                                                                            */
/* -------------------------------------------------------------------------- */


/* Structure:

AssocRuleMining
      |
      +-- TotalSupportTree
      		  |
		  +-- PartialSupportTree	 */ 

/* Java packages */ 
import java.io.*;
import java.util.*;

// Java GUI packages
import javax.swing.*;

/** Methods to implement the "Apriori-TFP" (Total From Partial) ARM algorithm 
using both the T-tree (Total support tree) and P-tree (Partial support tree 
data structures. 
@author Frans Coenen
@version 5 July 2003 */

public class PartialSupportTree extends TotalSupportTree {

    /*------------------------------------------------------------------------*/
    /*                                                                        */
    /*                                   FIELDS                               */
    /*                                                                        */
    /*------------------------------------------------------------------------*/

    /* ------ NESTED CLASSES ------ */
    
    /** Structurte to contain P-tree data in tabular form for improved
    computational efficiency when creating T-tree. <P> A 2-D array of these 
    structures is created in which to store the Ptree. */
        	
    protected class PtreeRecord {
    	/** Label for P-tree node. */
        private short[] pTreeNodeLabel = null;
	/** Uunion of a pTree node label (<TT>pTreeNodeLabel</TT>) and all its
    	ancestor node labels. */
        private short[] pTreeItemSet = null;
        /** Partial support count. */
	private int support = 0;
	
	/** Creaste P-tree record for inclusion in table.
	@param nodeLabel the label for P-tree node. 
	@param itemSet the uunion of a pTree node label (<TT>nodeLabel</TT>) 
	and all its ancestor node labels. 
	@param sup the partial support count. */
	private PtreeRecord(short[] nodeLabel, short[] itemSet, int sup) {
	    pTreeNodeLabel = nodeLabel;
	    pTreeItemSet   = itemSet;
	    support        = sup;
	    }  
        }		

    /* Array data structures for P tree */
    
    /** Null array describing an "emty" itemset. */	
    private short[]          zeroitemSet   = null;
    /** Reference variable pointing to start of P-tree. */
    private PtreeNodeTop[]   startPtreeRef = null;  	
    
    /* ------ P-TREE DATA TABLE ----- */
    
    /** Array of arrays data structures for P-tree table (used as a
    computational efficiency measure). */
    protected PtreeRecord[][] startPtreeTable = null;
    /** Array for holding the number of P-tree nodes for each possible
    cardinality given the number of attributes, maximum is equal to number of
    columns. */
    private int[] pTreeNodesOfCardinalityN  = null;
    /** Array of "markers" used during the generation of the P-tree, and
    contains "current index" values for each level of cardinality. */
    private int[] pTreeTableMarker          = null; 
    
    /* Other fields */
    
    /** Number of node updates (used for diagnostic purposes). */    
    private int numberOfNodeUpdates = 0;
    
    /*---------------------------------------------------------------------*/
    /*                                                                     */
    /*                           CONSTRUCTORS                              */
    /*                                                                     */
    /*---------------------------------------------------------------------*/

    /** Processes command line arguments. <P> The <TT>numOneItemSets</TT> is
    incremented by 1 so that indexes match the column numbers */
    	
    public PartialSupportTree(String[] args) {
        super(args);
	}
	
    /*-------------------------------------------------------------------*/
    /*                                                                   */
    /*                    TREE BUILDING METHODS                          */
    /*                                                                   */
    /*-------------------------------------------------------------------*/  
    
    /* CREATE P-TREE */

    /** Processes data set causing each row to be added to P-Tree. */
    
    public void createPtree() {        
	System.out.println("GENERATING P-TREE\n------------------");
	
	// Dimension top line of P-tree
	startPtreeRef     = new PtreeNodeTop[numOneItemSets+1];
	
	// Dimension P-tree table
        startPtreeTable          = new PtreeRecord[numOneItemSets+1][];
	pTreeNodesOfCardinalityN = new int[numOneItemSets+1];
	pTreeTableMarker         = new int[numOneItemSets+1];
	
	// Initilalise top level of Ptree with nulls
	for(int index=0;index<startPtreeRef.length;index++) 
		startPtreeRef[index] = null;
	    
	// Process input data, loop through input (stored in data array)
	// For each entry add the entry to the P-tree.	
	for (int index=0;index<dataArray.length;index++) {
	    if (dataArray[index] != null) addToPtreeTopLevel(dataArray[index]);
	    }     
	
	// Create P-tree table
	System.out.println("Creating P-tree table");
	createPtreeTable();
	}
	
    /* ADD TO P-TREE TOP LEVEL */

    /** Commences process to add an itemset to the P-tree starting with the top
    level of the tree. <P> Note that the top level is an array.
    @param itemset the given item set. */
    
    private void addToPtreeTopLevel(short[] itemSet) {
	int index = itemSet[0]; // Calculate index
	int itemSetLength = itemSet.length;

	// If single attibute itemSet create or update element, otherwise 
	// create or update element and proceed down child branch (flag = 1)
	
	if (itemSetLength == 1) { // Top level
	    if (startPtreeRef[index] == null) {
	    	startPtreeRef[index] = new PtreeNodeTop();
		pTreeNodesOfCardinalityN[1]++;
		}
	    else startPtreeRef[index].support = startPtreeRef[index].support+1;
	    numberOfNodeUpdates++; 
	    }
	    
	// itemSet length greater than 1 therefore proceed down rest of tree
	
	else {			
	    // If no top level node create one.
	    if (startPtreeRef[index] == null) {
	        startPtreeRef[index] = new PtreeNodeTop();
		pTreeNodesOfCardinalityN[1]++;
		}
	    else startPtreeRef[index].support = startPtreeRef[index].support+1;
	    numberOfNodeUpdates++; 
	    // Descend from top level node 
	    addToPtree(0,2,itemSetLength,startPtreeRef[index].childRef,
					realloc3(itemSet),index,null);
	    }	
	}
	
    /* ADD TO P-TREE */

    /** Inserts given itemset into P-tree. <P> Operates as follows:
    If found leaf node create new node and stop. Otherwise:
    <UL>
    <LI> code = 1, Increment support
    <LI> code = 2, Itemset before and subset of current node (parent)
    <LI> code = 3, Itemset before and not subset of current node (elder sibling)
    <LI> code = 4, Itemset after and superset of current node (child)
    <LI> code = 5, Itemset after and not superset of current node (younger sibling)
    </UL>
    <P>Codes generated by call the checkitemSet function. Arguments as follows:
    @param flag the type of branch currently under consideration:
    code 0 = root, 1 = child, 2 = sibling.
    @param parentLength the number of elements represented by the parent node
    of the current node. Used only when adding new "dummy" nodes to maintain
    count of number of nodes of a given size for when the Ptree table is
    generated.
    @param itemSetLength the number of elements in the current itemSet. Used
    only when adding new nodes to maintain count of number of nodes of a given
    size for when the Ptree table is generated.
    @param linkRef the reference (pointer) to current location in the P-tree.
    @param itemSet the row itemSet in the input file currently under
    consideration.
    @param topIndex the index of the element in the array marking the top level
    of the P-tree, used only when inserting new nodes hanging from this top
    level otherwise ignored.
    @param oldRef the reference (pointer) to the previous location in the P-tree,
    used when inserting new nodes. */
    
    public void addToPtree(int flag, int parentLength, int itemSetLength, 
    			PtreeNode linkRef, short[] itemSet, int topIndex, 
							PtreeNode oldRef) {
       
	// No child node hanging of previous level array therefore add new 
	// node here.
	
	if (linkRef == null) {
	    PtreeNode newRef = createPtreeNode(itemSet,itemSetLength);  
	    addSupport2(flag,newRef,topIndex,oldRef);
	    } 
	
	// Otherwise process tree

	else {
	    switch (checkItemSets(itemSet,linkRef.itemSet)) {
	        case 1:  	/* Rule 1: Same */
		    numberOfNodeUpdates++;
		    linkRef.support++;
		    break;
	        case 2:	  /* Rule 2: Before and subset (parent) */
		    beforeAndSubset(flag,itemSetLength,linkRef,itemSet,topIndex,
		    		oldRef);
		    break;
	        case 3:	  /* Rule 3: Before and not subset (elder sibling) */
	            beforeAndNotSubset(flag,parentLength,itemSetLength,linkRef,
		    		itemSet,topIndex,oldRef);
		    break;
	        case 4:   /* Rule 4: After and superset (child) */
	            afterAndSuperset(parentLength,itemSetLength,linkRef,
		    		itemSet);
		    break;
	        case 5:	  /* Rule 5: After and not superset (younger sibling) */
	            afterAndNotSuperset(flag,parentLength,itemSetLength,linkRef,
		    		itemSet,topIndex,oldRef);
		    break;
	        default:	/* Default: Error */
	        }		
	    }
	} 

    /* BEFORE AND SUBSET */

    /** Adds new node into the P-tree on a parent/child link so that the new
    node is the parent of the existing child branch and the child of the
    previous "parent"; also checks if any siblings need to be "moved up". <P>
    Possibilities:
    <OL>
    <LI>Connect to top level node with no siblings moved up ({1 2 3} {1 2})
    <LI>Connect to top level node with siblings moved up ({1 2 3} {1 4} {1 2})
    <LI>Connect to child ref with no siblings moved up ({1 2 3 4} {1 2} {1 2 3})
    <LI>Connect to child ref with siblings moved up ({1 2 3 4} {1 2 4 5} {1 2}
    			{1 2 3})
    <LI>connect to sibling ref with no siblings moved up ({1 2} {1 3 4} {1 3})
    <LI>connect to sibling ref with siblings moved up ({1 2} {1 3 4} (1 4)
    {1 3})
    </OL>
    @param flag the type of branch currently under consideration:
    code 0 = root, 1 = child, 2 = sibling.
    @param itemSetLength the number of elements in the current itemSet. Used
    only when adding new nodes to maintain count of number of nodes of a given
    size for when the Ptree table is generated.
    @param linkRef the reference (pointer) to current location in the P-tree.
    @param currentItemSet the row itemSet in the input file currently under
    consideration.
    @param topIndex the index of the element in the array marking the top level
    of the P-tree, used only when inserting new nodes hanging from this top
    level otherwise ignored.
    @param oldRef the reference (pointer) to the previous location in the P-tree,
    used when inserting new nodes.*/
    
    private void beforeAndSubset(int flag, int itemSetLength, PtreeNode linkRef, 
    			short[] currentitemSet, int topIndex, PtreeNode oldRef) {

	// Create new node with support of current node added in;
	
	PtreeNode newRef = createPtreeNode(currentitemSet,itemSetLength);	
	newRef.support = newRef.support+linkRef.support;
	numberOfNodeUpdates++;	
	
	// Link in existing branch
	
	newRef.childRef = linkRef;
	
	// Connect new node into tree structure and adjust existing current
	// node itemSet so that it does not include the new parent node itemSet
	
	addSupport2(flag,newRef,topIndex,oldRef);
	linkRef.itemSet = realloc4(linkRef.itemSet,currentitemSet);
	
	// Check whether any siblings of the existing node need to be 
	// "moved up" to become a sibling of the new node
	
	checkSiblingBranch(linkRef,currentitemSet,newRef);
	}
		
    /* BEFORE AND NOT SUBSET */

    /** Insets node into P-tree where new itemset is an elder sibling of the
    "current" node. <P> First checks for leading substring with existing node;
    if found and leading substring is not same as current parent creates a new
    P-tree node for this substring and then adds in the new node. Possibilities:
    <OL>
    <LI>Connect to top level node with no common leading substring with current
    		node ({1 3} {1 2}).
    <LI>Connect to top level node with common leading substring with current
    		node and no siblings moved up ({1 2 4} {1 2 3}).	
    <LI>Connect to top level node with common leading substring with current
    		node and siblings moved up ({1 2 4} (1 3} {1 2 3}).		
    <LI>Connect to child ref with no common leading substring with current node
    		({1 2} {1 2 4} {1 2 3}).
    <LI>Connect to child ref with common leading substring with current node
    		and no siblings moved up ({1 2} {1 2 4 5 7} {1 2 4 5 6}).
    <LI>Connect to child ref with common leading substring with current node
    		and siblings moved up ({1 2} {1 2 4 5 7} {1 3} {1 2 4 5 6}).	
    <LI>Connect to sibling ref with no common leading substring with current
    		node ({1 2} {1 4} {1 3}).
    <LI>Connect to sibling ref with common leading substring with current node
    		and no siblings moved up ({1 2} {1 4 5 7} {1 4 5 6}).
    <LI>Connect to sibling ref with common leading substring with current node
    		and siblings moved up ({1 2} {1 4 5 7} {1 6} {1 4 5 6}).
    </OL>