58
$\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?

Improve this question
$\endgroup$
4
  • 2
    $\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
    Commented Nov 7, 2014 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
    Commented Nov 7, 2014 at 14:53
  • $\begingroup$ related: stackoverflow.com/questions/21511801/… $\endgroup$
    – Andre Holzner
    Commented Nov 6, 2015 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
    Commented Aug 13, 2018 at 21:12

3 Answers 3

Reset to default
69
$\begingroup$

Seconding @micans 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..

It's super easy to use via many packages. It works on anything you can define the pairwise similarity on. 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
from sklearn.cluster import AffinityPropagation
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 = 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).

Improve this answer
$\endgroup$
10
  • $\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$
    – user130733
    Commented Sep 12, 2016 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$
    – Frames Catherine White
    Commented Sep 12, 2016 at 5:56
  • 1
    $\begingroup$ If you really wanted to avoid the dependency on distances. you could use the Rossetta Code Implementation $\endgroup$
    – Frames Catherine White
    Commented Sep 12, 2016 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$
    – user130733
    Commented Sep 13, 2016 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$
    – Frames Catherine White
    Commented Sep 12, 2018 at 9:10
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 7, 2014 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
    Commented Nov 7, 2014 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.

Improve this answer
$\endgroup$
0

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