# Clustering by common elements in a list

Suppose I have these elements:

a = [1, 6, 3, 4, 10, 32, 2, 54]
b = [20, 5, 14, 25, 18, 1]
c = [54, 3, 6, 12, 41, 1, 9]
d = [3, 4, 1]
e = [19, 20, 25, 5]


Each identified by a list of ids (that actually represent a string but we'll use numbers for simplicity).

How can I cluster these by finding those who have the most elements in common?
For example:
a and d have 3 elements in common
b and e have 3 elements in common
a and c have 4 elements in common

So the clusters I would like to have ar (a, c, d) and (b, e).
I would like to obtain this in a Python script

• Why (a, c, d) if a and d have 3 elements in common but a and c have 4 elements in common? – marco_gorelli May 30 '18 at 8:55
• Because c and d also have 2 elements in common, also, it's for clustering purposes, not couple creation, I just want a method to create a bucket where all similar elements would end up – Nicolò Gasparini May 30 '18 at 9:12

In order to do clustering, you only have to define a distance measure. When you have defined a distance, you can apply K-means, hierarchical clustering or other algorithms. In your case, I would define the following distance function:

$d(a, b) = 1 - \frac{\text{number of common elements of a and b}}{\text{maximum between lengths of a and b}}$

As $d(a, a) = 0$ and $d(a, b) > 0$ hold, this can be a distance. I don't think the triangle inequality holds, so this will not be a well-defined distance. However, you can still try to work with this function, it might give good results for your aim.

Edit: sklearn implementation

In order to implement this using scikit-learn, the way to make it work is to use DBSCAN, set metric='precomputed' and pass the distance matrix of our data as an argument. We have to use the precomputed distance matrix because scikit-learn does not allow (now) to use custom distances for clustering.

• I understand, do you believe there is a "standard" distance similar to this? I'm having some trouble in finding a way to apply this custom distance to scikit-learn – Nicolò Gasparini May 30 '18 at 10:35
• The dbscan method uses a distance matrix as an input, so you just have to compute all the distances between your training examples and pass it to the clustering method: scikit-learn.org/stable/modules/generated/… – David Masip May 30 '18 at 10:40
• You have to set metric = 'precomputed' in order to do this. – David Masip May 30 '18 at 10:42