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:

Example data grid

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.


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.

| cite | improve this answer | |
  • $\begingroup$ Thanks, this is how I've been going about it. I've been getting a guess on the grid by fitting 1D GMMs on each dimension separately, then using those fits to initialize the means, variances, and weights of the clusters in the full space. I'm getting good fits on maybe 93 or 94 of 96 populations in a 6x4x4 grid. From here I think I could get better results by using more data points (requires some optimizations for speed) or initializing clusters with some positive covariance. When I figure it out I'll post the exact tweaks I had to make and mark this as the correct answer. $\endgroup$ – JaredL Jul 2 '15 at 18:36
  • $\begingroup$ Haven't had a chance to optimize further, but I'm going to go ahead and mark this as correct as I'm already getting close to optimal results. People seem to be interested in this question so I'll post additional important optimizations here soon after I've done a bit more exploring. $\endgroup$ – JaredL Jul 9 '15 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.