/*
* 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.Arrays;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.linear.*;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.utils.FakeExecutor;
import jsat.utils.FibHeap;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;
/**
* Isomap is an extension of {@link MDS}. It uses a geodesic distance made from
* a nearest neighbor search of all the points in the data set. This
* implementation also includes the extension
* {@link #setCIsomap(boolean) C-Isomap}, which further weights distances by
* density.
*
* Note, that Isomap normally will fail on some datasets when two or more
* regions can not be connected in the induced neighbor graph. While increasing
* the number of neighbors considered will eventually resolve this problem, the
* separated groups may be desirable in practice. This implementation includes a
* non-standard addition that will forcibly connect such isolated regions with
* very large values, hoping to preserve the farther distances in the given
* dataset while maintaining local structure.
*
*
* See:
*
* - Tenenbaum, J. B., Silva, V. De, & Langford, J. C. (2000). A Global
* Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290,
* 2319–2323. doi:10.1126/science.290.5500.2319
* - De Silva, V., & Tenenbaum, J. B. (2003). Global Versus Local Methods
* in Nonlinear Dimensionality Reduction. In Advances in Neural Information
* Processing Systems 15 (pp. 705–712). MIT Press. Retrieved from
* here
*
*
* @author Edward Raff
*/
public class Isomap implements VisualizationTransform
{
private DistanceMetric dm = new EuclideanDistance();
private VectorCollection> vc = new DefaultVectorCollection<>();
private int searchNeighbors = 15;
private MDS mds = new MDS();
private boolean c_isomap = false;
/**
*
*/
public Isomap()
{
this(15, false);
}
/**
*
* @param searchNeighbors the number of nearest neighbors to consider
*/
public Isomap(int searchNeighbors)
{
this(searchNeighbors, false);
}
/**
*
* @param searchNeighbors the number of nearest neighbors to consider
* @param c_isomap {@code true} to use the C-Isomap extension, {@code false}
* for normal Isomap.
*/
public Isomap(int searchNeighbors, boolean c_isomap)
{
setNeighbors(searchNeighbors);
setCIsomap(c_isomap);
}
/**
* Set the number of neighbors to consider for the initial graph in Isomap
* @param searchNeighbors the number of nearest neighbors to consider
*/
public void setNeighbors(int searchNeighbors)
{
if(searchNeighbors < 2)
throw new IllegalArgumentException("number of neighbors considered must be at least 2, not " + searchNeighbors);
this.searchNeighbors = searchNeighbors;
}
/**
*
* @return the number of neighbors used when creating the initial graph
*/
public int getNeighbors()
{
return searchNeighbors;
}
/**
* Controls whether the C-Isomap extension is used. If set true, the initial
* distances will also be scaled based on the density of the region between
* the points. If false, normal Isomap will be used.
*
* @param c_isomap {@code true} to use the C-Isomap extension, {@code false}
* for normal Isomap.
*/
public void setCIsomap(boolean c_isomap)
{
this.c_isomap = c_isomap;
}
/**
*
* @return {@code true} if the C-Isomap extension is in use, {@code false}
* for normal Isomap.
*/
public boolean isCIsomap()
{
return c_isomap;
}
@Override
public Type transform(DataSet d, boolean parallel)
{
final int N = d.getSampleSize();
final Matrix delta = new DenseMatrix(N, N);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (i == j)
delta.set(i, j, 0);
else
delta.set(i, j, Double.MAX_VALUE);
final List> vecs = new ArrayList<>(N);
for(int i = 0; i < N; i++)
vecs.add(new VecPaired<>(d.getDataPoint(i).getNumericalValues(), i));
vc.build(parallel, vecs, dm);
final List cache = dm.getAccelerationCache(vecs, parallel);
final int knn = searchNeighbors+1;//+1 b/c we are closest to ourselves
//bleh, ugly generics...
final List, Double>>> neighborGraph = new ArrayList<>();
for (int i = 0; i < N; i++)
neighborGraph.add(null);
final double[] avgNeighborDist = new double[N];
//do knn search and store results so we can do distances
ParallelUtils.run(parallel, N, (i)->
{
List extends VecPaired, Double>> neighbors = vc.search(vecs.get(i).getVector(), knn);
neighborGraph.set(i, neighbors);
//Compute stats that may be used for c-isomap version
for (int z = 1; z < neighbors.size(); z++)
{
VecPaired, Double> neighbor = neighbors.get(z);
double dist = neighbor.getPair();
avgNeighborDist[i] += dist;
}
avgNeighborDist[i] /= (neighbors.size()-1);
});
if(c_isomap)
{
int i = 0;
for(List extends VecPaired, Double>> neighbors : neighborGraph)
{
for(VecPaired, Double> neighbor : neighbors)
neighbor.setPair(neighbor.getPair()/Math.sqrt(avgNeighborDist[neighbor.getVector().getPair()]+avgNeighborDist[i]+1e-6));
i++;
}
}
ParallelUtils.run(parallel, N, (k)->
{
double[] tmp_dist = dijkstra(neighborGraph, k);
for (int i = 0; i < N; i++)
{
tmp_dist[i] = Math.min(tmp_dist[i], delta.get(k, i));
delta.set(i, k, tmp_dist[i]);
delta.set(k, i, tmp_dist[i]);
}
});
//lets check for any disjoint groupings, replace them with something reasonable
//we will use the largest obtainable distance to be an offset for our infinity distances
double largest_natural_dist_tmp = 0;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
if(delta.get(i, j) < Double.MAX_VALUE)
largest_natural_dist_tmp = Math.max(largest_natural_dist_tmp, delta.get(i, j));
final double largest_natural_dist = largest_natural_dist_tmp;
ParallelUtils.run(parallel, N, (i)->
{
for (int j = i + 1; j < N; j++)
{
double d_ij = delta.get(i, j);
if (d_ij >= Double.MAX_VALUE)//replace with the normal distance + 1 order of magnitude?
{
d_ij = 10*dm.dist(i, j, vecs, cache)+1.5*largest_natural_dist;
delta.set(i, j, d_ij);
delta.set(j, i, d_ij);
}
}
});
SimpleDataSet emedded = mds.transform(delta, parallel);
DataSet transformed = d.shallowClone();
transformed.replaceNumericFeatures(emedded.getDataVectors());
return (Type) transformed;
}
private double[] dijkstra(List, Double>>> neighborGraph, int sourceIndex)
{
//TODO generalize and move this out into some other class as a static method
final int N = neighborGraph.size();
double[] dist = new double[N];
Arrays.fill(dist, Double.POSITIVE_INFINITY);
dist[sourceIndex] = 0;
List> nodes = new ArrayList<>(N);
FibHeap Q = new FibHeap<>();
for (int i = 0; i < N; i++)
nodes.add(null);
nodes.set(sourceIndex, Q.insert(sourceIndex, dist[sourceIndex]));
while (Q.size() > 0)
{
FibHeap.FibNode u = Q.removeMin();
int u_indx = u.getValue();
List extends VecPaired, Double>> neighbors = neighborGraph.get(u_indx);
for (int z = 1; z < neighbors.size(); z++)
{
VecPaired, Double> neighbor = neighbors.get(z);
int j = neighbor.getVector().getPair();
double u_j_dist = neighbor.getPair();
double alt = dist[u_indx] + u_j_dist;
if (alt < dist[j])
{
dist[j] = alt;
//prev[j] ← u
if(nodes.get(j) == null)
nodes.set(j, Q.insert(j, alt));
else
Q.decreaseKey(nodes.get(j), alt);
}
}
}
return dist;
}
@Override
public int getTargetDimension()
{
return mds.getTargetDimension();
}
@Override
public boolean setTargetDimension(int target)
{
return mds.setTargetDimension(target);
}
}
Ads help maintain this website.