Differentially private k-means — morie_dp

Lloyd iterations where each centre update uses a noisy count and a noisy sum.

Usage

morie_dp_kmeans(X, k = 3, epsilon = 1, n_iter = 5, bounds = NULL, seed = NULL)

Arguments

X: data matrix.
k: number of clusters.
epsilon: total budget across all iterations.
n_iter: Lloyd iterations.
bounds: c(lo, hi) for clipping, from outside the data.
seed: optional integer seed.

Value

list with centers, labels, epsilon_per_iteration, n_reinitialised, inertia, private_outputs, privacy_note. Only centers is the private release; labels and inertia are computed on the raw records.

Details

The budget splits across ITERATIONS as well as across the count and sum queries, so each pass is cheaper and noisier than the last one would like. More iterations therefore make the result WORSE, which inverts the usual intuition: keep n_iter small. A noisy count below 1 means the cluster cannot be located at all and the centre is reinitialised, which is reported.

References

Su, D. et al. (2016). Differentially private k-means clustering. CODASPY, 26-37.

Examples

set.seed(1)
r <- morie_dp_kmeans(matrix(rnorm(200), ncol = 2),
  k = 2, epsilon = 5,
  bounds = c(-4, 4)
)
dim(r$centers)
#> [1] 2 2