Difference between revisions of "User:Chase-san/KohonenMap"
Jump to navigation
Jump to search
m (→org.csdgn.nn.KohonenMap: ermo, 1D) |
m (→org.csdgn.maru.util.KohonenMap: Removing unneeded import and most finals.) |
||
(6 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Code Snippets|KohonenMap]] | [[Category:Code Snippets|KohonenMap]] | ||
− | This is my implementation of a [http://en.wikipedia.org/wiki/Self-organizing_map Self-organizing map] | + | 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]. | 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]. | ||
− | ===org.csdgn. | + | |
+ | ===How to use=== | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | //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); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ===org.csdgn.maru.util.KohonenMap=== | ||
<syntaxhighlight> | <syntaxhighlight> | ||
− | package org.csdgn. | + | package org.csdgn.maru.util; |
import java.util.Random; | import java.util.Random; | ||
Line 17: | 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> |
* | * | ||
− | * | + | * Train The Map<br> |
+ | * findInputBMU(double[])<br> | ||
+ | * train(double[])<br><br> | ||
+ | * Find Output<br> | ||
+ | * findInputBMU(double[])<br> | ||
+ | * getOutput() | ||
* | * | ||
− | |||
− | |||
*/ | */ | ||
public class KohonenMap { | public class KohonenMap { | ||
− | |||
− | |||
/** | /** | ||
* Holds the neighborhood layout; | * Holds the neighborhood layout; | ||
Line 35: | Line 83: | ||
private Density density; | private Density density; | ||
private Distance 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 | + | * @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 (1D only) | + | * dimensional map, each dimension having 10 nodes. Total nodes |
− | * @param output The length of the output vector (1D 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]; | ||
Line 54: | Line 111: | ||
this.density = new Density.Simple(); | this.density = new Density.Simple(); | ||
this.distance = new Distance.EulerSq(); | 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); | ||
Line 63: | Line 121: | ||
/* 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 75: | Line 133: | ||
* Initializes the map to random values | * Initializes the map to random values | ||
*/ | */ | ||
− | public | + | public void initialize() { |
Random r = new Random(); | Random r = new Random(); | ||
initialize(r); | initialize(r); | ||
Line 81: | Line 139: | ||
/** | /** | ||
− | * Initializes the map with the given random function. | + | * Initializes the map with the given random function. Uses the nextDouble |
− | * | + | * function. |
*/ | */ | ||
− | public | + | 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(); |
} | } | ||
} | } | ||
Line 95: | Line 153: | ||
/** | /** | ||
* 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 | + | 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.distance(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 114: | Line 173: | ||
/** | /** | ||
* 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 | + | 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.distance(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 131: | Line 191: | ||
/** | /** | ||
* 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 | + | 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.distance(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 148: | Line 209: | ||
/** | /** | ||
* 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 | + | 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.distance(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 165: | Line 227: | ||
/** | /** | ||
* Sets the Matched index to the set value. | * Sets the Matched index to the set value. | ||
+ | * | ||
* @param index | * @param index | ||
*/ | */ | ||
− | public | + | 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 | + | public double[] getInput() { |
return this.map[BMU].input; | return this.map[BMU].input; | ||
} | } | ||
Line 181: | Line 245: | ||
/** | /** | ||
* 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 | + | public double[] getOutput() { |
return this.map[BMU].output; | return this.map[BMU].output; | ||
} | } | ||
Line 189: | Line 254: | ||
/** | /** | ||
* 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | public double getLearningRate() { |
return learningRate; | return learningRate; | ||
} | } | ||
Line 226: | Line 296: | ||
* Sets the map to wrap its updates (slightly more costly) | * Sets the map to wrap its updates (slightly more costly) | ||
*/ | */ | ||
− | public | + | public void setWraps(boolean doesWrap) { |
− | wrap = | + | wrap = doesWrap; |
} | } | ||
/** | /** | ||
* Returns if the current map wraps | * Returns if the current map wraps | ||
+ | * | ||
* @return | * @return | ||
*/ | */ | ||
− | public | + | public boolean isWrapping() { |
return wrap; | return wrap; | ||
} | } | ||
/** | /** | ||
− | * | + | * Gets the current cutoff density. |
− | |||
− | |||
*/ | */ | ||
− | public | + | 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; | this.density = func; | ||
} | } | ||
Line 251: | Line 339: | ||
* 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 | + | public void setDistanceFunction(Distance func) { |
this.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 | + | * Updates the map with the given data. Uses the last found BMU or WMU. |
− | + | * | |
− | * @param input input vector | + | * @param input |
− | * @param output expected output vector | + | * input vector |
+ | * @param output | ||
+ | * expected output vector | ||
*/ | */ | ||
− | public | + | 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 { | |
− | |||
− | |||
− | private | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
/** Location in the neighborhood */ | /** Location in the neighborhood */ | ||
private final int[] position; | private final int[] position; | ||
Line 296: | Line 383: | ||
} | } | ||
− | private | + | private double train(double c, double t, double n) { |
return c + n * (t - c) * learningRate; | return c + n * (t - c) * learningRate; | ||
} | } | ||
− | private | + | 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; | ||
} | } | ||
Line 318: | Line 408: | ||
/* 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) | + | for (int i = 0; i < input.length; ++i) |
− | input[i] = | + | input[i] = train(input[i], in[i], neighborhood); |
− | for(int i=0; i<output.length; ++i) | + | for (int i = 0; i < output.length; ++i) |
− | output[i] = | + | output[i] = train(output[i], out[i], neighborhood); |
} | } | ||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | public static class | + | public static abstract class Density { |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
/** | /** | ||
− | * | + | * Calculates the density at the given point, where x is a certain distance from the center of the distribution. |
*/ | */ | ||
− | @Override | + | public abstract double density(double x); |
− | public 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]; | |
− | public | + | 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)); | |
− | + | } | |
} | } | ||
} | } | ||
} | } | ||
</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));
}
}
}
}