attributeinformationgain.java

著名的开源仿真软件yale

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2002, 2003
 *      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;

import edu.udo.cs.yale.operator.parameter.*;
import edu.udo.cs.yale.tools.LogService;
import edu.udo.cs.yale.tools.Ontology;
import edu.udo.cs.yale.example.ExampleSet;
import edu.udo.cs.yale.example.Example;
import edu.udo.cs.yale.example.ExampleReader;
import edu.udo.cs.yale.example.Tools;
import edu.udo.cs.yale.operator.learner.Model;
import edu.udo.cs.yale.operator.learner.ID3Learner;

import java.util.List;

/** Depending on the type of problem (classification or regression) it is more or less easy to 
 *  determine the information gain of each attribute. For classification tasks the well known 
 *  information gain methods derived from C4.5 (Quinlan) are used. For regression a new approach is used - 
 *  the regression information gain.
 *  <br/>
 *  Different from classification information gain entropies of subclasses can not be calculated since 
 *  there are no subclasses. The algorithm works as follows: 
 *  <ol>
 *  <li>First with the aid of a regression learner (e.g. mySVM) a model is learned from the complete example set.</li>
 *  <li>Then all examples are iterated and each attribute is varied relatively by <var>epsilon</var> both up
 *      and down.</li>
 *  <li>Now the labels can be predicted for all examples and errors to the real label (or another prediction
 *      without any variation) can be calculated. The mean value for both the variations are calculated.</li>
 *  <li>At last the mean value for each attribute is calculated. Each attribute gets this mean error as
 *      information value.</li>
 *  </ol>
 *  The greater the error achieved by the variation the more relevant it is that the attribute has exactly
 *  its values. The value of this attribute is important, also is the attribute itself.
 *  <h5>Example:</h5>
 *  Take a look at the very simple example with the attributes {@yale.math x}, {@yale.math y}, and {@yale.math z} and the true
 *  (unknown) function 
 *  {@yale.math f(x,y,z) = 2x + 0.0000001y - z}<br/>
 *  Variations of {@yale.math x} or {@yale.math z} should have much greater influence on the error than a variation of 
 *  {@yale.math y} and therefore it is probable that values of {@yale.math x} and {@yale.math z} are more informative for the
 *  function.
 *
 *  @yale.xmlclass InformationGain
 *  @author ingo
 *  @version $Id: AttributeInformationGain.java,v 2.6 2003/07/09 15:19:57 fischer Exp $
 */
public class AttributeInformationGain extends OperatorChain {

    public static final String INFORMATION_GAIN_KEY          = "attribute.information.gain";
    public static final String SMALLEST_INFORMATION_GAIN_KEY = "attribute.information.gain.smallest";

    private static final Class[] INPUT_CLASSES = {ExampleSet.class};

    public IOObject[] apply() throws OperatorException {

  	ExampleSet eSet = (ExampleSet)getInput(ExampleSet.class, false);

	double[] informationGain = new double[eSet.getNumberOfAttributes()];

	if (Ontology.ATTRIBUTE_VALUE_TYPE.isA(eSet.getLabel().getValueType(), Ontology.NOMINAL)) { 

	    // RatioGain gibt an, ob bei Klassifikationsproblemen ratio gain benutzt werden soll.
	    boolean ratioGain = getParameterAsBoolean("use_ratio_gain");
	    
	    informationGain = Tools.getInformationGain(eSet, ratioGain);
	    
	} else if (Ontology.ATTRIBUTE_VALUE_TYPE.isA(eSet.getLabel().getValueType(), Ontology.NUMERICAL)) {
	    
	    // inner operators
	    if (getNumberOfOperators() != 2) 
		throw new FatalException("InformationGain needs two inner operators for applying regression information gain: a learner and  a model applier.");

	    // Epsilon gibt den Variationsbereich fuer RegressionInformationGain an (in Prozent). Werte zwischen 0.1% 
	    // und 1% haben sich im allgemeinen als ganz gut herausgestellt.
	    double epsilon = getParameterAsDouble("epsilon");

	    // Gibt an ob das wahre Label beim RegressionsInformationGain oder das vorhergesagte benutzt werden soll. 
	    //  Default ist das wahre Label
	    boolean usePredictedLabel = getParameterAsBoolean("use_predicted_label");

	    // get information gain
	    informationGain = getRegressionInformationGain(eSet, epsilon, usePredictedLabel, getLearner(), getApplier());

	} else informationGain = handleProblem(eSet);

	normalize(informationGain);


	// Setzen der Infolabel fuer die Attribute.
	double smallestInformationGainValue = Double.POSITIVE_INFINITY;
	for (int i = 0 ; i < eSet.getNumberOfAttributes(); i++) {
	    if (informationGain[i] < smallestInformationGainValue) 
		smallestInformationGainValue = informationGain[i];
	    //eSet.setInformationGain(i, informationGain[i]);
	    //eSet.setUserData(INFORMATION_GAIN_KEY+"["+i+"]", informationGain[i]);
	    //eSet.setInformationGain(i, informationGain[i]);
	}

	eSet.setUserData(INFORMATION_GAIN_KEY, informationGain);
	eSet.setUserData(SMALLEST_INFORMATION_GAIN_KEY, new Double(smallestInformationGainValue));
	//eSet.setSmallestInformationGain(smallestInformationGainValue);
	
	return new IOObject[0];
    }
    

