/*
* Copyright (C) 2015 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.datatransform.visualization;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.DataPoint;
import jsat.linear.DenseMatrix;
import jsat.linear.Matrix;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.math.OnLineStatistics;
import jsat.utils.FakeExecutor;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
import jsat.utils.random.XORWOW;
/**
* Multidimensional scaling is an algorithm for finding low dimensional
* embeddings of arbitrary distance matrices. MDS will attempt to find an
* embedding that maintains the same pair-wise distances between all items in
* the distance matrix. MDS is a non-convex problem, so different runs can
* produce different results.
*
* MDS can be used on arbitrary dissimilarity matrices by calling {@link #transform(jsat.linear.Matrix, java.util.concurrent.ExecutorService)
* }.
*
* @author Edward Raff
*/
public class MDS implements VisualizationTransform
{
private static DistanceMetric embedMetric = new EuclideanDistance();
private DistanceMetric dm = new EuclideanDistance();
private double tolerance = 1e-3;
private int maxIterations = 300;
private int targetSize = 2;
/**
* Sets the tolerance parameter for determining convergence.
* @param tolerance the tolerance for declaring convergence
*/
public void setTolerance(double tolerance)
{
if(tolerance < 0 || Double.isInfinite(tolerance) || Double.isNaN(tolerance))
throw new IllegalArgumentException("tolerance must be a non-negative value, not " + tolerance);
this.tolerance = tolerance;
}
/**
*
* @return the tolerance parameter
*/
public double getTolerance()
{
return tolerance;
}
/**
* Sets the distance metric to use when creating the initial dissimilarity
* matrix of a new dataset. By default the {@link EuclideanDistance Euclidean
* } distance is used, but any distance may be substituted.The chosen
* distance need not be a valid metric, its only requirement is symmetry.
*
* @param embedMetric the distance metric to use when creating the
* dissimilarity matrix.
*/
public void setEmbeddingMetric(DistanceMetric embedMetric)
{
this.embedMetric = embedMetric;
}
/**
*
* @return the distance metric used when creating a dissimilarity matrix
*/
public DistanceMetric getEmbeddingMetric()
{
return embedMetric;
}
@Override
public Type transform(final DataSet d, boolean parallel)
{
final List orig_vecs = d.getDataVectors();
final List orig_distCache = dm.getAccelerationCache(orig_vecs, parallel);
final int N = orig_vecs.size();
//Delta is the true disimilarity matrix
final Matrix delta = new DenseMatrix(N, N);
OnLineStatistics avg = ParallelUtils.run(parallel, N, (i)->
{
OnLineStatistics local_avg = new OnLineStatistics();
for(int j = i+1; j < d.getSampleSize(); j++)
{
double dist = dm.dist(i, j, orig_vecs, orig_distCache);
local_avg.add(dist);
delta.set(i, j, dist);
delta.set(j, i, dist);
}
return local_avg;
}, (a,b)->OnLineStatistics.add(a, b));
SimpleDataSet embeded = transform(delta, parallel);
//place the solution in a dataset of the correct type
DataSet transformed = d.shallowClone();
transformed.replaceNumericFeatures(embeded.getDataVectors());
return (Type) transformed;
}
public SimpleDataSet transform(Matrix delta)
{
return transform(delta, false);
}
public SimpleDataSet transform(final Matrix delta, boolean parallel)
{
final int N = delta.rows();
Random rand = RandomUtil.getRandom();
final Matrix X = new DenseMatrix(N, targetSize);
final List X_views = new ArrayList<>();
for(int i = 0; i < N; i++)
{
for(int j = 0; j < targetSize; j++)
X.set(i, j, rand.nextDouble());
X_views.add(X.getRowView(i));
}
final List X_rowCache = embedMetric.getAccelerationCache(X_views, parallel);
//TODO, special case solution when all weights are the same, want to add general case as well
Matrix V_inv = new DenseMatrix(N, N);
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
if(i == j)
V_inv.set(i, j, (1.0-1.0/N)/N);
else
V_inv.set(i, j, (0.0-1.0/N)/N);
}
double stressChange = Double.POSITIVE_INFINITY;
double oldStress = stress(X_views, X_rowCache, delta, parallel);
//the gutman transform matrix
final Matrix B = new DenseMatrix(N, N);
final Matrix X_new = new DenseMatrix(X.rows(), X.cols());
for(int iter = 0; iter < maxIterations && stressChange > tolerance; iter++ )
{
ParallelUtils.run(parallel, B.rows(), (i)->
{
for (int j = i + 1; j < B.rows(); j++)
{
double d_ij = embedMetric.dist(i, j, X_views, X_rowCache);
if(d_ij > 1e-5)//avoid creating silly huge values
{
double b_ij = -delta.get(i, j)/d_ij;//-w_ij if we support weights in the future
B.set(i, j, b_ij);
B.set(j, i, b_ij);
}
else
{
B.set(i, j, 0);
B.set(j, i, 0);
}
}
});
X_new.zeroOut();
//set the diagonal values
for(int i = 0; i < B.rows(); i++)
{
B.set(i, i, 0);
for (int k = 0; k < B.cols(); k++)
if (k != i)
B.increment(i, i, -B.get(i, k));
}
// Matrix X_new = V_inv.multiply(B, ex).multiply(X, ex);
B.multiply(X, X_new, ParallelUtils.CACHED_THREAD_POOL);
X_new.mutableMultiply(1.0/N);
X_new.copyTo(X);
X_rowCache.clear();
X_rowCache.addAll(embedMetric.getAccelerationCache(X_views, parallel));
double newStress = stress(X_views, X_rowCache, delta, parallel);
stressChange = Math.abs(oldStress-newStress);
oldStress = newStress;
}
SimpleDataSet sds = new SimpleDataSet(new CategoricalData[0], targetSize);
for(Vec v : X_views)
sds.add(new DataPoint(v));
return sds;
}
private static double stress(final List X_views, final List X_rowCache, final Matrix delta, boolean parallel)
{
return ParallelUtils.run(parallel, delta.rows(), (i)->
{
double localStress = 0;
for(int j = i+1; j < delta.rows(); j++)
{
double tmp = embedMetric.dist(i, j, X_views, X_rowCache)-delta.get(i, j);
localStress += tmp*tmp;
}
return localStress;
}, (a,b)->a+b);
}
@Override
public int getTargetDimension()
{
return targetSize;
}
@Override
public boolean setTargetDimension(int target)
{
if(target < 1)
return false;
this.targetSize = target;
return true;
}
}
Ads help maintain this website.