Message Boards Message Boards


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

Posted 9 years ago
4 Replies
2 Total Likes

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

POSTED BY: david Bernard
4 Replies

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.

POSTED BY: Daniel Lichtblau

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?

POSTED BY: Daniel Lichtblau
Posted 9 years ago

Yes: k-points must be in the set!

POSTED BY: david Bernard

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}}
POSTED BY: Sean Clarke
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract