Lloyd's algorithm with transport in place of Euclidean distance

Clustering distributions by comparing their moments throws away shape; comparing them bin by bin makes the answer depend on an arbitrary binning. The Wasserstein distance does neither, and the empirical version obeys a central limit theorem, which is what makes the resulting clusters testable rather than merely descriptive. Both the assignment step and the centroid step are transport problems.

Usage

Otmcluster(X_list, k, max_iter = 10)

Arguments

X_list: List of point clouds, all with the same number of points.
k: Number of clusters.
max_iter: Lloyd iterations.

Value

List with labels, centers, inertia, K, n_clouds, n, d, iters.

Details

Formula: alternate label(i) = argmin_c W_2(mu_i, nu_c) and nu_c = argmin sum W_2^2(mu_i, nu); the barycentre step is Cuturi and Doucet's free-support update.

References

del Barrio, E., Cuesta-Albertos, J. A. and Matran, C. (2019). Annals of Probability 47(2):926-951. doi:10.1214/18-AOP1275 . Cuturi, M. and Doucet, A. (2014). Proceedings of Machine Learning Research 32:685-693 (ICML).

Examples

Otmcluster(X_list = c(1, 2, 3, 4, 5, 6, 7, 8), k = 5L)
#> $labels
#> [1] 0 1 2 3 3 4 4 4
#> 
#> $centers
#> $centers[[1]]
#>      [,1]
#> [1,]    1
#> 
#> $centers[[2]]
#>      [,1]
#> [1,]    2
#> 
#> $centers[[3]]
#>      [,1]
#> [1,]    3
#> 
#> $centers[[4]]
#>      [,1]
#> [1,]  4.5
#> 
#> $centers[[5]]
#>      [,1]
#> [1,]    7
#> 
#> 
#> $inertia
#> [1] 2.5
#> 
#> $K
#> [1] 5
#> 
#> $n_clouds
#> [1] 8
#> 
#> $n
#> [1] 1
#> 
#> $d
#> [1] 1
#> 
#> $iters
#> [1] 10
#> 
#> $method
#> [1] "Wasserstein k-means over point clouds"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"