User:Chase-san/KohonenMap

This is my implementation of a Self-organizing map. It is untested, but it should work just fine.

This and all my other code in which I display on the robowiki falls under the ZLIB License.

org.csdgn.nn.KohonenMap

package org.csdgn.nn;

import java.util.Random;

/**
 * A Self-Organizing Map implementation.
 * 
 * Requires: <br>
 * org.csdgn.nn.DensityFunction<br>
 * org.csdgn.nn.DistanceFunction<br>
 * org.csdgn.nn.density.StandardDensity<br>
 * org.csdgn.nn.distance.EulerDistanceSquared
 * 
 * TODO: Optimize for speed.
 * 
 * @author Chase
 * 
 */
public class KohonenMap {
	

	/**
	 * Holds the neighborhood layout;
	 */
	private final Node[] map;
	private final int[] mapSize;
	private double learningRate = 0.8;
	private Density density;
	private Distance distance;
	private boolean wrap = false;
	private int BMU;
	
	private double cutoff = 1e-4;

	/**
	 * @param mapSize
	 *            Size of the neighborhood. Example: {10,10} produces a 2
	 *            dimensional map, each dimension having 10 nodes. Total nodes
	 *            would be 100.
	 * @param input
	 *            The length of the input vector (1D only)
	 * @param output
	 *            The length of the output vector (1D only)
	 */
	public KohonenMap(int[] mapSize, int input, int output) {
		/* Setup the map */
		int size = 1;
		for (int m : mapSize)
			size *= m;
		
		this.map = new Node[size];

		this.mapSize = mapSize.clone();

		this.density = new Density.Simple();
		this.distance = new Distance.EulerSq();

		int[] pos = new int[mapSize.length];
		for (int i = 0; i < map.length; ++i) {
			this.map[i] = new Node(mapSize.length, input, output);
			/* Setup the location of each node, for speed reasons. */
			System.arraycopy(pos, 0, this.map[i].position, 0, pos.length);

			/* Update the position marker */
			++pos[0];
			for (int j = 0; j < pos.length - 1; ++j) {
				if (pos[j] >= mapSize[j]) {
					++pos[j + 1];
					pos[j] = 0;
				}
			}
		}
	}

	/**
	 * Initializes the map to random values
	 */
	public final void initialize() {
		Random r = new Random();
		initialize(r);
	}

	/**
	 * Initializes the map with the given random function. Uses the nextDouble
	 * function.
	 */
	public final void initialize(Random random) {
		for (Node n : map) {
			for (int i = 0; i < n.input.length; ++i)
				n.input[i] = random.nextDouble();
			for (int i = 0; i < n.output.length; ++i)
				n.output[i] = random.nextDouble();
		}
	}

	/**
	 * Finds the Best Matching Unit for the given input.
	 * 
	 * @return the BMUs identifier
	 */
	public final int findInputBMU(double[] input) {
		BMU = 0;

		double distance = Double.MAX_VALUE;
		for (int i = 0; i < map.length; ++i) {
			double dist = this.distance.distance(map[i].input, input);

			if (dist < distance) {
				distance = dist;
				BMU = i;
			}
		}
		return BMU;
	}

	/**
	 * Finds the Best Matching Unit for the given output.
	 * 
	 * @return the BMUs identifier
	 */
	public final int findOutputBMU(double[] output) {
		BMU = 0;
		double distance = Double.MAX_VALUE;
		for (int i = 0; i < map.length; ++i) {
			double dist = this.distance.distance(map[i].output, output);
			if (dist < distance) {
				distance = dist;
				BMU = i;
			}
		}
		return BMU;
	}

	/**
	 * Finds the Worst Matching Unit for the given input
	 * 
	 * @return the WMUs identifier
	 */
	public final int findInputWMU(double[] input) {
		BMU = 0;
		double distance = Double.MIN_VALUE;
		for (int i = 0; i < map.length; ++i) {
			double dist = this.distance.distance(map[i].input, input);
			if (dist > distance) {
				distance = dist;
				BMU = i;
			}
		}
		return BMU;
	}

	/**
	 * Finds the Worst Matching Unit for the given output
	 * 
	 * @return the WMUs identifier
	 */
	public final int findOutputWMU(double[] output) {
		BMU = 0;
		double distance = Double.MIN_VALUE;
		for (int i = 0; i < map.length; ++i) {
			double dist = this.distance.distance(map[i].output, output);
			if (dist > distance) {
				distance = dist;
				BMU = i;
			}
		}
		return BMU;
	}

	/**
	 * Sets the Matched index to the set value.
	 * 
	 * @param index
	 */
	public final void setMatchIndex(int index) {
		BMU = Math.max(0, Math.min(index, map.length - 1));
	}

	/**
	 * This returns the input of the last found BMU or WMU.
	 * 
	 * @return the input vector
	 */
	public final double[] getInput() {
		return this.map[BMU].input;
	}

	/**
	 * This returns the output of the last found BMU or WMU.
	 * 
	 * @return the output vector
	 */
	public final double[] getOutput() {
		return this.map[BMU].output;
	}

	/**
	 * This returns the input of the given ID.
	 * 
	 * @return the input vector
	 */
	public final double[] getInput(int id) {
		if (id >= 0 && id < map.length)
			return this.map[id].input;
		return null;
	}

	/**
	 * This returns the output of the given ID.
	 * 
	 * @return the output vector
	 */
	public final double[] getOutput(int id) {
		if (id >= 0 && id < map.length)
			return this.map[id].output;
		return null;
	}

