edu.umbc.cs.maple.utils
Class MathUtils

java.lang.Object
  extended by edu.umbc.cs.maple.utils.MathUtils

public class MathUtils
extends java.lang.Object

A collection of mathematical utility functions.

Copyright (c) 2008 Eric Eaton

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 http://www.gnu.org/licenses/.

Version:
0.1
Author:
Eric Eaton (EricEaton@umbc.edu)
University of Maryland Baltimore County

Nested Class Summary
static class MathUtils.SimilarityMetric
          Defines a similarity metric measure
 
Constructor Summary
MathUtils()
           
 
Method Summary
static double[] append(double[] v1, double d)
          Appends an element to a vector.
static double[] append(double[] v1, double[] v2)
          Appends two vectors.
static int[] append(int[] v1, int d)
          Appends an element to a vector.
static int[] append(int[] v1, int[] v2)
          Appends two vectors.
static double[] arrayAdd(double[] d1, double[] d2)
          Adds corresponding elements of two arrays.
static double[] arrayDivide(double[] d1, double denominator)
          Divides each element of an array by a number.
static double capValue(double value, double minValue, double maxValue)
          Caps a value to a given range.
static int capValue(int value, int minValue, int maxValue)
          Caps a value to a given range.
static double computeSimilarity(int[] targetV, int[] v, MathUtils.SimilarityMetric similarityMetric)
          Computes the similarity of the two vectors.
static double correlation(double[] p, double[] q)
          Computes the correlation between two arrays of the same length, p and q.
static double correlation(int[] p, int[] q)
          Computes the correlation between two arrays of the same length, p and q.
static double[][] getConfusionMatrix(int[] p, int[] q)
          Computes the normalized confusion matrix for two vectors.
static double getMachinePrecision()
          Gets the computed machine precision.
static java.util.Random getRandomGenerator()
          Retrieves the initialized random number generator.
static void initializeRandomGenerator(long seed)
          Initializes a random number generator with the given seed.
static boolean isApproxEqual(double value1, double value2)
          Determines whether two numbers are approximately equal according to the machine precision.
static boolean isApproxEqual(double value1, double value2, double precision)
          Determines whether two numbers are approximately equal according to the precision.
static double log2(double d)
          Computes the log-base-2 of a number.
static void main(java.lang.String[] args)
           
static int maxIndex(double[] v)
          Gets the index of the maximum element in the array.
static int maxIndex(int[] v)
          Gets the index of the maximum element in the array.
static int maxIndexRand(double[] v)
          Gets the index of the maximum element in the array.
static int maxIndexRand(int[] v)
          Gets the index of the maximum element in the array.
static double maxValue(double[] values)
          Computes the maximum value in the given array.
static int maxValue(int[] values)
          Computes the maximum value in the given array.
static double mean(double[] values)
          Computes the mean of the values in the given array.
static double mean(int[] values)
          Computes the mean of the values in the given array.
static int minIndex(double[] v)
          Gets the index of the minimum element in the array.
static int minIndex(int[] v)
          Gets the index of the minimum element in the array.
static int minIndexRand(double[] v)
          Gets the index of the minimum element in the array.
static int minIndexRand(int[] v)
          Gets the index of the minimum element in the array.
static double minValue(double[] values)
          Computes the minimum value in the given array.
static int minValue(int[] values)
          Computes the minimum value in the given array.
static double mutualInformation(int[] p, int[] q)
          Computes the mutual information between two vectors.
static double nextRandomGaussian(double mean, double stdev)
          Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.
static double nextRandomGaussian(java.util.Random randGenerator, double mean, double stdev)
          Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.
static double pairwiseAgreement(int[] p, int[] q)
          Computes the pairwise agreement between two pairwise arrays of labelings.
static int[] permutation(int n)
          Generates a random permutation of the numbers {0, ..., n-1}
static int[] permutation(int n, java.util.Random rand)
          Generates a random permutation of the numbers {0, ..., n-1}
