rulelist.java

多关联分类算法

/* -------------------------------------------------------------------------- */
/*                                                                            */
/*                              RULE LIST                                     */
/*                                                                            */
/*                            Frans Coenen                                    */
/*                                                                            */
/*                         Tuesday 2 March 2004                               */
/*                                                                            */
/*                    Department of Computer Science                          */
/*                     The University of Liverpool                            */
/*                                                                            */ 
/* -------------------------------------------------------------------------- */
/* Class structure

AssocRuleMining
      |
      +-- RuleList			*/

// Java packages
import java.io.*;
import java.util.*;

// Java GUI packages
import javax.swing.*;

/** Set of utilities to support various Association Rule Mining (ARM) 
algorithms included in the LUCS-KDD suite of ARM programs. 
@author Frans Coenen
@version 2 March 2004 */

public class RuleList extends AssocRuleMining {

    /* ------ FIELDS ------ */
	
    // --- Data structures ---
    
    /** Rule node in linked list of rules (either ARs or CRs). */ 
 
    protected class RuleNode { 
    	/** Antecedent of AR. */ 
	protected short[] antecedent; 
	/** Consequent of AR. */ 
	protected short[] consequent; 
	/** The confidence value associate with the rule represented by this 
	node. */ 
	double confidenceForRule=0.0; 
	/** Link to next node */ 
	RuleNode next = null; 
	 
	/** Three argument constructor 
	@param antecedent the antecedent (LHS) of the AR. 
    	@param consequent the consequent (RHS) of the AR. 
    	@param support the associated confidence value. */ 
	 
	private RuleNode(short[] ante, short[]cons, double confValue) { 
	    antecedent        = ante; 
	    consequent        = cons; 
	    confidenceForRule = confValue; 
	    } 
	} 

    /** Rule node in linked list of rules (either ARs or CRs) for CMAR 
    algorithm. */ 
 
    protected class RuleNodeCMAR { 
    	/** Antecedent of AR. */ 
	protected short[] antecedent; 
	/** Consequent of AR. */ 
	protected short[] consequent; 
	/** The confidence value associate with the rule represented by this 
	node. */ 
	double confidenceForRule=0.0; 
	/** The support value associate with the rule represented by this 
	node. */ 
	double supportForRule=0.0; 
	/** The support value associate with the antecedent of the rule  
	represented by this node. */ 
	double suppAntecedent=0.0; 
	/** The support value associate with the consequent of the rule  
	represented by this node. */ 
	double suppConsequent=0.0; 
	/** Link to next node */ 
	RuleNodeCMAR next = null; 
	 
	/** Six argument constructor 
	@param antecedent the antecedent (LHS) of the AR. 
    	@param consequent the consequent (RHS) of the AR. 
    	@param suppValue the associated support value.  
	@param suppAnte the associated support for the antecedent. 
	@param suppCons the associated support for the consequent. 
	@param comsvalue the associated confidence value.   */ 
	 
	private RuleNodeCMAR(short[] ante, short[]cons, double suppValue, 
	      	      double suppAnte, double suppCons, double confValue) { 
	    antecedent        = ante; 
	    consequent        = cons; 
	    supportForRule    = suppValue; 
	    suppAntecedent    = suppAnte; 
	    suppConsequent    = suppCons; 
	    confidenceForRule = confValue; 
	    } 
	} 
    
    /** The reference to start of the rule list. */ 
    protected RuleNode startRulelist = null;	
    /** The reference to start of the CMAR rule list. */ 
    protected RuleNodeCMAR startCMARrulelist = null; 
    /** 1-D array for observed values for Chi-Squared Testing. */ 
    private double[] obsValues = new double[4]; 
    /** 1-D array for expected values for Chi-Squared Testing. */ 
    private double[] expValues = new double[4]; 

    // --- Chi-Squared Testing Constants ---     
    /** Critical threshold for 10% "significance" level (assuming "degree of 
    freedom" equivalent to 1). */ 
    private static final double THRESHOLD_10    = 2.7055; 
    /** Critical threshold for 5% "significance" level (assuming "degree of 
    freedom" equivalent to 1). */ 
    private static final double THRESHOLD_5     = 3.8415; 
    /** Critical threshold for 2.5% "significance" level (assuming "degree of 
    freedom" equivalent to 1). */ 
    private static final double THRESHOLD_2HALF = 5.0239; 
    /** Critical threshold for 1% "significance" level (assuming "degree of 
    freedom" equivalent to 1). */ 
    private static final double THRESHOLD_1     = 6.6349; 
    /** Critical threshold for 0.5% "significance" level (assuming "degree of 
    freedom" equivalent to 1). */ 
    private static final double THRESHOLD_HALF  = 7.8794; 
     
