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$ Commented Jul 20, 2014 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
    Commented Jul 20, 2014 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$ Commented Jul 20, 2014 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
    Commented Jul 20, 2014 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
    Commented Jul 20, 2014 at 16:47

1 Answer 1


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.

Wagstaff, K.; Cardie, C.; Rogers, S.; Schrödl, S. (2001). "Constrained K-means Clustering with Background Knowledge". Proceedings of the Eighteenth International Conference on Machine Learning. pp. 577–584.

  • $\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$ Commented Jul 20, 2014 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$ Commented Jul 20, 2014 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$ Commented Jul 20, 2014 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$ Commented Jul 21, 2014 at 9:46

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.