Package elki.math.statistics.distribution

Class HaltonUniformDistribution

java.lang.Object

elki.math.statistics.distribution.HaltonUniformDistribution

All Implemented Interfaces:

Distribution

@Reference(title="Randomized halton sequences",
           authors="X. Wang, F. J. Hickernell",
           booktitle="Mathematical and Computer Modelling Vol. 32 (7)",
           url="https://doi.org/10.1016/S0895-7177(00)00178-3",
           bibkey="doi:10.1016/S0895-71770000178-3")
public class HaltonUniformDistribution
extends java.lang.Object
implements Distribution

Halton sequences are a pseudo-uniform distribution. The data is actually too regular for a true uniform distribution, but as such will of course often appear to be uniform.

Technically, they are based on Van der Corput sequence and the Von Neumann Katutani transformation. These produce a series of integers which then are converted to floating point values.

To randomize, we just choose a random starting position, as indicated by

Reference:

X. Wang, F. J. Hickernell
Randomized halton sequences
Mathematical and Computer Modelling Vol. 32 (7)

Important note: this code hasn't been double checked yet. While it probably works for some simple cases such as example data set generation, do not rely on it for, e.g., quasi monte carlo methods without double-checking the quality, and looking at more advanced methods!

Let me repeat this: this code was written to generate toy datasets. It may have deficits for other uses! There is a high chance it will produce correlated data when used for more than one dimension. - for toy data sets, try different random seeds until you find one that works for you.

TODO: find an improved algorithm that takes care of a better randomization, for example by adding scrambling.

Since:

0.5.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	HaltonUniformDistribution.Par	Parameterization class

Nested classes/interfaces inherited from interface elki.math.statistics.distribution.Distribution

Distribution.Parameterizer

Field Summary

Fields

Modifier and Type	Field	Description
private static double	ALMOST_ONE	Threshold
(package private) short	base	Base value
(package private) int	counter	Counter, for max iterations of fast function.
(package private) double	current	Current value
(package private) double	invbase	Inverse of base, for faster division by multiplication.
(package private) long	inverse	Integer inverse
private double	len	Len := max - min
(package private) double	logbase	Logarithm of base.
private double	max	Maximum
private static int	MAXFAST	Maximum number of iterations of fast variant
(package private) int	maxi	Maximum integer to use
private double	min	Minimum

Constructor Summary

Constructors

Constructor	Description
HaltonUniformDistribution(double min, double max, int base, double seed)	Constructor for a halton pseudo uniform distribution on the interval [min, max[
HaltonUniformDistribution(double min, double max, java.util.Random rnd)	Constructor for a random halton pseudo uniform distribution on the interval [min, max[.

Method Summary

Modifier and Type	Method	Description
double	cdf(double val)	Return the cumulative density function at the given value.
private static int	choosePrime(java.util.Random rnd)	Choose a random prime.
double	getMax()
double	getMin()
private long	inverse(double current)	Compute the inverse with respect to the given base.
double	logpdf(double val)	Return the log density of an existing value
private double	nextRadicalInverse()	Compute the next radical inverse.
double	nextRandom(java.util.Random random)	Generate a new random value
double	pdf(double val)	Return the density of an existing value
double	quantile(double val)	Quantile aka probit (for normal) aka inverse CDF (invcdf, cdf^-1) function.
private double	radicalInverse(long i)	Compute the radical inverse of i.
java.lang.String	toString()	Describe the distribution

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

min

private double min

Minimum

max

private double max

Maximum

len

private double len

Len := max - min

MAXFAST

private static final int MAXFAST

Maximum number of iterations of fast variant

See Also:

Constant Field Values

ALMOST_ONE

private static final double ALMOST_ONE

Threshold

See Also:

Constant Field Values

base

final short base

Base value

invbase

final double invbase

Inverse of base, for faster division by multiplication.

logbase

final double logbase

Logarithm of base.

maxi

final int maxi

Maximum integer to use

counter

int counter

Counter, for max iterations of fast function.

current

double current

Current value

inverse

long inverse

Integer inverse

Constructor Detail

HaltonUniformDistribution

public HaltonUniformDistribution(double min,
                                 double max,
                                 int base,
                                 double seed)

Constructor for a halton pseudo uniform distribution on the interval [min, max[

Parameters:

min - Minimum value

max - Maximum value

base - Base value

seed - Random seed (starting value)

HaltonUniformDistribution

public HaltonUniformDistribution(double min,
                                 double max,
                                 java.util.Random rnd)

Constructor for a random halton pseudo uniform distribution on the interval [min, max[.

Parameters:

min - Minimum value

max - Maximum value

rnd - Random generator

Method Detail

choosePrime

private static int choosePrime(java.util.Random rnd)

Choose a random prime. We try to avoid the later primes, as they are known to cause too correlated data.

Parameters:

rnd - Random generator

Returns:

Prime

pdf

public double pdf(double val)

Description copied from interface: Distribution

Return the density of an existing value

Specified by:

pdf in interface Distribution

Parameters:

val - existing value

Returns:

distribution density

logpdf

public double logpdf(double val)

Description copied from interface: Distribution

Return the log density of an existing value

Specified by:

logpdf in interface Distribution

Parameters:

val - existing value

Returns:

log distribution density

cdf

public double cdf(double val)

Description copied from interface: Distribution

Return the cumulative density function at the given value.

Specified by:

cdf in interface Distribution

Parameters:

val - existing value

Returns:

cumulative density

quantile

public double quantile(double val)

Description copied from interface: Distribution

Quantile aka probit (for normal) aka inverse CDF (invcdf, cdf^-1) function.

Specified by:

quantile in interface Distribution

Parameters:

val - Quantile to find

Returns:

Quantile position

inverse

private long inverse(double current)

Compute the inverse with respect to the given base.

Parameters:

current - Current value

Returns:

Integer inverse

radicalInverse

private double radicalInverse(long i)

Compute the radical inverse of i.

Parameters:

i - Input long value

Returns:

Double radical inverse

nextRadicalInverse

private double nextRadicalInverse()

Compute the next radical inverse.

Returns:

Next inverse

nextRandom

public double nextRandom(java.util.Random random)

Description copied from interface: Distribution

Generate a new random value

Specified by:

nextRandom in interface Distribution

Parameters:

random - Random number generator

Returns:

new random value

toString

public java.lang.String toString()

Description copied from interface: Distribution

Describe the distribution

Specified by:

toString in interface Distribution

Overrides:

toString in class java.lang.Object

Returns:

description

getMin

public double getMin()

Returns:

the minimum value

getMax

public double getMax()

Returns:

the maximum value