	/**
	 * Sets the learning rate of this KohonenMap
	 * 
	 * @param rate
	 *            value between 0 and 1
	 */
	public final void setLearningRate(double rate) {
		learningRate = Math.max(Math.min(rate, 1), 0);
	}

	/**
	 * Returns the current rate of learning
	 * 
	 * @return the learning rate
	 */
	public final double getLearningRate() {
		return learningRate;
	}

	/**
	 * Sets the map to wrap its updates (slightly more costly)
	 */
	public final void setWraps(boolean n) {
		wrap = n;
	}

	/**
	 * Returns if the current map wraps
	 * 
	 * @return
	 */
	public final boolean isWrapping() {
		return wrap;
	}

	public double getCutoff() {
		return cutoff;
	}

	public void setCutoff(double cutoff) {
		this.cutoff = cutoff;
	}

	/**
	 * Sets the density function this map uses for updating nearby nodes. If
	 * unset it uses the StandardDensity class.
	 * 
	 * @param func
	 *            the Density Function
	 */
	public final void setDensityFunction(Density func) {
		this.density = func;
	}

	/**
	 * Sets the distance function used to find the best or worst matching unit.
	 * If unset, this map uses the EulerDistanceSquared class.<br>
	 * The neighborhood distance is Manhattan Distance.
	 * 
	 * @param func
	 */
	public final void setDistanceFunction(Distance func) {
		this.distance = func;
	}

	/**
	 * Updates the map with the given data. Uses the last found BMU or WMU.
	 * 
	 * @param input
	 *            input vector
	 * @param output
	 *            expected output vector
	 */
	public final void train(double input[], double output[]) {
		Node bmu = map[BMU];
		for (int i = 0; i < map.length; ++i) {
			map[i].update(bmu.position, input, output);
		}
	}

	/**
	 * This uses Manhattan Distance.
	 */
	private static final double neighborhood(int[] p, int[] q) {
		if (p == null || q == null)
			return 0;
		int len = Math.min(p.length, q.length);
		int output = 0;
		for (int i = 0; i < len; ++i)
			output += Math.abs(p[i] - q[i]);
		return output;
	}

	private final class Node {
		/** Location in the neighborhood */
		private final int[] position;
		/** Input vector */
		private final double[] input;
		/** Output vector */
		private final double[] output;

		public Node(int mapSize, int inputSize, int outputSize) {
			position = new int[mapSize];
			input = new double[inputSize];
			output = new double[outputSize];
		}

		private final double weight(double c, double t, double n) {
			return c + n * (t - c) * learningRate;
		}

		private final void update(int[] pos, double[] in, double[] out) {
			double distance = neighborhood(pos, position);
			if (wrap) {
				int[] tpos = pos.clone();
				int[] npos = position.clone();
				for (int i = 0; i < tpos.length; ++i) {
					tpos[i] += mapSize[i] / 2;
					npos[i] += mapSize[i] / 2;
					if (tpos[i] > mapSize[i])
						tpos[i] -= mapSize[i];
					if (npos[i] > mapSize[i])
						npos[i] -= mapSize[i];
				}
				double ndist = neighborhood(tpos, npos);
				if (ndist < distance)
					distance = ndist;
			}

			double neighborhood = density.density(distance);

			/* Changes below this point benefits are negligible */
			if (neighborhood < cutoff)
				return;

			for (int i = 0; i < input.length; ++i)
				input[i] = weight(input[i], in[i], neighborhood);

			for (int i = 0; i < output.length; ++i)
				output[i] = weight(output[i], out[i], neighborhood);
		}

	}
}

org.csdgn.nn.Density

package org.csdgn.nn;

public abstract class Density {
	/**
	 * Calculates the density at the given point, where x is a certain distance from the center of the distribution.
	 */
	public abstract double density(double x);
	
	public static class Normal extends Density {
		private final double multi;
		private final double variance;
		private final double mean;
		public Normal() {
			this(1,0);
		}
		public Normal(double variance, double mean) {
			this.multi = 1.0 / Math.sqrt(2*Math.PI*variance);
			this.variance = variance;
			this.mean = mean;
		}
		@Override
		public double density(double x) {
			double e = ((x - mean)*(x - mean)) / (2*variance);
			return multi*Math.exp(-e);
		}
	}
	
	public static class Simple extends Density {
		/**
		 * <math>density(x) = 2^{-x^2}</math>
		 */
		@Override
		public double density(double x) {
			return Math.pow(2, -(x*x));
		}
	}
}

org.csdgn.nn.Distance

package org.csdgn.nn;

public abstract class Distance {
	public abstract double distance(double[] p, double[] q);

	public static class EulerSq extends Distance {
		/**
		 * <math>distSqr(p,q) = \sum_{i=0}^n (p_i - q_i)^2</math> where
		 * <math>n</math> is the size of the smaller of <math>p</math> or
		 * <math>q</math>
		 */
		@Override
		public double distance(double[] p, double[] q) {
			if (p == null || q == null)
				return 0;
			int len = Math.min(p.length, q.length);
			double k, output = 0;
			for (int i = 0; i < len; ++i)
				output += (k = (p[i] - q[i])) * k;
			return output;
		}
	}

	public static class Euler extends EulerSq {
		/**
		 * <math>dist(p,q) = \sqrt_{\sum_{i=0}^n (p_i - q_i)^2}</math> where
		 * <math>n</math> is the size of the smaller of <math>p</math> or
		 * <math>q</math>
		 */
		@Override
		public double distance(double[] p, double[] q) {
			return Math.sqrt(super.distance(p, q));
		}
	}
}