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?