featureoperator.java

一个很好的LIBSVM的JAVA源码。对于要研究和改进SVM算法的学者。可以参考。来自数据挖掘工具YALE工具包。

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2001-2004
 *      Simon Fischer, Ralf Klinkenberg, Ingo Mierswa, 
 *          Katharina Morik, Oliver Ritthoff
 *      Artificial Intelligence Unit
 *      Computer Science Department
 *      University of Dortmund
 *      44221 Dortmund,  Germany
 *  email: [e-mail]
 *  web:   http://yale.cs.uni-dortmund.de/
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as 
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version. 
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 *  USA.
 */
package edu.udo.cs.yale.operator.features;

import edu.udo.cs.yale.example.Attribute;
import edu.udo.cs.yale.example.AttributeWeights;
import edu.udo.cs.yale.example.ExampleSet;
import edu.udo.cs.yale.example.WeightApplier;
import edu.udo.cs.yale.example.AttributeWeightedExampleSet;
import edu.udo.cs.yale.operator.parameter.*;
import edu.udo.cs.yale.operator.MissingIOObjectException;
import edu.udo.cs.yale.operator.Value;
import edu.udo.cs.yale.operator.OperatorException;
import edu.udo.cs.yale.operator.UserError;
import edu.udo.cs.yale.operator.OperatorChain;
import edu.udo.cs.yale.operator.Operator;
import edu.udo.cs.yale.operator.OperatorException;
import edu.udo.cs.yale.operator.IOObject;
import edu.udo.cs.yale.operator.IOContainer;
import edu.udo.cs.yale.operator.IODescription;
import edu.udo.cs.yale.operator.IllegalInputException;
import edu.udo.cs.yale.operator.performance.PerformanceVector;
import edu.udo.cs.yale.tools.LogService;
import edu.udo.cs.yale.tools.Tools;

import java.util.List;
import java.util.Iterator;

/** This class is the superclass of all feature selection and generation operators.
 *  It provides an easy to use plug-in interface for operators that modify populations.
 *  Subclasses just have to supply lists of <tt>PopulationOperators</tt> by overriding
 *  <tt>getPreEvalutaionPopulationOperators()</tt> and <tt>getPostEvalutaionPopulationOperators()</tt>
 *  during a loop which will terminate if <tt>solutionGoodEnough()</tt> returns true.
 *
 *  <h4>Values:</h4>
 *  <ul>
 *    <li><tt>generation</tt> number of the the current generation
 *    <li><tt>best</tt> all generations' best individual's performance
 *    <li><tt>performance</tt> this generstion's best individual's performance
 *  </ul>
 *
 *  <h4>Operator-Input</h4>
 *  <ol>
 *    <li><tt>ExampleSet</tt> the original example set
 *  </ol>
 *  <h4>Operator-Output</h4>
 *  <ol>
 *    <li><tt>ExampleSet</tt> the best example set
 *    <li><tt>PerformanceVector</tt> its performance
 *  </ol>
 *
 *  @author simon
 *  @version $Id: FeatureOperator.java,v 2.30 2004/08/27 11:57:36 ingomierswa Exp $ <br>
 */
public abstract class FeatureOperator extends OperatorChain {

    private static final Class[] OUTPUT_CLASSES = { ExampleSet.class, AttributeWeights.class, PerformanceVector.class };
    private static final Class[] INPUT_CLASSES = { ExampleSet.class };

    private Population population;
    private WeightApplier weightApplier;

    public FeatureOperator() {
	addValue(new Value("generation", "The number of the current generation.") {
		public double getValue() {
		    if (population == null) return 0;
		    return population.getGeneration();
		}
	    });
	addValue(new Value("performance", "The performance of the current generation (main criterion).") {
		public double getValue() {
		    if (population == null) return Double.NaN;
		    if (population.lastBest() == null) return Double.NaN;
		    PerformanceVector pv = (PerformanceVector)population.lastBest().getUserData("performance");
		    if (pv == null) return Double.NaN;
		    return pv.getMainCriterion().getValue();
		}
	    });
	addValue(new Value("best", "The performance of the best individual ever (main criterion).") {
		public double getValue() {
  		    if (population == null) return Double.NaN;
		    PerformanceVector pv = population.bestPerformance();
		    if (pv == null) return Double.NaN;
		    return pv.getMainCriterion().getValue();
		}
	    });
	addValue(new Value("average_length", "The average number of attributes.") {
		public double getValue() {
		    if (population == null) return Double.NaN;
		    else {
			double lengthSum = 0.0d;
			for (int i = 0; i < population.getNumberOfIndividuals(); i++)
			    lengthSum += population.get(i).getNumberOfUsedAttributes();
			return lengthSum / (double)population.getNumberOfIndividuals();
		    }
		}
	    });
	addValue(new Value("best_length", "The number of attributes of the best example set.") {
		public double getValue() {
		    if (population == null) return Double.NaN;
		    AttributeWeightedExampleSet eSet = population.bestEver();
		    if (eSet != null) return eSet.getNumberOfUsedAttributes();
		    else return Double.NaN;
		}
	    });
    }

    /** Create an initial population. The example set will be cloned
     *  before the method is invoked. Submethods should make a blockwise creation if the flag is set. */
    public abstract Population createInitialPopulation(ExampleSet es);

    /** Must return a list of <tt>PopulationOperator</tt>s. All operators
     *  are applied to the population in their order within the list before
     *  the population is evaluated. */
    public abstract List getPreEvaluationPopulationOperators();

    /** Must return a list of <tt>PopulationOperator</tt>s. All operators
     *  are applied to the population in their order within the list after
     *  the population is evaluated. */ 
    public abstract List getPostEvaluationPopulationOperators();

    /** Has to return true if the main loop can be stopped because
     *  a solution is concidered to be good enough according to
     *  some criterion. */
    public abstract boolean solutionGoodEnough(Population pop) throws OperatorException;

    public Class[] getOutputClasses() { return OUTPUT_CLASSES; }
    public Class[] getInputClasses() { return INPUT_CLASSES; }

    
    /** Returns true if and only if all inner operators accept their precessors' ouput
     *  as input. */
    public Class[] checkIO(Class[] input) throws IllegalInputException {
	Class[] innerOutput = getOperator(0).checkIO(input);
	if (!IODescription.containsClass(PerformanceVector.class, innerOutput)) {
	    throw new IllegalInputException(this, getOperator(0), PerformanceVector.class);
	}
	return OUTPUT_CLASSES;
    }


    /** Applies the feature operator:
     *  <ol>
     *    <li>create an initial population
     *    <li>evaluate the initial population
     *    <li>loop as long as solution is not good enough
     *    <ol>
     *      <li>apply all pre evaluation operators
     *      <li>evaluate the population
     *      <li>update the population's best individual
     *      <li>apply all post evaluation operators
     *    </ol>
     *    <li>return all generation's best individual
     *  </ol>
     */
    public IOObject[] apply() throws OperatorException {
	String weightApplierName = getParameterAsString("weight_applier");
	try {
	    weightApplier = (WeightApplier)Class.forName(weightApplierName).newInstance();
	} catch (Exception e) { throw new UserError(this, e, 904, new Object[] { getName(), e}); }
	
	ExampleSet es = (ExampleSet)getInput().getInput(ExampleSet.class);
	population = createInitialPopulation((ExampleSet)es.clone());
	LogService.logMessage(getName() + ": initial population has " + population.getNumberOfIndividuals() + " individuals.", 
			      LogService.OPERATOR);
	evaluate(population);
	population.updateEvaluation();
	inApplyLoop();

	while (!solutionGoodEnough(population)) {
	    if (isMaximumReached()) { break; }
	    population.nextGeneration();
	    //System.out.println("\n### NEXT GENERATION ###");
	    applyOpList(getPreEvaluationPopulationOperators(), population);

	    LogService.logMessage(Tools.ordinalNumber(population.getGeneration()) + " generation has " + 
				  population.getNumberOfIndividuals() + " individuals.", LogService.OPERATOR);
	    LogService.logMessage(getName() + ": evaluating "+ Tools.ordinalNumber(population.getGeneration()) + " population.", 
				  LogService.OPERATOR);

	    evaluate(population);
	    population.updateEvaluation();
	    inApplyLoop();
	    applyOpList(getPostEvaluationPopulationOperators(), population);
	}

	applyOpList(getPostEvaluationPopulationOperators(), population);

	// create result example set
	AttributeWeightedExampleSet weightedResultSet = population.bestEver();
	ExampleSet result = null;
	if (getParameterAsBoolean("apply_best_weights")) {
	    weightedResultSet.setWeightApplier(weightApplier);
	    result = weightedResultSet.createExampleSetFromWeights();
	} else {
	    result = (ExampleSet)es.clone();
	    for (int i = 0; i < weightedResultSet.getNumberOfAttributes(); i++) {
		if (!result.contains(weightedResultSet.getAttribute(i)))
		    result.addAttribute(weightedResultSet.getAttribute(i));
	    }
	}
	
	// create result weights
	AttributeWeights weights = new AttributeWeights();
 	for (int i = 0; i < result.getNumberOfAttributes(); i++) {
	    Attribute attribute = result.getAttribute(i);
	    double weight = 0.0d;
	    if (weightedResultSet.contains(attribute))
		weight = weightedResultSet.getWeight(attribute);
 	    weights.setWeight(attribute.getName(), weight);
	}
	
	return new IOObject[] { result, weights, population.bestPerformance() };
    }