static void rangeCheck(double value, double min, double max)
          Throws an exception whenever a value falls outside the given range.
static void rangeCheck(int value, int min, int max)
          Throws an exception whenever a value falls outside the given range.
static double[] reverse(double[] array)
          Reverses the given array.
static int[] reverse(int[] array)
          Reverses the given array.
static int[] reverseCuthillMcKee(int[][] adjacencyLists, boolean runTwiceForOptimalResult)
          Runs the reverse Cuthill-McKee algorithm on the adjacency lists to provide an efficient ordering of the vertices
static double rmse(double[] a, double[] b)
          Computes the root mean squared error between two vectors.
static double round(double d, int decimalPlacesRequired)
          Reduces the precision of a double to a specified number of decimal places.
static int roundToMultiple(int value, int multipleOf)
          Rounds a value to the nearest number that is a specific multiple.
static
<T> java.util.Collection<T>
sampleWithoutReplacement(T[] objs, double[] probabilityDistribution, int numSamples)
          Samples from a set of weighted objects without replacement.
static
<T> java.util.Collection<T>
sampleWithReplacement(T[] objs, double[] probabilityDistribution, int numSamples)
          Samples from a set of weighted objects with replacement.
static int[] sortOrder(double[] values)
          Sorts the given values and returns the order of the original indices.
static int[] sortOrder(int[] values)
          Sorts the given values and returns the order of the original indices.
static double sum(double[] values)
          Sums the values in the given array.
static int sum(int[] values)
          Sums the values in the given array.
static double[] uniqueValues(double[] v)
          Determines the unique values of v.
static int[] uniqueValues(int[] v)
          Determines the unique values of v.
static double[] vectorAdd(double[] v1, double[] v2)
          Performs vector addition.
static double vectorL2Norm(double[] v)
          Computes the L2 norm of the given vector.
static double[] vectorMultiply(double s, double[] v)
          Performs scalar multiplication on a vector.
static double[] vectorNormalize(double[] v)
          Normalizes the given vector.
static double[] vectorSubtract(double[] v1, double[] v2)
          Performs vector subtraction.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

MathUtils

public MathUtils()
Method Detail

reverseCuthillMcKee

public static int[] reverseCuthillMcKee(int[][] adjacencyLists,
                                        boolean runTwiceForOptimalResult)
Runs the reverse Cuthill-McKee algorithm on the adjacency lists to provide an efficient ordering of the vertices

Parameters:
adjacencyLists - a list of the adjacency lists of the graph
runTwiceForOptimalResult - whether to run the algorithm twice to get the optimal result
Returns:
a permutation of the vertices that is efficient for a sparse matrix

permutation

public static int[] permutation(int n)
Generates a random permutation of the numbers {0, ..., n-1}

Parameters:
n - the length of the set of numbers to permute
Returns:
a random permutation of the numbers {0, ..., n-1}

permutation

public static int[] permutation(int n,
                                java.util.Random rand)
Generates a random permutation of the numbers {0, ..., n-1}

Parameters:
n - the length of the set of numbers to permute
rand - the random number generator
Returns:
a random permutation of the numbers {0, ..., n-1}

append

public static int[] append(int[] v1,
                           int d)
Appends an element to a vector.

Parameters:
v1 - the vector.
d - the element to append.
Returns:
A vector containing all the elements of v1 followed by d.

append

public static double[] append(double[] v1,
                              double d)
Appends an element to a vector.

Parameters:
v1 - the vector.
d - the element to append.
Returns:
A vector containing all the elements of v1 followed by d.

append

public static double[] append(double[] v1,
                              double[] v2)
Appends two vectors.

Parameters:
v1 - the first vector.
v2 - the second vector.
Returns:
A vector containing all the elements of v1 followed by all the elements of v2.

append

public static int[] append(int[] v1,
                           int[] v2)
Appends two vectors.

