001/** 002 * Copyright (c) 2011, The University of Southampton and the individual contributors. 003 * All rights reserved. 004 * 005 * Redistribution and use in source and binary forms, with or without modification, 006 * are permitted provided that the following conditions are met: 007 * 008 * * Redistributions of source code must retain the above copyright notice, 009 * this list of conditions and the following disclaimer. 010 * 011 * * Redistributions in binary form must reproduce the above copyright notice, 012 * this list of conditions and the following disclaimer in the documentation 013 * and/or other materials provided with the distribution. 014 * 015 * * Neither the name of the University of Southampton nor the names of its 016 * contributors may be used to endorse or promote products derived from this 017 * software without specific prior written permission. 018 * 019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package org.openimaj.math.matrix.similarity.processor; 031 032import java.util.ArrayList; 033import java.util.List; 034import java.util.Random; 035 036import org.openimaj.math.geometry.line.Line2d; 037import org.openimaj.math.geometry.point.Point2d; 038import org.openimaj.math.geometry.point.Point2dImpl; 039import org.openimaj.math.matrix.similarity.SimilarityMatrix; 040import org.openimaj.util.pair.IndependentPair; 041 042/** 043 * Implementation of Multidimensional Scaling. 044 * <p> 045 * Implementation originally based around Toby Segaran's python code. 046 * 047 * @see "http://blog.kiwitobes.com/?p=44" 048 * 049 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 050 * 051 */ 052public class MultidimensionalScaling implements SimilarityMatrixProcessor { 053 protected Random rng = new Random(); 054 protected int numIterations = 1000; 055 protected double rate = 0.01; 056 protected List<IndependentPair<String, Point2d>> points; 057 058 /** 059 * Default constructor. Sets the learning rate at 0.01 and the maximum 060 * number of iterations to 1000. 061 */ 062 public MultidimensionalScaling() { 063 // do nothing 064 } 065 066 /** 067 * Construct with the given random number generator and default learning 068 * rate at 0.01 and the maximum number of iterations to 1000. 069 * 070 * @param rng 071 * the random number generator 072 */ 073 public MultidimensionalScaling(Random rng) { 074 this.rng = rng; 075 } 076 077 /** 078 * Construct MDS with the given maximum number of iterations and rate. 079 * 080 * @param numIterations 081 * number of iterations 082 * @param rate 083 * learning rate 084 */ 085 public MultidimensionalScaling(int numIterations, double rate) { 086 this.numIterations = numIterations; 087 this.rate = rate; 088 } 089 090 /** 091 * Construct MDS with the given maximum number of iterations, rate and 092 * random number generator. 093 * 094 * @param numIterations 095 * number of iterations 096 * @param rate 097 * learning rate 098 * @param rng 099 * the random number generator 100 */ 101 public MultidimensionalScaling(int numIterations, double rate, Random rng) { 102 this.numIterations = numIterations; 103 this.rate = rate; 104 this.rng = rng; 105 } 106 107 /* 108 * (non-Javadoc) 109 * 110 * @see 111 * org.openimaj.math.matrix.similarity.processor.SimilarityMatrixProcessor 112 * #process(org.openimaj.math.matrix.similarity.SimilarityMatrix) 113 */ 114 @Override 115 public void process(SimilarityMatrix matrix) { 116 final int sz = matrix.getRowDimension(); 117 118 final double[][] realDists = matrix.process(new NormaliseData(true)).getArray(); 119 120 // initialise points randomly 121 points = new ArrayList<IndependentPair<String, Point2d>>(sz); 122 for (int i = 0; i < sz; i++) { 123 points.add(new IndependentPair<String, Point2d>(matrix.getIndexValue(i), Point2dImpl.createRandomPoint())); 124 } 125 126 final Point2dImpl[] grad = new Point2dImpl[sz]; 127 for (int i = 0; i < sz; i++) 128 grad[i] = new Point2dImpl(); 129 130 double lastError = Double.MAX_VALUE; 131 final double[][] fakeDists = new double[sz][sz]; 132 for (int m = 0; m < numIterations; m++) { 133 for (int r = 0; r < sz; r++) { 134 for (int c = r + 1; c < sz; c++) { 135 final double dist = Line2d.distance(points.get(r).secondObject(), points.get(c).secondObject()); 136 fakeDists[r][c] = dist; 137 fakeDists[c][r] = dist; 138 } 139 } 140 141 for (int i = 0; i < sz; i++) { 142 grad[i].x = 0; 143 grad[i].y = 0; 144 } 145 146 double totalError = 0; 147 for (int k = 0; k < sz; k++) { 148 for (int j = 0; j < sz; j++) { 149 if (k == j) 150 continue; 151 152 final double errorterm = (fakeDists[j][k] - realDists[j][k]) / realDists[j][k]; 153 154 grad[k].x += ((((Point2dImpl) points.get(k).secondObject()).x - points.get(j).secondObject().getX()) / fakeDists[j][k]) 155 * errorterm; 156 grad[k].y += ((((Point2dImpl) points.get(k).secondObject()).y - points.get(j).secondObject().getY()) / fakeDists[j][k]) 157 * errorterm; 158 159 totalError += Math.abs(errorterm); 160 } 161 } 162 163 if (lastError < totalError) 164 break; 165 lastError = totalError; 166 167 for (int k = 0; k < sz; k++) { 168 ((Point2dImpl) points.get(k).secondObject()).x -= rate * grad[k].x; 169 ((Point2dImpl) points.get(k).secondObject()).y -= rate * grad[k].y; 170 } 171 } 172 } 173 174 /** 175 * Get a list of the 2-D coordinates learned by the MDS algorithm for each 176 * element in the input similarity matrix. 177 * 178 * @return list of <index, point> 179 */ 180 public List<IndependentPair<String, Point2d>> getPoints() { 181 return points; 182 } 183 184 /** 185 * Get the predicted point for a specific element. 186 * 187 * @param key 188 * the element identifier 189 * @return the predicted point, or null if the key was not found. 190 */ 191 public Point2d getPoint(String key) { 192 for (final IndependentPair<String, Point2d> pair : points) 193 if (pair.firstObject().equals(key)) 194 return pair.secondObject(); 195 return null; 196 } 197 198 /* 199 * (non-Javadoc) 200 * 201 * @see java.lang.Object#toString() 202 */ 203 @Override 204 public String toString() { 205 if (points == null) 206 return super.toString(); 207 208 final StringBuilder sb = new StringBuilder(); 209 210 for (final IndependentPair<String, Point2d> pair : points) { 211 sb.append(String.format("%s\t%4.3f\t%4.3f\n", pair.firstObject(), pair.secondObject().getX(), pair 212 .secondObject().getY())); 213 } 214 215 return sb.toString(); 216 } 217}