    // Cover constant 
    /** Minimum times a record mist be covered */ 
    private static int MIN_COVER=3; 	// At least 3 rules 
     
    // --- Chi-Squared Fields --- 
    /** Support value for the antecedent of the rule. */ 
    private double supAntecedent; 
    /** Support value for NOT the antecedent of the rule. */ 
    private double supNotAntecedent; 
    /** Support value for the concequent of the rule. */ 
    private double supConsequent; 
    /** Support value for NOT the concequent of the rule. */ 
    private double supNotConsequent; 
    /** Support for the rule. */ 
    private double supRule;	 
    /** Number of records in the input (training) sets. */ 
    private double numRecords; 
    /** Current critical threshold value. */ 
    private double threshold = THRESHOLD_5;		// Default 

    /* ------ CONSTRUCTORS ------ */

    /** Default constructor to create an instance of the class RuleList  */
    	
    public RuleList() {
        }
	
    /* ------ METHODS ------ */	
	
    /* ---------------------------------------------------------------- */ 
    /*                                                                  */ 
    /*        RULE LINKED LIST ORDERED ACCORDING TO CMAR RANKING        */ 
    /*                                                                  */ 
    /* ---------------------------------------------------------------- */ 
     
    /* Methods for inserting rules into a linked list of rules ordered  
    according to CMAR ranking. Each rule described in terms of 4 fields: 1)  
    Antecedent (an item set), 2) a consequent (an item set), 3) a total support  
    value and 4) a confidence value (double). */ 
     
    /* INSERT (ASSOCIATION/CLASSIFICATION) RULE INTO RULE LINKED LIST (ORDERED 
    ACCORDING CONFIDENCE). */ 
     
    /** Inserts an (association/classification) rule into the linkedlist of 
    rules pointed at by <TT>startRulelist</TT>. <P> List is ordered according  
    to "CMAR" ranking.  
    @param antecedent the antecedent (LHS) of the rule. 
    @param consequent the consequent (RHS) of the rule. 
    @param supportForAntecedent the associated support for the antecedent. 
    @param supportForConsequent the associated support for the consequent. 
    @param supportForRule the associated support value.  
    @param confidenceForRule the associated confidence value. */ 
     
    protected void insertRinRlistCMARranking(short[] antecedent,  
    			     short[] consequent, double supportForAntecedent, 
			  double supportForConsequent, double supportForRule,  
			                          double confidenceForRule) {
	 
        // Test rule using Chi-Squared testing 
        if (!testRuleUsingChiSquaredTesting(supportForAntecedent, 
		        supportForConsequent,supportForRule,numRows)) return; 
	 
	// Create new node 
	RuleNodeCMAR newNode = new RuleNodeCMAR(antecedent,consequent, 
				       supportForRule,supportForAntecedent, 
				       supportForConsequent,confidenceForRule); 
	   
	// Empty rule list situation 
	if (startCMARrulelist == null) { 
	    startCMARrulelist = newNode; 
	    return; 
	    } 
	 
	// Check if more general rule with higher ranking exists.  
	if (moreGeneralRuleExists(newNode)) return; 
		 
	// Add new node to start	 
	if (ruleIsCMARgreater(newNode,startCMARrulelist)) { 
	    newNode.next = startCMARrulelist; 
	    startCMARrulelist  = newNode; 
	    return; 
	    } 
	 
	// Add new node to middle 
	RuleNodeCMAR markerNode = startCMARrulelist; 
	RuleNodeCMAR linkRuleNode = startCMARrulelist.next; 
	while (linkRuleNode != null) { 
	    if (ruleIsCMARgreater(newNode,linkRuleNode)) { 
	        markerNode.next = newNode; 
		newNode.next    = linkRuleNode; 
		return; 
		} 
	    markerNode = linkRuleNode; 
	    linkRuleNode = linkRuleNode.next;	     
	    }   
	 
	// Add new node to end 
	markerNode.next = newNode; 
	} 
	 
    /* MORE GENERAL EXISTS */ 
     
    /** Tests whether a more general rule, with higher ranking, already exists  
    in the rule list. 
    @param rule the rule under consideration. 
    @return true if more general rule with higher ranking exists, and false 
    otherwise. */ 
     