    /** Applies all PopulationOperators in opList to the population. */
    void applyOpList(List opList, Population population) throws OperatorException {
	Iterator i = opList.listIterator();
	while (i.hasNext()) {
	    PopulationOperator op = (PopulationOperator)i.next();
	    if (op.performOperation(population.getGeneration())) {
		//System.out.println("Applying: " + op.getClass().getName() + " on pop with size " + population.getNumberOfIndividuals());
		try {
		    op.operate(population);
		    for (int k=0 ; k < population.getNumberOfIndividuals(); k++){
			if (population.get(k).getNumberOfUsedAttributes() <= 0) {
			    LogService.logMessage("Population operator " + op + 
						  " has produced an example set without attributes!" ,
						  LogService.ERROR);
			}
		    }
		} catch (Exception e) {
		    throw new UserError(this, e, 108, e.toString());
		}
	    }
	}
    }

    /** Evaluates all individuals in the population by applying the inner operators. */
    protected void evaluate(Population population) throws OperatorException {
	//System.out.println("Evaluation!");
	for (int i=0 ; i < population.getNumberOfIndividuals(); i++){
	    AttributeWeightedExampleSet individual = population.get(i);
	    evaluate(individual);
	}
    }

    protected void evaluate(AttributeWeightedExampleSet individual) throws OperatorException {
	individual.setWeightApplier(weightApplier);
	AttributeWeightedExampleSet clone = individual.createCleanExampleSet();
	Operator operatorChain = getOperator(0);
	IOObject[] operatorChainInput = new IOObject[] { clone };
	IOContainer innerResult = operatorChain.apply(getInput().append(operatorChainInput));
	
	if (getParameterAsBoolean("set_inner_weights")) { 
	    try {
		AttributeWeights weightVector = (AttributeWeights)innerResult.getInput(AttributeWeights.class);
		LogService.logMessage("Applying weights created by inner operator.",
				      LogService.STATUS);
		Iterator i = weightVector.getAttributeNames().iterator();
		while (i.hasNext()) {
		    String attName = (String)i.next();
		    individual.setWeight(individual.getAttribute(attName), weightVector.getWeight(attName));
		}
	    } catch (MissingIOObjectException e) {
		LogService.logMessage("No weights created by inner operator. Using weights from example set.",
				      LogService.STATUS);
	    }
	}

	// user data must be set after applying the weights (because weight setting clears all user data)
	PerformanceVector performanceVector = (PerformanceVector)innerResult.getInput(PerformanceVector.class);
	individual.setUserData("performance", performanceVector);
    }

    private boolean isMaximumReached() {
	AttributeWeightedExampleSet eSet = population.bestEver();
	if (eSet != null) {
	    PerformanceVector pv = (PerformanceVector)eSet.getUserData("performance");
	    if (pv == null) return false;
	    else return pv.getMainCriterion().getMaxFitness() == pv.getMainCriterion().getFitness();
	} else return false;
    }

    /** Returns the highest possible value for the maximum number of innner operators. */
    public int getMaxNumberOfInnerOperators() { return 1; }
    /** Returns 0 for the minimum number of innner operators. */
    public int getMinNumberOfInnerOperators() { return 1; }


    public int getNumberOfSteps() {
	return 1;
    }

    public List getParameterTypes() {
	List types = super.getParameterTypes();
	types.add(new ParameterTypeBoolean("apply_best_weights", 
					   "Determines if the attributes of the result example set should be selected or weighted or if the original example set should be returned.", 
					   true));
	types.add(new ParameterTypeBoolean("set_inner_weights",
					   "Determines if weights calculated during evaluation should be applied to the individuals.", 
					   true));
	types.add(new ParameterTypeStringCategory("weight_applier", 
						  "The fully qualified classname of the weight applier.", 
						  new String[] { "edu.udo.cs.yale.example.ScalingWeightApplier", 
								 "edu.udo.cs.yale.example.DummyWeightApplier"}, 
						  "edu.udo.cs.yale.example.ScalingWeightApplier"));
	return types;
    }
}