0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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