partialsupporttree.java

多关联分类算法

    them all up to be siblings of the parent
    <LI>All nodes in sibling branch are supersets of parent, thus do
    nothing.
    <LI>Some nodes in sibling branch are supersets of parent, others are
    not; therefore move those that are not up to be siblings of the parent.
    </OL>
    Note: when a node is found that is not a superset of the parent we do not
    need to keep on checking.
    @param linkRef the reference (pointer) to the current node.
    @param parentItemSet the itemset label represented by the parent.
    @param newRef tghe reference (pointer) to the newly created parent node.*/

    private void checkSiblingBranch(PtreeNode linkRef, short[] parentItemSet, 
    				PtreeNode newRef) {
	// Check if first node in sibling branch is a superset of parent 
	// itemSet. If not move the entire branch up. 
	
	if (linkRef.siblingRef != null) {
	    if (! isSubset(parentItemSet,linkRef.siblingRef.itemSet)) {
	        newRef.siblingRef = linkRef.siblingRef;
	        linkRef.siblingRef = null;
	        }
	   
	// Check rest. Branch starts of with supersets of parent itemSet 
	// (which are OK where they are), must find the point where this is 
	// no longer the case, i.e. the  part of the branch that needs to be 
	// moved up (if any). 

	    else {
	        // Remove leading substring
	        linkRef.siblingRef.itemSet = 
				realloc4(linkRef.siblingRef.itemSet,
								parentItemSet);
	        // Set reference varibales
		PtreeNode markerRef = linkRef.siblingRef;
	        PtreeNode localLinkRef = linkRef.siblingRef.siblingRef;
	        while (localLinkRef != null) {
	            if (! isSubset(parentItemSet,localLinkRef.itemSet)) {
		        newRef.siblingRef = localLinkRef;
		        markerRef.siblingRef = null;
			break;
		        }
		    else {
		        localLinkRef.siblingRef.itemSet = 
			     realloc4(localLinkRef.siblingRef.itemSet,
						parentItemSet);	
	                markerRef = localLinkRef;
	                localLinkRef = localLinkRef.siblingRef;
			}
	            }
	        }
	    }
	}        

    /* CREAT P-TREE NODE */
    /** Creates a P-tree node (other than a top level node). 
    @param newItemSet the itemset to be stored at the node.  
    @param level the cardinality (length) of the item set to be stored in
    the node. */
    
    private PtreeNode createPtreeNode(short[] itemSet, int level) {
        pTreeNodesOfCardinalityN[level]++;
        return(new PtreeNode(itemSet));
	}

    /* GET START OF P-TREE */
    /** Gets reference to start of P-tree. */
    
    public PtreeNodeTop[] getStartOfPtree() {
        return(startPtreeRef);
	}

    /* GET NUMBER P-TREE NODES */
    /** Gets number of nodes in P-tree. */
    
    public int getNumPtreeNodes() {
        return(calculateNumNodes(startPtreeRef));
	}
	
    /*----------------------------------------------------------------------- */
    /*                                                                        */
    /*                                 P-TREE TABLE                           */
    /*                                                                        */
    /*----------------------------------------------------------------------- */
   
    /* CREATE P-TREE TABLE */
    /** Creates P-tree table starting with top level in P-tree. <P> Proceed as
    follows.
    <OL>
    <LI>Create an array of arrays.
    <LI>Add top level of Ptree.
    <LI>Add remaining nodes in sub-branches.
    </OL> */
    
    public void createPtreeTable() {
 	// Set up array of arrays 	
	for (int index=1;index<pTreeNodesOfCardinalityN.length;index++) {
	    // There may be no itemSets in the Ptree of a particular size
	    if (pTreeNodesOfCardinalityN[index] == 0) startPtreeTable[index] = null;
	    else startPtreeTable[index] = 
	    			new PtreeRecord[pTreeNodesOfCardinalityN[index]];
	    }
	    	
	// Process Ptree	
	for (int index=0;index < startPtreeRef.length;index++) {
	    // Check if valid node (non-null)
	    if (startPtreeRef[index] != null) {
		// Create a label	        
		short[] itemSet = new short[1];
		itemSet[0] = (short) index;
		// Add to P-tree table 
		addToPtreeArray(null,itemSet,startPtreeRef[index].support,1);
		// Process child branch
	    	createPtreeTable2(startPtreeRef[index].childRef,itemSet,1);
		startPtreeRef[index] = null;
		}
	    } 
	}
	
    /* CREATE P-TREE TABLE 2 */

    /** Process child branch hanging from a top level P-tree node.
    @param linkPtreeRef the reference/pointer to the current location in the
    P-tree.
    @param totalpTreeItemSet the union of all the parent labels sofar.
    @param currentLevel the current levl in the P-tree, initially set to 1. */
    	
    private void createPtreeTable2(PtreeNode linkPtreeRef, 
    			short[] totalpTreeItemSet, int currentLevel) {
	if (linkPtreeRef != null) {		// Not referencing null node
	    
	    // Calculate level represented by node
	    
	    int lastElementIndex = linkPtreeRef.itemSet.length-1;
	    int level = currentLevel+lastElementIndex+1; 
		
	    // OAdd to Ptree table 
	    
	    addToPtreeArray(linkPtreeRef.itemSet,totalpTreeItemSet,
	    					linkPtreeRef.support,level);
		
	    // Search through child branch
	
	    createPtreeTable2(linkPtreeRef.childRef,
	    			append(totalpTreeItemSet,
				linkPtreeRef.itemSet),level);
            linkPtreeRef.childRef = null;
		 
	    // Search through sibling branch
	    
	    createPtreeTable2(linkPtreeRef.siblingRef,totalpTreeItemSet,
	    		currentLevel);
	    linkPtreeRef.siblingRef= null;
	    }	         
	}

    /* ADD TO P-TREE ARRAY */

    /** Adds data associated with a P-tree node to the P-tree 2-D table.
    @param pTreeNodeLabel the union of all the parent labels.
    @param pTreeItemSet the node label.
    @param support the support associated with the node
    @param level the current levl in the P-tree. */
    
    private void addToPtreeArray(short[] pTreeNodeLabel, short[] pTreeItemSet, 
    			int support, int level) {
 	
	if (pTreeNodeLabel == null) {
	    startPtreeTable[level][pTreeTableMarker[level]] = 
			new PtreeRecord(pTreeItemSet,pTreeItemSet,support);
	    }
	else startPtreeTable[level][pTreeTableMarker[level]] = 
		new PtreeRecord(pTreeNodeLabel,append(pTreeItemSet,
							pTreeNodeLabel),support);
							
	pTreeTableMarker[level]++;
	}

    /*----------------------------------------------------------------------- */
    /*                                                                        */
    /*                       T-TREE BUILDING METHODS                          */
    /*                                                                        */
    /*----------------------------------------------------------------------- */
    
    /* CREATE TOTAL SUPPORT TREE */   
    /** Commences process of generating a total support tree (T-tree) from
    a P-tree. */
                
    public void createTotalSupportTree() {	
	System.out.println("APRIORI-TFP WITH X-CHECKING\n" +
	                   		"---------------------------");
	System.out.println("Minimum support threshold = " + 
				twoDecPlaces(support) + "% " + "(" + 
				twoDecPlaces(minSupport) + " (records)");
	
	// If no data (possibly as a result of an order and pruning operation)
	// return
	if (numOneItemSets==0) return;
	
	// Create Top level of T-tree (First pass of dataset)	
	startTtreeRef=null;
	numFrequentsets = 0;	
	createTtreeTopLevel();
	
	// Generate level 2
	generateLevel2();
	
	// Further passes of the dataset	
	createTtreeLevelN();
	}
	
    /* Set of methods for creating T-tree from P-tree which overide methods
    of smae name in parent class. */
    
    /*  GENERATE T-TREE TOP LEVEL 2 */
    /** Commences process to generate top level (singletons) of Ttree by
    looping through table level by level (row by row). */
    
    protected void createTtreeTopLevel2() {
        // Step through Ptree table	
	for(int index=1;index<startPtreeTable.length;index++) {
	    // Check if level exists
	    if (startPtreeTable[index] != null) {
		createTtreeTopLevel3(startPtreeTable[index]);
		}
	    }	 
	
	// Destroy top level of P-tree table
	startPtreeTable[1] = null;
	}

    /** Processes level (row) in P-tree table to generate top level of T-tree.
    @param pTreeTableLevel the given level (row) of P-tree table records. */
    	
    protected void createTtreeTopLevel3(PtreeRecord[] pTreeTableLevel) {
	// Loop through level in P-tree table level
	
	for(int index=0;index<pTreeTableLevel.length;index++) {
	    createTtreeTopLevel4(pTreeTableLevel[index].pTreeNodeLabel,
		    		pTreeTableLevel[index].support);
	    }	
	}

    /** Increments support counts in T-tree top level given a P-tree table
    label and an associated support value.
    @param pTreeNodeLabel the label associated with a P-tree node (not the union
    of its parent labels).
    &param pTreeNodeSupport the associated support value.*/
    		
    private void createTtreeTopLevel4(short[] pTreeNodeLabel, 
    							int pTreeNodeSupport) {
        // Loop through node label
	for (int index=0;index<pTreeNodeLabel.length;index++) {
	    // Increment support for T-tree singleton node    
	    startTtreeRef[pTreeNodeLabel[index]].support = 
	    	 startTtreeRef[pTreeNodeLabel[index]].support+pTreeNodeSupport;
	    numUpdates++;
	    }
	}
	
    /* CREATE T-TREE LEVEL N */

    /** Commences process of adding support values to further levels of the
    T-tree (not the top level). */

    protected void createTtreeLevelN() {
        int nextLevel=2;

	// Loop while a further level exists
	
	while (nextLevelExists) {  	    
            // Add support   
	    addSupportToTtreeLevelN(nextLevel);
	    // Destroy current level of P-tree table
	    startPtreeTable[nextLevel] = null;
	    // Prune unsupported candidate sets
	    pruneLevelN(startTtreeRef,nextLevel); 
	    // Attempt to generate next level 
	    nextLevelExists=false;
	    generateLevelN(startTtreeRef,nextLevel,null); 
	    nextLevel++; 
	    }
	    
	//End
	System.out.println("Levels in T-tree = " + nextLevel);  
	}
		
    /* ADD SUPPORT VALUES TO T-TREE LEVEL N */

    /** Continues process of adding support alues to further levels of the
    T-tree (not the top level) by stepping through the Ptree table from the
    current required level upto the maximum level that may be contained in the
    table.
    @param level the (start) current level. */
     	
    protected void addSupportToTtreeLevelN(int level) {

        // Nested loop to step through P-tree table
	
	for (int index1=level;index1<startPtreeTable.length;index1++) {
	    // Check that there are records in the table at current level
	    if (startPtreeTable[index1] != null) {
	        // step through records at currentd level in loop
	        for(int index2=0;index2<pTreeNodesOfCardinalityN[index1];
								index2++) {
	            addSupportToTtreeLevelN(startTtreeRef,level,
		                startPtreeTable[index1][index2].pTreeNodeLabel,
				startPtreeTable[index1][index2].pTreeItemSet,
				startPtreeTable[index1][index2].support);
		    }
	        }
	    }
        }
	   						
    /* ADD SUPPORT VALUES TO T-TREE LEVEL N */

    /** Adds support to to appropriate nodes in T-tree at a given level and
    given a record from the P-tree table.
    @param linkRef the reference (pointer) to the current branch in the T-tree
    (top at start)
    @param level the desired level in T-tree
    @param pTreeNodeLabel the actual P-tree node itemSet label (not the union
    of its parent labels).
    @param pTreeItemSet the Uunion of the pTreeNodeLabel and all parent node
    itemSets of the current node.
    @param support the upport count			*/
    
    private void addSupportToTtreeLevelN(TtreeNode[] linkRef, int level, 
    		short[] pTreeNodeLabel, short[] pTreeItemSet, int support) {
	int index;
	int tTreeLength = linkRef.length;

	// At right leve;

	if (level == 1) {