equivalentattributeremoval.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.AttributeWeightedExampleSet;
import edu.udo.cs.yale.example.Attribute;
import edu.udo.cs.yale.example.AttributeWeights;
import edu.udo.cs.yale.example.AttributeParser;
import edu.udo.cs.yale.example.DataRow;
import edu.udo.cs.yale.example.DataRowReader;
import edu.udo.cs.yale.example.Example;
import edu.udo.cs.yale.example.ExampleSet;
import edu.udo.cs.yale.example.ExampleTable;
import edu.udo.cs.yale.example.SimpleExampleSet;
import edu.udo.cs.yale.example.MemoryExampleTable;
import edu.udo.cs.yale.example.ExampleReader;
import edu.udo.cs.yale.example.Tools;
import edu.udo.cs.yale.tools.LogService;
import edu.udo.cs.yale.tools.RandomGenerator;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

/** If the example set contain two equivalent attributes, the longer representation is removed. The length is 
 *  calculated as the number of nested brackets. The equivalency probe is not done by structural comparison. 
 *  The attribute values of the equations in question are randomly sampled and the equation results compared. 
 *  If the difference is less than <i>epsilon</i> for <i>k</i> trials, the equations are probably equivalent. 
 *  At least they produce similar values. <br/>
 * 
 *  The values of the attributes are sampled in the range of the minimum and maximum values of the attribute. 
 *  This ensures equivalency or at least very similar values for the definition range in question. 
 *  Therefore a {@link MemoryExampleTable} is constructed and filled with random values. Then a 
 *  {@link AttributeParser} is used to construct the attributes values.
 *
 *  @version $Id: EquivalentAttributeRemoval.java,v 2.8 2004/08/27 11:57:36 ingomierswa Exp $
 */
public class EquivalentAttributeRemoval extends IndividualOperator {

    /** Indicates the number of examples which should be randomly generated to check equivalency. */
    private int numberOfSamples = 5;
    /** If the difference is smaller than epsilon, the attributes are checked as equivalent. */
    private double epsilon = 0.05d;

    /** Creates a new equivalent attribute removal population operator. */
    public EquivalentAttributeRemoval(int numberOfSamples, double epsilon) {
	this.numberOfSamples = numberOfSamples;
	this.epsilon = epsilon;
    }

    public List operate(AttributeWeightedExampleSet exampleSet) throws Exception {
 	Attribute[] allAttributes = exampleSet.getExampleTable().getAttributes();
 	List simpleAttributesList = new ArrayList();
 	for (int i = 0; i < allAttributes.length; i++) {
 	    if ((allAttributes[i] != null) && (!allAttributes[i].isGenerated()))
		simpleAttributesList.add(allAttributes[i]);
 	}

	Map removeMap = new HashMap();
	for (int i = 0; i < exampleSet.getNumberOfAttributes(); i++) {
	    for (int j = i+1; j < exampleSet.getNumberOfAttributes(); j++) {
		Attribute att1 = exampleSet.getAttribute(i);
		Attribute att2 = exampleSet.getAttribute(j);
		if (att1.equals(att2)) {
		    //System.out.println("### EQUALS: Example set contains equally constructed attributes:\n" + att1 + ",\n" + att2);
		    removeMap.put(att2.getName(), att2);
		} else {
		    ExampleTable exampleTable = new MemoryExampleTable(simpleAttributesList, numberOfSamples);
		    // create parser
		    AttributeParser parser = new AttributeParser(exampleTable);		
		    parser.parse(att1.getConstructionDescription(false));
		    parser.parse(att2.getConstructionDescription(false));
		    
		    // create data set and attributes to check 
		    Tools.fillTableWithRandomValues(exampleTable);
		    ExampleSet randomSet = new SimpleExampleSet(exampleTable, new LinkedList());
		    parser.generateAll(randomSet);
		    // add longer attribute to remove map if equivalent
		    if (equivalent(randomSet)) {
			//System.out.println("Equivalent!");
			int depth1 = att1.getConstructionDepth();
			int depth2 = att2.getConstructionDepth();
			// System.out.println(att1.getName() + ":=" + att1.getConstructionDescription() + 
// 					   " has depth " + depth1 + ", " + 
// 					   att2.getName() + ":=" + att2.getConstructionDescription() + 
// 					   " has depth " + depth2);
			if (depth1 > depth2) removeMap.put(att1.getName(), att1);
			else removeMap.put(att2.getName(), att2);
		    }
		}
	    }
	}

 	Iterator i = removeMap.values().iterator();
 	while (i.hasNext()) {
	    Attribute attribute = (Attribute)i.next();
	    LogService.logMessage("Remove equivalent attribute '" + attribute.getName() + "'.", LogService.STATUS);
 	    exampleSet.removeAttribute(attribute);
 	}

	List l = new LinkedList();
	l.add(exampleSet);
	return l;
    }

    private boolean equivalent(ExampleSet exampleSet) {
	if (exampleSet.getNumberOfAttributes() < 2) {
	    return true;
	} else {
	    ExampleReader reader = exampleSet.getExampleReader();
	    Attribute a1 = exampleSet.getAttribute(0);
	    Attribute a2 = exampleSet.getAttribute(1);
	    if (a1.equals(a2)) return true;
	    while (reader.hasNext()) {
		Example example = reader.next();
		if (Math.abs(example.getValue(a1) - example.getValue(a2)) > epsilon) return false;
	    }
	    return true;
	}
    }
}