How to use cluster analysis with grouped data so one cluster may only have not more than one item from each group?

Question

I need to group items by their approximity to each other in multi (<5) dimensional space. The items also have a categorical feature. I need to form groups (clusters) such that none of the records from the same category would appear in thr same cluster. Is there a class of clustering algorithms that can do that?

My way of thinking is to use custom distances that would measure two records in the same category further then ones in different categories. That works to some extent, but it does not guarantee satisfaction of the given requirement.

A simple one dimension (x) + category (c) example:

    x       c
0   0.80    0
1   0.90    1
2   0.10    0
3   0.30    1
4   0.20    0

The goal is to group records into two clusters [0, 1];and [2 or 4, 3]; then record 4 or 2 respectively should remain outside of the second cluster because a record with c=0 is already present in the cluster.

Any suggestions?

Answer 1

You can write your own algorithm. I drafted something up quickly. It can be significantly optimized.

Let's make some random data

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

n = 9
x = np.random.rand(n,2)
y = np.zeros((n,))
y[n//3:2*n//3] = 1
y[2*n//3::] = 2

plt.scatter(x[:,0], x[:,1], c=y)
plt.show()

Now let's get the interdistance of each of these points.

dists = np.asarray([np.linalg.norm(i-j) for i in x for j in x]).reshape(n,n)

plt.imshow(dists)
plt.show()

We will make a list which will hold the radius of each circle for each point. For each point we will iterate over the other points by their relative nearness. If an associated label is not yet seen, add it to the temporary list. Otherwise, we end the function and take the average of the last distance and the current illegal point.

radii = []

for row in dists:
    labels = []
    dis = []
    for i in np.argsort(row):
        if y[i] not in labels:
            labels.append(y[i])
            dis = row[i]
        else:
            dis = (dis + row[i])/2
            break
    radii.append(dis)

Now we can plot these circles by

fig, ax = plt.subplots(figsize=(10,10))

for ix, i in enumerate(radii):
    circle = plt.Circle((x[ix, 0], x[ix, 1]), i, color='b', fill=False, alpha = 0.5)
    ax.add_artist(circle)

plt.scatter(x[:,0], x[:,1], c=y)
plt.xlim([-0.2,1.4])
plt.ylim([-0.2,1.4])
plt.show()

---

If we increase the number of datapoints $n$ we get

Answer 2

Use a constraint optimizer instead.

Define your objective - what is a good result.

Then define your constraints (all points in exactly one group, no duplicate labels in any group) and run it.