I have data of 90 persons.

Data of a person:
- x coordinate
- y coordinate
- score (1 to 6)

I want to form groups of 9 people each so that:
- the distance between people in one group is as small as possible
- people with the same coordinates are in different groups
- people within a group should have different scores

I am not expecting a full-fledged algorithm but rather hints in the right direction. So far I am using a simple k-means algorithm which forms groups so that the distance between people gets minimized however the two other constraints are not considered, unfortunately.

  • $\begingroup$ What is the distance between two people in your case? $\endgroup$
    – Frostic
    Apr 5, 2018 at 15:14
  • 1
    $\begingroup$ If there are 9 in a group but only 6 scores how do people within a group have different scores? $\endgroup$
    – user121049
    Apr 5, 2018 at 15:31
  • $\begingroup$ It may be a continuous score in [1,6] $\endgroup$
    – Ripstein
    Apr 5, 2018 at 15:36

1 Answer 1


What you are looking for is actually called constrained clustering

There are different examples of them, but probably none as the one you want to do. For example, this one by Microsoft imposes the constraint of neglect clusters with few points. Section 2 shows you how they imposed constrains.

An additional possible way is pure brute force: for each iteration of the algorithm, simply analyze the proposal given by k-means and reject it if it does not fulfill your requirements.

I recommend you to consider posting this question in Data Science as well


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .