assocrulemining.java

Decision Tree Decision Tree Decision Tree

	// Loop through columns
        for (int colIndex=1;colIndex<=numOneItemSets;colIndex++) {
	    outputPartitionToFile(fName,(short) colIndex);
	    }
	}

    /* CALCULATE NUMBER OF ROWS PER SEGMENT */

    /** Calculatwes the number of records per segement for a given number of
    segements
    @param numSegments the number of segments into which the data is to be
    decompossed.
    @return the number of rows per segment. */

    protected int calcRowsPerSegment(int numSegments) {
        int rowsPerSegment = numRows/numSegments;

	// If 0 error message and exits
	if (rowsPerSegment==0) {
	    System.out.println("DATA SEGMENTATION ERROR: number of desired " +
	    	"segments (" + numSegments + ") exceeds number of records ("+
		numRows + ") in input dataset");
	    System.exit(1);
	    }

	// Return
	return(rowsPerSegment);
	}

    /* -------------------------------------------------------------- */
    /*                                                                */
    /*        RULE LINKED LIST ORDERED ACCORDING TO CONFIDENCE        */
    /*                                                                */
    /* -------------------------------------------------------------- */

    /* Methods for inserting rules into a linked list of rules ordered
    according to confidence (most confident first). Each rule described in
    terms of 3 fields: 1) Antecedent (an item set), 2) a consequent (an item
    set), 3) a confidence value (double). <P>The support field is not used. */

    /* INSERT (ASSOCIATION/CLASSIFICATION) RULE INTO RULE LINKED LIST (ORDERED
    ACCORDING CONFIDENCE). */

    /** Inserts an (association/classification) rule into the bianry tree of
    rules pointed at by <TT>startRulelist</TT>. <P> The list is ordered from
    left to right so that rules with highest "ordering value" (this is assumed
    to be a confidence value but could equaly well be some other value such as
    lift) are listed in the left most branch. If two rules have the same
    ordering value the new rule will be placed after the existing rule. Thus,
    if using an Apriori approach to generating rules, more general rules will
    appear first in the list with more specific rules (i.e. rules with a larger
    antecedent) appearing later as the more general rules will be generated
    first.
    @param antecedent the antecedent (LHS) of the rule.
    @param consequent the consequent (RHS) of the rule.
    @param ordValue1 the primary ordering value (usually the confidence value).
    @param ordValue2 the secondary ordering value (usually the support
    value).          */

    protected void insertRuleIntoRulelist(short[] antecedent,
                       short[] consequent, double ordValue1, double ordValue2) {
        // Check if limit is reached
	if (numRules > MAX_NUM_RULES) return;
	
	// Check for empty tree.
	if (startRulelist == null) startRulelist = new RuleNode(antecedent,
                                               consequent,ordValue1,ordValue2);
        // Otherwise "walk" tree
	else insertRuleIntoRulelist(startRulelist,antecedent,consequent,
                                                          ordValue1,ordValue2);

	}
	
    /** Inserts an (association/classification) rule into the bianry tree of
    rules pointed at by <TT>startRulelist</TT>. <P>Version which uses only one
    ordinal value, second ordinal value set to 0.0.
    @param antecedent the antecedent (LHS) of the rule.
    @param consequent the consequent (RHS) of the rule.
    @param ordValue1 the primary ordering value (usually the confidence 
    value).          */

    protected void insertRuleIntoRulelist(short[] antecedent,
                                        short[] consequent, double ordValue1) {
        double ordValue2=0.0;
	
	// Check for empty tree.
	if (startRulelist == null) startRulelist = new RuleNode(antecedent,
                                               consequent,ordValue1,ordValue2);
        // Otherwise "walk" tree
	else insertRuleIntoRulelist(startRulelist,antecedent,consequent,
                                                          ordValue1,ordValue2);
	}
	
    /** Continues process of adding rule to binary tree.
    @param node the current location in the bin tree.
    @param antecedent the antecedent (LHS) of the rule.
    @param consequent the consequent (RHS) of the rule.
    @param ordValue1 the primary ordering value (usually the confidence value).
    @param ordValue2 the secondary ordering value (usually the support
    value).          */

    private void insertRuleIntoRulelist(RuleNode node, short[] antecedent,
                      short[] consequent, double ordValue1, double ordValue2) {

        // Calculate selector
        boolean prcDwnLftBrnch = insertRuleSelector(node,antecedent,
                                                          ordValue1,ordValue2);

        // Left branch
        if (prcDwnLftBrnch) {
	    if (node.leftBranch==null) node.leftBranch = new
                           RuleNode(antecedent,consequent,ordValue1,ordValue2);
	    else insertRuleIntoRulelist(node.leftBranch,antecedent,consequent,
                                                          ordValue1,ordValue2);
	    }
	// Right branch
        else {
	    if (node.rightBranch==null) node.rightBranch = new
                           RuleNode(antecedent,consequent,ordValue1,ordValue2);
	    else insertRuleIntoRulelist(node.rightBranch,antecedent,consequent,
                                                          ordValue1,ordValue2);
	    }
	}

    /** Calculates selector for deciding whether to add rule to left or right
    branch of binary-tree rule storage structure.
    @param node the current location in the bin tree.
    @param antecedent the antecedent (LHS) of the rule.
    @param ordValue1 the primary ordering value (usually the confidence value).
    @param ordValue2 the secondary ordering value (usually the support
    value).
    @return true if left branch and false otherwise. */

    protected boolean insertRuleSelector(RuleNode node, short[] antecedent,
                                           double ordValue1, double ordValue2) {
        boolean prcDwnLftBrnch = false;

        // Compare "confidence" value
        if (ordValue1>node.confidenceForRule) prcDwnLftBrnch = true;
        else {
            // Compare "support" value
            if (ordValue1==node.confidenceForRule) {
                if (ordValue2>node.supportForRule) prcDwnLftBrnch = true;
                // Compare size of antecedent
                else {
                    if (ordValue2==node.supportForRule &&
                                     antecedent.length>node.antecedent.length)
                                                        prcDwnLftBrnch = true;
                    }
                }
            }

        // Rerturn
        return(prcDwnLftBrnch);
        }

    /* -------------------------------------------------------------- */
    /*                                                                */
    /*                         NUMBER RULES                           */
    /*                                                                */
    /* -------------------------------------------------------------- */

    /** Numbers and counts rules contained in binary-tree, usually done
    when tree is complete. */

    protected void numberRulesInBinTree() {
        // Check for empty tree.
	if (startRulelist == null) numRules=0;
	// Else proceed
	else {
	    short startNumber=1;
	    numRules = numberRulesInBinTree(startNumber,startRulelist)-1;
            }
	}

    /** Continues provess of numbering rules in rule binary (if any).
    @param number the current rule number.
    @param linkRuleNode the currentNode.
    @return the updated rule number sofar. */

    private short numberRulesInBinTree(short number, RuleNode linkRuleNode) {
        // Process node
        if (linkRuleNode != null) {
	    // Left branch
            number = numberRulesInBinTree(number,linkRuleNode.leftBranch);
	    // Node
	    linkRuleNode.ruleNumber=number;
	    number++;
	    // Right branch
            number = numberRulesInBinTree(number,linkRuleNode.rightBranch);
	    }

	// Return
	return(number);
        }

    /* -------------------------------------------------------------- */
    /*                                                                */
    /*                 GET CONSEQUENT FOR RULE N                      */
    /*                                                                */
    /* -------------------------------------------------------------- */

    /** Gets the consequent associated with a particular rule identified by
    its rule number.
    @param ruleNumber the identifying number of the desired rule consequent.
    @return the associated consequent (as an itemset). */

    protected short[] getConsequentOfRuleN(int ruleNumber) {
        // Check for empty tree.
	if (startRulelist == null) return(null);

	// Else proceed
	return(getConsequentOfRuleN(ruleNumber,startRulelist));
        }

    /** Continues provess of returning consequent associated with a particular
    rule identified by its rule number.
    @param ruleNum the identifying number of the desired rule consequent.
    @param linkRuleNode the currentNode.
    @return the associated consequent (as an itemset). */

    public short[] getConsequentOfRuleN(int ruleNum, RuleNode linkRuleNode) {
//System.out.println("getConsequentOfRuleN: ruleNum = " + ruleNum);
//System.out.println("linkRuleNode.ruleNumber = " + linkRuleNode.ruleNumber);
        // Found rule
        if (linkRuleNode.ruleNumber==ruleNum) return(linkRuleNode.consequent);

        // Proceed down left branch?
        if (ruleNum<linkRuleNode.ruleNumber) {
//System.out.println("Proceed down left branch");
            // Left branch exists?
            if (linkRuleNode.leftBranch!=null)
                  return(getConsequentOfRuleN(ruleNum,linkRuleNode.leftBranch));
            // Else cock up!
            else return(null);
            }
        // Proceed down righ branch
        else {  
//System.out.println("Proceed down right branch");
            // Right branch exists?
            if (linkRuleNode.rightBranch!=null)
                 return(getConsequentOfRuleN(ruleNum,linkRuleNode.rightBranch));
            // Else cock up!
            else return(null);
            }
        }


    /* -------------------------------------------------------------- */
    /*                                                                */
    /*                        COPY FIRST N RULES                      */
    /*                                                                */
    /* -------------------------------------------------------------- */

    /** Copies first N rules contained in one rule bin tree to another
    new bin tree.
    @param number the number of desired rules.
    @param node the currentNode.
    @return the number of rules accounred for sofar. */

    protected int copyFirstNrules(int number, RuleNode node) {
        // Process node
        if (node != null) {
	    // Left branch
            number = copyFirstNrules(number,node.leftBranch);
	    if (number==0) return(number);
            // Node
	    insertRuleIntoRulelist(node.antecedent,node.consequent,
                              node.confidenceForRule,node.supportForRule);
	    number--;
	    if (number==0) return(number);
	    // Right branch
            return(copyFirstNrules(number,node.rightBranch));
	    }
        
        // Return
        return(number);
        }

    /* -------------------------------------------------------------- */
    /*                                                                */
    /*    RULE LINKED LIST ORDERED ACCORDING TO SIZE OF ANTECEDENT    */
    /*                                                                */
    /* -------------------------------------------------------------- */

    /* INSERT (ASSOCIATION/CLASSIFICATION) RULE INTO RULE LINKED LIST 2
    (ORDERED ACCORDING SIZE OF ANTECEDENT --- MORE SPECIFIC RULES FIRST). */

    /** Inserts an (association/classification) rule into the linked list of
    rules pointed at by <TT>startRulelist</TT>. <P> List is ordered so that
    more specific rules (i.e. rules with most attributes in their antecedent)
    are listed first.      **** NOT CURRENTLY USED ****
    @param antecedent the antecedent (LHS) of the rule.
    @param consequent the consequent (RHS) of the rule.
    @param confidenceForRule the associated confidence value. */

    /* protected void insertRuleIntoRulelist2(short[] antecedent,
    				short[] consequent, double confidenceForRule) {
        // Check for empty tree.
	if (startRulelist == null) startRulelist = new RuleNode(antecedent,
                                                 consequent,confidenceForRule);
        // Otherwise "walk" tree
	else insertRuleIntoRulelist2(startRulelist,antecedent,consequent,
                                                            confidenceForRule);
	} */

    /** Continues process of adding rule to binary tree according to size of
    antecedent
    @param currentNode the current location in the bin tree.
    @param antecedent the antecedent (LHS) of the rule.
    @param consequent the consequent (RHS) of the rule.
    @param orderingValue the associated support value.   */

    /* private void insertRuleIntoRulelist2(RuleNode currentNode,
                short[] antecedent, short[] consequent, double orderingValue) {
        // Left branch
        if (antecedent.length>currentNode.antecedent.length) {
	    if (currentNode.leftBranch==null) currentNode.leftBranch = new
                              RuleNode(antecedent,consequent,orderingValue);
	    else insertRuleIntoRulelist2(currentNode.leftBranch,antecedent,
                                                  consequent,orderingValue);
	    }
	// Right branch
        else {
	    if (currentNode.rightBranch==null) currentNode.rightBranch = new
                              RuleNode(antecedent,consequent,orderingValue);
	    else insertRuleIntoRulelist2(currentNode.rightBranch,antecedent,
                                                  consequent,orderingValue);
	    }
	}   */

    /* ----------------------------------------------- */
    /*                                                 */
    /*        ITEM SET INSERT AND ADD METHODS          */
    /*                                                 */
    /* ----------------------------------------------- */

    /* APPEND */

    /** Concatenates two itemSets --- resizes given array so that its
    length is increased by size of second array and second array added.
    @param itemSet1 The first item set.
    @param itemSet2 The item set to be appended.
    @return the combined item set */

    protected short[] append(short[] itemSet1, short[] itemSet2) {

	// Test for empty sets, if found return other
	if (itemSet1 == null) return(copyItemSet(itemSet2));
	else if (itemSet2 == null) return(copyItemSet(itemSet1));

	// Create new array
	short[] newItemSet = new short[itemSet1.length+itemSet2.length];

	// Loop through itemSet 1
	int index1