1
$\begingroup$

I have a list of words (names actually) on which I would like to apply some entity resolution. My first guess was to create clusters of similar names so I could extract a representative entity from multiple name shapes.

I need to specify that I have no labelled data, and I am not working on a document analysis (this is different from Improve results of a clustering for example), only a raw list.

To do so, and based on what I could read, I attempted two approaches :

  • apply n-gram transformation on my names and use k-means clustering

  • apply n-gram transformation, compute a similarity matrix (cosine distance) and use it for affinity propagation

Both approaches give me interesting results, yet I can't understand some of the results. For example, I get the following clusters :

Geronese, Varonese, Veronefe, Veronese, Veronesse, ...

Cameroni, Veronèse, Veronèse P., Veronése, Veronêse

Why do I get two different clusters for shapes that look so similar (except for Cameroni which I don't know why it is in that cluster) ? Is this a problem in the k-means algorithm tuning ?

Also, I tried using the silhouette metrics to find the optimum number of clusters but I get the exact same value no matter what is the number of clusters (0.315 for what it's worth).

As for the affinity propagation approach, I get a lower silhouette score for my clusters, and I get some similar effects, like having this kind of cluster :

Birttetti, Laruette, Laruelle, Larvette, Laurette, ...

Any ideas how I could improve my results (if this is possible) ? Or maybe any idea for a better approach than mine ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I cannot write comments yet, so I will start with an answer that still contains some questions, feel free to complement/correct it!

A) The data

Without any contextual information, it looks like the only solution you have to link entities is their character similarity. I don't know which distance metric you use, but have you tried these metrics that are well designed for string data?:

  • Levenshtein distance (also called string edit distance): basically computes the number of operations needed to transform one string into another
  • Jaro-Winkler distance: close to levenshtein but favoring strings with a common prefix
  • Jaccard similarity: roughly computes the ratio of common elements between two sets, be it characters, ngrams, words..

You can try these metrics without the n-gram transformation first, but also on transformed data and use cosine distance afterwards.

You can also perform additional normalization but you need to assess whether it is relevant for your dataset, which I don't know, so I am just firing ideas, not advices: stripping accents, special characters, short tokens (like the 'P.' in your example), which will reduce the variance in your data.

B) The clustering

One thing that could explain your result is that with KMeans or Affinity Propagation, any data point must belong to a cluster, so names that should be alone are assigned to the cluster so that it minimizes the loss of the algorithm.

Have you thought of trying DBSCAN? It can label some data points as noise, and if you are using one of the string distances above, you can encode prior knowledge about the maximum distance between two potential matches through the epsilon parameter.

But as with any unsupervised method, you will never have the guarantee to get rid of noise.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you for those hints ! Regarding A)The data : I mostly used cosine distance, but also did try Levensthein distance on raw data, with similar yet slightly less satisfying results. Didn't try the two other though. As for the normalization process, I thought the ngram transformation (using ntlk.util package) would do strip accents but after double checking, it is not ! I will try to add this and estimate the benefit. $\endgroup$
    – Beinje
    Mar 26, 2020 at 16:12
  • $\begingroup$ As for the B), this is interesting to know. You're right, some names probably should be alone. I didn't try DBSCAN so I'll give it a try. Not sure about how to tune the epsilon parameter though but I get the idea behind : estimate the maximum difference between 2 shapes for belonging to the same cluster ? $\endgroup$
    – Beinje
    Mar 26, 2020 at 16:14
  • $\begingroup$ @A Co I tried testing DBSCAN using an estimated epsilon parameter, but I get only ~1-5 clusters and a roughly 90% noise points... Even if I set epsilon at the max distance computed (with Levenshtein), which is 20, I still get 33% noise points, how is it possible ? $\endgroup$
    – Beinje
    Mar 27, 2020 at 13:14
  • $\begingroup$ @Beinje actually the epsilon value interpretation is a bit different from what you have here. DBSCAN starts by finding 'core points', which are points having more than min_points in their neighborhood. The notion of neighborhood is controled by epsilon: two points that are at a distance less than epsilon are in the same neighborhood. A point is assigned to a cluster only if it is at a distance less than epsilon from a core point belonging to that cluster. $\endgroup$
    – A Co
    Mar 27, 2020 at 13:59
  • $\begingroup$ So if a point A is at a distance less than epsilon from another point B belonging to a cluster, it will be assigned to the cluster only if B is a core point. But if B is not, meaning B has less than min_points points in its neighborhood, A will be labeled as noise. That explains the 33% nois points left. If you set min_points = 2 and epsilon = maximum distance computed, you should get one big connected cluster $\endgroup$
    – A Co
    Mar 27, 2020 at 14:03

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.