featureselectionoperator.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.features;

import edu.udo.cs.yale.example.ExampleSet;
import edu.udo.cs.yale.example.AttributeSelectionExampleSet;
import edu.udo.cs.yale.operator.parameter.*;
import edu.udo.cs.yale.operator.OperatorException;

import java.util.LinkedList;
import java.util.List;

/** This operator realizes the two deterministic greedy feature selection algorithms
 *  forward selection and backward elimination.
 *
 *  <h4>Forward Selection</h4>
 *  <ol>
 *    <li>Create an initial population with {@yale.math n} individuals where {@yale.math n}
 *        is the input example set's number of attributes. Each individual will use 
 *        exactly one of the features.</li>
 *    <li>Evaluate the attribute sets and select only the best {@yale.math k}.</li>
 *    <li>For each of the {@yale.math k} attribute sets do: 
 *        If there are {@yale.math j} unused attributes, make {@yale.math j} copies of the attribute set
 *        and add exactly one of the previously unused attributes to the attribute set.</li>
 *    <li>As long as the performance improves go to 2</li>
 *  </ol>
 *
 *  <h4>Backward Elimination</h4>
 *  <ol>
 *    <li>Start with an attribute set which has all features switched on.</li>
 *    <li>Evaluate all attribute sets and select the best {@yale.math k}.</li>
 *    <li>For each of the {@yale.math k} attribute sets do: 
 *        If there are {@yale.math j} attributes used, make {@yale.math j} copies of the attribute set
 *        and remove exactly one of the previously used attributes from the attribute set.</li>
 *    <li>As long as the performance improves go to 2</li>
 *  </ol>
 *
 *  The parameter {@yale.math k} can be specified by the parameter <code>keep_best</code>.
 *
 *  @yale.xmlclass FeatureSelection
 *  @author simon
 *  @version $Id: FeatureSelectionOperator.java,v 2.7 2003/08/23 18:55:49 mierswa Exp $
 */
public class FeatureSelectionOperator extends FeatureOperator {

    public static final int FORWARD_SELECTION    = 0;
    public static final int BACKWARD_ELIMINATION = 1;
    private static final String[] DIRECTIONS = { "forward", "backward" };

    private List preOp, postOp;
    private int direction;
    private int generationsWOImp;

    public void initApply() throws OperatorException {
	super.initApply();

	direction            = getParameterAsInt("selection_direction");
	int keepBest         = getParameterAsInt("keep_best");
	generationsWOImp     = getParameterAsInt("generations_without_improval");

	preOp = new LinkedList();
	preOp.add(new KeepBest(keepBest));
	if (direction == FORWARD_SELECTION) {
	    preOp.add(new ForwardSelection());
	} else {
	    preOp.add(new BackwardElimination());
	}
	preOp.add(new RedundanceRemoval());

	postOp = new LinkedList();
    }

    int getDefaultDirection() {
	return BACKWARD_ELIMINATION;
    }

    /** May <tt>es</tt> have <i>n</i> features. 
     *  The initial population contains (depending on wether forward 
     *  selection or backward elimination is used) either
     *  <ul>
     *    <li><i>n</i> elements with exactly 1 feature switched on or
     *    <li>1 element with all <i>n</i> features switched on.
     *  </ul> */
    public Population createInitialPopulation(ExampleSet es) {
	Population initP = new Population();
	if (direction == FORWARD_SELECTION) {
	    AttributeSelectionExampleSet nes = new AttributeSelectionExampleSet((ExampleSet)es.clone());
	    for (int i = 0; i < es.getNumberOfAttributes(); i++)
		nes.setAttributeUsed(i, false);
	    for (int i = 0; i < es.getNumberOfAttributes(); i++) {
		AttributeSelectionExampleSet forwardES = (AttributeSelectionExampleSet)nes.clone();
		forwardES.setAttributeUsed(i, true);
		initP.add(forwardES);
	    }
	} else {
	    AttributeSelectionExampleSet nes = new AttributeSelectionExampleSet((ExampleSet)es.clone());
	    for (int i = 0; i < nes.getNumberOfAttributes(); i++)
		nes.setAttributeUsed(i, true);
	    initP.add(nes);	 
	}
	return initP;
    }

    /** The operators performs two steps:
     *  <ol>
     *    <li>forward selection/backward elimination
     *    <li>kick out all but the <tt>keep_best</tt> individuals
     *    <li>remove redundant individuals
     *  </ol>  
     */
    public List getPreEvaluationPopulationOperators() {
	return preOp;
    }

    /** empty list */
    public List getPostEvaluationPopulationOperators() {
	return postOp;
    }

    /** Returns true if the best individual is not better than  
     *  the last generation's best individual. */
    public boolean solutionGoodEnough(Population pop) throws OperatorException {
	boolean stop = pop.empty() || (pop.getGenerationsWithoutImproval() >= generationsWOImp);
	return stop;
    }



    public List getParameterTypes() {
	List types = super.getParameterTypes();
	types.add(new ParameterTypeCategory("selection_direction", "Forward selection or backward elimination.", DIRECTIONS, getDefaultDirection()));
	types.add(new ParameterTypeInt("keep_best", "Keep the best n individuals in each generation.", 1, Integer.MAX_VALUE, 1));
	types.add(new ParameterTypeInt("generations_without_improval", "Stop after n generations without improval of the performance.", 1, Integer.MAX_VALUE, 1));
	return types;
    }
}