upgma.java

著名的开源仿真软件yale

package edu.udo.cs.yale.operator.clusterer.upgma;

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

import java.awt.Component;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Iterator;

/** This operator generates a tree each node of which represents a cluster. UPGMA
 *  stands for Unweighted Pair Group Method using Arithmetic Means. Since the way 
 *  cluster distances are calculated can be specified using parameters, this name is 
 *  slightly misleading. Unfortunately, the name of the algorithm changes depending on 
 *  the parameters used.
 *  <br/>
 *  Starting with initial clusters of size 1, the algorithm unites two clusters with
 *  minimal distance forming a new tree node. This is iterated until there is only one
 *  cluster left which forms the root of the tree.
 *  <br/>
 *  This operator does not generate a special cluster attribute and does not modify
 *  the input example set at all, since it generates too many clusters. The tree
 *  generated by this cluster is considered the interesting result of the algorithm.
 *
 *  @yale.xmlclass 
 *  @version $Id: UPGMA.java,v 1.3 2003/08/14 10:24:57 fischer Exp $
 */
public class UPGMA extends Operator {

    public IOObject[] apply() throws OperatorException {
	ClusterDistanceMeasure clusterDistanceMeasure =
	    DistanceMeasure.createClusterDistanceMeasure(getParameterAsInt("cluster_distance_measure"));
	DistanceMatrix distanceMatrix = DistanceMeasure.createDistanceMeasure(getParameterAsInt("distance_measure")).calculateDistanceMatrix((ExampleSet)getInput(ExampleSet.class));
	List clusters = new ArrayList();

	for (int i = 0; i < distanceMatrix.getDimension(); i++) {
	    double[] distances = new double[distanceMatrix.getDimension()];
	    for (int j = 0; j < distanceMatrix.getDimension(); j++) {
		distances[j] = distanceMatrix.getDistance(i, j);
	    }
	    clusters.add(new Cluster(distanceMatrix.getName(i), distances, i));
	}

	while (clusters.size() > 1) {

	    // find two clusters i,j with minimal distance d, j > i
	    Cluster clusterI = null;
	    Cluster clusterJ = null;
	    double d = Double.POSITIVE_INFINITY;
	    for (int i = 0; i < clusters.size(); i++) {
		Cluster tempI = (Cluster)clusters.get(i);
		for (int j = 0; j < i; j++) {
		    Cluster tempJ = (Cluster)clusters.get(j);
		    double distance = tempI.getDistance(tempJ.getIndex());
		    if (distance < d) {
			d = distance;
			clusterI = tempI;
			clusterJ = tempJ;
		    }
		}
	    }

	    Tree t1 = clusterI.getTree();
	    double h1 = t1.getHeight();
	    Tree t2 = clusterJ.getTree();
	    double h2 = t2.getHeight();
	    Tree newTree = new Tree(""+((double)(Math.round(d/2*100))/100), 
				    t1, d/2-h1,
				    t2, d/2-h2);
	    newTree.setHeight(d/2);
	    clusterI.setTree(newTree);
	    clusters.remove(clusterJ);

	    // recalculate the distances
	    Iterator l = clusters.iterator();
	    while (l.hasNext()) {
		Cluster clusterL = (Cluster)l.next();
		if (clusterI.getIndex() != clusterL.getIndex()) {
		    double newDistance = 
			clusterDistanceMeasure.calculateUnionDistance(clusterI.getDistance(clusterL.getIndex()),
								      clusterJ.getDistance(clusterL.getIndex()),
								      clusterI,
								      clusterJ,
								      clusterL);
		    clusterL.setDistance(clusterI.getIndex(), newDistance);
		    clusterI.setDistance(clusterL.getIndex(), newDistance);
		} else {
		    clusterI.setDistance(clusterL.getIndex(), Double.POSITIVE_INFINITY);
		}
	    }
	    clusterI.union(clusterJ);
	}

	return new IOObject[] { ((Cluster)clusters.get(0)).getTree() };
    }

    public Class[] getInputClasses() { return new Class[] { ExampleSet.class }; }
    public Class[] getOutputClasses() { return new Class[0]; }


    public List getParameterTypes() {
	List types = super.getParameterTypes();

	types.add(new ParameterTypeCategory("distance_measure", "Specifies the way the distance of two examples is calculated.", DistanceMeasure.TYPE_NAMES, DistanceMeasure.TYPE_EUKLIDIAN));
	types.add(new ParameterTypeCategory("cluster_distance_measure", "Specifies the way the distance of two clusters is calculated.", DistanceMeasure.CLUSTER_TYPE_NAMES, DistanceMeasure.TYPE_AVERAGE));
	return types;
    }

}