How to identify similar sublists in a list and visualize the clusters?

Question

Consider a list (list) as

list = {{50, 124, 53, 25, 100, 28, 5, 52, 3, 4}, {1, 51, 31, 27, 25, 28, 2, 
  50, 4, 26}, {26, 23, 75, 1, 24, 50, 2, 25, 4, 3}, {29, 28, 27, 23, 
  26, 7, 25, 4, 3, 1}, {51, 75, 23, 53, 27, 22, 5, 1, 50, 4}, {75, 25,
   27, 4, 28, 5, 51, 50, 3, 1}, {25, 76, 22, 23, 26, 5, 4, 50, 27, 
  2}, {52, 7, 23, 49, 4, 1, 24, 3, 50, 27}, {3, 25, 22, 73, 27, 74, 2,
   49, 21, 4}, {71, 79, 29, 8, 154, 75, 46, 125, 100, 54}, {48, 27, 
  50, 52, 26, 25, 4, 2, 6, 3}, {5, 76, 28, 49, 52, 26, 4, 25, 3, 
  50}, {76, 30, 75, 74, 100, 49, 1, 4, 3, 25}, {27, 53, 4, 54, 1, 5, 
  3, 26, 25, 2}, {75, 1, 50, 5, 26, 4, 2, 51, 25, 3}, {49, 23, 52, 50,
   28, 4, 6, 1, 2, 3}, {100, 28, 26, 53, 52, 48, 50, 4, 2, 3}, {78, 
  77, 1, 50, 98, 25, 125, 48, 4, 73}, {62, 56, 75, 8, 101, 154, 125, 
  46, 100, 54}, {125, 153, 56, 8, 53, 154, 99, 46, 100, 54}, {101, 
  124, 21, 2, 100, 50, 54, 3, 24, 25}, {22, 74, 28, 73, 21, 4, 99, 26,
   1, 51}, {28, 73, 100, 3, 49, 50, 23, 25, 1, 2}, {23, 22, 5, 4, 52, 
  3, 100, 27, 2, 1}, {7, 49, 77, 78, 125, 22, 4, 3, 25, 52}, {25, 98, 
  2, 125, 73, 50, 4, 48, 23, 52}, {77, 123, 100, 125, 102, 25, 75, 48,
   4, 73}, {105, 8, 106, 154, 99, 179, 46, 125, 100, 54}, {52, 146, 
  53, 8, 56, 50, 154, 46, 54, 100}, {1, 55, 26, 200, 125, 100, 50, 54,
   75, 25}, {146, 47, 28, 103, 49, 27, 52, 2, 50, 73}, {2, 103, 100, 
  1, 99, 29, 76, 25, 50, 26}, {100, 50, 125, 74, 104, 49, 1, 75, 25, 
  77}, {74, 50, 26, 20, 28, 49, 52, 77, 1, 25}, {2, 25, 49, 125, 5, 4,
   75, 48, 52, 23}, {98, 75, 102, 48, 77, 25, 4, 125, 5, 73}, {150, 
  58, 8, 53, 46, 55, 154, 125, 100, 54}, {55, 146, 53, 101, 52, 46, 8,
   154, 54, 100}, {71, 151, 75, 51, 99, 24, 53, 100, 125, 25}, {25, 
  50, 21, 52, 47, 28, 96, 77, 72, 75}, {50, 27, 73, 23, 49, 24, 100, 
  2, 25, 51}, {99, 124, 25, 24, 97, 27, 51, 72, 100, 50}, {150, 99, 
  24, 4, 52, 74, 102, 26, 27, 25}, {1, 75, 102, 2, 73, 125, 4, 52, 23,
   48}, {75, 72, 3, 77, 125, 98, 25, 48, 4, 73}, {53, 104, 102, 46, 8,
   75, 154, 125, 100, 54}, {146, 55, 50, 8, 75, 53, 154, 46, 54, 
  100}, {29, 50, 124, 1, 125, 49, 150, 54, 100, 25}, {123, 1, 49, 51, 
  21, 151, 53, 48, 26, 100}, {50, 148, 49, 75, 73, 28, 23, 1, 26, 
  25}, {29, 26, 125, 75, 77, 49, 25, 51, 1, 50}, {101, 125, 4, 53, 77,
   25, 52, 51, 49, 75}, {73, 75, 102, 24, 50, 4, 48, 52, 23, 2}, {100,
   3, 98, 102, 125, 5, 77, 4, 48, 73}, {29, 8, 46, 179, 79, 75, 53, 
  125, 100, 54}, {125, 51, 146, 105, 55, 8, 46, 154, 54, 100}, {48, 
  101, 24, 52, 150, 125, 25, 26, 100, 54}, {50, 100, 22, 2, 51, 49, 
  24, 75, 28, 1}, {101, 22, 47, 102, 71, 28, 27, 50, 51, 1}, {23, 26, 
  51, 27, 28, 48, 49, 2, 1, 50}, {29, 50, 1, 125, 27, 52, 77, 4, 53, 
  28}, {127, 3, 2, 73, 50, 52, 4, 5, 23, 48}, {102, 100, 98, 77, 5, 
  52, 125, 4, 48, 73}, {8, 50, 150, 75, 79, 25, 46, 125, 100, 
  54}, {52, 22, 28, 3, 99, 27, 53, 100, 25, 54}, {100, 125, 72, 275, 
  150, 50, 25, 175, 22, 28}, {26, 200, 97, 125, 6, 31, 47, 22, 50, 
  28}, {47, 32, 4, 25, 31, 6, 3, 1, 22, 28}, {2, 47, 75, 1, 200, 25, 
  6, 53, 22, 28}, {53, 3, 26, 30, 2, 47, 1, 6, 22, 28}, {47, 2, 23, 
  50, 24, 52, 28, 73, 22, 4}, {23, 25, 1, 4, 5, 77, 75, 125, 48, 
  73}, {51, 2, 3, 30, 53, 1, 54, 28, 27, 125}, {50, 29, 23, 30, 24, 
  22, 2, 26, 27, 28}, {4, 150, 22, 50, 24, 23, 26, 175, 27, 28}, {25, 
  24, 29, 47, 22, 125, 3, 26, 27, 28}, {29, 30, 1, 31, 24, 22, 26, 2, 
  28, 27}, {25, 200, 52, 125, 29, 24, 26, 27, 75, 28}, {33, 3, 2, 23, 
  29, 31, 24, 26, 27, 28}, {22, 200, 31, 75, 29, 125, 2, 26, 28, 
  27}, {18, 125, 75, 47, 25, 53, 52, 1, 73, 4}};

