Return to Answer

Seconding @mican's recommendation for affinity propagation.

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.

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

Seconding @micans recommendation for Affinity Propagation.

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.

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

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. Only one parameter -- damping and 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).

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

Seconding @mican's recommendation for Affinity Propergation.

From the papar: "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. Only one parameter -- damping and 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 python3:

import numpy as np #from numpy package
import sklearn.cluster  # from sklearn package
import distance #from distance package

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

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. Only one parameter -- damping and 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).