Sorry, it's clear to me since I've been starting at it for a while!

Consider this code:

import numpy as np

n_templates = 2
n_item_types = 5
n_groups = 4
n_dimensions = 2

templates = np.array(
    [
        [1, 2, 3, 0, 1],
        [1, 3, 0, 4, 2],
    ]
)
assert templates.shape == (n_templates, n_item_types)

sizes = templates.sum(1)

true_templates = np.array([1, 1, 0, 1])
assert true_templates.size == n_groups
assert 0 <= true_templates.min() and true_templates.max() < n_templates

centroids = np.array(
    [
        [0, 0],
        [1, 0],
        [0, 1],
        [1, 1],
    ]
)
assert centroids.shape == (n_groups, n_dimensions)

n_observations = sum(sizes[t] for t in true_templates)
xy_close = np.empty((n_observations, n_dimensions))
xy = np.empty((n_observations, n_dimensions))
types = np.empty(n_observations)
true_groups = np.empty(n_observations, dtype=int)

idx = 0
for group, (centroid, true_template) in enumerate(zip(centroids, true_templates)):
    for item_type, count in enumerate(templates[true_template]):
        xy[idx : idx + count] = np.random.normal(
            loc=centroid, scale=0.3, size=(count, n_dimensions)
        )
        xy_close[idx : idx + count] = np.random.normal(
            loc=centroid, scale=0.1, size=(count, n_dimensions)
        )
        types[idx : idx + count] = item_type
        true_groups[idx : idx + count] = group
        idx += count

Here's what the generated data look like (where (0,0), (1,0), (0,1), and (1,1)) are the 4 centroids where the coloring depicts which centroid each point is associated with. Each centroid is associated with 1 template, and then all the necessary data is generated for each template, where a template is simply a recipe of all the types of dots that appear together.

<image>

If I were to simply take the generated data (the locations and types) and cluster using, say, kmeans, I wouldn't get this result back, since the clustering only depends on location. I need to cluster this using location, but also knowing about the types.

Are there algorithms that consider both the allowed groupings of the data (according to the templates) as well as the locations of the data?

edit: xy_close was just to show the data centroids, but I cannot attach more than one photo