Given some clusters created from similarity measures between items, is there a recommended way to assign a new item to an existing cluster based on similarity alone? (i.e. avoiding re-clustering)

Measuring the similarity of a new item to all other items is fairly cheap, so I'm looking for a way of using this to assign it to the cluster it's most likely to belong to. It's also important for it to take cluster size into account (i.e. doesn't unfairly weight towards or against larger clusters).

Basically, I'm trying to sacrifice some clustering accuracy in exchange for avoiding a complete re-clustering when the occasional new item is added.

  • $\begingroup$ I'm not sure about type of data you perform clustering on, but maybe this related answer of mine will be helpful in terms of figuring out a method for measuring similarity, optimal for your situation. $\endgroup$ Feb 16, 2015 at 15:20
  • $\begingroup$ If your clusters have an exemplar, you could compare the incoming samples against it, otherwise you could compare it against the centroid, which you could keep track of. I'm not sure what the problem is, as this seems obvious. $\endgroup$
    – Emre
    Feb 16, 2015 at 18:13
  • $\begingroup$ @Emre - that's part of the problem, I don't have an exemplar or centroid for each cluster easily available, though perhaps this is something I can calculate (in case it helps, I'm using MCL clustering - micans.org/mcl, so input is a similarity matrix rather than feature vectors) $\endgroup$ Feb 16, 2015 at 18:20
  • 1
    $\begingroup$ You can always calculate the centroid from the raw features, so I'd give it a try. $\endgroup$
    – Emre
    Feb 16, 2015 at 18:30

1 Answer 1


I suggest you think about this in terms of "data set" and "training set" (technically, it is also recommended to have a separate test set). Once you have your clusters defined on the training set, your can start using them to classify any amount of new data without recalculating, by simply measuring similarity to cluster centroids, for example.

(This doesn't prevent you from deciding to enlarge your training set and data set later, just try to not do that selectively to avoiding overfitting.)

  • $\begingroup$ I guess it's really a method of measuring similarity to a cluster that I'm looking for. The clustering is based on a graph of similarities between nodes, so I don't really have any centroid measurements. $\endgroup$ Feb 16, 2015 at 14:27

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.