2
$\begingroup$

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:

enter image description here

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?

$\endgroup$
2
$\begingroup$

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]

clustering 1


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]

clustering 2

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

clustering 3

$\endgroup$
2
$\begingroup$

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}]

enter image description here

clusterF[][list, 6]

enter image description here

clusterF[][list, 8]

enter image description here

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}

$\endgroup$

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.