31
$\begingroup$

I have the following problem at hand: I have a very long list of words, possibly names, surnames, etc. I need to cluster this word list, such that similar words, for example words with similar edit (Levenshtein) distance appears in the same cluster. For example "algorithm" and "alogrithm" should have high chances to appear in the same cluster.

I am well aware of the classical unsupervised clustering methods like k-means clustering, EM clustering in the Pattern Recognition literature. The problem here is that these methods work on points which reside in a vector space. I have words of strings at my hand here. It seems that, the question of how to represent strings in a numerical vector space and to calculate "means" of string clusters is not sufficiently answered, according to my survey efforts until now. A naive approach to attack this problem would be to combine k-Means clustering with Levenshtein distance, but the question still remains "How to represent "means" of strings?". There is a weight called as TF-IDF weight, but it seems that it is mostly related to the area of "text document" clustering, not for the clustering of single words. It seems that there are some special string clustering algorithms existing, like the one at http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

My search in this area is going on still, but I wanted to get ideas from here as well. What would you do recommend in this case, is anyone aware of any methods for this kind of problem?

$\endgroup$
  • 1
    $\begingroup$ I have learned about the existence of a variant of k-means named as "K-medoids". en.wikipedia.org/wiki/K-medoids It does not work witk L2 Euclidian distance and does not need the calculation of means. It uses the data point which is closest to other ones in a cluster as the "medoid". $\endgroup$ – Ufuk Can Bicici Nov 7 '14 at 13:32
  • 1
    $\begingroup$ It seems that there are some special string clustering algorithms. If you come from specifically text-mining field, not statistics /data analysis, this statement is warranted. However, if you get to learn clustering branch as it is you'll find that there exist no "special" algorithms for string data. The "special" is how you pre-process such data before you input it into a cluster analysis. $\endgroup$ – ttnphns Nov 7 '14 at 14:53
  • $\begingroup$ related: stackoverflow.com/questions/21511801/… $\endgroup$ – Andre Holzner Nov 6 '15 at 20:16
  • $\begingroup$ Note the difference between Affinity Propagation and K-Means clustering and how it will effect compute time. quora.com/… $\endgroup$ – Gabriel Alon Aug 13 '18 at 21:12
37
$\begingroup$

Seconding @mican's recommendation for affinity propagation.

From the paper: L Frey, Brendan J., and Delbert Dueck. "Clustering by passing messages between data points." science 315.5814 (2007): 972-976..

Its super easy to use via many packages. It works on anything you can define the pairwise similarity one. Which you can get by multiplying the Levenshtein distance by -1.

I threw together a quick example using the first paragraph of your question as input. In Python 3:

import numpy as np
import sklearn.cluster
import distance

words = "YOUR WORDS HERE".split(" ") #Replace this line
words = np.asarray(words) #So that indexing with a list will work
lev_similarity = -1*np.array([[distance.levenshtein(w1,w2) for w1 in words] for w2 in words])

affprop = sklearn.cluster.AffinityPropagation(affinity="precomputed", damping=0.5)
affprop.fit(lev_similarity)
for cluster_id in np.unique(affprop.labels_):
    exemplar = words[affprop.cluster_centers_indices_[cluster_id]]
    cluster = np.unique(words[np.nonzero(affprop.labels_==cluster_id)])
    cluster_str = ", ".join(cluster)
    print(" - *%s:* %s" % (exemplar, cluster_str))

Output was (exemplars in italics to the left of the cluster they are exemplar of):

  • have: chances, edit, hand, have, high
  • following: following
  • problem: problem
  • I: I, a, at, etc, in, list, of
  • possibly: possibly
  • cluster: cluster
  • word: For, and, for, long, need, should, very, word, words
  • similar: similar
  • Levenshtein: Levenshtein
  • distance: distance
  • the: that, the, this, to, with
  • same: example, list, names, same, such, surnames
  • algorithm: algorithm, alogrithm
  • appear: appear, appears

Running it on a list of 50 random first names:

  • Diane: Deana, Diane, Dionne, Gerald, Irina, Lisette, Minna, Nicki, Ricki
  • Jani: Clair, Jani, Jason, Jc, Kimi, Lang, Marcus, Maxima, Randi, Raul
  • Verline: Destiny, Kellye, Marylin, Mercedes, Sterling, Verline
  • Glenn: Elenor, Glenn, Gwenda
  • Armandina: Armandina, Augustina
  • Shiela: Ahmed, Estella, Milissa, Shiela, Thresa, Wynell
  • Laureen: Autumn, Haydee, Laureen, Lauren
  • Alberto: Albertha, Alberto, Robert
  • Lore: Ammie, Doreen, Eura, Josef, Lore, Lori, Porter

Looks pretty great to me (that was fun).

$\endgroup$
  • $\begingroup$ is it possible to have the same algorithm using only sklearn? or use scipy.spatial.distance with hamming? what is the advantage to use levenshtein? I guess i will have to try using this question: stackoverflow.com/questions/4588541/… $\endgroup$ – pierre Sep 12 '16 at 5:41
  • 1
    $\begingroup$ @pierre Levenshtein is what I would call a "spellchecker's distance", it is a good proxy for the chance of a human spelling mistake. Damerau Levenshtein might be even better. I don't know that Hamming Distance is defined for strings of nonequal lengths. It only allows swaps, not insertions. determining how to pad/trim the string most reasonably is almost as hard as calculating the Levenshtein distence. Should you pad/trim the start? The end? Some from the middle? $\endgroup$ – Lyndon White Sep 12 '16 at 5:56
  • $\begingroup$ If you really wanted to avoid the dependency on distances. you could use the Rossetta Code Implementation $\endgroup$ – Lyndon White Sep 12 '16 at 6:03
  • $\begingroup$ reading the en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance i can see how transposition can make the difference specially for typo and python has a brand new package for it. I can see how i can use this against a list of words and get the "closest one" but may be not the most important. I have to get my list and check with the tf-idf. Cool thank you $\endgroup$ – pierre Sep 13 '16 at 19:47
  • 1
    $\begingroup$ @dduhaime almost certainly. In general Affinity Propagation works for nonsymatric perferences, but since this is symmetric go ahead. I am sure something in SciPy has a triangular matrix type that ducktypes as a complete matrix. I've been over in julia-lang land too long and can't recall how this is done in python. (In julia you'ld use Symmetric) $\endgroup$ – Lyndon White Sep 12 '18 at 9:10
5
$\begingroup$

Use graph clustering algorithms, such as Louvain clustering, Restricted Neighbourhood Search Clustering (RNSC), Affinity Propgation Clustering (APC), or the Markov Cluster algorithm (MCL).

$\endgroup$
  • $\begingroup$ What about the K-medoids method I have found? I need to implement this solution as soon as possible, so it seemed a good solution to me. I am aware of the existence of these graph based methods but I am afraid that I cannot afford the time I need to understand and implement those. $\endgroup$ – Ufuk Can Bicici Nov 7 '14 at 15:02
  • $\begingroup$ For all of them software is available with fairly non-restrictive licensing agreements, such as the GNU GPL. I am not a big fan of the k-mediods type of algorithm mostly because of the k parameter but it's up to you naturally. If you need an in-house implementation then I think APC and MCL are probably the easiest to implement. If you were to do that, try them out first of course. $\endgroup$ – micans Nov 7 '14 at 16:36
2
$\begingroup$

You could try the vector space model with the n-grams of the words as the vector space entries. I think you would have to use a measure like cosine similarity in this case instead of edit distance.

$\endgroup$

protected by Community Nov 9 '18 at 10:10

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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