Parameters:
v1 - the first vector.
v2 - the second vector.
Returns:
A vector containing all the elements of v1 followed by all the elements of v2.

vectorAdd

public static double[] vectorAdd(double[] v1,
                                 double[] v2)
Performs vector addition.

Parameters:
v1 - the first vector.
v2 - the second vector.
Returns:
v1 + v2

vectorSubtract

public static double[] vectorSubtract(double[] v1,
                                      double[] v2)
Performs vector subtraction.

Parameters:
v1 - the first vector.
v2 - the second vector.
Returns:
v1 - v2

vectorMultiply

public static double[] vectorMultiply(double s,
                                      double[] v)
Performs scalar multiplication on a vector.

Parameters:
s - a scalar value.
v - the vector.
Returns:
the scalar product of s and v.

vectorL2Norm

public static double vectorL2Norm(double[] v)
Computes the L2 norm of the given vector.

Parameters:
v - the vector.
Returns:
the L2 norm of v.

vectorNormalize

public static double[] vectorNormalize(double[] v)
Normalizes the given vector.

Parameters:
v - the vector.
Returns:
v with the values normalized.

getRandomGenerator

public static java.util.Random getRandomGenerator()
Retrieves the initialized random number generator. Use of this rand generator allows an entire program to use a single rand generator.

Returns:
the initialized random number generator.

initializeRandomGenerator

public static void initializeRandomGenerator(long seed)
Initializes a random number generator with the given seed. Repeated calls to this initialize function create a new random generator.

Parameters:
seed - the seed for the random generator.

nextRandomGaussian

public static double nextRandomGaussian(double mean,
                                        double stdev)
Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.

Parameters:
mean - the mean of the Gaussian
stdev - the standard deviation of the Gaussian
Returns:
a random number from the specified distribution

nextRandomGaussian

public static double nextRandomGaussian(java.util.Random randGenerator,
                                        double mean,
                                        double stdev)
Gets a random number from a one dimensional Gaussian distribution with the given mean and variance.

Parameters:
randGenerator - the random generator.
mean - the mean of the Gaussian
stdev - the standard deviation of the Gaussian
Returns:
a random number from the specified distribution

rmse

public static double rmse(double[] a,
                          double[] b)
Computes the root mean squared error between two vectors.

Parameters:
a -
b -
Returns:
the RMSE between a and b

main

public static void main(java.lang.String[] args)

sampleWithoutReplacement

public static <T> java.util.Collection<T> sampleWithoutReplacement(T[] objs,
                                                                   double[] probabilityDistribution,
                                                                   int numSamples)
Samples from a set of weighted objects without replacement.

Parameters:
objs - the array of objects
probabilityDistribution - the probability distribution over the set of objects (i.e. the weight assigned to each object)
numSamples - the desired number of samples

sampleWithReplacement

public static <T> java.util.Collection<T> sampleWithReplacement(T[] objs,
                                                                double[] probabilityDistribution,
                                                                int numSamples)
Samples from a set of weighted objects with replacement.

Parameters:
objs - the array of objects
probabilityDistribution - the probability distribution over the set of objects (i.e. the weight assigned to each object)
numSamples - the desired number of samples

capValue

public static double capValue(double value,
                              double minValue,
                              double maxValue)
Caps a value to a given range.

Parameters:
value - the value to constrain.
minValue - the min value.
maxValue - the max value.
Returns:
the value altered to lie in [minValue, maxValue].

capValue

public static int capValue(int value,
                           int minValue,
                           int maxValue)
Caps a value to a given range.

Parameters:
value - the value to constrain.
minValue - the min value.
maxValue - the max value.
Returns:
the value altered to lie in [minValue, maxValue].

rangeCheck

public static void rangeCheck(int value,
                              int min,
                              int max)
Throws an exception whenever a value falls outside the given range.