Each sublist in list has 10 elements. I need to cluster the sublists based on the similarity between them and visualize the clusters. For example, if I set the similarity threshold to be 5 i.e. two sublists will belong to the same cluster if they have minimum 5 common elements, I can have a sample cluster as highlighted in the image below:

One approach can be to compare each sublist with the other and find the similarity. But this approach is very tedious.

Is there any smarter way to this?

Answer 1

If we define a test function that counts the similar elements

similarElements[a_, b_] := 
 Length[a] + Length[b] - Length[DeleteDuplicates[Join[a, b]]]

then the clustering is just a matter of doing

clusters = Gather[list, similarElements[#1, #2] >= 5 &]

To display the clusters together, you can use a combination of Grid and Multicolumn:

Style[Multicolumn[
  Framed@Grid[#, Alignment -> Right, ItemSize -> {1.8, 1}] & /@ 
   clusters, 3], 8]

---

I did not really like ordering by cluster length much though and I thought we could do something better.

For starters, let's sort the clusters by decreasing length and mix then taking one from the beginning and one from the end

mid = Ceiling[Length[clusters]/2];
clustersSorted = Reverse@SortBy[clusters, Length];
newclusters = 
  Riffle[Take[clustersSorted, mid], 
   Reverse@Drop[Reverse@SortBy[clustersSorted, Length], mid]];

This is the length of the re-sorted clusters:

Length /@ newclusters

(* {21, 1, 14, 1, 12, 1, 11, 1, 4, 1, 4, 2, 4, 2, 2} *)

Now we can fill the columns by assigning each successive cluster to the column with the least total elements

columns = {{}, {}, {}};
Scan[AppendTo[
    columns[[First[
       OrderingBy[columns, Length[Flatten[#, 1]] &, 1]]]], #] &, 
  newclusters];

This is the result

Style[Row[
  Map[Column[#, BaselinePosition -> Top] &, 
   Map[Framed@Grid[#, Alignment -> Right, ItemSize -> {1.8, 1}] &, 
    columns, {2}]], Spacer[2]], 8]

Better, but still not perfect. The issue here is that the gap between the grids takes up space that we are not counting. Let's add it!

columns = {{}, {}, {}};
Scan[AppendTo[
    columns[[First[
       OrderingBy[columns, Length[Flatten[#, 1]] + Length[#] - 1 &, 
        1]]]], #] &, newclusters];

And now it's what I wanted

Answer 2

One possible reading of the requirement

if I set the similarity threshold to be 5 (...). two sublists will belong to the same cluster if they have minimum 5 common elements

is as follows:

ClearAll[clusterF]
clusterF[a : ("Index" | "List" | "Grid") : "Grid"] := Module[{lst = #, t = #2, clstr}, 
  clstr = First @ ConnectedComponents @ RelationGraph[
    UnsameQ[##] && Length[Intersection[lst[[#]], lst[[#2]]]] >= t &, Range[Length @ lst]];
  Switch[a, "Index", clstr, "List", lst[[clstr]], _, 
    Grid[lst[[Join[clstr, Complement[Range[Length@lst], clstr]]]], 
      Frame -> {None, None, {{{1, Length[clstr]}, {1, -1}} -> True}}, 
      FrameStyle -> Directive[Thick, Green]]]] &;

Examples:

There is a single cluster containing all elements if the threshold t is less than 6:

TableForm[Transpose[{#, Length[clusterF["Index"][list, #]]} & /@ Range[10]],
 TableHeadings -> {{"threshold", "cluster size"}, None}]

clusterF[][list, 6]

clusterF[][list, 8]

Note: You can use the test function Length[Intersection[##]] >= 5 & as the second argument of Gather to get the result in @Batracos's answer.

 Gather[list, Length[Intersection[##]] >= 5 &] == 
   Gather[list, similarElements[#1, #2] >= 5 &] 

True

However, (if the above interpretation of OP's requirement is correct), this result does not satisfy the requirement that two sublists belong to the same cluster if they have minimum 5 common elements. For example, Gather[list, similarElements[#1, #2] >= 5 &] gives 15 groups with lengths

Length /@ (clusters = Gather[list, similarElements[#1, #2] >= 5 &])

{14, 21, 4, 2, 12, 11, 4, 1, 2, 2, 1, 1, 1, 1, 4}

If we check, for example, the intersection of the first element in the third group (clusters[[3,1]] with some elements of the first group (clusters[[1, {2, 3, 4, 7, 10, 11, 12, 13}]]), we see that clusters[[3,1]] have 5 or more common elements with each of the elements clusters[[1, {2, 3, 4, 7, 10, 11, 12, 13}]], so it must belong to the same cluster per OP's requirement:

Length[Intersection[#, clusters[[3, 1]]]] & /@ 
 clusters[[1, {2, 3, 4, 7, 10, 11, 12, 13}]]

{5, 5, 5, 7, 5, 6, 5, 5}