3
$\begingroup$

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?

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

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()

enter image description here

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()

enter image description here

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()

enter image description here


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

enter image description here

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

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.

$\endgroup$

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.