Parameters:
value -
min - the minimal value
max - the maximal value
Throws:
java.lang.IllegalArgumentException - if the value is outside of the given range.

rangeCheck

public static void rangeCheck(double value,
                              double min,
                              double max)
Throws an exception whenever a value falls outside the given range.

Parameters:
value -
min - the minimal value
max - the maximal value
Throws:
java.lang.IllegalArgumentException - if the value is outside of the given range.

round

public static final double round(double d,
                                 int decimalPlacesRequired)
Reduces the precision of a double to a specified number of decimal places.

Parameters:
d - number to reduce precision
decimalPlacesRequired - the number of required decimal places
Returns:
d reduced to the specified precision

roundToMultiple

public static final int roundToMultiple(int value,
                                        int multipleOf)
Rounds a value to the nearest number that is a specific multiple.

Parameters:
value - the value to round
multipleOf - the value that the final number should be a multiple of.
Returns:
value rounded to the nearest number that is a multiple of multipleOf.

minIndex

public static int minIndex(double[] v)
Gets the index of the minimum element in the array. Returns the first min index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the minimum element of v.

minIndex

public static int minIndex(int[] v)
Gets the index of the minimum element in the array. Returns the first min index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the minimum element of v.

minIndexRand

public static int minIndexRand(double[] v)
Gets the index of the minimum element in the array. Randomly chooses the min index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the minimum element of v.

minIndexRand

public static int minIndexRand(int[] v)
Gets the index of the minimum element in the array. Randomly chooses the min index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the minimum element of v.

maxIndex

public static int maxIndex(double[] v)
Gets the index of the maximum element in the array. Returns the first max index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the maximum element of v.

maxIndex

public static int maxIndex(int[] v)
Gets the index of the maximum element in the array. Returns the first max index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the maximum element of v.

maxIndexRand

public static int maxIndexRand(double[] v)
Gets the index of the maximum element in the array. Randomly chooses the max index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the maximum element of v.

maxIndexRand

public static int maxIndexRand(int[] v)
Gets the index of the maximum element in the array. Randomly chooses the max index if there are multiple matching elements.

Parameters:
v -
Returns:
the index of the maximum element of v.

maxValue

public static int maxValue(int[] values)
Computes the maximum value in the given array.

Parameters:
values -
Returns:
the maximum value in the given array.

maxValue

public static double maxValue(double[] values)
Computes the maximum value in the given array.

Parameters:
values -
Returns:
the maximum value in the given array.

minValue

public static double minValue(double[] values)
Computes the minimum value in the given array.

Parameters:
values -
Returns:
the minimum value in the given array.

minValue

public static int minValue(int[] values)
Computes the minimum value in the given array.

Parameters:
values -
Returns:
the minimum value in the given array.

mean

public static double mean(double[] values)
Computes the mean of the values in the given array.

Parameters:
values -
Returns:
the mean of the values in the given array.

mean

public static double mean(int[] values)
Computes the mean of the values in the given array.

Parameters:
values -
Returns:
the mean of the values in the given array.

sum

public static double sum(double[] values)
Sums the values in the given array.

Parameters:
values -
Returns:
the sum of the values in the given array.

sum

public static int sum(int[] values)
Sums the values in the given array.

Parameters:
values -
Returns:
the sum of the values in the given array.

arrayAdd

public static double[] arrayAdd(double[] d1,
                                double[] d2)
Adds corresponding elements of two arrays.

Parameters:
d1 - the first array
d2 - the second array
Returns:
the element-wise sum of d1 + d2

arrayDivide

public static double[] arrayDivide(double[] d1,
                                   double denominator)
Divides each element of an array by a number.

Parameters:
d1 - the first array
denominator - the denominator for the devision
Returns:
d1 / denominator

sortOrder

public static int[] sortOrder(int[] values)
Sorts the given values and returns the order of the original indices.

Parameters:
values - the values to sort
Returns:
an array of the original indices of values reordered according to the sort.

