# Separating objects into a constrained number of groups where data is known about all object pairs

In Frequency Planning, we may know the interference between one cell and another cell. You may be a able to operate a specific number of frequencies. How would one separate them into the best groups. I have been toying with Classify but am unable to see how to program it to perform the required grouping.

I have a program to produce sample data.

Combinations[all___] := Flatten[Outer[List, all, 1], Length[{all}] - 1];
all=ToString/@Range[6];
groups=ToString[#]&/@Range[2];
contents=Association[];
(contents[#]=groups[[1]])&/@all[[;;3]];
(contents[#]=groups[[2]])&/@all[[4;;]];
contents;
reverseContents=contents//Normal//GroupBy[Last->First];
makeValues[{a_,b_}]:=Module[{},
If[a==b,Missing[],
c=contents[a]==contents[b];
If[c,
{a,b,RandomReal[{-28,-50}],{a,b}->"same group"},
{a,b,RandomReal[{0,-30}],{a,b}->"different group"}
]]];
training=Select[makeValues/@Combinations[all,all],Not[MissingQ[#]]&];


The data as I have programmed gives the following dataset where the fourth column is the recommendation. Either the nodes should be in the same group or they should be in different groups.

Grid[training]
1   2   -36.0319    {1,2}->same group
1   3   -33.4696    {1,3}->same group
1   4   -26.8633    {1,4}->different group
1   5   -18.9969    {1,5}->different group
1   6   -14.5339    {1,6}->different group
2   1   -42.4544    {2,1}->same group
2   3   -32.0968    {2,3}->same group
2   4   -25.3401    {2,4}->different group
2   5   -19.9827    {2,5}->different group
2   6   -7.73741    {2,6}->different group
3   1   -49.5421    {3,1}->same group
3   2   -41.9788    {3,2}->same group
3   4   -13.1989    {3,4}->different group
3   5   -18.0183    {3,5}->different group
3   6   -10.5025    {3,6}->different group
4   1   -17.6852    {4,1}->different group
4   2   -0.997097   {4,2}->different group
4   3   -5.0447     {4,3}->different group
4   5   -47.2881    {4,5}->same group
4   6   -43.6139    {4,6}->same group
5   1   -20.8662    {5,1}->different group
5   2   -29.4012    {5,2}->different group
5   3   -4.96949    {5,3}->different group
5   4   -31.5497    {5,4}->same group
5   6   -29.7002    {5,6}->same group
6   1   -3.60692    {6,1}->different group
6   2   -28.6723    {6,2}->different group
6   3   -12.8056    {6,3}->different group
6   4   -44.3089    {6,4}->same group
6   5   -48.3195    {6,5}->same group


This is a simple example I plan to expand to hundreds of cells and up to 10 groups. Anybody's help would be much appreciated.

• Linear programming comes up quite a lot with allocation problems like these. Apr 27 at 17:49

This seems like it would be best interpreted as a graph partition problem instead of looking at it like a 'machine learning' problem.

data = {
{1, 2, -36.0319, {1, 2} -> "same"},
{1, 3, -33.4696, {1, 3} -> "same"},
{1, 4, -26.8633, {1, 4} -> "different"},
{1, 5, -18.9969, {1, 5} -> "different"},
{1, 6, -14.5339, {1, 6} -> "different"},
{2, 1, -42.4544, {2, 1} -> "same"},
{2, 3, -32.0968, {2, 3} -> "same"},
{2, 4, -25.3401, {2, 4} -> "different"},
{2, 5, -19.9827, {2, 5} -> "different"},
{2, 6, -7.73741, {2, 6} -> "different"},
{3, 1, -49.5421, {3, 1} -> "same"},
{3, 2, -41.9788, {3, 2} -> "same"},
{3, 4, -13.1989, {3, 4} -> "different"},
{3, 5, -18.0183, {3, 5} -> "different"},
{3, 6, -10.5025, {3, 6} -> "different"},
{4, 1, -17.6852, {4, 1} -> "different"},
{4, 2, -0.997097, {4, 2} -> "different"},
{4, 3, -5.0447, {4, 3} -> "different"},
{4, 5, -47.2881, {4, 5} -> "same"},
{4, 6, -43.6139, {4, 6} -> "same"},
{5, 1, -20.8662, {5, 1} -> "different"},
{5, 2, -29.4012, {5, 2} -> "different"},
{5, 3, -4.96949, {5, 3} -> "different"},
{5, 4, -31.5497, {5, 4} -> "same"},
{5, 6, -29.7002, {5, 6} -> "same"},
{6, 1, -3.60692, {6, 1} -> "different"},
{6, 2, -28.6723, {6, 2} -> "different"},
{6, 3, -12.8056, {6, 3} -> "different"},
{6, 4, -44.3089, {6, 4} -> "same"},
{6, 5, -48.3195, {6, 5} -> "same"}
};

edges = UndirectedEdge @@@ data[[All, 1 ;; 2]];
weights = data[[All, 3]];

g = Graph[edges, EdgeWeight -> Thread[edges -> weights],
VertexLabels -> Automatic]

recommendedg =
Graph[Select[data[[All, 4]], #[[2]] == "same" &][[All, 1]],
VertexLabels -> Automatic]

ConnectedComponents[recommendedg]
(* {{4, 5, 6}, {1, 2, 3}} *)

FindGraphPartition[g]
(* result {{4, 5, 6}, {1, 2, 3}} *)



The recommendation agrees with the result of FindGraphPartition which takes into account the weights (presumably decibel values for interference strength). This might not scale well to more cells because you could get good groupings that minimize the total interference - but it might make more sense to minimize the maximum interference - in which case it becomes a more difficult optimization problem.

• Thanks for the ideas presented. Having programmed this on a small version of the real data, I note that FindGraphPartition takes more notice of making even groups than of taking notice of the weights. When I make the simple change for all data to be 8 values, the answer should be a group of 3 and a group of 5 but it tries very hard to make the group sizes equal. Apr 27 at 21:37
• @NigelKg look at the docs for FindGraphPartition and you'll see there's a second argument that can take a list of partition sizes Apr 28 at 13:36
• I have taken a look at FindGraphPartition and the variation in the second argument but I don't believe that this has the necessary flexibility. Also if the sum of items in the second argument does not equal the items in the graph then the function seems to hang, and require Forcing Quit on the Kernel. Apr 29 at 10:11
• @NigelKg What flexibility do you need? The other thing sounds like a bug in Mathematica - it should warn or error but not bring down the kernel. Can confirm it crashes the kernel in 12.2 on Windows 10. No upvotes and nobody has come up with a better answer. You may want to read this publication which suggests a binary linear programming approach to frequency allocation. I don't think Classify is going to be of much use. Apr 29 at 13:46
• Thanks for the reference, that will take a bit of reading! I have decided to perform the grouping by assembling a random set of groups of approximately equal size and then minimising the interference between members of the groups by moving the worst case to another group. This is a little brute force but that is OK. What this thought process made me do is to properly create a proper value for the goodness of the result required, recognising that there will probably be some left which will interfere partially. Apr 29 at 14:17