I have a dataset consisting of 2D points, where each point has an associated key k that influences its y coordinate. The key is an integer k ∈ {0, 1, ..., K}.
I would like to partition the keys into intervals, and cluster the associated 2D points with a fixed budget of N clusters per interval such that some criteria is optimized, e.g. maximize likelihood, minimize SSE, etc. Ultimately, I want to use the clusters to estimate the density of out-of-sample points, i.e. model P(X, Y | k).
To illustrate, I've generated a simple dataset below. Each color represents a different group, and since there are more groups than the cluster budget allows, each group will need to be associated with a cluster.
Here the cluster budget per key interval is N=3. One solution is to partition the key k into intervals {[0, 2], [3, 5], [6, 8]}. The black x markers indicate a cluster center.
Example of how such a model may be used:
- Observe key
k - Look up interval containing
k - Sample points from resulting clusters, or estimate density at some point
p
I'm familiar with methods such as K-means and GMMs, but it's not clear how to incorporate my key input and cluster budget constraint. I've experimented with kernel mixture networks, but the training time and results were not satisfactory.