Kohonen Map

From Robowiki
Jump to navigation Jump to search

This is about all I can remember on how Kohonen maps work, you may tweak this if you like. Fix any bugs that keeps it from actually working in a robot, etc.

package chase.meh;

/**
 * This is a basic stand alone Kohonen map for use in Succubus, this allows me to worry
 * about Kohonen Map stuff in the Kohonen Map, and robot stuff in the robot.
 * 
 * @author Chase
 */
public class KohonenMap {
	private KohonenNode[] map;
	private int mapSize;
	private long time;
	private double[] weights;
	
	/**
	 * The dimensions in the dim, are only used with the neighborhood function. The true
	 * dimensionality that makes Kohonen Maps work is the input and output weights.<br><br>
	 * The input weights are used to determine the BMU, while the output weights are unused
	 * @param dim Sets the size of the internal map. Where the length is the number of dimensions and
	 * each index determines the size of that particular dimension. So {8,4} would initialize a 2
	 * dimensional map, 8 wide, and 4 high.
	 * @param inputL The lower range of the input weights that each node contains. The number of entries
	 * determines the number of input weights. 
	 * @param inputU The upper range of the input weights that each node contains. The number of entries
	 * determines the number of input weights. 
	 * @param outputL The lower range of the output weights that each node contains. The number of entries
	 * determines the number of output weights.
	 * @param outputU The upper range of the output weights that each node contains. The number of entries
	 * determines the number of output weights.
	 */
	public KohonenMap(int[] dim, int input, int output, double[] weight) {
		mapSize = 1;
		for(int i=0; i<dim.length; ++i)
			mapSize *= dim[i];
		
		map = new KohonenNode[mapSize];
		
		//Logarithms have this thing against zero :)
		time = 1;
		
		weights = weight.clone();
		
		/**
		 * Initialize each node.
		 */
		int tDim[] = new int[dim.length];
		for(int i=0; i<mapSize; ++i) {
			map[i] = new KohonenNode(input,output);
			
			/** !! VERY IMPORTANT !! VERY IMPORTANT !!
			 * Here we are setting up the neighborhood,
			 * so it doesn't need to be calculated later
			 * which makes things much simpler.
			 */
			map[i].my_pos = tDim.clone();
			
			++tDim[0];
			for(int j=0;j<dim.length-1;++j) {
				if(tDim[j] >= dim[j]) {
					tDim[j+1]++;
					tDim[j] = 0;
				}
			}
		}
	}
	
	/**
	 * Returns the best matching unit for the given data
	 * @param input Data used to locate the BMU
	 * @return the best matching BMU for this input data
	 */
	public KohonenNode getBMU(double input[]) {
		KohonenNode out = null;
		double distance = Double.POSITIVE_INFINITY;
		for(int i=0;i<mapSize;++i) {
			KohonenNode n = map[i];
			double dist = distance(input,n.input);
			if(dist < distance) {
				distance = dist;
				out = n;
			}
		}
		return out;
	}
	
	/**
	 * Updates this KohonenMap with the given data.
	 * @param input The input data that will be updated to the map
	 * @param output The output data that will be updated to the map
	 */
	public void update(double input[], double output[]) {
		KohonenNode bmu = getBMU(input);
		for(int i=0;i<mapSize;++i) {
			map[i].update(bmu.my_pos, input, output);
		}
		++time;
	}
	
	/**
	 * Sets the internal time used for weighting the update data by time.
	 * The internal time automatically gets incremented with each update,
	 * calling this is unnecessary.
	 * @param time
	 */
	public void setTime(long time) {
		if(time < 1) time = 1;
		this.time = time;
	}
	
	public long getTime() {
		return this.time;
	}
	
	/**
	 * This is a KohonenNode, it just contains the data
	 * @author Chase
	 */
	public class KohonenNode {
		/** this is the location of this node in the neighborhood. */
		private int[] my_pos;
		
		public double[] input;
		public double[] output;
		
		/**
		 * @param inputL The lower range of the input weights that this node contains. The number of entries
		 * determines the number of input weights. 
		 * @param inputU The upper range of the input weights that this node contains. The number of entries
		 * determines the number of input weights. 
		 * @param outputL The lower range of the output weights that this node contains. The number of entries
		 * determines the number of output weights.
		 * @param outputU The upper range of the output weights that this node contains. The number of entries
		 * determines the number of output weights.
		 */
		public KohonenNode(int inputs, int outputs) {
			input = new double[inputs];
			output = new double[outputs];
			
			/** !! VERY IMPORTANT !! VERY IMPORTANT !!
			 * Randomize the startup data
			 */
			for(int i=0;i<input.length;++i) {
				input[i] = (Math.random()-0.5)*2.0;
			}
			for(int i=0;i<output.length;++i) {
				output[i] = (Math.random()-0.5)*2.0;
			}
		}
		
		
		private double gaussian(double u) {
			/** This normalizes it so that 0 = 1 */
			final double oos2p = (1.0/Math.sqrt(2.0*Math.PI));
			return oos2p*Math.exp(-0.5*u*u);
		}
		
		private double weight(double current, double target, double neighborhood, double time) {
			return current + neighborhood * time * (target - current);
		}
		
		private void update(int[] bmu, double input[], double output[]) {
			double distance = neighborDistance(my_pos,bmu);
			//double neighborhood = Math.exp(-(distance*distance));
			double neighborhood = gaussian(distance);
			double timeFunc = 1.0/(Math.log(time)+0.01);
			//double timeFunc = Math.exp(-(time*time)/2.0);
			
			/** Beyond this point its benefit is negligible. */
			//if(neighborhood*timeFunc < 0.001) return;
			if(distance > 4) return;
			
			/** Update the input and output weights */
			for(int i=0;i<input.length;++i) {
				this.input[i] = weight(this.input[i], input[i], neighborhood, timeFunc);
			}
			for(int i=0;i<output.length;++i) {
				this.output[i] = weight(this.output[i], output[i], neighborhood, timeFunc);
			}
		}
	}
	
	/**
	 * The weight distance function.
	 */
	public double distance(double[] p, double[] q) {
		if(p == null || q == null) return Double.POSITIVE_INFINITY;
		double k, d = 0;
		for(int i = 0; i < p.length; i++) {
			k = p[i] - q[i];
			d += k*k*weights[i];
		}
		return d;
	}
	/**
	 * The neighborhood distance function.
	 */
	public static final double neighborDistance(int[] p, int[] q) {
		double k, d = 0;
		for(int i = 0; i < p.length; i++) {
			k = p[i] - q[i];
			d += k*k; 
		}
		return d;
	}
}