sortOrder

public static int[] sortOrder(double[] values)
Sorts the given values and returns the order of the original indices.

Parameters:
values - the values to sort
Returns:
an array of the original indices of values reordered according to the sort.

reverse

public static int[] reverse(int[] array)
Reverses the given array.

Parameters:
array -
Returns:
the array with the elements in reverse order

reverse

public static double[] reverse(double[] array)
Reverses the given array.

Parameters:
array -
Returns:
the array with the elements in reverse order

getMachinePrecision

public static double getMachinePrecision()
Gets the computed machine precision.

Returns:
the computed machine precision.

isApproxEqual

public static boolean isApproxEqual(double value1,
                                    double value2)
Determines whether two numbers are approximately equal according to the machine precision.

Parameters:
value1 -
value2 -
Returns:
whether the two numbers are approximately equal

isApproxEqual

public static boolean isApproxEqual(double value1,
                                    double value2,
                                    double precision)
Determines whether two numbers are approximately equal according to the precision.

Parameters:
value1 -
value2 -
precision -
Returns:
whether the two numbers are approximately equal

correlation

public static double correlation(int[] p,
                                 int[] q)
Computes the correlation between two arrays of the same length, p and q. Computes the correlation between p and q as r = (|p| * \sum_i(p[i]*q[i]) - \sum_i(p[i]) * \sum_i(q[i]))/ sqrt((|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2) * (|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2)) This correlation can be tested for statistical significance via t-tests. See e.g.: http://www.socialresearchmethods.net/kb/statcorr.htm

Returns:
The correlation between the elements of the two arrays.

correlation

public static double correlation(double[] p,
                                 double[] q)
Computes the correlation between two arrays of the same length, p and q. Computes the correlation between p and q as r = (|p| * \sum_i(p[i]*q[i]) - \sum_i(p[i]) * \sum_i(q[i]))/ sqrt((|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2) * (|p| * \sum_i((p[i])^2) - (\sum_i(p[i]))^2)) This correlation can be tested for statistical significance via t-tests. See e.g.: http://www.socialresearchmethods.net/kb/statcorr.htm

Returns:
The correlation between the elements of the two arrays.

pairwiseAgreement

public static double pairwiseAgreement(int[] p,
                                       int[] q)
Computes the pairwise agreement between two pairwise arrays of labelings. The pairwise agreement is the number-of-pairs-in-agreement / the-total-number-of-pairs. The two arrays must be the same length.

Parameters:
p - An array of labels.
q - An array of labels.
Returns:
The pairwise agreement between the labelings in p and q.

uniqueValues

public static int[] uniqueValues(int[] v)
Determines the unique values of v. The values are returned in no particular order.

Parameters:
v -
Returns:
the unique values of v in no particular order.

uniqueValues

public static double[] uniqueValues(double[] v)
Determines the unique values of v. The values are returned in no particular order.

Parameters:
v -
Returns:
the unique values of v in no particular order.

getConfusionMatrix

public static double[][] getConfusionMatrix(int[] p,
                                            int[] q)
Computes the normalized confusion matrix for two vectors.

Parameters:
p - the first vector
q - the second vector
Returns:
the normalized confusion matrix for p and q

mutualInformation

public static double mutualInformation(int[] p,
                                       int[] q)
Computes the mutual information between two vectors.

Parameters:
p - the first vector.
q - the second vector.
Returns:
the mutual information between p and q.

computeSimilarity

public static double computeSimilarity(int[] targetV,
                                       int[] v,
                                       MathUtils.SimilarityMetric similarityMetric)
Computes the similarity of the two vectors.

Parameters:
targetV - the target vector that forms the basis for comparison.
v - the vector for comparison
similarityMetric - the metric to use for computing the similarity
Returns:
The similarity of the two models.

log2

public static double log2(double d)
Computes the log-base-2 of a number.

Parameters:
d -
Returns:
the log-base-2 of d