ttbary (version 0.3-0)

kmeansbarynet: Compute Pseudo-Barycenter of a List of Point Patterns on a Network

Description

Starting from an initial candidate point pattern zeta, use a k-means-like algorithm to compute a local minimum in the barycenter problem based on the TT-1 metric for a collection of point patterns on a network. The data needs to be in a special form which can be produced with the function netsplit.

Usage

kmeansbarynet(dpath, zeta, ppmatrix, penalty, N = 200L, eps = 0.005)

Value

A list containing the following components:

cost

the sum of TT-1 distances between the computed pseudo-barycenter and the point patterns.

barycenter

the pseudo-barycenter as a vector of vertex-indices.

zetalist

a list containing the alternative vertex-indices for each point of the pseudo-barycenter.

barycost

a vector containing the cluster costs for each point of the pseudo-barycenter (the alternative indices in zetalist lead to the same cluster cost).

perm

the permutation matrix for the clusters.

iterations

the number of iterations required until convergence.

Arguments

dpath

a square matrix whose (i,j)th entry is the shortest-path distance between vertex i and vertex j. Vertex means either network vertex or data point.

zeta

a vector containing the vertex-indices of the initial candidate for the barycenter.

ppmatrix

a matrix specifying in its columns the vertex-indices of the different data point patterns. A virtual index that is one greater than the maximum vertex-index can be used to fill up columns so they all have the same length (see examples).

penalty

the penalty for adding/deleting points when computing TT-1 distances.

N

the maximum number of iterations.

eps

the algorithm stops if the relative improvement of the objective function between two iterations is less than eps.

Author

Raoul Müller
Dominic Schuhmacher

Details

Given \(k\) planar point patterns \(\xi_1, \ldots, \xi_k\) (specified by giving the indices of their points in the \(k\) columns of ppmatrix), this function finds a local minimizer \(\zeta^*\) of $$\sum_{j=1}^k \tau_1(\xi_j, \zeta),$$ where \(\tau_1\) denotes the TT-1 metric based on the shortest-path metric between points in the network.

Starting from an initial candidate point pattern zeta (specified by giving the indices of its points), the algorithm alternates between assigning a point from each pattern \(\xi_j\) to each point of the candidate and computing new candidate patterns by shifting points (addition and deletion of points is currently not implemented). A detailed description of the algorithm is given in Müller, Schuhmacher and Mateu (2019).

The most convenient way to obtain objects dpath and ppmatrix of the right form is by calling netsplit and extracting components network$dpath and ppmatrix from the resulting object (see examples below).

References

Raoul Müller, Dominic Schuhmacher and Jorge Mateu (2019).
Metrics and Barycenters for Point Pattern Data.
Preprint arXiv:1909.07266

See Also

kmeansbary for a similar function for point patterns in \(R^2\)

Examples

set.seed(123456)
nvert <- 100 #number of vertices in the network
npp <- 5 #number of data point patterns
npts <- 40 #number of points per data point pattern
ln <- delaunayNetwork(runifpoint(nvert)) #create an artificial network
ppnetwork <- runiflpp(npts,ln,nsim = npp)
  #simulate npp point patterns with npts points each

plot(ppnetwork[[1]]$domain, cex=0.5, main="")
for (i in 1:npp) {
  plot(as.ppp(ppnetwork[[i]]),vpch=1,col=i,add=TRUE)
     #plotting the point patterns in different colors
}

res <- netsplit(ln, ppnetwork)
  #incorporate data point patterns into the network
  #calculating all pairwise distances between vertices
  #and creating matrix of vertex-indices of data point patterns
  
zeta <- sample(res$nvirtual - 1, median(res$dimensions))
  #sample random vertex-indices in the network
  #taking as cardinality the median of point pattern cardinalities

res2 <- kmeansbarynet(res$network$dpath, zeta, res$ppmatrix, penalty = 0.1)

barycenter <- ppp(res$network$vertices$x[res2$barycenter], res$network$vertices$y[res2$barycenter])
  #construct the barycenter pattern based on the index information in res2
points(barycenter,cex = 1.2, lwd = 2, pch = 4, col = "magenta")
  #add the computed barycenter as magenta crosses

res2$cost
#[1] 18.35171
sumppdistnet(res$network$dpath, res2$barycenter, res$ppmatrix, penalty=0.1, type="tt", p=1, q=1)
#[1] 18.35171
#attr(,"distances")
#[1] 3.666471 3.774709 3.950079 3.841166 3.119284