I am trying to find a clustering algorithm, but I'm working with already classified items.

Basically, items belongs to one or more category, which are already known. Categories are absolutely not linked each other. I need to create clusters where the number of distinct categories among all items is minimum. The same category could be splitted in several clusters.

Cluster count and cluster size are known at the beginning.


| Item   | Category |
| Item 1 | C1, C2   |                        
| Item 2 | C1       |  cluster count = 2     
| Item 3 | C2       |  cluster size = 3
| Item 4 | C2       |                        
| Item 5 | C3       |
| Item 6 | C1       |

 - Cluster 1: [Item 1, Item 3, Item 4] // 2 categories (C1, C2)
 - Cluster 2: [Item 2, Item 5, Item 6] // 2 categories (C1, C3)

I have already tried custom k-means implementation, but it seems to produce results far from optimal. Am I missing something? Does a well-known algorithm correspond to this kind of problem?

EDIT let's explain a bit more

I need to classify items based on the only attribute I know: their category belonging. I have used a custom distance function, which can be expressed as:

d(I1, I2) = number of category that I1 and I2 do not have in common

I have only tried to use random starting point, and it gives me different results, but far from optimal.

  • $\begingroup$ Can you say more about your situation, your data, & your goals? This all seems rather unusual. How did you run the k-means? Are all of your data categorical? What distance measure did you use? I think k-means only uses squared Euclidean distance & doesn't work well w/ categorical data. Also, k-means is not guaranteed to find the global optimum, only a local optimum; people often have to run it several times, initiallizing it from several different starting places. $\endgroup$ – gung - Reinstate Monica Jul 20 '14 at 13:41
  • $\begingroup$ You did not say anything about the variables (features) by which you want to cluster. Or are the categories the just and only such features? $\endgroup$ – ttnphns Jul 20 '14 at 15:07
  • $\begingroup$ Thanks for your help. Sorry, I'm not familiar with technical terms of data mining. I am not sure to understand what is a feature in my case. I need to classify items in clusters, using the only attribute I know about them: their category belonging. $\endgroup$ – Guillaume Poussel Jul 20 '14 at 16:35
  • $\begingroup$ If the only features to cluster items by are category belongings then you have a classic task to cluster by categorical or binary variables (your question isn't about constrained clustering). $\endgroup$ – ttnphns Jul 20 '14 at 16:47
  • 1
    $\begingroup$ (Cont.) Since an item in your example can belong to >=1 category at once, you have a set of binary variables (each variable = category; 1=belong, 0=no). Compute one of the numerous indices for binary data and submit the matrix of the index values to hierarchical cluster analysis. $\endgroup$ – ttnphns Jul 20 '14 at 16:47

What you are asking for sounds like constrained clustering.

The basic idea is that you have additional information in the form of constraints such as

  • must-link
  • cannot-link

See e.g.


  • $\begingroup$ Thanks for your answer. I have already read this Wikipedia article, but I can't find a link with my input: I can't express binary constraints. $\endgroup$ – Guillaume Poussel Jul 20 '14 at 16:25
  • $\begingroup$ When items 1 and 2 are both labeled as class C1, then this is a must-link constraint. When they are labeled, but do not have any category in common, it is a cannot-link constraint. $\endgroup$ – Anony-Mousse Jul 20 '14 at 16:42
  • $\begingroup$ We cannot have such binary thinking. My example may be misleading, but we can have more items labelled C1 than cluster size. On the other hand, data can be so sparsed that items in the same cluster do not share any category. $\endgroup$ – Guillaume Poussel Jul 20 '14 at 18:35
  • $\begingroup$ The constraints are not exhaustive. They are just the part of the data that you know. If you were required to know everything, then you would not need to run the clustering algorithm. $\endgroup$ – Anony-Mousse Jul 21 '14 at 9:46

Your Answer

