jsat.linear.distancemetrics

Interface DistanceMetric

All Superinterfaces:

java.lang.Cloneable, java.io.Serializable

All Known Subinterfaces:

DenseSparseMetric

All Known Implementing Classes:

ChebyshevDistance, CosineDistance, CosineDistanceNormalized, DistanceCounter, EuclideanDistance, JaccardDistance, KernelDistance, MahalanobisDistance, ManhattanDistance, MinkowskiDistance, NormalizedEuclideanDistance, PearsonDistance, SquaredEuclideanDistance, TrainableDistanceMetric, WeightedEuclideanDistance

public interface DistanceMetric
extends java.lang.Cloneable, java.io.Serializable

A distance metric defines the distance between two points in a metric space. There are three necessary properties for a metric to be valid, symmetry, indisceribility, and the triangle inequality . A metric that does not meet all, (or none) or these properties is called a pseudo-metric. Many learning algorithms rely on these properties to accelerate computations, though may not need all the properties to hold.

A metric may support the use of a list of pre-computed information to accelerate distance computations between points, which can be checked using the supportsAcceleration() method. The associated methods are defined such that the cache calls can be used in a seamless way that will automatically invoke the caching behavior when supported. Simply initiate with
List<Double> distCache = dm.getAccelerationCache(vecList);
to initiate the cache, if not supported - null will be returned, which is allowed when calling
double dist = dm.dist(indx1, indx2, vecList, distCache);
Null is used as a special case for distCache, at which point the implementation will call the standard dist(jsat.linear.Vec, jsat.linear.Vec) using the list and indices. The other cache accelerated methods behave in the same way, including getQueryInfo(jsat.linear.Vec)
Using this set up, no branching or special case code is necessary to automatically use the acceleration capabilities of supported distance metrics.

Method Summary

Modifier and Type	Method and Description
DistanceMetric	clone()
default double	dist(int a, int b, java.util.List<? extends Vec> vecs, java.util.List<java.lang.Double> cache) Computes the distance between 2 vectors in the original list of vectors.
default double	dist(int a, Vec b, java.util.List<? extends Vec> vecs, java.util.List<java.lang.Double> cache) Computes the distance between one vector in the original list of vectors with that of another vector not from the original list.
default double	dist(int a, Vec b, java.util.List<java.lang.Double> qi, java.util.List<? extends Vec> vecs, java.util.List<java.lang.Double> cache) Computes the distance between one vector in the original list of vectors with that of another vector not from the original list, but had information generated by getQueryInfo(jsat.linear.Vec).
double	dist(Vec a, Vec b) Computes the distance between 2 vectors.
default java.util.List<java.lang.Double>	getAccelerationCache(java.util.List<? extends Vec> vecs) Returns a cache of double values associated with the given list of vectors in the given order.
default java.util.List<java.lang.Double>	getAccelerationCache(java.util.List<? extends Vec> vecs, boolean parallel) Returns a cache of double values associated with the given list of vectors in the given order.
default java.util.List<java.lang.Double>	getQueryInfo(Vec q) Pre computes query information that would have be generated if the query was a member of the original list of vectors when calling getAccelerationCache(java.util.List) .
boolean	isIndiscemible() Returns true if this distance metric obeys the rule that, for any x and y ∈ S d(x, y) = 0 if and only if x = y
boolean	isSubadditive() Returns true if this distance metric obeys the rule that, for any x, y, and z ∈ S d(x, z) ≤ d(x, y) + d(y, z)
boolean	isSymmetric() Returns true if this distance metric obeys the rule that, for any x, y, and z ∈ S d(x, y) = d(y, x)
default boolean	isValidMetric() Returns true if this distance method obeys all the rules required to be a valid metric.
double	metricBound() All metrics must return values greater than or equal to 0.
default boolean	supportsAcceleration() Indicates if this distance metric supports building an acceleration cache using the getAccelerationCache(java.util.List) and associated distance methods.
java.lang.String	toString() Returns a descriptive name of the Distance Metric in use

Method Detail

dist

double dist(Vec a,
            Vec b)

Computes the distance between 2 vectors. The smaller the value, the closer, and there for, more similar, the vectors are. 0 indicates the vectors are the same.

Parameters:

a - the first vector

b - the second vector

Returns:

the distance between them

isSymmetric

boolean isSymmetric()

Returns true if this distance metric obeys the rule that, for any x, y, and z ∈ S
d(x, y) = d(y, x)

Returns:

true if this distance metric is symmetric, false if it is not

isSubadditive

boolean isSubadditive()

