directedgeneratingmutation.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.ga;

import edu.udo.cs.yale.generator.FeatureGenerator;
import edu.udo.cs.yale.generator.GenerationException;
import edu.udo.cs.yale.operator.features.IndividualOperator;
import edu.udo.cs.yale.operator.OperatorException;
import edu.udo.cs.yale.example.AttributeWeightedExampleSet;
import edu.udo.cs.yale.example.Attribute;
import edu.udo.cs.yale.example.AttributeWeights;
import edu.udo.cs.yale.example.Tools;
import edu.udo.cs.yale.tools.RandomGenerator;
import edu.udo.cs.yale.tools.LogService;

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

/** The mutation operator for directed GGAs. This operator adds single attributes from the original set, 
 *  creates new ones and deselect single attributes. The number of attributes remains until longer or
 *  shorter example sets have proven to perform better.
 *
 *  @version $Id: DirectedGeneratingMutation.java,v 2.10 2004/08/27 11:57:36 ingomierswa Exp $
 *  @see DirectedGGA */
public class DirectedGeneratingMutation extends IndividualOperator {

    private List generators;
    private Attribute[] originalAttributes;
    private double p;
    private int maxGeneratedAttributes = 2;
    private int maxAddedOriginalAttributes = 2;
    private int maxDepth = -1;
    private String[] unusableFunctions = new String[0];

    private RandomGenerator random = RandomGenerator.getGlobalRandomGenerator();

    public DirectedGeneratingMutation(Attribute[] originalAttributes, 
				      double p, 
				      List generators,
				      int maxGeneratedAttributes,
				      int maxAddedOriginalAttributes,
				      int maxDepth,
				      String[] unusableFunctions) {
	this.originalAttributes = originalAttributes;
	this.p = p/(double)(maxGeneratedAttributes+maxAddedOriginalAttributes);
	this.generators = generators;
	this.maxGeneratedAttributes = maxGeneratedAttributes;
	this.maxAddedOriginalAttributes = maxAddedOriginalAttributes;
	this.maxDepth = maxDepth;
	this.unusableFunctions = unusableFunctions;
    }

    /** Performs one of the following three mutations:
     *  <ul>
     *    <li>add a newly generated attribute</li>
     *    <li>add an original attribute</li>
     *    <li>remove an attribute</li>
     *  </ul> */
    public List operate(AttributeWeightedExampleSet exampleSet) throws Exception {
	LinkedList l = new LinkedList();
	AttributeWeightedExampleSet clone = (AttributeWeightedExampleSet)exampleSet.clone();
	
	//System.out.println("\n### NEW EXAMPLE SET ###");
	//System.out.println("ExampleSet:\n" + clone + "\n");

	try {
	    addOriginalAttribute(clone);
	    addGeneratedAttribute(clone);
	    deselect(clone, maxGeneratedAttributes + maxAddedOriginalAttributes);

	    if (clone.getNumberOfUsedAttributes() > 0) {
		Iterator i = exampleSet.getUserDataKeys().iterator();
		while (i.hasNext()) {
		    String key = (String)i.next();
		    clone.setUserData(key, exampleSet.getUserData(key));
		}
		l.add(clone);
	    } else {
		l.add(exampleSet);
	    }
	} catch (GenerationException e) {
	    LogService.logMessage("DirectedGGA: Exception occured during generation of attributes, using original example set instead.", LogService.WARNING);
	    l.add(exampleSet);
	}
	return l;
    }

    private void addGeneratedAttribute(AttributeWeightedExampleSet exampleSet) throws GenerationException {
	for (int i = 0; i < maxGeneratedAttributes; i++) {
	    if (random.nextDouble() < p) {
		FeatureGenerator generator = FeatureGenerator.selectGenerator(exampleSet, generators, maxDepth, unusableFunctions);
		if (generator != null) {
		    generator = generator.newInstance();
		    Attribute[] args = Tools.getWeightedCompatibleAttributes(exampleSet, generator, maxDepth, unusableFunctions);
		    generator.setArguments(args);
		
		    List generatorList = new LinkedList();
		    generatorList.add(generator);
		    List result = FeatureGenerator.generateAll(exampleSet.getExampleTable(), generatorList);
		    double weightSum = 0.0d;
		    for (int j = 0; j < args.length; j++) weightSum += exampleSet.getWeight(args[j]);
		    weightSum /= args.length;
		    exampleSet.addAllAttributes(result);
		    Iterator a = result.iterator();
		    while (a.hasNext()) {
			Attribute att = (Attribute)a.next();
			exampleSet.setWeight(att, weightSum);
		    }
		    //System.out.println("GENERATE NEW ATTRIBUTES: " + generator.getFunction() + " with weight " + weightSum + " --> " + result);
		}
	    }
	}
    }

    private void addOriginalAttribute(AttributeWeightedExampleSet exampleSet) {
	for (int j = 0; j < maxAddedOriginalAttributes; j++) {
	    if (random.nextDouble() < p) {
		Attribute originalAttribute = originalAttributes[random.nextInt(originalAttributes.length)];
		double avgWeight = Tools.getAverageWeight(exampleSet);
		//System.out.println("ADD ORIGINAL: " + originalAttribute.getName() + " with weight " + avgWeight);
		if (!exampleSet.contains(originalAttribute)) {
		    exampleSet.addAttribute(originalAttribute);
		    exampleSet.setWeight(originalAttribute, avgWeight);
		}
	    }
	}
    }
 
    private void deselect(AttributeWeightedExampleSet exampleSet, int numberNew) {
	int n = exampleSet.getNumberOfAttributes();
	double[] probs = Tools.getInverseProbabilitiesFromWeights(Tools.createAttributeArray(exampleSet), exampleSet);
	for (int i = n-1; i >= 0; i--) {
	    if (random.nextDouble() < p*probs[i]*numberNew) {
		//if (random.nextDouble() < p*numberNew / n) {
		//System.out.println("REMOVE ATTRIBUTE: " + exampleSet.getAttribute(i).getName());
		exampleSet.removeAttribute(i);
	    }
	}
	// prob sum must 1/4 of new
	//System.out.println("new: " + numberNew + ", delete prob sum: " + probSum);
    }
}