Difference between revisions of "User:Chase-san/KohonenMap"

From Robowiki
Jump to navigation Jump to search
(→‎org.csdgn.nn.SOM: minor tweaks)
m (→‎org.csdgn.maru.util.KohonenMap: Removing unneeded import and most finals.)
 
(10 intermediate revisions by the same user not shown)
Line 1: Line 1:
This is my implementation of a [http://en.wikipedia.org/wiki/Self-organizing_map Self-organizing map]. It is untested, but it should work just fine.
+
[[Category:Code Snippets|KohonenMap]]
 +
This is my implementation of a [http://en.wikipedia.org/wiki/Self-organizing_map Self-organizing map].
 +
 
 +
This and all my other code in which I display on the robowiki falls under the [http://en.wikipedia.org/wiki/Zlib_License ZLIB License].
 +
 
 +
 
 +
===How to use===
  
===org.csdgn.nn.SOM===
 
 
<syntaxhighlight>
 
<syntaxhighlight>
package org.csdgn.nn;
+
//Create the map, 16 nodes, 2 input, 1 output
 +
KohonenMap map = new KohonenMap(new int[]{16},2,1);
  
import java.util.Arrays;
+
//Initializing gives every input and output a random value, which allows the Kohonen map to work.
import java.util.Random;
+
map.initialize();
  
import org.csdgn.nn.density.StandardDensity;
+
//For example a KohonenMap can be used for binary values
import org.csdgn.nn.distance.EulerDistanceSquared;
+
//A larger map is recommended for better output
import org.csdgn.utils.VDA;
 
  
/**
+
//XOR
* An Optimized Self-Organizing Map implementation.
+
//0 0 0
* This makes use of the VDA class.
+
//0 1 1
*
+
//1 0 1
* @author Chase
+
//1 1 0
*
 
*/
 
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;
 
  
/**
+
double[][] input = new double[][] {
* @param mapSize
+
{0,0}, {0,1}, {1,0}, {1,1}
*            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];
 
}
 
}
 
  
/**
+
double[][] output = new double[][] {
* Initializes the map to random values
+
{0}, {1}, {1}, {0}
*/
+
};
public final void initialize() {
+
//To train your map
Random r = new Random();
+
for(int i = 0; i < input.length; ++i) {
initialize(r);
+
//find the BMU you want to train
}
+
map.findInputBMU(input[i]);
 +
//and then tell the main to train on that BMU
 +
map.train(input[i], output[i]);
 +
}
  
/**
+
//to get meaningful data from the map
* Initializes the map with the given random function. Uses the nextDouble
+
for(int i = 0; i < input.length; ++i) {
* function.
+
//find the BMU
*/
+
map.findInputBMU(input[i]);
public final void initialize(Random random) {
 
Object[] tmp = vda.getBackingArray();
 
for(Object o : tmp) {
 
double[] tmp2 = (double[])o;
 
for(int i = 0; i < tmp2.length; ++i) {
 
tmp2[i] = random.nextDouble();
 
}
 
}
 
}
 
 
 
/**
+
//get the output for that BMU
* Initializes the map nodes to the given values.
+
double out = map.getOutput()[0];
*/
 
public final void initialize(double[] in, double[] out) {
 
Object[] tmp = vda.getBackingArray();
 
for(Object o : tmp) {
 
double[] array = (double[])o;
 
for(int i = 0; i < array.length; ++i) {
 
if(i < inputSize) {
 
array[i] = in[i];
 
} else {
 
array[i] = out[i - inputSize];
 
}
 
}
 
}
 
}
 
 
 
/**
+
//You can simply round to get the desired binary output
* Initializes the map nodes to the given values.
+
System.out.println(Arrays.toString(input[i]) + " " + Math.round(out) + " " + out);
*/
 
public final void initialize(Random input, double[] out) {
 
Object[] tmp = vda.getBackingArray();
 
for(Object o : tmp) {
 
double[] array = (double[])o;
 
for(int i = 0; i < array.length; ++i) {
 
if(i < inputSize) {
 
array[i] = input.nextDouble();
 
} else {
 
array[i] = out[i - inputSize];
 
}
 
}
 
}
 
}
 
 
 
/**
 
* 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) * learningRate;
 
 
 
/* 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);
 
}
 
 
 
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;
 
}
 
}
 
}
 
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
===org.csdgn.nn.KohonenMap===
+
===org.csdgn.maru.util.KohonenMap===
 
<syntaxhighlight>
 
<syntaxhighlight>
package org.csdgn.nn;
+
package org.csdgn.maru.util;
  
 
import java.util.Random;
 
import java.util.Random;
import org.csdgn.nn.density.StandardDensity;
+
import org.csdgn.nn.distance.EulerDistanceSquared;
 
 
 
 
/**
 
/**
 
  * A Self-Organizing Map implementation.
 
  * A Self-Organizing Map implementation.
Line 336: Line 64:
 
  * org.csdgn.nn.DistanceFunction<br>
 
  * org.csdgn.nn.DistanceFunction<br>
 
  * org.csdgn.nn.density.StandardDensity<br>
 
  * org.csdgn.nn.density.StandardDensity<br>
  * org.csdgn.nn.distance.EulerDistanceSquared
+
  * org.csdgn.nn.distance.EulerDistanceSquared<br><br>
 
  *  
 
  *  
  * TODO: Optimize for speed.
+
  * Train The Map<br>
 +
* findInputBMU(double[])<br>
 +
* train(double[])<br><br>
 +
* Find Output<br>
 +
* findInputBMU(double[])<br>
 +
* getOutput()
 
  *  
 
  *  
* @author Chase
 
*
 
 
  */
 
  */
 
public class KohonenMap {
 
public class KohonenMap {
private static final double cutoff = 1e-4;
 
 
 
/**
 
/**
 
* Holds the neighborhood layout;
 
* Holds the neighborhood layout;
 
*/
 
*/
public final Node[] map;
+
private final Node[] map;
public final int[] mapSize;
+
private final int[] mapSize;
public double learningRate = 0.8;
+
private double learningRate = 0.8;
private DensityFunction density;
+
private Density density;
private DistanceFunction distance;
+
private Distance distance;
 +
private Distance neighborhood;
 
private boolean wrap = false;
 
private boolean wrap = false;
 
private int BMU;
 
private int BMU;
+
 +
private double cutoff = 1e-4;
 +
 
/**
 
/**
* @param mapSize Size of the neighborhood. Example: {10,10} produces a 2 dimensional
+
* @param mapSize
* map, each dimension having 10 nodes. Total nodes would be 100.
+
*            Size of the neighborhood. Example: {10,10} produces a 2
* @param input The length of the input vector (2D only)
+
*           dimensional map, each dimension having 10 nodes. Total nodes
* @param output The length of the output vector (2D only)
+
*            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) {
 
public KohonenMap(int[] mapSize, int input, int output) {
 
/* Setup the map */
 
/* Setup the map */
 
int size = 1;
 
int size = 1;
for(int m : mapSize) size *= m;
+
for (int m : mapSize)
 +
size *= m;
 +
 
this.map = new Node[size];
 
this.map = new Node[size];
+
 
this.mapSize = mapSize.clone();
 
this.mapSize = mapSize.clone();
+
this.density = new StandardDensity();
+
this.density = new Density.Simple();
this.distance = new EulerDistanceSquared();
+
this.distance = new Distance.EulerSq();
+
this.neighborhood = new Distance.Manhattan();
 +
 
int[] pos = new int[mapSize.length];
 
int[] pos = new int[mapSize.length];
for(int i=0; i<map.length; ++i) {
+
for (int i = 0; i < map.length; ++i) {
this.map[i] = new Node(mapSize.length,input,output);
+
this.map[i] = new Node(mapSize.length, input, output);
 
/* Setup the location of each node, for speed reasons. */
 
/* Setup the location of each node, for speed reasons. */
 
System.arraycopy(pos, 0, this.map[i].position, 0, pos.length);
 
System.arraycopy(pos, 0, this.map[i].position, 0, pos.length);
+
 
/* Update the position marker */
 
/* Update the position marker */
 
++pos[0];
 
++pos[0];
for(int j=0;j<pos.length-1;++j) {
+
for (int j = 0; j < pos.length - 1; ++j) {
if(pos[j] >= mapSize[j]) {
+
if (pos[j] >= mapSize[j]) {
++pos[j+1];
+
++pos[j + 1];
 
pos[j] = 0;
 
pos[j] = 0;
 
}
 
}
Line 390: Line 129:
 
}
 
}
 
}
 
}
+
 
/**
 
/**
 
* Initializes the map to random values
 
* Initializes the map to random values
 
*/
 
*/
public final void initialize() {
+
public void initialize() {
 
Random r = new Random();
 
Random r = new Random();
 
initialize(r);
 
initialize(r);
 
}
 
}
+
 
/**
 
/**
* Initializes the map with the given random function.
+
* Initializes the map with the given random function. Uses the nextDouble
* Uses the nextDouble function.
+
* function.
 
*/
 
*/
public final void initialize(Random random) {
+
public void initialize(Random random) {
for(Node n : map) {
+
for (Node n : map) {
for(int i = 0; i < n.input.length; ++i)
+
for (int i = 0; i < n.input.length; ++i)
 
n.input[i] = random.nextDouble();
 
n.input[i] = random.nextDouble();
for(int i = 0; i < n.output.length; ++i)
+
for (int i = 0; i < n.output.length; ++i)
n.output[i] = random.nextDouble();  
+
n.output[i] = random.nextDouble();
 
}
 
}
 
}
 
}
+
 
/**
 
/**
 
* Finds the Best Matching Unit for the given input.
 
* Finds the Best Matching Unit for the given input.
 +
*
 
* @return the BMUs identifier
 
* @return the BMUs identifier
 
*/
 
*/
public final int findBMInput(double[] input) {
+
public int findInputBMU(double[] input) {
 
BMU = 0;
 
BMU = 0;
+
 
double distance = Double.MAX_VALUE;
 
double distance = Double.MAX_VALUE;
for(int i=0; i<map.length; ++i) {
+
for (int i = 0; i < map.length; ++i) {
double dist = this.distance.calculate(map[i].input, input);
+
double dist = this.distance.distance(map[i].input, input);
+
if(dist < distance) {
+
if (dist < distance) {
 
distance = dist;
 
distance = dist;
 
BMU = i;
 
BMU = i;
Line 430: Line 170:
 
return BMU;
 
return BMU;
 
}
 
}
+
 
/**
 
/**
 
* Finds the Best Matching Unit for the given output.
 
* Finds the Best Matching Unit for the given output.
 +
*
 
* @return the BMUs identifier
 
* @return the BMUs identifier
 
*/
 
*/
public final int findBMOutput(double[] output) {
+
public int findOutputBMU(double[] output) {
 
BMU = 0;
 
BMU = 0;
 
double distance = Double.MAX_VALUE;
 
double distance = Double.MAX_VALUE;
for(int i=0; i<map.length; ++i) {
+
for (int i = 0; i < map.length; ++i) {
double dist = this.distance.calculate(map[i].output, output);
+
double dist = this.distance.distance(map[i].output, output);
if(dist < distance) {
+
if (dist < distance) {
 
distance = dist;
 
distance = dist;
 
BMU = i;
 
BMU = i;
Line 447: Line 188:
 
return BMU;
 
return BMU;
 
}
 
}
+
 
/**
 
/**
 
* Finds the Worst Matching Unit for the given input
 
* Finds the Worst Matching Unit for the given input
 +
*
 
* @return the WMUs identifier
 
* @return the WMUs identifier
 
*/
 
*/
public final int findWMInput(double[] input) {
+
public int findInputWMU(double[] input) {
 
BMU = 0;
 
BMU = 0;
 
double distance = Double.MIN_VALUE;
 
double distance = Double.MIN_VALUE;
for(int i=0; i<map.length; ++i) {
+
for (int i = 0; i < map.length; ++i) {
double dist = this.distance.calculate(map[i].input, input);
+
double dist = this.distance.distance(map[i].input, input);
if(dist > distance) {
+
if (dist > distance) {
 
distance = dist;
 
distance = dist;
 
BMU = i;
 
BMU = i;
Line 464: Line 206:
 
return BMU;
 
return BMU;
 
}
 
}
+
 
/**
 
/**
 
* Finds the Worst Matching Unit for the given output
 
* Finds the Worst Matching Unit for the given output
 +
*
 
* @return the WMUs identifier
 
* @return the WMUs identifier
 
*/
 
*/
public final int findWMOutput(double[] output) {
+
public int findOutputWMU(double[] output) {
 
BMU = 0;
 
BMU = 0;
 
double distance = Double.MIN_VALUE;
 
double distance = Double.MIN_VALUE;
for(int i=0; i<map.length; ++i) {
+
for (int i = 0; i < map.length; ++i) {
double dist = this.distance.calculate(map[i].output, output);
+
double dist = this.distance.distance(map[i].output, output);
if(dist > distance) {
+
if (dist > distance) {
 
distance = dist;
 
distance = dist;
 
BMU = i;
 
BMU = i;
Line 481: Line 224:
 
return BMU;
 
return BMU;
 
}
 
}
+
 
/**
 
/**
 
* Sets the Matched index to the set value.
 
* Sets the Matched index to the set value.
 +
*
 
* @param index
 
* @param index
 
*/
 
*/
public final void setMatchIndex(int index) {
+
public void setMatchIndex(int index) {
BMU = Math.max(0,Math.min(index, map.length-1));
+
BMU = Math.max(0, Math.min(index, map.length - 1));
 
}
 
}
+
 
/**
 
/**
 
* This returns the input of the last found BMU or WMU.
 
* This returns the input of the last found BMU or WMU.
 +
*
 
* @return the input vector
 
* @return the input vector
 
*/
 
*/
public final double[] getInput() {
+
public double[] getInput() {
 
return this.map[BMU].input;
 
return this.map[BMU].input;
 
}
 
}
+
 
/**
 
/**
 
* This returns the output of the last found BMU or WMU.
 
* This returns the output of the last found BMU or WMU.
 +
*
 
* @return the output vector
 
* @return the output vector
 
*/
 
*/
public final double[] getOutput() {
+
public double[] getOutput() {
 
return this.map[BMU].output;
 
return this.map[BMU].output;
 
}
 
}
+
 
/**
 
/**
 
* This returns the input of the given ID.
 
* This returns the input of the given ID.
 +
*
 
* @return the input vector
 
* @return the input vector
 
*/
 
*/
public final double[] getInput(int id) {
+
public double[] getInput(int id) {
if(id > 0 && id < map.length)
+
if (id >= 0 && id < map.length)
 
return this.map[id].input;
 
return this.map[id].input;
return new double[0];
+
return null;
 
}
 
}
+
 
/**
 
/**
 
* This returns the output of the given ID.
 
* This returns the output of the given ID.
 +
*
 
* @return the output vector
 
* @return the output vector
 
*/
 
*/
public final double[] getOutput(int id) {
+
public double[] getOutput(int id) {
if(id > 0 && id < map.length)
+
if (id >= 0 && id < map.length)
 
return this.map[id].output;
 
return this.map[id].output;
return new double[0];
+
return null;
 
}
 
}
+
 
/**
 
/**
 
* Sets the learning rate of this KohonenMap
 
* Sets the learning rate of this KohonenMap
* @param rate value between 0 and 1
+
*
 +
* @param rate
 +
*            value between 0 and 1
 
*/
 
*/
public final void setLearningRate(double rate) {
+
public void setLearningRate(double rate) {
learningRate = Math.max(Math.min(rate, 1),0);
+
learningRate = Math.max(Math.min(rate, 1), 0);
 
}
 
}
+
 
/**
 
/**
 
* Returns the current rate of learning
 
* Returns the current rate of learning
* @return the learning rate  
+
*
 +
* @return the learning rate
 
*/
 
*/
public final double getLearningRate() {
+
public double getLearningRate() {
 
return learningRate;
 
return learningRate;
 
}
 
}
+
 
/**
 
/**
 
* Sets the map to wrap its updates (slightly more costly)
 
* Sets the map to wrap its updates (slightly more costly)
 
*/
 
*/
public final void setWraps(boolean n) {
+
public void setWraps(boolean doesWrap) {
wrap = n;
+
wrap = doesWrap;
 
}
 
}
+
 
/**
 
/**
 
* Returns if the current map wraps
 
* Returns if the current map wraps
 +
*
 
* @return
 
* @return
 
*/
 
*/
public final boolean isWrapping() {
+
public boolean isWrapping() {
 
return wrap;
 
return wrap;
 
}
 
}
+
 +
/**
 +
* Gets the current cutoff density.
 +
*/
 +
public double getCutoff() {
 +
return cutoff;
 +
}
 +
 +
/**
 +
* The cutoff density in which under a node will not be trained.
 +
* @param cutoff
 +
*/
 +
public void setCutoff(double cutoff) {
 +
this.cutoff = cutoff;
 +
}
 +
 
/**
 
/**
* Sets the density function this map uses for updating nearby nodes.
+
* Sets the density function this map uses for updating nearby nodes. If
* If unset it uses the StandardDensity class.
+
* unset it uses the StandardDensity class.
* @param func the Density Function
+
*
 +
* @param func
 +
*            the Density Function
 
*/
 
*/
public final void setDensityFunction(DensityFunction func) {
+
public void setDensityFunction(Density func) {
 
this.density = func;
 
this.density = func;
 
}
 
}
+
 
/**
 
/**
 
* Sets the distance function used to find the best or worst matching unit.
 
* Sets the distance function used to find the best or worst matching unit.
 
* If unset, this map uses the EulerDistanceSquared class.<br>
 
* If unset, this map uses the EulerDistanceSquared class.<br>
 
* The neighborhood distance is Manhattan Distance.
 
* The neighborhood distance is Manhattan Distance.
 +
*
 
* @param func
 
* @param func
 
*/
 
*/
public final void setDistanceFunction(DistanceFunction func) {
+
public void setDistanceFunction(Distance func) {
 
this.distance = func;
 
this.distance = func;
 
}
 
}
 
 
 
/**
 
/**
* Updates the map with the given data. Uses the last found
+
* Sets the distance function used to calculate the neighborhood distance between nodes.
* BMU or WMU.
+
* @param func
* @param input input vector
+
*/
* @param output expected output vector
+
public void setNeighborhoodDistanceFunction(Distance func) {
 +
this.neighborhood = 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[]) {
+
public void train(double input[], double output[]) {
 
Node bmu = map[BMU];
 
Node bmu = map[BMU];
for(int i=0; i<map.length; ++i) {
+
for (int i = 0; i < map.length; ++i) {
 
map[i].update(bmu.position, input, output);
 
map[i].update(bmu.position, input, output);
 
}
 
}
 
}
 
}
+
/**
+
private class Node {
* 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 */
 
/** Location in the neighborhood */
 
private final int[] position;
 
private final int[] position;
Line 608: Line 376:
 
/** Output vector */
 
/** Output vector */
 
private final double[] output;
 
private final double[] output;
+
 
public Node(int mapSize, int inputSize, int outputSize) {
 
public Node(int mapSize, int inputSize, int outputSize) {
 
position = new int[mapSize];
 
position = new int[mapSize];
Line 614: Line 382:
 
output = new double[outputSize];
 
output = new double[outputSize];
 
}
 
}
+
private final double weight(double c, double t, double n) {
+
private double train(double c, double t, double n) {
 
return c + n * (t - c) * learningRate;
 
return c + n * (t - c) * learningRate;
 
}
 
}
+
private final void update(int[] pos, double[] in, double[] out) {
+
private void update(int[] pos, double[] in, double[] out) {
double distance = neighborhood(pos,position);
+
double distance = neighborhood.distance(pos, position);
if(wrap) {
+
if (wrap) {
 
int[] tpos = pos.clone();
 
int[] tpos = pos.clone();
 
int[] npos = position.clone();
 
int[] npos = position.clone();
for(int i=0; i<tpos.length; ++i) {
+
for (int i = 0; i < tpos.length; ++i) {
tpos[i] += mapSize[i]/2;
+
tpos[i] += mapSize[i] / 2;
npos[i] += mapSize[i]/2;
+
npos[i] += mapSize[i] / 2;
if(tpos[i] > mapSize[i]) tpos[i] -= mapSize[i];
+
if (tpos[i] > mapSize[i])
if(npos[i] > mapSize[i]) npos[i] -= mapSize[i];
+
tpos[i] -= mapSize[i];
 +
if (npos[i] > mapSize[i])
 +
npos[i] -= mapSize[i];
 
}
 
}
double ndist = neighborhood(tpos,npos);
+
double ndist = neighborhood.distance(tpos, npos);
if(ndist < distance) distance = ndist;
+
if (ndist < distance)
 +
distance = ndist;
 
}
 
}
+
double neighborhood = density.calculate(distance);
+
double neighborhood = density.density(distance);
+
 
/* Changes below this point benefits are negligible */
 
/* Changes below this point benefits are negligible */
if(neighborhood < cutoff) return;
+
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 < input.length; ++i)
+
input[i] = train(input[i], in[i], neighborhood);
for(int i=0; i<output.length; ++i)
+
output[i] = weight(output[i], out[i], neighborhood);
+
for (int i = 0; i < output.length; ++i)
 +
output[i] = train(output[i], out[i], neighborhood);
 
}
 
}
+
 
}
 
}
}
 
</syntaxhighlight>
 
 
 
===org.csdgn.nn.DensityFunction===
 
<syntaxhighlight>
 
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);
 
}
 
</syntaxhighlight>
 
===org.csdgn.nn.DistanceFunction===
 
<syntaxhighlight>
 
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);
 
}
 
</syntaxhighlight>
 
===org.csdgn.nn.density.StandardDensity===
 
<syntaxhighlight>
 
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));
 
}
 
}
 
</syntaxhighlight>
 
===org.csdgn.nn.density.NormalDistribution===
 
<syntaxhighlight>
 
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() {
+
public static abstract class Density {
this(1,0);
+
/**
}
+
* Calculates the density at the given point, where x is a certain distance from the center of the distribution.
public NormalDistribution(double variance, double mean) {
+
*/
this.multi = 1.0 / Math.sqrt(2*Math.PI*variance);
+
public abstract double density(double x);
this.variance = variance;
+
this.mean = mean;
+
public static class Normal extends Density {
}
+
private final double multi;
@Override
+
private final double variance;
public double calculate(double x) {
+
private final double mean;
double e = ((x - mean)*(x - mean)) / (2*variance);
+
public Normal() {
return multi*Math.exp(-e);
+
this(1,0);
 +
}
 +
public Normal(double variance, double mean) {
 +
this.multi = 1.0 / Math.sqrt(2*Math.PI*variance);
 +
this.variance = 2.0*variance;
 +
this.mean = mean;
 +
}
 +
@Override
 +
public double density(double x) {
 +
double e = ((x - mean)*(x - mean)) / 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));
 +
}
 +
}
 
}
 
}
  
}
+
public static abstract class Distance {
</syntaxhighlight>
+
public abstract double distance(double[] p, double[] q);
===org.csdgn.nn.distance.EulerDistanceSquared===
+
public double distance(int[] p, int[] q) {
<syntaxhighlight>
+
double[] dp = new double[p.length];
package org.csdgn.nn.distance;
+
double[] dq = new double[q.length];
 
+
for(int i=0;i<p.length;++i)
import org.csdgn.nn.DistanceFunction;
+
dp[i] = p[i];
 
+
for(int i=0;i<p.length;++i)
public class EulerDistanceSquared implements DistanceFunction {
+
dq[i] = q[i];
/**
+
return distance(dp,dq);
* <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>
+
*/
+
public static class Manhattan extends Distance {
@Override
+
/**
public final double calculate(double[] p, double[] q) {
+
* Calculates the manhatten distance between the two points.
if(p == null || q == null) return 0;
+
*/
int len = Math.min(p.length, q.length);
+
@Override
double k,output = 0;
+
public double distance(double[] p, double[] q) {
for(int i=0; i<len; ++i)
+
if (p == null || q == null)
output += (k=(p[i] - q[i]))*k;
+
return 0;
return output;
+
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;
 +
}
 +
}
 +
 +
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));
 +
}
 +
}
 
}
 
}
 
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 07:56, 24 January 2014

This is my implementation of a Self-organizing map.

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


How to use

//Create the map, 16 nodes, 2 input, 1 output
KohonenMap map = new KohonenMap(new int[]{16},2,1);

//Initializing gives every input and output a random value, which allows the Kohonen map to work.
map.initialize();

//For example a KohonenMap can be used for binary values
//A larger map is recommended for better output

//XOR
//0 0	0
//0 1	1
//1 0	1
//1 1	0

double[][] input = new double[][] {
		{0,0}, {0,1}, {1,0}, {1,1}	
};

double[][] output = new double[][] {
		{0}, {1}, {1}, {0}
};
//To train your map
for(int i = 0; i < input.length; ++i) {
	//find the BMU you want to train
	map.findInputBMU(input[i]);
	//and then tell the main to train on that BMU
	map.train(input[i], output[i]);
}

//to get meaningful data from the map
for(int i = 0; i < input.length; ++i) {
	//find the BMU
	map.findInputBMU(input[i]);
	
	//get the output for that BMU
	double out = map.getOutput()[0];
	
	//You can simply round to get the desired binary output
	System.out.println(Arrays.toString(input[i]) + " " + Math.round(out) + " " + out);
}

org.csdgn.maru.util.KohonenMap

package org.csdgn.maru.util;

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<br><br>
 * 
 * Train The Map<br>
 * findInputBMU(double[])<br>
 * train(double[])<br><br>
 * Find Output<br>
 * findInputBMU(double[])<br>
 * getOutput()
 * 
 */
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 Distance neighborhood;
	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();
		this.neighborhood = new Distance.Manhattan();
 
		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 void initialize() {
		Random r = new Random();
		initialize(r);
	}
 
	/**
	 * Initializes the map with the given random function. Uses the nextDouble
	 * function.
	 */
	public 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 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 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 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 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 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 double[] getInput() {
		return this.map[BMU].input;
	}
 
	/**
	 * This returns the output of the last found BMU or WMU.
	 * 
	 * @return the output vector
	 */
	public double[] getOutput() {
		return this.map[BMU].output;
	}
 
	/**
	 * This returns the input of the given ID.
	 * 
	 * @return the input vector
	 */
	public 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 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 void setLearningRate(double rate) {
		learningRate = Math.max(Math.min(rate, 1), 0);
	}
 
	/**
	 * Returns the current rate of learning
	 * 
	 * @return the learning rate
	 */
	public double getLearningRate() {
		return learningRate;
	}
 
	/**
	 * Sets the map to wrap its updates (slightly more costly)
	 */
	public void setWraps(boolean doesWrap) {
		wrap = doesWrap;
	}
 
	/**
	 * Returns if the current map wraps
	 * 
	 * @return
	 */
	public boolean isWrapping() {
		return wrap;
	}
 
	/**
	 * Gets the current cutoff density.
	 */
	public double getCutoff() {
		return cutoff;
	}
 
	/**
	 * The cutoff density in which under a node will not be trained.
	 * @param 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 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 void setDistanceFunction(Distance func) {
		this.distance = func;
	}
	
	/**
	 * Sets the distance function used to calculate the neighborhood distance between nodes. 
	 * @param func
	 */
	public void setNeighborhoodDistanceFunction(Distance func) {
		this.neighborhood = 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 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);
		}
	}
 
	private 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 double train(double c, double t, double n) {
			return c + n * (t - c) * learningRate;
		}
 
		private void update(int[] pos, double[] in, double[] out) {
			double distance = neighborhood.distance(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.distance(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] = train(input[i], in[i], neighborhood);
 
			for (int i = 0; i < output.length; ++i)
				output[i] = train(output[i], out[i], neighborhood);
		}
 
	}
	
	public static 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 = 2.0*variance;
				this.mean = mean;
			}
			@Override
			public double density(double x) {
				double e = ((x - mean)*(x - mean)) / 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));
			}
		}
	}

	public static abstract class Distance {
		public abstract double distance(double[] p, double[] q);
		public double distance(int[] p, int[] q) {
			double[] dp = new double[p.length];
			double[] dq = new double[q.length];
			for(int i=0;i<p.length;++i)
				dp[i] = p[i];
			for(int i=0;i<p.length;++i)
				dq[i] = q[i];
			return distance(dp,dq);
		}
		
		public static class Manhattan extends Distance {
			/**
			 * Calculates the manhatten distance between the two points.
			 */
			@Override
			public double distance(double[] p, double[] 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;
			}
		}
	 
		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));
			}
		}
	}
}