Returns true if this distance metric obeys the rule that, for any x, y, and z ∈ S
d(x, z) ≤ d(x, y) + d(y, z)

Returns:

true if this distance metric supports the triangle inequality, false if it does not.

isIndiscemible

boolean isIndiscemible()

Returns true if this distance metric obeys the rule that, for any x and y ∈ S
d(x, y) = 0 if and only if x = y

Returns:

true if this distance metric is indicemible, false otherwise.

isValidMetric

default boolean isValidMetric()

Returns true if this distance method obeys all the rules required to be a valid metric.

Returns:

true if this distance method obeys all the rules required to be a valid metric.

metricBound

double metricBound()

All metrics must return values greater than or equal to 0. The upper bound on the value returned is different for different metrics. This method returns the theoretical maximal value that could be returned by this distance metric. That means Double.POSITIVE_INFINITY is a valid return value.

Returns:

the maximal distance for any two points in that could exist by this distance metric.

supportsAcceleration

default boolean supportsAcceleration()

Indicates if this distance metric supports building an acceleration cache using the getAccelerationCache(java.util.List) and associated distance methods. By default this method will return false. If true, then a cache can be obtained from this distance metric and used in conjunction with dist(int, jsat.linear.Vec, java.util.List, java.util.List) and dist(int, int, java.util.List, java.util.List) to perform distance computations.

Returns:

true if cache acceleration is supported for this metric, false otherwise.

getAccelerationCache

default java.util.List<java.lang.Double> getAccelerationCache(java.util.List<? extends Vec> vecs)

Returns a cache of double values associated with the given list of vectors in the given order. This can be used by the distance metric to increase runtime at the cost of memory. This is an optional method.
If this metric does not support acceleration, null will be returned.

Parameters:

vecs - the list of vectors to build an acceleration cache for

Returns:

the list of double for the cache

getAccelerationCache

default java.util.List<java.lang.Double> getAccelerationCache(java.util.List<? extends Vec> vecs,
                                                              boolean parallel)

Returns a cache of double values associated with the given list of vectors in the given order. This can be used by the distance metric to increase runtime at the cost of memory. This is an optional method.
If this metric does not support acceleration, null will be returned.

Parameters:

vecs - the list of vectors to build an acceleration cache for

parallel - true if multiple threads should be used to perform clustering. false if it should be done in a single threaded manner.

Returns:

the list of double for the cache

dist

default double dist(int a,
                    int b,
                    java.util.List<? extends Vec> vecs,
                    java.util.List<java.lang.Double> cache)

Computes the distance between 2 vectors in the original list of vectors.
If the cache input is null, then dist(jsat.linear.Vec, jsat.linear.Vec) will be called directly.

Parameters:

a - the index of the first vector

b - the index of the second vector

vecs - the list of vectors used to build the cache

cache - the cache associated with the given list of vectors

Returns:

the distance between the two vectors

dist

default double dist(int a,
                    Vec b,
                    java.util.List<? extends Vec> vecs,
                    java.util.List<java.lang.Double> cache)

Computes the distance between one vector in the original list of vectors with that of another vector not from the original list.
If the cache input is null, then dist(jsat.linear.Vec, jsat.linear.Vec) will be called directly.

Parameters:

a - the index of the vector in the cache

b - the other vector

vecs - the list of vectors used to build the cache

cache - the cache associated with the given list of vectors

Returns:

the distance between the two vectors

getQueryInfo

default java.util.List<java.lang.Double> getQueryInfo(Vec q)

Pre computes query information that would have be generated if the query was a member of the original list of vectors when calling getAccelerationCache(java.util.List) . This can then be used if a large number of distance computations are going to be done against points in the original set for a point that is outside the original space.

If this metric does not support acceleration, null will be returned.

Parameters:

q - the query point to generate cache information for

Returns:

the cache information for the query point

dist

default double dist(int a,
                    Vec b,
                    java.util.List<java.lang.Double> qi,
                    java.util.List<? extends Vec> vecs,
                    java.util.List<java.lang.Double> cache)

Computes the distance between one vector in the original list of vectors with that of another vector not from the original list, but had information generated by getQueryInfo(jsat.linear.Vec).
If the cache input is null, then dist(jsat.linear.Vec, jsat.linear.Vec) will be called directly.

Parameters:

a - the index of the vector in the cache

b - the other vector

qi - the query information about b

vecs - the list of vectors used to build the cache

cache - the cache associated with the given list of vectors

Returns:

the distance between the two vectors

toString

java.lang.String toString()

Returns a descriptive name of the Distance Metric in use

Overrides:

toString in class java.lang.Object

Returns:

the name of this metric

clone

DistanceMetric clone()