totalsupporttree.java

多关联分类算法

    <LI> For each combination from (2) append to itemSet1 
    </OL>
    <P>Example 1: 
    <PRE>
    currentItemSet = {A,B,C} 
    itemSet1 = {B,A} (change of ordering)
    size = {A,B,C}-2 = 1
    itemSet2 = {C} (currentItemSet with first two elements removed)
    calculate combinations between {B,A} and {C}
    </PRE>
    <P>Example 2: 
    <PRE>
    currentItemSet = {A,B,C,D} 
    itemSet1 = {B,A} (change of ordering)
    itemSet2 = {C,D} (currentItemSet with first two elements removed)
    calculate combinations between {B,A} and {C,D}
    </PRE>
    @param currentItemSet the given itemset.		*/
    
    protected boolean testCombinations(short[] currentItemSet) {  
	// No need to test 1- and 2-itemsets
        if (currentItemSet.length < 3) return(true);
	   
	// Creat itemSet1 (note ordering)
	
	short[] itemSet1 = new short[2];
	itemSet1[0] = currentItemSet[1];
	itemSet1[1] = currentItemSet[0];
	
	// Creat itemSet2
	
	int size = currentItemSet.length-2;
	short[] itemSet2 = removeFirstNelements(currentItemSet,2);
	
	// Calculate combinations

	return(combinations(null,0,2,itemSet1,itemSet2));
	}
	
    /* COMBINATIONS */
    
    /** Determines the cardinality N combinations of a given itemset and then
    checks whether those combinations are supported in the T-tree. <P> 
    Operates in a recursive manner.
    <P>Example 1: Given --- sofarSet=null, 
    startIndex=0, endIndex=2, itemSet1 = {B,A} and itemSet2 = {C}
    <PRE>
    itemSet2.length = 1
    endIndex = 2 greater than itemSet2.length if condition succeeds
    tesSet = null+{B,A} = {B,A}
    retutn true if {B,A} supported and null otherwise
    </PRE>
    <P>Example 2: Given --- sofarSet=null, 
    startIndex=0, endIndex=2, itemSet1 = {B,A} and itemSet2 = {C,D}
    <PRE>
    endindex not greater than length {C,D}
    go into loop
    tempSet = {} + {C} = {C}
    	combinations with --- sofarSet={C}, startIndex=1, 
			endIndex=3, itemSet1 = {B,A} and itemSet2 = {C}
	endIndex greater than length {C,D}
	testSet = {C} + {B,A} = {C,B,A}
    tempSet = {} + {D} = {D}
    	combinations with --- sofarSet={D}, startIndex=1, 
			endIndex=3, itemSet1 = {B,A} and itemSet2 = {C}
	endIndex greater than length {C,D}
	testSet = {D} + {B,A} = {D,B,A}
    </PRE>
    @param sofarSet The combination itemset generated so far (set to null at
    start)
    @param startIndex the current index in the given itemSet2 (set to 0 at 
    start).
    @param endIndex The current index of the given itemset (set to 2 at start)
    and incremented on each recursion until it is greater than the length of
    itemset2.
    @param itemSet1 The first two elements (reversed) of the totla label for the
    current item set.
    @param itemSet2 The remainder of the current item set.
    */	
	
    private boolean combinations(short[] sofarSet, int startIndex,
    		    int endIndex, short[] itemSet1, short[] itemSet2) {
	// At level
	
	if (endIndex > itemSet2.length) {
	    short[] testSet = append(sofarSet,itemSet1);
	    // If testSet exists in the T-tree sofar then it is supported
	    return(findItemSetInTtree(testSet));
	    }
	
	// Otherwise
	else {
	    short[] tempSet;
	    for (int index=startIndex;index<endIndex;index++) {
	        tempSet = realloc2(sofarSet,itemSet2[index]);
	        if (!combinations(tempSet,index+1,endIndex+1,itemSet1,
				itemSet2)) return(false);
	        }
	    }						
        
	// Return
	
	return(true);
	}
		
    /* ---------------------------------------------------------------- */
    /*                                                                  */
    /*                           ADD TO T-TREE                          */
    /*                                                                  */
    /* ---------------------------------------------------------------- */
	
    /* ADD TO T-TREE */
    
    /** Commences process of adding an itemset (with its support value) to a
    T-tree when using a T-tree either as a storage mechanism, or when adding to 
    an existing T-tree. 
    @param itemSet The given itemset. Listed in numeric order (not reverse
    numeric order!).
    @param support The support value associated with the given itemset. */
    
    /*public void addToTtree(short[] itemSet, int support) {
        // Determine index of last elemnt in itemSet.
	int endIndex = itemSet.length-1;
	
	// Add itemSet to T-tree.
        startTtreeRef = addToTtree(startTtreeRef,numOneItemSets+1,
			endIndex,itemSet,support);
	}   */
		
    /* ADD TO T-TREE */
    
    /** Inserts a node into a T-tree. <P> Recursive procedure.
    @param linkRef the reference to the current array in Ttree.
    @param size the size of the current array in T-tree.
    @param endIndex the index of the last elemnt/attribute in the itemset, 
    which is also used as a level counter.	
    @param itemSet the given itemset.
    @param support the support value associated with the given itemset. 
    @return the reference to the revised sub-branch of t-tree. */
    
    /*private TtreeNode[] addToTtree(TtreeNode[] linkRef, int size, int endIndex,
    				short[] itemSet, int support) {
	// If no array describing current level in the T-tree or T-tree
	// sub-branch create one with "null" nodes.	
	if (linkRef == null) {
	    linkRef = new TtreeNode[size];
	    for(int index=1;index<linkRef.length;index++) 
			linkRef[index] = null;
	    }
	
	// If null node at index of array describing curent level in T-tree 
	// (T-tree sub-branch) create a T-tree node describing the current 
	// itemset sofar.
	int currentAttribute = itemSet[endIndex]; 
	if (linkRef[currentAttribute] == null)
	    		linkRef[currentAttribute] = new TtreeNode();
	
	// If at right level add support 	
	if (endIndex == 0) {
	    linkRef[currentAttribute].support =
	    			linkRef[currentAttribute].support + support;
	    return(linkRef);
	    }
	    
	// Otherwise proceed down branch and return	
	linkRef[currentAttribute].childRef = 
			addToTtree(linkRef[currentAttribute].childRef,
				currentAttribute,endIndex-1,itemSet,support);
	// Return
	return(linkRef);
	}    */
    	
    /*---------------------------------------------------------------------- */
    /*                                                                       */
    /*                        T-TREE SEARCH METHODS                          */
    /*                                                                       */
    /*---------------------------------------------------------------------- */  
    
    /* FIND ITEM SET IN T-TREE*/
    
    /** Commences process of determining if an itemset exists in a T-tree. <P> 
    Used to X-check existance of Ttree nodes when generating new levels of the 
    Tree. Note that T-tree node labels are stored in "reverse", e.g. {3,2,1}. 
    @param itemSet the given itemset (IN REVERSE ORDER). 
    @return returns true if itemset found and false otherwise. */
    
    protected boolean findItemSetInTtree(short[] itemSet) {

    	// first element of itemset in Ttree (Note: Ttree itemsets stored in 
	// reverse)
  	if (startTtreeRef[itemSet[0]] != null) {
    	    int lastIndex = itemSet.length-1;
	    // If single item set return true
	    if (lastIndex == 0) return(true);
	    // Otherwise continue down branch
	    else if (startTtreeRef[itemSet[0]].childRef!=null) {
	        return(findItemSetInTtree2(itemSet,1,lastIndex,
			startTtreeRef[itemSet[0]].childRef));
	        }
	    else return(false);
	    }	
	// Item set not in Ttree
    	else return(false);
	}
    
    /** Returns true if the given itemset is found in the T-tree and false 
    otherwise. <P> Operates recursively. 
    @param itemSet the given itemset. 
    @param index the current index in the given T-tree level (set to 1 at
    start).
    @param lastIndex the end index of the current T-tree level.
    @param linRef the reference to the current T-tree level. 
    @return returns true if itemset found and false otherwise. */
     
    private boolean findItemSetInTtree2(short[] itemSet, int index, 
    			int lastIndex, TtreeNode[] linkRef) {  

        // Attribute at "index" in item set exists in Ttree
  	if (linkRef[itemSet[index]] != null) {
  	    // If attribute at "index" is last element of item set then item set
	    // found
	    if (index == lastIndex) return(true);
	    // Otherwise continue
	    else if (linkRef[itemSet[index]].childRef!=null) {
	        return(findItemSetInTtree2(itemSet,index+1,lastIndex,
	    		linkRef[itemSet[index]].childRef));
	        }
	    else return(false); 
	    }	
	// Item set not in Ttree
	else return(false);    
    	}

    /* GET SUPPORT FOT ITEM SET IN T-TREE */
    
    /** Commences process for finding the support value for the given item set
    in the T-tree. <P> Used when generating Associoation Rules (ARs). Note that
    itemsets are stored in reverse order in the T-tree therefore the given
    itemset must be processed in reverse. 
    @param itemSet the given itemset. 
    @return returns the support value (0 if not found). */
    
    protected int getSupportForItemSetInTtree(short[] itemSet) {
	int lastIndex = itemSet.length-1;
	
    	// Last element of itemset in Ttree (Note: Ttree itemsets stored in 
	// reverse)
  	if (startTtreeRef[itemSet[lastIndex]] != null) {
	    // If single item set return support
	    if (lastIndex == 0) return(startTtreeRef[itemSet[0]].support);
	    // Otherwise continue down branch
	    else return(getSupportForItemSetInTtree2(itemSet,lastIndex-1,
			startTtreeRef[itemSet[lastIndex]].childRef));
	    }	
	// Item set not in Ttree thererfore return 0
    	else return(0);
	}
    
    /** Returns the support value for the given itemset if found in the T-tree 
    and 0 otherwise. <P> Operates recursively. 
    @param itemSet the given itemset. 
    @param index the current index in the given itemset.
    @param linRef the reference to the current T-tree level. 
    @return returns the support value (0 if not found). */
     
    private int getSupportForItemSetInTtree2(short[] itemSet, int index, 
    			TtreeNode[] linkRef) {  

        // Element at "index" in item set exists in Ttree
  	if (linkRef[itemSet[index]] != null) {
  	    // If element at "index" is last element of item set then item set
	    // found
	    if (index == 0) return(linkRef[itemSet[0]].support);
	    // Otherwise continue
	    else return(getSupportForItemSetInTtree2(itemSet,index-1,
	    		linkRef[itemSet[index]].childRef));
	    }	
	// Item set not in Ttree thererfore return 0
	else return(0);    
    	}
		
    /*----------------------------------------------------------------------- */
    /*                                                                        */
    /*                    ASSOCIATION RULE (AR) GENERATION                    */
    /*                                                                        */
    /*----------------------------------------------------------------------- */	
    
    /* GENERATE ASSOCIATION RULES */
    
    /** Initiates process of generating Association Rules (ARs) from a 
    T-tree. */
    
    /*public void generateARs() {
	// Command line interface output
	System.out.println("GENERATE ARs:\n-------------");
	
	// Set rule data structure to null
	currentRlist.startRulelist = null;
	
	// Generate
	generateARs2();
	}*/
	
    /** Loops through top level of T-tree as part of the AR generation 
    process. */
    
    /* private void generateARs2() {	
	// Loop	
	for (int index=1;index <= numOneItemSets;index++) {
	    if (startTtreeRef[index] !=null) {
	        if (startTtreeRef[index].support >= minSupport) {
	            short[] itemSetSoFar = new short[1];
		    itemSetSoFar[0] = (short) index;
		    generateARs(itemSetSoFar,index,
		    			startTtreeRef[index].childRef);
		    }
		}
	    } 
	} */
		
    /* GENERATE ASSOCIATION RULES */
    
    /** Continues process of generating association rules from a T-tree by 
    recursively looping through T-tree level by level. 
    @param itemSetSofar the label for a T-treenode as generated sofar.
    @param size the length/size of the current array lavel in the T-tree.
    @param linkRef the reference to the current array lavel in the T-tree. */
    
    /* protected void generateARs(short[] itemSetSofar, int size,
    							TtreeNode[] linkRef) {
	
	// If no more nodes return	
	if (linkRef == null) return;
	
	// Otherwise process
	for (int index=1; index < size; index++) {
	    if (linkRef[index] != null) {
	        if (linkRef[index].support >= minSupport) {
		    // Temp itemset
		    short[] tempItemSet = realloc2(itemSetSofar,(short) index);
		    // Generate ARs for current large itemset
		    generateARsFromItemset(tempItemSet,linkRef[index].support);
	            // Continue generation process
		    generateARs(tempItemSet,index,linkRef[index].childRef); 
	            }
		}