    private boolean moreGeneralRuleExists(RuleNodeCMAR rule) { 
        RuleNodeCMAR linkRef = startCMARrulelist; 
	 
	// Loop through list 
	while (linkRef!=null) { 
	    if (ruleIsMoreGeneral(rule,linkRef) &&  
	    			ruleIsCMARgreater2(rule,linkRef)) return(true); 
	    linkRef=linkRef.next; 
	    } 
	 
	// Default return 
	return(false); 
	} 
    	 
    /* RULE IS MORE GENERAL */ 
     
    /** Compares two rules and returns true if the first is a more general rule 
    than the second (has fewer antecedent attributes). 
    @param rule1 the given rule to be compared to the second. 
    @param rule2 the rule which the given rule1 is to be compared to. 
    @return true id rule1 is greater then rule2, and false otherwise. */ 
     
    private boolean ruleIsMoreGeneral(RuleNodeCMAR rule1, RuleNodeCMAR rule2) { 
        if (rule1.antecedent.length < rule2.antecedent.length) return(true); 
	 
	// Otherwise return false    
	return(false); 
	}  
	 
    /* RULE IS CMAR GREATER */ 
     
    /** Compares two rules and returns true if the first is "CMAR greater" (has  
    a higher ranking) than the second. <P> CMAR ordering is as follows: 
    <OL> 
    <LI>Confidence, a rule <TT>r1</TT> has priority over a rule <TT>r2</TT> if  
    <TT>confidence(r1) &gt; confidence(r2)</TT>.  
    <LI>Support, a rule <TT>r1</TT> has priority over a rule <TT>r2</TT> if  
    <TT>confidence(r1)==confidence(r2) &amp;&amp; support(r1)&gt;support(r2) 
    </TT>.  
    <LI>Size of antecedent, a rule <TT>r1</TT> has priority over a rule  
    <TT>r2</TT> if <TT>confidence(r1)==confidence(r2) &amp;&amp; 
    support(r1)==spoort(r2) &amp;&amp;|A<SUB>r1</SUB>|&lt;|A<SUB>r2</SUB>| 
    </TT>.  
    </OL> 
    @param rule1 the given rule to be compared to the second. 
    @param rule2 the rule which the given rule1 is to be compared to. 
    @return true id rule1 is greater then rule2, and false otherwise. */ 
     
    private boolean ruleIsCMARgreater(RuleNodeCMAR rule1, RuleNodeCMAR rule2) { 
        // Compare confidences 
	if (rule1.confidenceForRule > rule2.confidenceForRule) return(true); 
	 
	// If confidences are the same compare support values 
        if (similar2dec(rule1.confidenceForRule,rule2.confidenceForRule)) { 
	   if (rule1.supportForRule > rule2.supportForRule) return(true); 
	   // If confidences and supports are the same compare antecedents 
	   if (similar2dec(rule1.supportForRule,rule2.supportForRule)) { 
	       if (rule1.antecedent.length < rule2.antecedent.length)  
	       							return(true); 
	       } 
	   } 
	 
	// Otherwise return false    
	return(false); 
	}  
	 
    /* RULE IS CMAR GREATER 2 */ 
    	 
    /** Compares two rules, such that the first id more general than the second, 
    and returns true if the first is "CMAR greater" (has a higher ranking) than  
    the second. <P> Method similar to ruleIsCMARgreater method but with the 
    "more general rule" prerequisite. CMAR ordering (founded on confidence and  
    support only) is as follows: 
    <OL> 
    <LI>Confidence, a rule <TT>r1</TT> has priority over a rule <TT>r2</TT> if  
    <TT>confidence(r1) &gt; confidence(r2)</TT>.  
    <LI>Support, a rule <TT>r1</TT> has priority over a rule <TT>r2</TT> if  
    <TT>confidence(r1)==confidence(r2) &amp;&amp; support(r1)&gt;support(r2) 
    </TT>.
    </OL> 
    @param rule1 the given rule to be compared to the second. 
    @param rule2 the rule which the given rule1 is to be compared to. 
    @return true id rule1 is greater then rule2, and false otherwise. */ 
     
    private boolean ruleIsCMARgreater2(RuleNodeCMAR rule1, RuleNodeCMAR rule2) { 
        // Compare confidences 
	if (rule1.confidenceForRule > rule2.confidenceForRule) return(true); 
	 
	// If confidences are the same compare support values 
        if (similar2dec(rule1.confidenceForRule,rule2.confidenceForRule)) { 
	   if (rule1.supportForRule > rule2.supportForRule) return(true); 
	   } 
	 
	// Otherwise return false    
	return(false); 
	}  
	 
    /* -------------------------------------------- */ 
    /*                                              */