I have a problem where I have a list of n words with truly k different ones (k is unknown) because some may be malformed or contracted. I would like to automatically cluster them.

I thought about using something like a dendogram with a distance between words (I don't know which), how can this be handled efficiently?


You can get a dendrogram from any hierarchical clustering method. The tricky thing here is how to compute the distances between the words. If efficiency is your main concern, I would consider using HDBSCAN clustering.

The Jaro-Winkler distance was originally designed for such tasks. There is an efficient implementation in the python Levenshtein package, but it still might be too slow for computing the distance between all pairs of words.

If this is still too slow, you can opt for some more approximative methods and represented the strings as vectors - bags of characters (or character n-grams). You lose some information about how exactly characters are ordered in the string, but you will get them represented as vectors and vector comparison is fast. In this way, you can use algorithms that do not require comparing all pairs of data points such as K-Means.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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