jsat.linear.distancemetrics

Class JaccardDistance

java.lang.Object

jsat.linear.distancemetrics.JaccardDistance

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, KernelTrick, DistanceMetric, Parameterized

public class JaccardDistance
extends java.lang.Object
implements DistanceMetric, KernelTrick

This class implements both the weighted Jaccard Distance and the standard Jaccard distance. If a input is given with only binary 0 or 1 values, the weighted Jaccard is equivalent to the un-weighted version.
For the weighted Jaccard version, all values less than or equal to zero will be treated as zero. For the unweighted versions, all non-zero values will behave as if their value is 1.0.
The Jaccard Distance and similarity are intertwined, and so this method is both a distance metric and kernel trick.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
JaccardDistance() Creates a new Weighted Jaccard distance / similarity
JaccardDistance(boolean weighted) Creates a new Jaccard similarity, which can be weighted or unweighted.

Method Summary

Modifier and Type	Method and Description
void	addToCache(Vec newVec, java.util.List<java.lang.Double> cache) Appends the new cache values for the given vector to the list of cache values.
JaccardDistance	clone()
double	dist(Vec a, Vec b) Computes the distance between 2 vectors.
double	eval(int a, int b, java.util.List<? extends Vec> trainingSet, java.util.List<java.lang.Double> cache) Produces the correct kernel evaluation given the training set and the cache generated by KernelTrick.getAccelerationCache(List).
double	eval(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 kernel product between one vector in the original list of vectors with that of another vector not from the original list, but had information generated by KernelTrick.getQueryInfo(jsat.linear.Vec).
double	eval(Vec a, Vec b) Evaluate this kernel function for the two given vectors.
double	evalSum(java.util.List<? extends Vec> finalSet, java.util.List<java.lang.Double> cache, double[] alpha, Vec y, int start, int end) Performs an efficient summation of kernel products of the form ∑ αi k(xi, y) where x are the final set of vectors, and α the associated scalar multipliers
double	evalSum(java.util.List<? extends Vec> finalSet, java.util.List<java.lang.Double> cache, double[] alpha, Vec y, java.util.List<java.lang.Double> qi, int start, int end) Performs an efficient summation of kernel products of the form ∑ αi k(xi, y) where x are the final set of vectors, and α the associated scalar multipliers
java.util.List<java.lang.Double>	getAccelerationCache(java.util.List<? extends Vec> trainingSet) Returns a cache of double values associated with the given list of vectors in the given order.
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 DistanceMetric.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)
double	metricBound() All metrics must return values greater than or equal to 0.
boolean	normalized() This method indicates if a kernel is a normalized kernel or not.
boolean	supportsAcceleration() Indicates if this distance metric supports building an acceleration cache using the DistanceMetric.getAccelerationCache(java.util.List) and associated distance methods.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jsat.linear.distancemetrics.DistanceMetric

dist, dist, dist, getAccelerationCache, isValidMetric, toString

Methods inherited from interface jsat.distributions.kernels.KernelTrick

toString

Methods inherited from interface jsat.parameters.Parameterized

getParameter, getParameters

Constructor Detail

JaccardDistance

public JaccardDistance(boolean weighted)

Creates a new Jaccard similarity, which can be weighted or unweighted.

Parameters:

weighted - true to use the weighted Jaccard, false otherwise.

JaccardDistance

public JaccardDistance()

Creates a new Weighted Jaccard distance / similarity

Method Detail

dist

public double dist(Vec a,
                   Vec b)

Description copied from interface: DistanceMetric

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.

Specified by:

dist in interface DistanceMetric

Parameters:

a - the first vector

b - the second vector

Returns:

the distance between them

isSymmetric

public boolean isSymmetric()

Description copied from interface: DistanceMetric

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

Specified by:

isSymmetric in interface DistanceMetric

Returns:

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

isSubadditive

public boolean isSubadditive()

Description copied from interface: DistanceMetric

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)

Specified by:

isSubadditive in interface DistanceMetric

Returns:

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

isIndiscemible

public boolean isIndiscemible()

Description copied from interface: DistanceMetric

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

Specified by:

isIndiscemible in interface DistanceMetric

Returns:

true if this distance metric is indicemible, false otherwise.

metricBound

public double metricBound()

Description copied from interface: DistanceMetric

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.

Specified by:

metricBound in interface DistanceMetric

Returns:

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

supportsAcceleration

public boolean supportsAcceleration()

Description copied from interface: DistanceMetric

Indicates if this distance metric supports building an acceleration cache using the DistanceMetric.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 DistanceMetric.dist(int, jsat.linear.Vec, java.util.List, java.util.List) and DistanceMetric.dist(int, int, java.util.List, java.util.List) to perform distance computations.

Specified by:

supportsAcceleration in interface KernelTrick

Specified by:

supportsAcceleration in interface DistanceMetric

Returns:

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

getQueryInfo

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

Description copied from interface: DistanceMetric

Pre computes query information that would have be generated if the query was a member of the original list of vectors when calling DistanceMetric.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.

Specified by:

getQueryInfo in interface KernelTrick

Specified by:

getQueryInfo in interface DistanceMetric

Parameters:

q - the query point to generate cache information for

Returns:

the cache information for the query point

eval

public double eval(Vec a,
                   Vec b)

Description copied from interface: KernelTrick

Evaluate this kernel function for the two given vectors.

Specified by:

eval in interface KernelTrick

Parameters:

a - the first vector

b - the first vector

Returns:

the evaluation

clone

public JaccardDistance clone()

Specified by:

clone in interface KernelTrick

Specified by:

clone in interface DistanceMetric

Overrides:

clone in class java.lang.Object

addToCache

public void addToCache(Vec newVec,
                       java.util.List<java.lang.Double> cache)

Description copied from interface: KernelTrick

Appends the new cache values for the given vector to the list of cache values. This method is present for online style kernel learning algorithms, where the set of vectors is not known in advance. When a vector is added to the set of kernel vectors, its cache values can be added using this method.

The results of calling this sequentially on a lit of vectors starting with an empty double list is equivalent to getting the results from calling KernelTrick.getAccelerationCache(java.util.List)

If this kernel does not support acceleration, this method call will function as a nop.

Specified by:

addToCache in interface KernelTrick

Parameters:

newVec - the new vector to add to the cache values

cache - the original list of cache values to add to

eval

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

Description copied from interface: KernelTrick

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

Specified by:

eval in interface KernelTrick

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 kernel product of the two vectors

eval

public double eval(int a,
                   int b,
                   java.util.List<? extends Vec> trainingSet,
                   java.util.List<java.lang.Double> cache)

Description copied from interface: KernelTrick

Produces the correct kernel evaluation given the training set and the cache generated by KernelTrick.getAccelerationCache(List). The training vectors should be in the same order.

Specified by:

eval in interface KernelTrick

Parameters:

a - the index of the first training vector

b - the index of the second training vector

trainingSet - the list of training set vectors

cache - the double list of cache values generated by this kernel for the given training set

Returns:

the same kernel evaluation result as KernelTrick.eval(jsat.linear.Vec, jsat.linear.Vec)

evalSum

public double evalSum(java.util.List<? extends Vec> finalSet,
                      java.util.List<java.lang.Double> cache,
                      double[] alpha,
                      Vec y,
                      int start,
                      int end)

Description copied from interface: KernelTrick

Performs an efficient summation of kernel products of the form
∑ α_i k(x_i, y)
where x are the final set of vectors, and α the associated scalar multipliers

Specified by:

evalSum in interface KernelTrick

Parameters:

finalSet - the final set of vectors

cache - the cache associated with the final set of vectors

alpha - the coefficients associated with each vector

y - the vector to perform the summed kernel products against

start - the starting index (inclusive) to sum from

end - the ending index (exclusive) to sum from

Returns:

the sum of the multiplied kernel products

evalSum

public double evalSum(java.util.List<? extends Vec> finalSet,
                      java.util.List<java.lang.Double> cache,
                      double[] alpha,
                      Vec y,
                      java.util.List<java.lang.Double> qi,
                      int start,
                      int end)

Description copied from interface: KernelTrick

Performs an efficient summation of kernel products of the form
∑ α_i k(x_i, y)
where x are the final set of vectors, and α the associated scalar multipliers

Specified by:

evalSum in interface KernelTrick

Parameters:

finalSet - the final set of vectors

cache - the cache associated with the final set of vectors

alpha - the coefficients associated with each vector

y - the vector to perform the summed kernel products against

qi - the query information about y

start - the starting index (inclusive) to sum from

end - the ending index (exclusive) to sum from

Returns:

the sum of the multiplied kernel products

normalized

public boolean normalized()

Description copied from interface: KernelTrick

This method indicates if a kernel is a normalized kernel or not. A normalized kernel is one in which k(x,x) = 1 for the same object, and no value greater than 1 can be returned.

Specified by:

normalized in interface KernelTrick

Returns:

true if this is a normalized kernel. false otherwise.

getAccelerationCache

public java.util.List<java.lang.Double> getAccelerationCache(java.util.List<? extends Vec> trainingSet)

Description copied from interface: DistanceMetric

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.

Specified by:

getAccelerationCache in interface KernelTrick

Specified by:

getAccelerationCache in interface DistanceMetric

Parameters:

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

Returns:

the list of double for the cache