Find k point that minimize the variance between the items in a numeric set

Questions
, ,
1

hi all,
i don’t know if this is the right forum, but i really need your help: as the title says i need to find k points that minimize the variance between the items in a numeric set.
For example K = 5 and S={1,2,3,6,7,9,11,22,44,50}: the points that minimize the total sum are {2,7,22,44,50}; SUM = 9 , the distance between points are (1,0,1,1,0,2,4,0,0,0).

I thought at k-median problem, is it right?

Thanks all

2

Is there a name for this?

Here is a straightforward implementation. For larger datasets, it’d probably pay to write a smarter algorithm than an exhaustive search:

K = 5; S = {1, 2, 3, 6, 7, 9, 11, 22, 44, 50};
subsets = Subsets[S, {K}];
myMetric[subset_] := Total[Abs[# - First@Nearest[subset, #]]& /@ S]
MinimalBy[{#, myMetric[#]} & /@ subsets, Last]

{{{2, 7, 22, 44, 50}, 9}, {{2, 9, 22, 44, 50}, 9}}
3

Yes, it looks like a k-median problem, or a variant thereof (I never remember what distance function is used for what flavor of location siting). Do the point values have to also live in the set?

4

Yes: k-points must be in the set!

5

Okay. I don’t have time right now but this can be done using FindMinimum, with integer (0-1) variables to determine which elements are selected, and which other elements are to be associated with which selected ones.