2
$\begingroup$

I have a text file document containing a set of words strings that I want to cluster. I want to use the K-means algorithm. As a distance I'll be using the Levenshtein distance.

Question

Usually if we have for example real number vectors we can just compute the mean of all the vectors and it will represent the centroid of the cluster.

What approach can I use to compute the centroid of a cluster containing strings?

$\endgroup$
3
  • $\begingroup$ @micans The algorithms that you suggested can handle string clustering right? What you said about the euclidean space is interesting. Can you please explain more. Thank you. $\endgroup$
    – Hani Gotc
    Mar 7, 2014 at 11:36
  • $\begingroup$ ok Thank you @micans . Can you add it as an answer please. $\endgroup$
    – Hani Gotc
    Mar 7, 2014 at 13:20
  • $\begingroup$ I'm working on a similar problem, was wondering if you had any progress? $\endgroup$
    – djechlin
    Jul 15, 2014 at 21:30

1 Answer 1

2
$\begingroup$

I would strongly recommend using a network clustering algorithm rather than K-means. K-means is strongly tied to Euclidean distances (and variance minimisation), and what you have is something completely different. A number of well-known network algorithms are Louvain clustering, RNSC, Affinity Propagation Clustering, and MCL.

Strings are a type of data that I think maps well onto networks, as the pair-wise relation is not really based on measurement of traits but rather on direct comparison. (Another situation where network approaches make sense is in certain types of high-dimensional data). In bioinformatics sequence clustering with string similarity has been very successfully approached using network clustering algorithms. NOTE you need a similarity, not a distance. For more information on K-means and where it is applicable see e.g. Anony Mousse's answer here - Why only the mean value is used in (K-means) clustering method?. Anony Mousse has written about this many times, with great insight.

$\endgroup$

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.