partialsupporttree.java

多关联分类算法

    @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 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 beforeAndNotSubset(int flag, int parentLength, 
    		int itemSetLength, PtreeNode linkRef, short[] currentItemSet,
					    int topIndex, PtreeNode oldRef) {
			
	// Find leading common ellements in row and sibling itemSets if any
	
	short[] subsetItemSet = checkForLeadingSubString(currentItemSet,
			linkRef.itemSet);
	
	// If leading common ellements exists create new node representing 
	// common elements and add current itemSet as child of this new node. 
	// Otherwise add new itemSet as elder sibling.

	if (subsetItemSet != null) {	// Leading substring exists 
	    // Create new parent representing subset
	    PtreeNode newParentRef = createPtreeNode(subsetItemSet,
	    				subsetItemSet.length+parentLength-1);
	    // Add support made up of existing support + 1 for current row
	    newParentRef.support = linkRef.support+1;
	    // Insert new parent node into tree
	    addSupport2(flag,newParentRef,topIndex,oldRef);
	    // Remove leading substring from row itemSet
	    currentItemSet = realloc4(currentItemSet,subsetItemSet);
	    // Attach as child and add on sibling,
	    newParentRef.childRef = createPtreeNode(currentItemSet,
	    							itemSetLength);
	    newParentRef.childRef.siblingRef = linkRef;
	    // Check whether any siblings need to be "moved up"
	    checkSiblingBranch(newParentRef.childRef,subsetItemSet,newParentRef); 
	    }
	else {
	    // Create new node
	    PtreeNode newSiblingRef = 
	    			createPtreeNode(currentItemSet,itemSetLength);
	    // Attach existing node as younger sibling
	    newSiblingRef.siblingRef = linkRef;
	    // Insert into tree
	    addSupport2(flag,newSiblingRef,topIndex,oldRef);
	    }
	}

    /* AFTER AND SUPERSET */

    /** Insets node into P-tree where new itemset is an child of the "current"
    node. <P> If no more child nodes add new node to "current" node as child,
    else carry on down the tree with flag set to 1 to indicate we are following
    a child branch. Possibilities:
    <OL>
    <LI> Add to top level node ({1 2}).
    <LI> Add to child ref ({1 2} {1 2 3}).
    </OL>
    @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 currentItemSet the row itemSet in the input file currently under
    consideration. */

    private void afterAndSuperset(int parentLength, int itemSetLength, 
    				PtreeNode linkRef, short[] currentItemSet) {    
    	
	numberOfNodeUpdates++;
	linkRef.support = linkRef.support+1;	// Increment support
	
	// End of child branch
	 
	if (linkRef.childRef == null) {
	    // Remove existing parent itemSet from currentItemSet

	    PtreeNode newRef = createPtreeNode(realloc4(currentItemSet,
	    				linkRef.itemSet),itemSetLength);
	    // Add to existing node as child
	    linkRef.childRef = newRef;
	    }
	
	// More children, remove existing current itemSet from row itemSet and 
	// continue down child branch
	
	else addToPtree(1,parentLength+linkRef.itemSet.length,itemSetLength,
			linkRef.childRef,realloc4(currentItemSet,
					linkRef.itemSet),0,linkRef);
	}
	
    /* AFTER AND NOT SUPERSET */

    /** Commeences process of inserting node into P-tree where new itemset is
    a younger sibling of the "current" node. <P> Possible actions:
    <OL>
    <LI> There are NO more sibling nodes (call <TT>afterAndNotSuperset1</TT>).
    <LI> There are more sibling nodes (call <TT>afterAndNotSuperset2</TT>).
    </OL>
    @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 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 afterAndNotSuperset(int flag, int parentLength, 
    		int itemSetLength, PtreeNode linkRef, short[] currentItemSet, 
					    int topIndex, PtreeNode oldRef) { 

	// Test if end of sibling branch, if not continue  
	 
    	if (linkRef.siblingRef == null) 
			afterAndNotSuperset1(flag,parentLength,itemSetLength,
				linkRef,currentItemSet,topIndex,oldRef);
	    
	// Not end of sibling branch
	
	else afterAndNotSuperset2(flag,parentLength,itemSetLength,linkRef,
				currentItemSet,topIndex,oldRef);	    
	}
	
    /* AFTER AND NOT SUPERSET 1 */

    /** Inserts node into P-tree where new itemset is a younger sibling of the
    "current" node and there are no more younger siblings on current existing
    node therefore new node added as sibling. <P> Also tests for leading
    substring. If found and this is not equal to an existing parent itemSet
    method causes a dummy node to represent the substring to be inserted (call
    to <TT>addSupport2</TT>). Possibilities:
    <OL>
    <LI>Add to siblingRef with no common leading substring ({1 2} {1 3}).
    <LI>Add to siblingRef with common leading substring
       	({1 2} {1 3 5} {1 3 4}).
    </OL>   	
    @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 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 afterAndNotSuperset1(int flag, int parentLength, 
    		int itemSetLength, PtreeNode linkRef, short[] currentItemSet, 
					int topIndex, PtreeNode oldRef) { 

	// Find leading common ellements in row and sibling itemSets if any
	
	short[] subsetItemSet = checkForLeadingSubString(currentItemSet,
							linkRef.itemSet);
       
	// If leading common ellements exists create new node representing 
	// common elements and add current itemSet as child of this new node. 
	// Otherwise add new itemSet as elder sibling.
	 
	if (subsetItemSet != null) { 
	    // Create new parent representing subset
	    PtreeNode newParent = createPtreeNode(subsetItemSet,
	    				subsetItemSet.length+parentLength-1);
	    // Add support made up of existing support + 1 for current row
	    newParent.support = linkRef.support+1;
	    // Insert new parent node into tree
            addSupport2(flag,newParent,topIndex,oldRef);
	    // Remove leading substring from current existing node
	    linkRef.itemSet = realloc4(linkRef.itemSet,subsetItemSet);
	    // Attach existing branch as child of new parent and new node
            // as sibling
	    newParent.childRef = linkRef;
	    linkRef.siblingRef = createPtreeNode(realloc4(currentItemSet,
		   				subsetItemSet),itemSetLength);
	    }
	 
	// No leading substring	
	
	else linkRef.siblingRef = createPtreeNode(currentItemSet,
								itemSetLength);
	}

    /* AFTER AND NOT SUPERSET 2 */

    /** Inserts node into P-tree where new itemset is a younger sibling of the
    "current" node and there are more younger sibling on current existing
    node. <P> Possible actions:
    <OL>
    <LI> If there are more sibling nodes and the current row itemSet shares a
    leading substring with the current P-tree node and this is not equal to
    an existing parent itemSet then add a dummy node to represent the
    substring (call <TT>addSupport2</TT>). Then add new node.
    <LI> If more sibling nodes and no shared leading substring continue down
    sibling branch.
    </OL>
    Possibility:
    <OL>
    <LI>Add in dummy node ({1 2 3} {1 3 5} {1 6} {1 3 6}).
    </OL>
    @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 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 afterAndNotSuperset2(int flag, int parentLength, 
    			int itemSetLength,  PtreeNode linkRef, 
			short[] currentItemSet, int topIndex, PtreeNode oldRef) { 
        
	// Find leading common ellements in row and sibling itemSets if any
	
	short[] subsetItemSet = checkForLeadingSubString(currentItemSet,
			linkRef.itemSet);
       
	// If leading common ellements exists create new node representing 
	// common elements and add current itemSet as child of this new node. 
	// Otherwise add new itemSet as elder sibling.
	
	if (subsetItemSet != null) { 
	    // Create new parent representing leading common elements
	    PtreeNode newParentRef = createPtreeNode(subsetItemSet,
	    			     subsetItemSet.length+parentLength-1);
	    // Add support made up of existing support + 1 for current row
	    newParentRef.support = linkRef.support+1;
	    // Insert new parent node into tree
            addSupport2(flag,newParentRef,topIndex,oldRef); 
	    // Remove leading substring from current existing node and add
	    // as child of new parent node
	    linkRef.itemSet = realloc4(linkRef.itemSet,subsetItemSet);
	    newParentRef.childRef = linkRef;
	    // Store reference to existing branch of current existing node
	    // in temporary variable
	    PtreeNode tempRef = linkRef.siblingRef; 
	    // Create new node representing row and add as sibling of 
	    // current existing ref (NOTE: leading sub string will be 
	    // removed when checking siblings (checkSiblingBranch)
	    linkRef.siblingRef = createPtreeNode(currentItemSet,itemSetLength);
	    // Now add in previous siblings
	    linkRef.siblingRef.siblingRef = tempRef;
	    // Check whether any siblings need to be "moved up"
	    checkSiblingBranch(newParentRef.childRef,subsetItemSet,newParentRef); 
	    }	
	
	// Otherwise carry on along sibling branch
	
	else addToPtree(2,parentLength,itemSetLength,linkRef.siblingRef,
						currentItemSet,0,linkRef);
	}
				
    /* ------ ADD SUPPORT 2 ------ */

    /** Adds new node where "before and subset" or "after and not superset". <P>
    The flag argument indicates which type of branch is currently under 
    consideration: 0 = root, 1 = child, 2 = sibling.
    @param flag the type of branch currently under consideration:
    code 0 = root, 1 = child, 2 = sibling.
    @param newRef the reference (pointer) to newly created parent indicating
    current laction in the P-tree.
    @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 addSupport2(int flag, PtreeNode newRef, int topIndex, 
    						PtreeNode oldRef) {
	
	// Add node
	
	switch (flag) {		
	    case 0:
		startPtreeRef[topIndex].childRef = newRef;
		break;
	    case 1:
		oldRef.childRef = newRef;
		break;
	    case 2:
		oldRef.siblingRef = newRef;
		break;
	    default:
		System.out.println("ERROR: Unidentified flag in addSupport\n"); 
	    }
	}
	
    /* ------ CHECK SIBLING BRANCH ------ */

    /** Checks sibling branch to determine whether the siblings are all
    supersets of the parent and readjusts P-tree accordingly. <P> Possibilities:
    <OL>
    <LI>Sibling branch is empty (do nothing).
    <LI>No nodes in sibling branch are supersets of parent there for move