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

Posted 9 years ago
2569 Views
|
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
4 Replies
Sort By:
Posted 9 years ago
 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 9 years ago
 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 9 years ago
 Yes: k-points must be in the set!
Posted 9 years ago
 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}}