Spatial KWD for Large Spatial Maps
Project description
Spatial-KWD: Kantorovich-Wasserstein Distances for Large Spatial Maps
The Spatial-KWD package contains efficient implementations of Discrete Optimal Transport algorithms for the computation of Kantorovich-Wasserstein distances [1], which are customized for large spatial maps. All the algorithms are based on an ad-hoc implementation of the Network Simplex algorithm [1,2]. Each implemented algorithm builds a different network, exploiting the special structure of spatial maps.
Details
This library contains three helper functions and two main classes.
The three helper functions are compareOneToOne
, compareOneToMany
, and compareAll
. All the functions take in input the data and an options list. Using the options is possible to configure the Kantorivich-Wasserstein solver, so that it uses different algorithms with different parameters.
The helper functions are built on top of two main classes: Histogram2D
and Solver
.
Note that in case of non-convex maps, the algorithm builds the convex-hull of the input bins and pads the weights with zeros.
Prerequisities
You only need the following library:
- cython
- numpy
Installation
To install Spatial-KWD you can run the following command:
pip3 install Spatial-KWD
This will compile the C++ code and build the python wrapper.
Testing
For testing the library you can run the following command:
python3 test_matrix.py
The test program is the following
import numpy as np
from KWD import compareOneToOne, compareOneToMany, compareAll
np.random.seed(13)
N = 32*32
M = 3
# Random data
Coordinates = np.random.randint(0, 32, size=(N, 2), dtype=np.int32)
Weights = np.random.uniform(0, 100, size=(N, 2))
# Testing the first helper function
print('-----------------------------\nTest one2one approx:')
Options = {'Verbosity': 'debug'}
sol = compareOneToOne(Coordinates, Weights, Options)
for k in sol:
print(k, sol[k])
References
[1] Bassetti, F., Gualandi, S. and Veneroni, M., 2020. On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows. SIAM Journal on Optimization, 30(3), pp.2441-2469.
[2] Cunningham, W.H., 1976. A Network Simplex method. Mathematical Programming, 11(1), pp.105-116.
[3] https://github.com/eurostat/Spatial-KWD
Authors and maintainers
Stefano Gualandi, stefano.gualandi@gmail.com.
Maintainer: Stefano Gualandi stefano.gualandi@gmail.com
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for Spatial_KWD-0.2.5-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6754d1f85195506d142f519fcfb56951445f4604e0a84ae26e2261a9c5820939 |
|
MD5 | 03d60ab5c90b3639778a69ca67100773 |
|
BLAKE2b-256 | 8d880d76a17cee038f80afb0302e52c6b61cc6e03b845b53d896e01611e4dbe9 |
Hashes for Spatial_KWD-0.2.5-cp39-cp39-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e10276c58704e4ced5b419374dcead8e1a8fa10674d8f772cf1c2fde97dfdc9 |
|
MD5 | d1d57a33dccb2971aaee380897f42151 |
|
BLAKE2b-256 | 7baf36e7c407c13d99a19b913782b30a6ae39517f775189d2188be588671cce2 |
Hashes for Spatial_KWD-0.2.5-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 77e5a5c2ac3a95d9b5644f0aa6ffb230115efeb661db445b4f793eaa2b078933 |
|
MD5 | 1a325e3e43dc013b3632de7c93e34eb8 |
|
BLAKE2b-256 | 61f6282afd430bdcb90cf733312690ae9363b9f982b7d6d4af6ba88d66cd2acc |
Hashes for Spatial_KWD-0.2.5-cp38-cp38-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2fb9f50495c5c45fe01e56583525760bfad3601b2237772178f9e5ea5128c94e |
|
MD5 | 42dbb80e744546f0d23bd2e74b2c7a0d |
|
BLAKE2b-256 | 00875d4f3e3f49e78c8135d24c7463a0f965d303accda70112058b364d475405 |
Hashes for Spatial_KWD-0.2.5-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3929f9ad683ced6bbab24b40317a56bd0e04e3e40bec0b55ab9bbc885a746bdd |
|
MD5 | d97c31814753e298eb5f50e3b06b00cc |
|
BLAKE2b-256 | 585f4e56435035e8848413e515ba54ec1b125f17cc304d053afce3e90590de7a |
Hashes for Spatial_KWD-0.2.5-cp37-cp37m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 79de5f3d2cc6a7f44cd957800b6c086f62135548c40a3da36fe08dbc63c570b8 |
|
MD5 | 533121ed584386c70d92a785d2cd9129 |
|
BLAKE2b-256 | 9b1d406d89dd0428379a741fee84681f7ca85a0246fcd80ba6f8eea795b88d23 |
Hashes for Spatial_KWD-0.2.5-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 168add608dbec0c64d07e58bebc9dc4565c8457a5a825ac3e987d641a4d8cf97 |
|
MD5 | d2b6426df59bfb249594384a0b46acf2 |
|
BLAKE2b-256 | defd6b086d0aa1e2016e8ab6eb8082a8301b5b4eb8686758bf42befaec0a3064 |