    // ================================================================================

    /** Diese Methode &uuml;bernimmt die weiter oben vorgestellte Methode des Regression Information Gain zur Findung informativer
     *  Attribute bei Regressionsproblemen.
     */
    public static double[] getRegressionInformationGain(ExampleSet eSet, double epsilon, boolean usePredictedLabel, 
							Operator learner, Operator applier) throws OperatorException {

	// initialisierung
	double[] infoGain = new double[eSet.getNumberOfAttributes()];
	double[] labels = new double[eSet.getSize()];
	ExampleReader reader;
	int k;
	IOContainer modelContainer = null;
	Model model = null;
	ExampleSet learnSet = (ExampleSet)eSet.clone();
	//learnSet.setAllAttributesUsed();

	// learn a model
	try {
	    modelContainer = learn(learnSet, learner);
	    model = (Model)modelContainer.getInput(Model.class);

	    if (usePredictedLabel) {

		applyModel(learnSet, applier, model);
		reader = learnSet.getExampleReader();
		k = 0;
		while (reader.hasNext()) 
		    labels[k++] = ((Example)reader.next()).getPredictedLabel();
		//modelContainer = new IOContainer(modelContainer.appendUnused(new IOObject[] { model }));

	    } else {

		reader = learnSet.getExampleReader();
		k = 0;
		while (reader.hasNext()) 
		    labels[k++] = ((Example)reader.next()).getLabel();

	    }
	} catch (OperatorException e) {
	    LogService.logException("InformationGain: Exception occurred during learning a model.", e);
	}


	// fuer jedes Attribut mache:
	for (int i = 0 ; i < learnSet.getNumberOfAttributes(); i++) {

	    // retten der alten Werte
	    double[] oldValues = new double[learnSet.getSize()];
	    reader = learnSet.getExampleReader();
	    k = 0;
	    while (reader.hasNext()) 
		oldValues[k++] = ((Example)reader.next()).getValue(i);
	    
	    // einmal nach oben und einmal nach unten variieren
	    double fault = 0;
	    for (int op = 0; op < 2; op++) {

		// alle Beispiele durchgehen
		reader = learnSet.getExampleReader();
		k = 0;
		while (reader.hasNext()) {
		    double newValue = op == 0 ? 
			oldValues[k] - (oldValues[k] * epsilon) :
			oldValues[k] + (oldValues[k] * epsilon);
		    k++;
		    ((Example)reader.next()).setValue(i, newValue);
		}

		IOContainer predictedContainer = null;
		// applier aufrufen
		try {
		    //modelContainer = new IOContainer(modelContainer.appendUnused(new IOObject[] { model }));
		    predictedContainer = applyModel(learnSet, applier, model);
		} catch (OperatorException e) {
		    LogService.logException("InformationGain: Exception occurred during learning a model.", e);
		}

		// Berechnung des Fehlers
		ExampleSet predictedSet = null;
		predictedSet = (ExampleSet)predictedContainer.getInput(ExampleSet.class);

		reader = predictedSet.getExampleReader();
		k = 0;
		while (reader.hasNext()) 
		    fault += Math.abs(labels[k++] - ((Example)reader.next()).getPredictedLabel());
	    }

	    // der Mittelwert ueber alle Beispiele wird dann der RegressionInformationGain - Wert.
	    // Die 2 kommt von den beiden Variationen (oben und unten).
	    infoGain[i] = fault / (2 * learnSet.getSize());
    
	}

	return infoGain;
    }

