0
|
2789 Views
|
4 Replies
|
2 Total Likes
View groups...
Share
GROUPS:

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

Posted 10 years ago
 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 10 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 10 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 10 years ago
 Yes: k-points must be in the set!
Posted 10 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}}