rulelist.java

多关联分类算法

    /*              CHI SQUARED TESTING             */ 
    /*                                              */ 
    /* -------------------------------------------- */ 
	     
    /* TEST RULE USING CHI SQUARED TESTING */ 
     
    /** Tests a classification rule with the given parameters to determine  
    the interestingness/surprisingness of the rule. 
    @param supA the support value for the antecedent of the rule.  
    @param supC the support value for the consequent of the rule.  
    @param supAC the support for the rule.  
    @param numR the number of records in the input (training) sets.  
    @return true if Chi squared value is above critical threshold and false 
    otherwise.  */ 
     
    public boolean testRuleUsingChiSquaredTesting(double supA, double supC,  
    					double supAC, double numR) { 
	// Calculate Chi squared value 
	double chiSquaredValue = getChiSquaredValue(supA,supC,supAC,numR);
				 
	// Test Chi Squared value. 
	if (chiSquaredValue>threshold) return(true); 
	else return(false); 
	} 
	 
    /* GET CHI-SQUARED VALUE */ 
         
    /** Calculates and returns the Chi-Squared value for a rule.  
    @param supA the support value for the antecedent of the rule.  
    @param supC the support value for the consequent of the rule.  
    @param supAC the support for the rule.  
    @param numR the number of records in the input (training) sets.  
    @return the Chi squared value.  */ 
     
    private double getChiSquaredValue(double supA, double supC,  
    						double supAC, double numR) { 
	// Set values 
	supAntecedent = supA; 
    	supConsequent = supC; 
    	supRule       = supAC;	 
    	numRecords    = numR; 
    	 
	// Calculate observed and expected values 
	calculateObsValues(); 
	calculateExpValues(); 
	 
	// Calculate and return Chi squared value 
	return(calcChiSquaredValue()); 
	} 
				 
    /* CALCULATE OBSERVED VALUES */ 
     
    /** Calculates observed values for Chi squared testing calculation. */ 
      
    private void calculateObsValues() { 
        obsValues[0]=supRule; 
	obsValues[1]=supAntecedent-supRule; 
	obsValues[2]=supConsequent-supRule; 
	obsValues[3]=numRecords-supAntecedent-supConsequent+supRule; 
	  
	// Calculate additional support values 
	supNotAntecedent=numRecords-supAntecedent; 
    	supNotConsequent=numRecords-supConsequent;
	} 
	 
    /* CALIULASTE EXPECTED VALUES */ 
     
    /** Calculates expected values for Chi squared testing calculation. */ 
      
    private void calculateExpValues() { 
         expValues[0]=(supConsequent*supAntecedent)/numRecords; 
	 expValues[1]=(supNotConsequent*supAntecedent)/numRecords; 
	 expValues[2]=(supConsequent*supNotAntecedent)/numRecords; 
	 expValues[3]=(supNotConsequent*supNotAntecedent)/numRecords;
	 } 
	 
    /* CALCULATE CHI SQUARED VALUE */ 
     
    /** Calculates the Chi squared values and returns their sum. 
    @return the sum of the Chi Squared values. */  
     
    private double calcChiSquaredValue() { 
        double sumChiSquaredValues = 0.0; 
	 
	for (int index=0;index<obsValues.length;index++) { 
	    double chiValue = Math.pow((obsValues[index]- 
	    			    expValues[index]),2.0)/expValues[index]; 
	    sumChiSquaredValues = sumChiSquaredValues+chiValue; 
	    } 
	 
	// Return
	return(sumChiSquaredValues); 
	} 
		 
    /* ------------------------------------------------------------- */ 
    /*                                                               */ 
    /*                     RULE PRUNING (CMAR)                       */ 
    /*                                                               */ 
    /* ------------------------------------------------------------- */ 
     
    /* PRUNE USING COVER */ 
     
    /** Prunes the current CMAR list of rules according to the "cover"  
    principle. 
    @param trainingSet the input data set.	*/ 
     
    protected void pruneUsingCover(short[][] trainingSet) { 
        // Initialise cover array 
	int[] cover = new int[trainingSet.length]; 
	 
	// Define rule list references 
	RuleNodeCMAR newStartRef = null; 
	RuleNodeCMAR markerRef   = null; 
	RuleNodeCMAR linkRef     = startCMARrulelist; 
 
	// Loop through rule list 
	while (linkRef!=null) {
	    // If no more training records end 
	    if (emptyDataSet(trainingSet)) break; 
	    // Set cover flag to false, will be set to true of a rule matches  
	    // a record. 
	    boolean coverFlag=false; 
	    // Loop through training set
	    for (int index=0;index<trainingSet.length;index++) { 
	   	// If record satisfies a rule increment cover element for  
		// record and set cover flag to true to indicate that rule 
		// is required by at least one record 
		if (isSubset(linkRef.antecedent,trainingSet[index])) { 
		   cover[index]++; 
		   coverFlag=true;  
		   } 
		}
	    // If current rule is required by at least one record (cover flag 
	    // set to true) add to new rule list 
	    if (coverFlag) { 
	    	if (newStartRef==null) newStartRef=linkRef; 
		else markerRef.next=linkRef; 
		markerRef=linkRef; 
		linkRef=linkRef.next; 
		markerRef.next=null; 
		}	    
	    else linkRef=linkRef.next; 
	    // Remove records from training set if adequately covered 
	    for (int index=0;index<cover.length;index++) { 
	        if (cover[index]>MIN_COVER) trainingSet[index]=null; 
	        } 
	    } 
	 
	// Set rule list  
	startCMARrulelist = newStartRef; 
	} 
     
    /* EMPTY DATA SET */ 
     
    /** Tests whether a data set is empty or not (all records set to null). 
    @param dataSet the input data set. 
    @return true if empty, false othjerwise. */ 
     
    private boolean emptyDataSet(short[][] dataSet) { 
        // Loop through given data set 
        for (int index=0;index<dataSet.length;index++)  
	    			   if (dataSet[index]!=null) return(false); 
	 
	// Default 
	return(true); 
	} 

    /* ------------------------------------------------------------- */ 
    /*                                                               */ 
    /*                         CLASSIFIER                            */ 
    /*                                                               */ 
    /* ------------------------------------------------------------- */ 
     
    /* CLASSIFY RECORD (USING WEIGHTED CHI SQUARED) */ 
    /** Selects the best rule in a rule list according to the Weighted Chi- 
    Squared (WCS) Value. <P> Proceed as follows: <OL> 
    <LI>Collect rules that satisfy the record. if 
    <OL type="i"> 
    <LI>If consequents of all rules are all identical, or 
    only one rule, classify record. 
    <LI>Else group rules according to classifier and determine the combined 
    effect of the rules in each group, the classifier associated with 
    the "strongest group" is then selected. 
    </OL> 
    @param classification the possible classes. 
    @param itemset the record to be classified.	 
    @return the class label (or 0 if no class found).	*/ 
 
    protected short classifyRecordWCS(short[] itemSet) { 
//outputCMARrules();         
	RuleNodeCMAR linkRef = startCMARrulelist; 
	RuleNodeCMAR tempRulelist = startCMARrulelist;	 
	startCMARrulelist=null; 
	 
	// Obtain rules that satisfy record (iremSet) 
       obtainallRulesForRecord(linkRef,itemSet); 
//System.out.println("*********\nclassifyRecordWCS: Rules that satisy record = "); 
//outputItemSet(itemSet); 
//System.out.println(":"); 
//outputCMARrules(); 
//System.out.println(); 
 
        // If no rules satisfy record return 0 
	if (startCMARrulelist==null) return(0); 
	 
	// If only one rule return class 
	if (startCMARrulelist.next== null) { 
	    short answer = startCMARrulelist.consequent[0]; 
//System.out.println("ONLY ONE RULE: consequent = " + answer); 
	    startCMARrulelist=tempRulelist; 
	    return(answer); 
	    } 
	     
	// If more than one rule but all have the same class return calss 
	if (onlyOneClass()) { 
	    short answer = startCMARrulelist.consequent[0]; 
//System.out.println("ALL SAME CLASS consequent = " + answer); 
	    startCMARrulelist=tempRulelist; 
	    return(answer); 
	    } 
 
//System.out.println("CONFLICTING RULES");	 
	// Group rules 
	RuleNodeCMAR[] ruleGroups = groupRules(); 
	 
	// Determine Weighted Chi-Squared (WCS) Values for each group 
	double[] wcsValues = calcWCSvalues(ruleGroups); 
//System.out.println("wcsValues: "); 
//for (int index=0;index<wcsValues.length;index++)  
//System.out.println(wcsValues[index]);	 
	// Select group with best WCS value and return associated label 
	short consequent = selectBestWCS(wcsValues); 
//System.out.println("consequent = " + consequent);	 
	// Reset global rule list reference 
	startCMARrulelist=tempRulelist; 
	// Return class 
	return(consequent); 
	}  
     
    /* GROUP RULES */ 
     
    /** Groups rules contained in a linked list of rules pointed at by  
    <TT>startCMARrulelist</TT> according to their consequent.     
    @return an array of rule groups. */ 
     
    private RuleNodeCMAR[] groupRules() { 
        // Initialise rule groups data structure 
	RuleNodeCMAR[] ruleGroups = new RuleNodeCMAR[numClasses]; 
	for (int index=0;index<ruleGroups.length;index++) 
							ruleGroups[index]=null;	 
	// Loop through rule list 
	RuleNodeCMAR linkRef = startCMARrulelist; 
	while (linkRef!=null) { 
	   // Identify index for consequent 
	   int index = numOneItemSets-linkRef.consequent[0]; 
           // Add to rule group 
	   RuleNodeCMAR ruleCopy = new RuleNodeCMAR(linkRef.antecedent, 
	   			     linkRef.consequent,linkRef.supportForRule, 
				 linkRef.suppAntecedent,linkRef.suppConsequent, 
						    linkRef.confidenceForRule); 
	   ruleCopy.next=ruleGroups[index]; 
	   ruleGroups[index]=ruleCopy; 
	   // Increment link reference 
	   linkRef=linkRef.next; 
	   } 
	 
//outputGroups(ruleGroups); 
	// Return 
	return(ruleGroups); 
	}	 
	 
   /* ONLY ONE CLASS */ 
    
   /** Checks whether given rule list consequents all refer to the same class  
   or not. 
   @return true if identical consequent in all rules, false otherwise. */ 
    
   private boolean onlyOneClass() { 
       RuleNodeCMAR linkRef = startCMARrulelist; 
        
       // Class for first rule. 
       short firstClass = linkRef.consequent[0]; 
       
       // loop through rest of list. 
       linkRef = linkRef.next; 
       while (linkRef!=null) {   
           if (linkRef.consequent[0]!=firstClass) return(false); 
	   linkRef=linkRef.next; 
	   } 
	    
       // Default return 
       return(true); 
       } 
	 
    /* CALCULATE WEIGHTED CHI SQUARED VALUE FOR RULE GROUPS */ 
     
    /** Determines and returns the weighted Chi Squared values for the groups of 
    rules. 
    @param ruleGroups the given groups of rule. 
    @return array of weighted Chi-Squared value for a set of rule groups */ 
     
    private double[] calcWCSvalues(RuleNodeCMAR[] ruleGroups) { 
        // Dimension array 
	double[] wcsArray = new double[ruleGroups.length]; 
	 
	for (int index=0;index<ruleGroups.length;index++) { 
	    RuleNodeCMAR linkRuleNode = ruleGroups[index]; 
	    double wcsValue = 0.0; 
	    while (linkRuleNode != null) { 
		double chiSquaredValue =  
				 getChiSquaredValue(linkRuleNode.suppAntecedent, 
					linkRuleNode.suppConsequent, 
					linkRuleNode.supportForRule,numRecords); 
		double chiSquaredUB =  
			   calcChiSquaredUpperBound(linkRuleNode.suppAntecedent, 
						   linkRuleNode.suppConsequent); 
		wcsValue =  
		      wcsValue + (chiSquaredValue*chiSquaredValue)/chiSquaredUB; 
//System.out.println("chiSquaredValue = " + chiSquaredValue +  
//",  chiSquaredUB = " + chiSquaredUB + ",  wcsValue = " + wcsValue);		 
		linkRuleNode = linkRuleNode.next; 
		} 
	    wcsArray[index]=wcsValue; 
	    } 
	 
	// Return 
	return(wcsArray); 
	} 
     
    /* BEST WCS VALUE */ 
     
    /** Determines the best of the given WCS values and returns the consequent 
    associated with this bet value. 
    @param wcsArray the given array of weighted Chi-Squared value for a set  
    of rule groups.  
    @return the selected consequent. */