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

  • $\begingroup$ Why (a, c, d) if a and d have 3 elements in common but a and c have 4 elements in common? $\endgroup$ – marco_gorelli May 30 '18 at 8:55
  • $\begingroup$ 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 $\endgroup$ – 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.

| improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – Nicolò Gasparini May 30 '18 at 10:35
  • 1
    $\begingroup$ 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/… $\endgroup$ – David Masip May 30 '18 at 10:40
  • $\begingroup$ You have to set metric = 'precomputed' in order to do this. $\endgroup$ – David Masip May 30 '18 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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