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.


2 Answers 2


I found this article on "Clustering with Constraints" to be a helpful resource to what you're talking about:

Credit: Clustering with Constraints Incorporating Prior Knowledge into Clustering Adapted from a Tutorial of Sugato Basu and Ian Davidson (SDM 2005)


You are describing a variation on optimization, maximize a real function by systematically choosing input values from within an allowed set and computing the value of the function. Specifically, a variation called linear programming where you to maximize the similarity (similarity is the inverse of distance) subject to a couple of constraints:

enter image description here

  • $\begingroup$ I thought about defining a cost function and then minimize it. But I couldn't figure out how to properly do updates. I can't compute a gradient and use gradient descent. Do you have recommendations on how to do updates? $\endgroup$
    – siva
    Commented Apr 6, 2018 at 21:06
  • $\begingroup$ Gradient descent is not the best optimization technique for clustering. Expectation–maximization (EM) is superior for clustering. $\endgroup$ Commented Apr 7, 2018 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.