assocrulemining.java

apriori algorithm using datasets implementation

    /** Resizes given item set so that its length is increased by one
    and appends new element (identical to append method)
    @param oldItemSet the original item set
    @param newElement the new element/attribute to be appended
    @return the combined item set */
    
    protected short[] realloc1(short[] oldItemSet, short newElement) {
        
	// No old item set
	
	if (oldItemSet == null) {
	    short[] newItemSet = {newElement};
	    return(newItemSet);
	    }
	
	// Otherwise create new item set with length one greater than old 
	// item set
	
	int oldItemSetLength = oldItemSet.length;
	short[] newItemSet = new short[oldItemSetLength+1];
	
	// Loop
	
	int index;
	for (index=0;index < oldItemSetLength;index++)
		newItemSet[index] = oldItemSet[index];
	newItemSet[index] = newElement;
	
	// Return new item set
	
	return(newItemSet);
	}

    /* REALLOC 2 */
    
    /** Resizes given array so that its length is increased by one element
    and new element added to front
    @param oldItemSet the original item set
    @param newElement the new element/attribute to be appended
    @return the combined item set */
    
    protected short[] realloc2(short[] oldItemSet, short newElement) {
        
	// No old array
	
	if (oldItemSet == null) {
	    short[] newItemSet = {newElement};
	    return(newItemSet);
	    }
	
	// Otherwise create new array with length one greater than old array
	
	int oldItemSetLength = oldItemSet.length;
	short[] newItemSet = new short[oldItemSetLength+1];
	
	// Loop
	
	newItemSet[0] = newElement;
	for (int index=0;index < oldItemSetLength;index++)
		newItemSet[index+1] = oldItemSet[index];
	
	// Return new array
	
	return(newItemSet);
	}
	
    /* --------------------------------------------- */
    /*                                               */
    /*            ITEM SET DELETE METHODS            */
    /*                                               */
    /* --------------------------------------------- */

    /* REMOVE FIRST N ELEMENTS */
    
    /** Removes the first n elements/attributes from the given item set.
    @param oldItemSet the given item set.
    @param n the number of leading elements to be removed. 
    @return Revised item set with first n elements removed. */
    
    protected short[] removeFirstNelements(short[] oldItemSet, int n) {
        if (oldItemSet.length == n) return(null);
    	else {
	    short[] newItemSet = new short[oldItemSet.length-n];
	    for (int index=0;index<newItemSet.length;index++) {
	        newItemSet[index] = oldItemSet[index+n];
	        }
	    return(newItemSet);
	    }
	}
	
    /* ---------------------------------------------------------------- */
    /*                                                                  */
    /*              METHODS TO RETURN SUBSETS OF ITEMSETS               */
    /*                                                                  */
    /* ---------------------------------------------------------------- */ 
	
    /* COMPLEMENT */
    
    /** Returns complement of first itemset with respect to second itemset.
    @param itemSet1 the first given item set.
    @param itemSet2 the second given item set.
    @return complement if <TT>itemSet1</TT> in <TT>itemSet2</TT>. */
    
    protected short[] complement(short[] itemSet1, short[] itemSet2) {
        int lengthOfComp = itemSet2.length-itemSet1.length;
	
	// Return null if no complement
	if (lengthOfComp<1) return(null);
	
	// Otherwsise define combination array and determine complement
	short[] complement  = new short[lengthOfComp];
	int complementIndex = 0;
	for(int index=0;index<itemSet2.length;index++) {
	    // Add to combination if not in first itemset
	    if (notMemberOf(itemSet2[index],itemSet1)) {
	    	complement[complementIndex] = itemSet2[index];
		complementIndex++;
		}	
	    }
	
	// Return
	return(complement);
	}
			    	
    /* --------------------------------------- */
    /*                                         */
    /*             SORT ITEM SET               */
    /*                                         */
    /* --------------------------------------- */
    		
    /* SORT ITEM SET: Given an unordered itemSet, sort the set */
    
    /** Sorts an unordered item set.
    @param itemSet the given item set. */   
    
    protected void sortItemSet(short[] itemSet) {
        short temp;	
        boolean isOrdered;
        int index; 
               
        do {
	    isOrdered = true;
            index     = 0; 
            while (index < (itemSet.length-1)) {
                if (itemSet[index] <= itemSet[index+1]) index++;
	        else {
	            isOrdered=false;
                    // Swap
		    temp = itemSet[index];
	            itemSet[index] = itemSet[index+1];
                    itemSet[index+1] = temp;
	            // Increment index
		    index++;  
	            }
	  	}     
	    } while (isOrdered==false);	
    	}	

    /* ----------------------------------------------------- */
    /*                                                       */
    /*             BOOLEAN ITEM SET METHODS ETC.             */
    /*                                                       */
    /* ----------------------------------------------------- */
	
    /* NOT MEMBER OF */
    
    /** Checks whether a particular element/attribute identified by a 
    column number is not a member of the given item set.
    @param number the attribute identifier (column number).
    @param itemSet the given item set.
    @return true if first argument is not a member of itemSet, and false 
    otherwise */
    
    protected boolean notMemberOf(short number, short[] itemSet) {
        
	// Loop through itemSet
	
	for(int index=0;index<itemSet.length;index++) {
	    if (number < itemSet[index]) return(true);
	    if (number == itemSet[index]) return(false);
	    }
	
	// Got to the end of itemSet and found nothing, return false
	
	return(true);
	}
		
    /* -------------------------------------------------- */
    /*                                                    */
    /*                ITEM SET COMBINATIONS               */
    /*                                                    */
    /* -------------------------------------------------- */ 
    
    /* COMBINATIONS */
    
    /** Invokes <TT>combinations</TT> method to calculate all possible 
    combinations of a given item set. <P>
    For example given the item set [1,2,3] this will result in the
    combinations[[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]].
    @param inputSet the given item set.
    @return array of arrays representing all possible combinations (may be null
    if no combinations). */

    protected short[][] combinations(short[] inputSet) {
	if (inputSet == null) return(null);
	else {
	    short[][] outputSet = new short[getCombinations(inputSet)][];
	    combinations(inputSet,0,null,outputSet,0);
	    return(outputSet);
	    }
	}
	
    /** Recursively calculates all possible combinations of a given item 
    set. 
    @param inputSet the given item set.
    @param inputIndex the index within the input set marking current 
    element under consideration (0 at start).
    @param sofar the part of a combination determined sofar during the
    recursion (null at start). 
    @param outputSet the combinations collected so far, will hold all
    combinations when recursion ends.
    @param outputIndex the current location in the output set. 
    @return revised output index. */
    
    private int combinations(short[] inputSet, int inputIndex, 
    		short[] sofar, short[][] outputSet, int outputIndex) {
    	short[] tempSet;
	int index=inputIndex;
	
    	// Loop through input array
	
	while(index < inputSet.length) {
            tempSet = realloc1(sofar,inputSet[index]);
            outputSet[outputIndex] = tempSet;
	    outputIndex = combinations(inputSet,index+1,
	    		copyItemSet(tempSet),outputSet,outputIndex+1);	
    	    index++;
	    }    

    	// Return

    	return(outputIndex);
    	}

    /* GET COMBINATTIONS */
    
    /** Gets the number of possible combinations of a given item set.
    @param set the given item set.
    @return number of possible combinations. */
    
    private int getCombinations(short[] set) {
    	int counter=0, numComb;	
	
	numComb = (int) Math.pow(2.0,set.length)-1;
	    
    	// Return

        return(numComb);
        }   	
		
    /* ---------------------------------------------------------------- */
    /*                                                                  */
    /*                            MISCELANEOUS                          */
    /*                                                                  */
    /* ---------------------------------------------------------------- */ 
    
    /* COPY ITEM SET */
    
    /** Makes a copy of a given itemSet. 
    @param itemSet the given item set.
    @return copy of given item set. */
    
    protected short[] copyItemSet(short[] itemSet) {
	
	// Check whether there is a itemSet to copy
	if (itemSet == null) return(null);
	
	// Do copy and return
	short[] newItemSet = new short[itemSet.length];
	for(int index=0;index<itemSet.length;index++) {
	    newItemSet[index] = itemSet[index];
	    }
        
	// Return
	return(newItemSet);
	}
	
    /* ------------------------------------------------- */
    /*                                                   */
    /*                    GET METHODS                    */
    /*                                                   */
    /* ------------------------------------------------- */ 
    
    /* GET CONFIDENCE */    
    /** Gets the current confidence setting. 
    @return the confidence value. */
    
    public double getConfidence() {
        return(confidence);
	}
	
    /* ------------------------------------------------- */
    /*                                                   */
    /*                   OUTPUT METHODS                  */
    /*                                                   */
    /* ------------------------------------------------- */
	
    /* ----------- */
    /* OUTPUT MENU */
    /* ----------- */
    /** Outputs menu for command line arguments. */
    
    protected void outputMenu() {
        System.out.println();
	System.out.println("-C  = Confidence (default 80%)");
	System.out.println("-F  = File name");
	System.out.println("-S  = Support (default 20%)"); 
	System.out.println();
	
	// Exit
	
	System.exit(1);
	}
    
    /* --------------- */
    /* OUTPUT SETTINGS */
    /* --------------- */
    /** Outputs command line values provided by user. */
    
    protected void outputSettings() {
        System.out.println("SETTINGS\n--------");
	System.out.println("File name                = " + fileName);
	System.out.println("Support (default 20%)    = " + support); 
	System.out.println("Confidence (default 80%) = " + confidence);
	System.out.println();
        }
	
    /* -------------- */
    /* OUTPUT ITEMSET */  
    /* -------------- */  
    /** Outputs a given item set. 
    @param itemSet the given item set. */
    
    protected void outputItemSet(short[] itemSet) {
	    
	// Loop through item set elements
	
	if (itemSet == null) System.out.print(" null ");
	else {
            int counter = 0;
	    for (int index=0;index<itemSet.length;index++) {
	        if (counter == 0) {
	    	    counter++;
		    System.out.print(" {");
		    }
	        else System.out.print(" ");
	        System.out.print(itemSet[index]);
		}
	    System.out.print("} ");
	    }
	}	   	   
    
    /* ---------------------------------*/
    /* OUTPUT ITEMSET WITH RECONVERSION */
    /* ---------------------------------*/    
    /** Outputs a given item set reconverting it to its original column number
    labels (used where input dataset has been reordered and possible pruned). 
    @param itemSet the given item set. */
    
    protected void outputItemSetWithReconversion(short[] itemSet) {
	    
	// Loop through item set elements
	
	if (itemSet == null) System.out.print(" null ");
	else {
            int counter = 0;
	    for (int index=0;index<itemSet.length;index++) {
	        if (counter == 0) {
	    	    counter++;
		    System.out.print(" [");
		    }
	        else System.out.print(" ");
	        System.out.print(reconversionArray[itemSet[index]]);
		}
	    System.out.print("] ");
	    }
	}
    
    /* --------------------------------- */
    /*                                   */
    /*        DIAGNOSTIC OUTPUT          */
    /*                                   */
    /* --------------------------------- */
        
    /* OUTPUT DURATION */    
    /** Outputs difference between two given times.
    @param time1 the first time.
    @param time2 the second time. 
    @return duration. */
    
    public double outputDuration(double time1, double time2) {
        double duration = (time2-time1)/1000;
	System.out.println("Generation time = " + twoDecPlaces(duration) + 
			" seconds (" + twoDecPlaces(duration/60) + " mins)");
        
	// Return
	return(duration);
	}
    
    /* GET DURATION */
    /** Returns the difference between two given times as a string.
    @param time1 the first time.
    @param time2 the second time. 
    @return the difference between the given times as a string. */
    
    protected String getDuration(double time1, double time2) {
        double duration = (time2-time1)/1000;
    	return("Generation time = " + twoDecPlaces(duration) + 
			" seconds (" + twoDecPlaces(duration/60) + " mins)");
	}
		
    /* -------------------------------- */
    /*                                  */
    /*        OUTPUT UTILITIES          */
    /*                                  */
    /* -------------------------------- */
    
    /* TWO DECIMAL PLACES */
    
    /** Converts given real number to real number rounded up to two decimal 
    places. 
    @param number the given number.
    @return the number to two decimal places. */ 
    
    protected double twoDecPlaces(double number) {
    	int numInt = (int) ((number+0.005)*100.0);
	number = ((double) numInt)/100.0;
	return(number);
	}    
    
    }