`scipy.stats._qmc:_lloyd_centroidal_voronoi_tessellation`

source: /scipy/stats/_qmc.py :2747

Signature

   def     _lloyd_centroidal_voronoi_tessellation (    sample  :  npt.ArrayLike    ,  * ,     tol  :  DecimalNumber    =  1e-05   ,    maxiter  :  IntNumber    =  10   ,    qhull_options  :  str | None    =  None   ,   ** kwargs  :  dict      )   →  np.ndarray

Summary

Approximate Centroidal Voronoi Tessellation.

Extended Summary

Perturb samples in N-dimensions using Lloyd-Max algorithm.

Parameters

sample : array_like (n, d): The sample to iterate on. With n the number of samples and d the dimension. Samples must be in $[0, 1]^{d}$ , with d>=2.
tol : float, optional: Tolerance for termination. If the min of the L1-norm over the samples changes less than tol, it stops the algorithm. Default is 1e-5.
maxiter : int, optional: Maximum number of iterations. It will stop the algorithm even if tol is above the threshold. Too many iterations tend to cluster the samples as a hypersphere. Default is 10.
qhull_options : str, optional: Additional options to pass to Qhull. See Qhull manual for details. (Default: "Qbb Qc Qz Qj Qx" for ndim > 4 and "Qbb Qc Qz Qj" otherwise.)

Returns

sample : array_like (n, d): The sample after being processed by Lloyd-Max algorithm.

Notes

Lloyd-Max algorithm is an iterative process with the purpose of improving the dispersion of samples. For given sample: (i) compute a Voronoi Tessellation; (ii) find the centroid of each Voronoi cell; (iii) move the samples toward the centroid of their respective cell. See ^[1], ^[2].

A relaxation factor is used to control how fast samples can move at each iteration. This factor is starting at 2 and ending at 1 after maxiter following an exponential decay.

The process converges to equally spaced samples. It implies that measures like the discrepancy could suffer from too many iterations. On the other hand, L1 and L2 distances should improve. This is especially true with QMC methods which tend to favor the discrepancy over other criteria.

Examples

import numpy as np
from scipy.spatial import distance
from scipy.stats._qmc import _lloyd_centroidal_voronoi_tessellation
rng = np.random.default_rng()
sample = rng.random((128, 2))

✓

.. note:: The samples need to be in :math:`[0, 1]^d`. `scipy.stats.qmc.scale` can be used to scale the samples from their original bounds to :math:`[0, 1]^d`. And back to their original bounds. Compute the quality of the sample using the L1 criterion.

def l1_norm(sample):
   return distance.pdist(sample, 'cityblock').min()

✓

l1_norm(sample)

✗

Now process the sample using Lloyd's algorithm and check the improvement on the L1. The value should increase.

sample = _lloyd_centroidal_voronoi_tessellation(sample)

✓

l1_norm(sample)

✗

Aliases

scipy.stats._qmc._lloyd_centroidal_voronoi_tessellation