User:Chase-san/KohonenMap
Jump to navigation
Jump to search
This is my implementation of a Self-organizing map. It is untested, but it should work just fine.
Contents
org.csdgn.nn.SOM
package org.csdgn.nn;
import java.util.Arrays;
import java.util.Random;
import org.csdgn.nn.density.StandardDensity;
import org.csdgn.nn.distance.EulerDistanceSquared;
import org.csdgn.utils.VDA;
/**
* An Optimized Self-Organizing Map implementation.
* This makes use of the VDA class.
*
* @author Chase
*
*/
public class SOM {
private static final double cutoff = 1.0e-4;
private final VDA<double[]> vda;
private final int inputSize;
private DensityFunction density = new StandardDensity();
private DistanceFunction distance = new EulerDistanceSquared();
private boolean wrap = false;
private double learningRate = 0.8;
private int[] BMU;
/**
* @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 (2D only)
* @param output
* The length of the output vector (2D only)
*/
public SOM(int[] mapSize, int input, int output) {
this.vda = new VDA<double[]>(mapSize);
this.inputSize = input;
Object[] obj = vda.getBackingArray();
for(int i = 0; i < obj.length; ++i) {
obj[i] = new double[input + output];
}
}
/**
* 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) {
Object[] tmp = vda.getBackingArray();
for(int i = 0; i < tmp.length; ++i) {
double[] tmp2 = ((double[])tmp[i]);
for(int j = 0; j < tmp2.length; ++j) {
tmp2[j] = random.nextDouble();
}
}
}
/**
* Finds the Best Matching Unit for the given input.
*/
public final void findBMInput(double[] input) {
if(input.length != inputSize)
return;
double bestDistance = Double.MAX_VALUE;
Object[] backArray = vda.getBackingArray();
int[] size = vda.getSize();
int[] pos = new int[size.length];
for(Object o : backArray) {
double[] array = (double[])o;
double dist = distance.calculate(array, input);
if(dist < bestDistance) {
bestDistance = dist;
BMU = pos.clone();
}
next(pos, size);
}
// return BMU;
// return BMU.clone();
}
/**
* Finds the Worst Matching Unit for the given input.
*/
public final void findWMInput(double[] input) {
if(input.length != inputSize)
return;
double worstDistance = Double.MIN_VALUE;
Object[] backArray = vda.getBackingArray();
int[] size = vda.getSize();
int[] pos = new int[size.length];
for(Object o : backArray) {
double[] array = (double[])o;
double dist = distance.calculate(array, input);
if(dist > worstDistance) {
worstDistance = dist;
BMU = pos.clone();
}
next(pos, size);
}
}
public final void setMatchingIndex(int... index) {
if(index.length != vda.getSize().length)
throw new IllegalArgumentException("Incorrect or Bad Dimensionality.");
BMU = index.clone();
}
/**
* This returns the input of the last found BMU or WMU.
*
* @return the input vector
*/
public final double[] getInput() {
if(BMU == null)
throw new UnsupportedOperationException("BMU/WMU must be found first.");
return Arrays.copyOf(vda.get(BMU), inputSize);
}
/**
* This returns the output of the last found BMU or WMU.
*
* @return the output vector
*/
public final double[] getOutput() {
if(BMU == null)
throw new UnsupportedOperationException("BMU/WMU must be found first.");
double[] bmu = vda.get(BMU);
double[] output = new double[bmu.length - inputSize];
System.arraycopy(bmu, inputSize, output, 0, bmu.length - inputSize);
return output;
}
/**
* 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;
}
/**
* 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(DensityFunction func) {
this.density = func;
}
/**
* Sets the distance function used to find the best or worst matching unit.
* If not set, the map uses the EulerDistanceSquared class.<br>
* The neighborhood distance is Manhattan Distance.
*
* @param func
*/
public final void setDistanceFunction(DistanceFunction 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[]) {
if(BMU == null)
throw new UnsupportedOperationException("BMU/WMU must be found first.");
Object[] backArray = vda.getBackingArray();
int[] size = vda.getSize();
int[] pos = new int[size.length];
for(Object o : backArray) {
double[] array = (double[])o;
double distance = neighborhood(pos, BMU);
if(wrap) {
int[] tpos = pos.clone();
int[] npos = BMU.clone();
for(int i = 0; i < tpos.length; ++i) {
tpos[i] += size[i] / 2;
npos[i] += size[i] / 2;
if(tpos[i] > size[i])
tpos[i] -= size[i];
if(npos[i] > size[i])
npos[i] -= size[i];
}
double ndist = neighborhood(tpos, npos);
if(ndist < distance)
distance = ndist;
}
double neighborhood = density.calculate(distance);
/* Changes below this point benefits are negligible */
if(neighborhood < cutoff) {
next(pos, size);
continue;
}
for(int i = 0; i < array.length; ++i) {
if(i < inputSize) {
array[i] = weight(array[i], input[i], neighborhood);
} else {
array[i] = weight(array[i], output[i - inputSize], neighborhood);
}
}
next(pos, size);
}
}
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 double weight(double c, double t, double n) {
return c + n * (t - c) * learningRate;
}
private static final void next(int[] pos, int[] size) {
++pos[pos.length - 1];
for(int i = pos.length - 1; i > 0; --i) {
if(pos[i] >= size[i]) {
++pos[i - 1];
pos[i] = 0;
}
}
}
}org.csdgn.nn.KohonenMap
package org.csdgn.nn;
import java.util.Random;
import org.csdgn.nn.density.StandardDensity;
import org.csdgn.nn.distance.EulerDistanceSquared;
/**
* 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 {
private static final double cutoff = 1e-4;
/**
* Holds the neighborhood layout;
*/
public final Node[] map;
public final int[] mapSize;
public double learningRate = 0.8;
private DensityFunction density;
private DistanceFunction distance;
private boolean wrap = false;
private int BMU;
/**
* @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 (2D only)
* @param output The length of the output vector (2D 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 StandardDensity();
this.distance = new EulerDistanceSquared();
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 findBMInput(double[] input) {
BMU = 0;
double distance = Double.MAX_VALUE;
for(int i=0; i<map.length; ++i) {
double dist = this.distance.calculate(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 findBMOutput(double[] output) {
BMU = 0;
double distance = Double.MAX_VALUE;
for(int i=0; i<map.length; ++i) {
double dist = this.distance.calculate(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 findWMInput(double[] input) {
BMU = 0;
double distance = Double.MIN_VALUE;
for(int i=0; i<map.length; ++i) {
double dist = this.distance.calculate(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 findWMOutput(double[] output) {
BMU = 0;
double distance = Double.MIN_VALUE;
for(int i=0; i<map.length; ++i) {
double dist = this.distance.calculate(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 new double[0];
}
/**
* 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 new double[0];
}
/**
* 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;
}
/**
* 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(DensityFunction 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(DistanceFunction 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.calculate(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.DensityFunction
package org.csdgn.nn;
public interface DensityFunction {
/**
* Calculates the density at the given point, where x is a certain distance from the center of the distribution.
*/
public double calculate(double x);
}org.csdgn.nn.DistanceFunction
package org.csdgn.nn;
/**
* A function for determining the distance between two double arrays.
* @author Chase
*/
public interface DistanceFunction {
public double calculate(double[] p, double[] q);
}org.csdgn.nn.density.StandardDensity
package org.csdgn.nn.density;
import org.csdgn.nn.DensityFunction;
/**
* <math>density(x) = 2^{-x^2}</math>
*/
public final class StandardDensity implements DensityFunction {
/**
* <math>density(x) = 2^{-x^2}</math>
*/
@Override
public double calculate(double x) {
return Math.pow(2, -(x*x));
}
}org.csdgn.nn.density.NormalDistribution
package org.csdgn.nn.density;
import org.csdgn.nn.DensityFunction;
public final class NormalDistribution implements DensityFunction {
private final double multi;
private final double variance;
private final double mean;
public NormalDistribution() {
this(1,0);
}
public NormalDistribution(double variance, double mean) {
this.multi = 1.0 / Math.sqrt(2*Math.PI*variance);
this.variance = variance;
this.mean = mean;
}
@Override
public double calculate(double x) {
double e = ((x - mean)*(x - mean)) / (2*variance);
return multi*Math.exp(-e);
}
}org.csdgn.nn.distance.EulerDistanceSquared
package org.csdgn.nn.distance;
import org.csdgn.nn.DistanceFunction;
public class EulerDistanceSquared implements DistanceFunction {
/**
* <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 final double calculate(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;
}
}
