Clustering lists based on values

logicNotFound 0
Viewed 30

If we have a input of a dictionary with format {key: [list]} like below

List1: [value01, value02, value 03]
List2: [value02, value04, value 05]
List3: [value04, value05, value 07]
  • The values are strings

Is there a way where we can group/cluster the keys (list names ) based on the similarity between it's values(lists) in python?

Thanks in advance!

hierarchical-clustering dbscan data-science python-3.x python
1 Answers

Really sorry for the late answer, I'm not a frequent user of SO.

To group by percentage a function like so should do the trick:

import difflib

def cluster(seq_matcher, input_dict, percentage):
 joined_dict = {key : "".join(values) for key, values in input_dict.items()}
 all_values = tuple(joined_dict.values())
 for i, key in enumerate(joined_dict):
  values = joined_dict[key]
  if any(seq_matcher(values, other_values) >= percentage for other_values in all_values[:i]):
   joined_dict[key] = 0
 return {key : values for key, values in input_dict.items() if joined_dict[key]}

seq_matcher = lambda x, y: difflib.SequenceMatcher(None, x, y).ratio() * 100
cluster(seq_matcher, input_dict, 60)

One of the best ways to compare iterables in python is using the difflib module as described below. Of course, different sequence matchers have different key features which you want so to use, so to change the algorithm which determines the percentage similarity between your lists of values you can change the seq_matcher function.

I recommend the difflib sequence matcher because it's the best algorithm in terms of comparing objects the way a human would.

You can also change the percentage argument to, as you can probably imagine, change the percentage cutoff for keys.

Hope this helps!

user173018340
Related