fptree.java

java platform java-growth algorithm

    
    private void addRefToFPgrowthHeaderTable(short columnNumber, 
    		     FPgrowthItemPrefixSubtreeNode newNode, 
		     FPgrowthHeaderTable[] headerRef) {
        FPgrowthItemPrefixSubtreeNode tempRef;

	// Loop through header table
	for (int index=1;index<headerRef.length;index++) {
	    // Found right attribute in table?
	    if (columnNumber == headerRef[index].itemName) {
	        tempRef = headerRef[index].nodeLink;
		headerRef[index].nodeLink = newNode;
		newNode.nodeLink = tempRef;
		break;
		}
	    }   
        }

    /* ---------------------------------------------------------- */
    /*                                                            */
    /*                       FP-TREE MINING                       */
    /*                                                            */
    /* ---------------------------------------------------------- */
    
    /* Methodology:

    1) Step through header table from end to start (least common single 
    attribute to most common single attribute). For each item.
    a) Count support by following node links and add to linked list of 
       supported sets.
    b) Determine the "ancestor trails" connected to the nodes linked to the
       current item in the header table.
    c) Treat the list of ancestor itemSets as a new set of input data and 
       create a new header table based on the accumulated supported counts of 
       the single items in the ancestor itemSets 
    d) Prune the ancestor itemSets so as to remove unsupported items.
    e) Repeat (1) with local header table and list of pruned ancestor itemSets 
       as input */
       
    /* START MINING */
    
    /** Top level "FP-growth method" to mine the FP tree. */
    
    public void startMining() {
        
	System.out.println("Mining FP-tree");
	 
    	startMining(headerTable,null);
	
	// Generate ARs
	generateARs();
	}
    
    /* START MINING */
    
    /** Commences process of mining the FP tree. <P> Commence with the bottom 
    of the header table and work upwards. Working upwards from the bottom of 
    the header table if there is a link to an FP tree node :
    <OL>
    <LI> Count the support.
    <LI> Build up itemSet sofar.
    <LI> Add to supported sets.
    <LI> Build a new FP tree: (i) create a new local root, (ii) create a 
	 new local header table and (iii) populate with ancestors.
    <LI> If new local FP tree is not empty repeat mining operation.
    </OL>
    Otherwise end. 
    @param tableRef the reference to the current location in the header table
    (commencing with the last item).
    @param itemSetSofar the label fot the current item sets as generated to
    date (null at start). */	
    
    private void startMining(FPgrowthHeaderTable[] tableRef, 
    						       short[] itemSetSofar) {
        int headerTableEnd = tableRef.length-1;
	FPgrowthColumnCounts[] countArray = null;
	FPgrowthHeaderTable[] localHeaderTable = null;
	FPtreeNode localRoot;
	int support;
	short[] newCodeSofar;
	
	// Loop through header table from end to start, item by item
	
        for (int index=headerTableEnd;index>=1;index--) {
	    // Check for null link
	    if (tableRef[index].nodeLink != null) {
	        // process trail of links from header table element
	        startMining(tableRef[index].nodeLink,tableRef[index].itemName,
						itemSetSofar);
		}
	    }
	}
	
    /** Commence process of mining FP tree with respect to a single element in
    the header table.
    @param nodeLink the firsty link from the header table pointing to an FP-tree
    node.
    @param itemName the label associated with the element of interest in the 
    header table.
    @param itemSetSofar the item set represented by the current FP-tree. */
    	
    protected void startMining(FPgrowthItemPrefixSubtreeNode nodeLink,	
     				short itemName, short[] itemSetSofar) {
	
    	// Count support for current item in header table and store a
	// T-tree data structure
	int support = genSupHeadTabItem(nodeLink); 
	short[] newCodeSofar = realloc2(itemSetSofar,itemName);
	addToTtree(newCodeSofar,support); 
	        
	// Collect ancestor itemSets and store in linked list structure 
	startTempSets=null;
	generateAncestorCodes(nodeLink); 
	
	// Process Ancestor itemSets
	if (startTempSets != null) {
	    // Count singles in linked list
	    FPgrowthColumnCounts[] countArray = countFPgrowthSingles(); 
	    // Create and populate local header table
	    FPgrowthHeaderTable[] localHeaderTable = 
	    				createLocalHeaderTable(countArray); 
	    if (localHeaderTable != null) {
		// Prune ancestor itemSets
		pruneAncestorCodes(countArray); 
	        // Create new local root for local FP tree
	        FPtreeNode localRoot = generateLocalFPtree(localHeaderTable);
		// Mine new FP tree
		startMining(localHeaderTable,newCodeSofar);
		}
	    }
	}
			
    /* ---------------------------------------------------------------------- */
    /*                                                                        */
    /*                     PROCESS CURRENT HEADER TABLE                       */
    /*                                                                        */
    /* ---------------------------------------------------------------------- */  
    
    /* GENERATE SUPPORT FOR HEADER TABLE SINGLE ITEM: */
    
    /** Counts support for single attributes in header table by following node 
    links. 
    @param nodeLink the start link from the header table. 
    @return the support valye for the item set indicated by the header table. */
    
    private int genSupHeadTabItem(FPgrowthItemPrefixSubtreeNode nodeLink) {
        int counter = 0;
	
	// Loop
	
        while(nodeLink != null) {
	    counter = counter+nodeLink.itemCount;
	    numUpdates++;
	    nodeLink = nodeLink.nodeLink;
	    }	
	
	// Return
	
	return(counter);
	}
	
    /* ---------------------------------------------------------------------- */
    /*                                                                        */
    /*                              ANCESTOR CODES                            */
    /*                                                                        */
    /* ---------------------------------------------------------------------- */  
    
    /* GENERATE ANCESTOR CODES */
    
    /** Generates ancestor itemSets are made up of the parent nodes of a given 
    node. This method collects such itemSets and stores them in a linked list 
    pointed at by startTempSets. 
    @param ref the reference to the current node in the prefix tree containing
    itemsets together with support values.*/
                 
    private void generateAncestorCodes(FPgrowthItemPrefixSubtreeNode ref) {
        short[] ancestorCode = null;
	int support;
	
	// Loop
	
        while(ref != null) {
	    support = ref.itemCount;
	    ancestorCode = getAncestorCode(ref.parentRef);
	    // Add to linked list with current support
	    if (ancestorCode != null) startTempSets = 
	    			new FPgrowthSupportedSets(ancestorCode,support,
								startTempSets);
	    // Next ref	
	    ref = ref.nodeLink;
	    }	
	}

    /* GET ANCESTOR CODE */
    
    /** Generate the ancestor itemSet from a given node. 
    @param ref the reference to the current node in the prefix tree containing
    itemsets together with support values. */
    	
    private short[] getAncestorCode(FPgrowthItemPrefixSubtreeNode ref) {
        short[] itemSet = null;
	
	if (ref == null) return(null);
	
	// Else process
	
	while (ref != null) {
	    itemSet = realloc2(itemSet,ref.itemName);
	    ref = ref.parentRef;
	    }
	
	// Return
	
	return(itemSet);
	}

    /* PRUNE ANCESTOR CODES */
    
    /** Removes elements in ancestor itemSets (pointed at by 
    <TT>startTempSets</TT>) which are not supported by referring to count 
    array (which contains all the current supported 1 itemsets). 
    @param countArray the array of <TT>FPgrowthColumnCounts</TT> structures 
    describing the single item sets (in terms of labels and associated 
    support), contained in a linked list of <TT>FPgrowthSupportedSets</TT>
    which in turn describe the ancestor 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 void pruneAncestorCodes(FPgrowthColumnCounts[] countArray) {
	FPgrowthSupportedSets ref = startTempSets;
	
	// Loop through linked list of ancestor paths
	
	while(ref != null) { 
	    for(int index=0;index<ref.itemSet.length;index++) {
	        if (countArray[ref.itemSet[index]].support < minSupport)
		      ref.itemSet = removeElementN(ref.itemSet,index);
		}
	    ref = ref.nodeLink;
	    }
	}
				
    /* ---------------------------------------------------------------------- */
    /*                                                                        */
    /*      CREATE NEW HEADER TABLE FROM SINGLE ITEMS IN ANCESTOR CODES       */
    /*                                                                        */
    /* ---------------------------------------------------------------------- */  
    
    /* COUNT SINGLES */
    
    /** Counts frequent 1 item sets in ancestor itemSets linked list and place 
    into an array. 
    @return array of <TT>FPgrowthColumnCounts</TT> structures describing the
    single item sets (in terms of labels and associated support), contained in 
    a linked list of <TT>FPgrowthSupportedSets</TT> which in turn describe the 
    ancestor 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 FPgrowthColumnCounts[] countFPgrowthSingles() {
        int index, place=0;
	FPgrowthSupportedSets nodeLink = startTempSets; // Start of linked list
        
	// Dimension array, assume all attributes present, then it will
	// be possible to index in to the array.
	
	FPgrowthColumnCounts[] countArray = new 
					FPgrowthColumnCounts[numOneItemSets+1];	
	
	// Initialise array
	
	for (index=1;index<numOneItemSets+1;index++) countArray[index] = 
				new FPgrowthColumnCounts(index);
	    
	// Loop through linked list of ancestor itemSets
	
	while (nodeLink != null) {
	    // Loop through itemSet 
	    for (index=0;index<nodeLink.itemSet.length;index++) {
		place = nodeLink.itemSet[index];
		countArray[place].support = countArray[place].support +
			nodeLink.support;
		numUpdates++;
		}
	    nodeLink = nodeLink.nodeLink;
	    }    
	               	                                                  
	// Return
	
	return(countArray);
	}

    /* CREATE LOCAL HEADER TABLE */
    
    /** Creates a local header table comprising those item that are supported 
    in the count array. 
    @param countArray the support for the 1 item sets. 
    @return a FPgrowth header table. */
    
    private FPgrowthHeaderTable[] 
    		createLocalHeaderTable(FPgrowthColumnCounts[] countArray) {
        int index;
	FPgrowthHeaderTable[] localHeaderTable;
	
	localHeaderTable = localHeadTabUnordered(countArray);
	
	// Order according single item support
	
        //orderLocalHeaderTable(localHeaderTable,countArray);
	                	                                                  
	// Return
	
	return(localHeaderTable);
	}		
    
    /* CREATE NEW LOCAL HEADER TABLE (UNORDERED) */
    
    /** Creatwx a new local header table, but unorderd. 
    @param countArray the csupport for the 1 item sets. 
    @return a FPgrpwth header table. */
    
    private FPgrowthHeaderTable[] 
    		localHeadTabUnordered(FPgrowthColumnCounts[] countArray) {
        int counter = 1;
	
	// Loop through array and count supported one item sets	 
	for (int index=1;index<countArray.length;index++) {
	    if (countArray[index].support >= minSupport) counter++;
	    }
	    
	// Build new Header Table array containing only supported items
	
	if (counter == 1) return(null);
	FPgrowthHeaderTable[] localHeaderTable = 
					new FPgrowthHeaderTable[counter];
	    
	// Populate header table
	
	int place=1;
	for (int index=1;index<countArray.length;index++) {
	    if (countArray[index].support >= minSupport) {
	        localHeaderTable[place] = new 
		    FPgrowthHeaderTable((short) countArray[index].columnNum);    
	        place++;
	        }
	    }    
        
	// Return
	
	return(localHeaderTable);
	}