What clustering algorithm should I use for clusters spaced on a grid?

Question

I have some data sets of clusters of points arranged more or less on a regular grid. The data sets have these properties:

1. The data is two, three, or maybe rarely four-dimensional.
2. I know in advance how many rows/columns there are in each dimension (typically 3-6), but the number can differ by dimension.
3. Each grid point has a population centered at it (although I would be interested to know if anything changes if I know in advance that some won't).
4. The grid is pretty evenly aligned with the axes, but may be slightly skewed.
5. Rows/columns are pretty evenly spaced within each dimension, but the spacing can be different from one dimension to the next.
6. The number of points per cluster is similar, maybe up to a factor of two.
7. Each cluster is pretty close to a multivariate gaussian distribution.
8. The variance of each cluster is pretty constant when looking at one dimension at a time.
9. The co-variance of each cluster is pretty constant for each pair of dimensions, and typically takes on one of two values in a particular data set:
   • Occasionally, a low value for the entire first row/column of a dimension (see example)
   • Otherwise, a fairly high value
10. There is a fair amount of overlap between adjacent clusters when looking at a single dimension, but a lot less when you consider the dimensions are correlated.
11. There may be some outlier populations, but these will be much smaller than the ones I am trying to find.

Here's an example of one two-dimensional "slice" of one of these data sets (5x4), where clusters in the bottom row have less covariance than the others:

An overall goal is probably to classify at least 90% of data points correctly, and it would be much better to classify a point as an outlier than as belonging to the wrong cluster. Speed is a slight factor, I might need to process a group of 500 data sets each with 100 clusters of 500-1000 points and the grids might differ slightly between sets. Preferably that wouldn't take all day.

My idea at this point is to treat the data as a gaussian mixture model and use expectation maximization. I could either use the standard model and use what I know about the structure of the data to generate a good initial guess, which will hopefully converge reliably, or I could impose some sort of prior on the cluster means and variances. Looking for other opinions through.

Answer 1

Use Gaussian Mixture Modeling.

You can make it much faster and reliable if you initialize it with a reasonable estimate of where the clusters are, and e.g. by providing an initial covariance matrix.

That data looks well-behaved enough so that EM should just work, so try it.

It also is an option to simply first cut your data set into the observed pieces, then model each grid cell separately.