    // ================================================================================


    /** Wendet den Learner an. 
     */
    private static IOContainer learn(ExampleSet eSet, Operator learner) throws OperatorException {
	//return learner.apply(new IOContainer(input.appendUnused(new IOObject[] { eSet })));
	return learner.apply(new IOContainer(new IOObject[] { eSet }));
    }

    /** Wendet den ModelApplier an.
     */
    private static IOContainer applyModel(ExampleSet eSet, Operator applier, Model model) throws OperatorException {
	return applier.apply(new IOContainer(new IOObject[] { eSet, model }));
    }

    /** Liefert den Lerner zur&uuml;ck.
     */
    private Operator getLearner() { return getOperator(0); }

    /** Liefert den ModelApplier zur&uuml;ck.
     */
    private Operator getApplier() { return getOperator(1); }


    // ================================================================================

    /** Diese Methode uebernimmt das Normieren der Werte auf einen Bereich zwischen 0 und 1. Das informativste Attribut 
     *  bekommt dabei uebrigens den Wert 1 zugewiesen, alle anderen sind Bruchteile dieses Wertes.
     */
    public static void normalize(double[] infoGain) {
	double best = Double.NEGATIVE_INFINITY;
	for (int i = 0; i < infoGain.length; i++) 
	    if (infoGain[i] > best) best = infoGain[i];

	for (int i = 0; i < infoGain.length; i++)
	    infoGain[i] /= best;
    }


    /** Sollte nicht angegeben worden sein, um welche Art von Problem es sich handelt und es auch nicht automatisch 
     *  erkannt werden koennen bzw. die Angabe falsch sein, so wird der Informationsgewinn f&uuml;r jedes Attribut auf den 
     *  gleichen Wert gesetzt.
     */
    public static double[] handleProblem(ExampleSet eSet) {
	LogService.logMessage("InformationGain: Can not identify if the problem is a classification or regression problem. Use same information gain label for all attributes!", LogService.WARNING);

	// 1 / # Attribute wird info gain label fuer alle Attribute.
	
	double[] infoGain = new double[eSet.getNumberOfAttributes()];
	for (int i = 0; i < infoGain.length; i++) infoGain[i] = 1 / eSet.getNumberOfAttributes();
	
	return infoGain;
    }

    /** Der erste Operator muss ein Modell zur&uuml;ckliefern und der zweite Operator ein ExampleSet mit predicted labels. 
     */
    public Class[] checkIO(Class[] input) throws IllegalInputException {
	Operator learner   = getLearner();
	Operator evaluator = getApplier();
	input = learner.checkIO(input);
	if (!IODescription.containsClass(Model.class, input))
	    throw new IllegalInputException(getName() + ": " + learner.getName() + " doesn't provide model", this);

	// GUT?
	Class[] newInput = new Class[input.length+1];
	for (int i = 0; i < input.length; i++) {
	    newInput[i] = input[i];
	}
	newInput[newInput.length-1] = ExampleSet.class;
	input = evaluator.checkIO(newInput);
	// ???
	if (!IODescription.containsClass(ExampleSet.class, input))
	    throw new IllegalInputException(getName() + ": " + evaluator.getName() + " doesn't provide example set", this);

	return input;
    }

    public Class[] getOutputClasses() {
	return new Class[0];
    }

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

    public List getParameterTypes() {
	List types = super.getParameterTypes();
	types.add(new ParameterTypeBoolean("use_ratio_gain", "If set to true the ratio gain criterion is used.", true));
	types.add(new ParameterTypeDouble("epsilon", "Variation range of attribute values for the attribute information gain.", 0, 1, 0.1));
	types.add(new ParameterTypeBoolean("use_predicted_label", "if set to true, the predicted label is used for the attribute information gain.", true));
	return types;
    }

    /** Returns the maximum number of innner operators. */
    public int getMaxNumberOfInnerOperators() { return 2; }
    /** Returns the minimum number of innner operators. */
    public int getMinNumberOfInnerOperators() { return 0; }

    public int getNumberOfSteps() {
	return 1;
    }

}