Clustering with some cluster centers fixed/known

Question

Thanks for reading my question.

I have several thousand data points scattered on an (x,y) grid that I am trying to cluster. The data points are not uniformly distributed across the grid, but are concentrated in certain areas. I am most interested in identifying the centers of the clusters as representing starting points that minimize the average (Euclidean) distance from a point to the nearest cluster center.

Depending on the specific model and data set, there are between 3 and 7 clusters. The number of clusters is known beforehand in each instance, and does not need to be determined by an algorithm. In each situation, some of the centers of the clusters are known (0 to 4 known starting points), but the rest are unknown. The goal is to identify the centers of the unknown clusters that minimize the average distance to a center across all the data points.

How can I run a clustering algorithm where I can specify a certain number of cluster centers, and solve for the others? I am using R, and have looked primarily at package mclust. My thought was that specifying priors for mean and scale to Mclust with very small scale variances for the known centers and very large scale variances (uninformative prior) for the unknowns would be a good approach, but I am having trouble coding it. The available examples for specifying priors in the package documentation aren't terribly helpful (to me), and might be used for a completely different purpose than what I'm trying to do.

My attempt to code this in R looks something like:

# create data matrix of points
x <- rnorm(100, 50, 25)
y <- rnorm(100, 50, 25)
my.data <- cbind(x,y)

# Two known centers, rest are unknown so provide mean of x,y as default starting point
#
# known centers are (25, 10) and (90, 65), assume midpoints of grid for others
x.prior.mean <- c(25, 90, 50, 50, 50)
y.prior.mean <- c(10, 65, 50, 50, 50)

# Provide small scale (variance) for known centers, large scale for unknown centers (uninformative prior)
x.prior.scale <- c( 0.1, 0.1, 100, 100, 100)
y.prior.scale <- c( 0.1, 0.1, 100, 100, 100)

# Create a cluster model with no prior specified
my.clust.noprior <- Mclust(data=my.data, G=5)

# Now add a prior for mean
my.clust.prior <-   Mclust(data=my.data, G=5, prior=priorControl(mean=cbind(x=x.prior.mean, y=y.prior.mean)))

# Compare what I think are the centers of the clusters (mean of parameters).
# The centers in the prior-specified case don't seem to reflect the known centers
my.clust.noprior$parameters$mean
my.clust.prior$parameters$mean

# Commented out, but attempting the following statement that adds scale parameter yields an error:
#    Error in chol.default(priorParams$scale) : non-square matrix in 'chol'
#
# my.clust <-   Mclust(data=my.data, G=5, prior=priorControl(mean=cbind(x=x.prior.mean, y=y.prior.mean), scale=cbind(x.prior.scale, y.prior.scale)))

Is there a way to accomplish what I'm trying to do? I am open to using other R packages besides mclust if there's one better suited for this problem.

Thank you

Answer 1

Sorry I can't help with mclust (I don't know r). What if you run K-mean clustering with some initial centres fixed and some free to move? To fix a centre you simply need to pad it with large amount of points. For example, if there is centre A with known coordinates, to fix it add many (say, a thousand) extra data points, all with these same coordinates, so that during iterations the centre will be pinned to its position under their "gravity". As for the centres you want to move and eventually find their positions, specify some approximate guess coordinates for them at the start of iterations.