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

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?

• Can we see a sample of your dataset? – Aditya Mar 14 '18 at 0:36
• @Aditya I have updated the post. – Mitya Gimon Mar 14 '18 at 14:15

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


Now we can plot these circles by

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

circle = plt.Circle((x[ix, 0], x[ix, 1]), i, color='b', fill=False, alpha = 0.5)

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

• Thank you @JahKnows, that's a great suggestion. I will work from there. It is also important to know, that is no established algorithm. – Mitya Gimon Mar 16 '18 at 16:37
• Let me know if I can help with anything! – JahKnows Mar 17 '18 at 2:51