crossvalidation.java

Short description: GUI Ant-Miner is a tool for extracting classification rules from data. It is an u

							else
								isEqual = false;
						}
					}
					if(!termOccurs)//if trainingSet does not contain term ij then...
						hArray[i][j] = 0.0;
					else if(isEqual)
						hArray[i][j] = (log2(numClasses)) / sum;
					else
						hArray[i][j] = (log2(numClasses) - infoTij[i][j]) / sum;

				}else
					hArray[i][j] = 0.0;
			}
		}
	}
	
	/**
	 * Calculates the probability that each term ij be selected to constitute
	 * part of the rule. The probability is given by:
	 * Pij = nij * tij(t) / S xm * (S hmn * tmn(t))
	 * @param ant
	 * @param pheromoneArray
	 */
	private void calculateProbabilities(Ant ant, double [][] pheromoneArray){
		double sum=0.0;
		int x=0, y=0;
		for(x=0; x < pheromoneArray.length; x++)
			if(ant.getMemory()[x] == 0) //if the attribute has not been used...
				for(y=0; y < hArray[x].length; y++)
					sum += hArray[x][y] * pheromoneArray[x][y];
		for(x=0; x < probabilitiesArray.length; x++){
			for(y=0; y < probabilitiesArray[x].length; y++){
				if(ant.getMemory()[x] == 0){
					double result = (hArray[x][y] * pheromoneArray[x][y]) / sum;
					//if division by zero, attribute cannot be used
					if(Double.isNaN(result)){
						probabilitiesArray[x][y] = 0.0;
						ant.getMemory()[x] = 2;
					}else
						probabilitiesArray[x][y] = result;
				}
				else
					probabilitiesArray[x][y] = 0.0;
			}
		}
	}
	
	/**
	 * Tries to add term ij to the rule. If the term is successfully added,
	 * returns true, otherwise returns false.
	 * @param ant
	 * @param i
	 * @param j
	 * @return
	 */
	private boolean ruleConstructor(Ant ant, int i, int j){
		int x;
		int total = 0;
		Object temp;
		List indexToRemoveList = new ArrayList();
		
		if(!ant.hasRules()){
			for(x=0; x < trainingSet.length; x++){
				if(trainingSet[x].getValues()[i] == attributesArray[i].getIntTypesArray()[j]){
					ant.getInstancesIndexList().add(new Integer(x));
					total++;
				}
			}
			if(total < minCasesRule){
				ant.clearRulesArray();
				ant.getInstancesIndexList().clear();
			}
		}else{
			ListIterator liInstancesIndex = ant.getInstancesIndexList().listIterator();
			while(liInstancesIndex.hasNext()){
				temp = liInstancesIndex.next();
				if(trainingSet[((Integer) temp).intValue()].getValues()[i] == attributesArray[i].getIntTypesArray()[j])
					total++;
				else
					indexToRemoveList.add(temp);
			}
		}
		
		if(total >= minCasesRule){
			ant.getRulesArray()[i] = j;
			ant.getMemory()[i] = 1; //cannot use attribute i to construct rule anymore
			ListIterator li = indexToRemoveList.listIterator();
			while(li.hasNext()){
				ant.getInstancesIndexList().remove(ant.getInstancesIndexList().indexOf(li.next()));
			}
			return true;
		}else
			return false;
	}
	
	
	/**
	 * Determines the consequent value of the rule.
	 * @param ant
	 * @return
	 */
	private int determineRuleConsequent(Ant ant){
		int ruleConsequent=-1;
		int [] freqClass = new int[numClasses];
		int trainingSetIndex;
		int trainingSetClass;
		
		ListIterator li = ant.getInstancesIndexList().listIterator();
		while(li.hasNext()){
			trainingSetIndex = ((Integer) li.next()).intValue();
			trainingSetClass = trainingSet[trainingSetIndex].getClassValue();
			freqClass[trainingSetClass]++;
		}
		
		int mostFreq = 0, mostFreqIndex = -1;
		for(int x=0; x < numClasses; x++){
			if(mostFreq < freqClass[x]){
				mostFreq = freqClass[x];
				mostFreqIndex = x;
			}
		}
		if(mostFreqIndex != -1)
			ruleConsequent = attributesArray[attributesArray.length-1].getIntTypesArray()[mostFreqIndex];
		ant.setRuleConsequent(ruleConsequent);
		return ruleConsequent;
	}
	
	/**
	 * Calculates the rule quality of the ant. 
	 * @param ant
	 * @return
	 */
	private double calculateRuleQuality(Ant ant){
		double quality;
		int vp, fp, fn, vn;
		vp=fp=fn=vn=0;
		
		int antDataInstIndex=-1;
		ListIterator li=null;
		if(!ant.getInstancesIndexList().isEmpty()){
			li = ant.getInstancesIndexList().listIterator();
			antDataInstIndex = (Integer)li.next();
		}
		
		for(int dataInstanceIndex=0; dataInstanceIndex < trainingSet.length; dataInstanceIndex++){
			//if the data instance is covered by the rule...
			if(dataInstanceIndex == antDataInstIndex){
				if(li.hasNext())
					antDataInstIndex = (Integer)li.next();
				if(trainingSet[dataInstanceIndex].getClassValue() == ant.getRuleConsequent())
					vp++;
				else
					fp++;
			}else{
				if(trainingSet[dataInstanceIndex].getClassValue() == ant.getRuleConsequent())
					fn++;
				else
					vn++;
			}
		}
		quality = ((double) vp / (vp + fn)) * ((double) vn / (fp + vn));
		if(Double.isNaN(quality))
			quality = 0.0;		
		ant.setRuleQuality(quality);
		return quality;
	}
	
	/** 
	 * Updates the ant list that contains the indexes of the instances/cases covered
	 * by the ant rule. This method must be run when the ant rule changes.
	 */
	private void updateInstancesIndexList(Ant ant){
		ant.getInstancesIndexList().clear();
		boolean isCoveredByRule;
		
		for(int x=0; x < trainingSet.length; x++){
			isCoveredByRule=true;
			for(int y=0; y < trainingSet[x].getValues().length-1  && isCoveredByRule; y++)
				if(ant.getRulesArray()[y] != -1 && trainingSet[x].getValues()[y] != ant.getRulesArray()[y])
					isCoveredByRule = false;
			if(isCoveredByRule)
				ant.getInstancesIndexList().add(new Integer(x));			
		}
	}
	
	/**
	 * Prunes the rule of the ant.
	 * @param ant
	 * @return
	 * @throws CloneNotSupportedException
	 */
	private Ant pruneRule(Ant ant) throws CloneNotSupportedException{
		int numCond;
		double greatestQuality, currentRuleQuality;
		Ant antClone;
		Ant antCloneWithBestPrunedRule = ant;

		for(int a1=0; a1 < ant.getRulesArray().length; a1++){
			greatestQuality = currentRuleQuality = ant.getRuleQuality();
			numCond = 0;
			for(int a=0; a < ant.getRulesArray().length; a++){
				if(ant.getRulesArray()[a] != -1){
					numCond++;
					antClone = (Ant)ant.clone();
					antClone.getRulesArray()[a] = -1;
					updateInstancesIndexList(antClone);
					determineRuleConsequent(antClone);
					calculateRuleQuality(antClone);
					if(antClone.getRuleQuality() >= greatestQuality){
						greatestQuality = antClone.getRuleQuality(); 
						antCloneWithBestPrunedRule = (Ant) antClone.clone();
					}
				}
			}
			if(greatestQuality >= currentRuleQuality && numCond > 1)
				ant = (Ant) antCloneWithBestPrunedRule.clone();
			else //rule could not be improved, so leave block
				a1 = ant.getRulesArray().length;
		}
		return ant;
	}
	
	/**
	 * Updates the trail of pheromone.
	 * @param ant
	 */
	private void updatePheromone(Ant ant){
		//update pheromone for used terms
		for(int x=0; x < ant.getRulesArray().length; x++){
			if(ant.getRulesArray()[x] != -1){
				double currentValue = pheromoneArray[x][ant.getRulesArray()[x]];
				pheromoneArray[x][ant.getRulesArray()[x]] = currentValue + currentValue*(ant).getRuleQuality();
			}
		}
		//normalize pheromone
		double sum=0;
		for(int x=0; x < pheromoneArray.length; x++){
			for(int y=0; y < pheromoneArray[x].length; y++){
				sum += pheromoneArray[x][y];
			}
		}
		for(int x=0; x < pheromoneArray.length; x++){
			for(int y=0; y < pheromoneArray[x].length; y++){
				pheromoneArray[x][y] /= sum;
			}
		}
	}
	
	/**
	 * Converts the rule from []int to a readable String
	 * @param rule
	 * @param ruleConsequent
	 * @return the rule in String format
	 */
	private String getRuleString(int [] rule, int ruleConsequent){
		String ruleStr;
		ruleStr = "IF "; 
		boolean first=false;
		for(int x=0; x < rule.length; x++){
			if(rule[x] != -1){
				if(!first)
					ruleStr += attributesArray[x].getAttributeName() + " = '" + attributesArray[x].getTypes()[rule[x]] + "' ";
				else
					ruleStr += "AND " + attributesArray[x].getAttributeName() + " = '" + attributesArray[x].getTypes()[rule[x]] + "' ";
				first=true;
			}
		}
		ruleStr += "THEN '" + attributesArray[attributesArray.length-1].getTypes()[ruleConsequent] + "'";
		return ruleStr;
	}
	
	private String getInstanceString(int [] instance){
		String instanceStr="";
		for(int x=0; x < instance.length; x++){
			if(instance[x] == -1)
				instanceStr += "?";
			else
				instanceStr += attributesArray[x].getTypes()[instance[x]];
			if(x < instance.length-1)
				instanceStr += ", ";
		}
		return instanceStr;
	}
	
	/**
	 * Calculates the size of the rule.
	 * @param rule
	 * @return
	 */
	private int ruleSize(int [] rule){
		int count=0;
		for(int x=0; x < rule.length; x++)
			if(rule[x] != -1)
				count++;
		return count;
	}
	
	/**
	 * Returns the total number of possible attributes values
	 * @return the total number of possible attributes values
	 */
	public int totalDistinct(){
		int count=0;
		for(int n=0; n < attributesArray.length; n++){
			count += attributesArray[n].getTypes().length;
		}
		return count;
	}
	
	/**
	 * @param d
	 * @return
	 */
	private double log2(double d) {
		return Math.log(d)/Math.log(2.0);
	}

	class InvalidArgumentException extends Exception {
		private static final long serialVersionUID = 1L;
		InvalidArgumentException() {
			super("At least one of the parameters is invalid.");
	    }
		InvalidArgumentException(String msg) {
	        super(msg);
	    }
	}

}