Clustering unknown product names

Question

I have a parser that reads messages that contain product names. I would like to automatically cluster product names in clusters where each cluster would be one product and all the ways it can be written in, i.e. 'laptop', 'lptop', 'lptopt', laptop/laptop' etc. The idea is that I can review this weekly and see which products I do not cover yet and add them manually to my parser.

The products I cover usually have two words in it, one describes product group, and another describes type. For example, I can have a string 'car/mercedes' or 'truck/volvo'. It might be better performing to cluster both the product group such as the 'car' and then subcluster 'mercedes' in it.

From what I gather I need to choose a distance metric such as Jaccard/Levenshtein/... and use a clustering algorithm such as Hierarchical Clustering. However I don't know how many products there are in total so I don't know how many clusters.

Note: the product names I handle are not really English words, so methods that rely on semantic differences won't work here. I need to compare actual strings as sequences.

How do I frame this problem?

Answer 1

Can you try this and give me feedback?

import numpy as np
from sklearn.cluster import AffinityPropagation
import distance
    
words = "kitten belly squooshy merley best eating google feedback face extension impressed map feedback google eating face extension climbing key".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))

Result:

• eating: climbing, eating
• google: google, squooshy
• face: face, map
• impressed: impressed
• feedback: feedback
• extension: extension
• key: belly, best, key, kitten, merley