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).