rust-wsp

A rust implementation of the WSP space filling algorithm.

This is based on the paper from J. Santiago et al:

[1] Santiago, J., Claeys-Bruno, M., & Sergent, M. (2012). Construction of space-filling designs using WSP algorithm for high dimensional spaces. Chemometrics and Intelligent Laboratory Systems, 113, 26-31.

Crate usage

Add the following line to the Cargo.toml file:

[dependencies]
wsp = "0.1.6"

Use cases

A space-filling algorithm enables to remove points to close to each other in a given space. Given a minimal distance d_min and an initial set of points, wsp builds a subset where all remaining points are at least d_min distant from each other.

wsp also provides an alternative version of the classical WSP algorithm. Certain scenarios do not have any clue about the d_min to choose, but require a given number of remaining points in the subset. adaptive_wsp search the best d_min to create a subset of a target number of points.

Example

WSP

The following example generates an initial set of 1000 points from a uniform random distribution, in a 20-dimensions space. The generation uses the seed 51. The minimal distance is arbitrarily set to 3.0.

// Generates the initial set
let mut points = wsp::PointSet::init_from_random(1000, 20, 51);

// Only keep distant enough points
let d_min = 3.0;
wsp::wsp(&mut points, d_min);

// Iterate over the remaining points
for valid_point in points.get_remaining() {
    println!("{:?}", valid_point);
}

Adaptive WSP

The next example uses the adaptive_wsp function with verbose mode. The initial set is similar to the previous example thanks to the seed. We aim to find a minimal distance such that the resulting set only contains 100 points.

// Generates the initial set
let mut points = wsp::PointSet::init_from_random(1000, 20, 51);

// Adaptive WSP makes a binary search to reach the target
// number of remaining points
let objective_nb: usize = 100;
wsp::adaptive_wsp(&mut points, objective_nb, false);

// Save the result in a CSV file
if let Err(err) = points.save_in_csv("wsp.csv", false) {
    println!("Error writing in CSV: {}", err);
    std::process::exit(1);
}

Binary usage

Use cargo install wsp to install a binary version of the rust-wsp crate. Both wsp() and adaptive_wsp are available through the command line.

Classic WSP

You may run the classic WSP version with

wsp -n 1000 -m 20 -d 0.5

This will run the WSP algorithm with 1000 initial points. Each point has a dimension of 10. The minimal distance between each point, as detailed in [1], is set to 0.5. For now, the algorithm uses the l1 (Manhattan) distance, as it provides better separation in high dimensional space than the l2 (euclidian) distance. The result is stored in a file named wsp.csv. Each row represents a point in a 20 dimensions space that is far enough from its other neighbours. You may change the output file with the -o option.

Adaptive WSP

$ wsp -n 1000 -m 20 --adaptive 100

Similarly to the previous command, the initial space if filled with 1000 points of 20 dimensions. However, now, the user does not need to specify the minimal distance between points, but instead the desired number of points in the resulting set. The algorithm will perform a binary search on the minimal distance until 1) the resulting set contains the desired number of points or 2) there is not distance that can be found to reach this quantity. In the second scenario, rust-wsp uses the minimal distance resulting in a space where the number of points is as close as possible to the desired value.

Consider the example below, where we want 200 points in a space of 20 dimensions, initially filled with 1000 points:

$ wsp -n 1000 -m 20 --adaptive 200 -v
Iter #1: distance=7.430897367982144, nb_active=5
Iter #2: distance=5.028120018334874, nb_active=98
Iter #3: distance=3.826731343511239, nb_active=591
Iter #4: distance=4.427425680923057, nb_active=270
Iter #5: distance=4.727772849628966, nb_active=168
Iter #6: distance=4.577599265276012, nb_active=209
Iter #7: distance=4.652686057452489, nb_active=170
Iter #8: distance=4.615142661364251, nb_active=195
Iter #9: distance=4.5963709633201315, nb_active=207
Iter #10: distance=4.605756812342191, nb_active=194
Iter #11: distance=4.601063887831161, nb_active=191
Iter #12: distance=4.5987174255756464, nb_active=206
Iter #13: distance=4.599890656703404, nb_active=206
Iter #14: distance=4.600477272267282, nb_active=201
Iter #15: distance=4.600770580049222, nb_active=194
Iter #16: distance=4.600623926158252, nb_active=194
Iter #17: distance=4.600550599212767, nb_active=197
[...]
Iter #53: distance=4.60049404718639, nb_active=201
Iter #54: distance=4.600494047186391, nb_active=197
Last iter: best approximation is distance=4.600477272267282, nb_active=201
Nb active: 201

The algorithm performs 54 iterations until the minimal distance search space is completely explored. It will recompute the space (if needed) qith the minimal distance resulting in the best approximation of the target number of active points in the set. Here, it is 201, with an error of 1 compared to the objective. The resulting matrix is also stored in a file named wsp.csv by default.

More help

Run wsp -h or wsp --help for more information about the arguments.