加权中值计算

Question

我正在寻找关于加权中值算法和/或C++中的示例代码的计算的好的学习材料.我的中位数的权重是0到1之间的值.你能推荐一些链接吗？

Answer 1

加权中位数的定义如下:

如果x是N元素的排序数组,并且w是具有总权重的权重数组W,则加权中值是最后一个x[i],使得w[i]所有先前权重的总和小于或等于S/2.

在C++中,这可以这样表达(假设x,w并W定义如上)

double sum = 0;
int i;
for(i = 0; i < N; ++i)
{
    sum += w[i];
    if(sum > W/2)
        break;
}
double median = x[i-1];

编辑

所以我似乎过于草率地回答了这个问题并犯了一些错误.我从R文档中找到了加权中值的简洁描述,它描述如下:

对于n元件x = c(x[1], x[2], ..., x[n])具有正权重w = c(w[1], w[2], ..., w[n]),使得sum(w) = S,加权平均被定义为元素x[k]为其初始所有元素的总重量计x[i] < x[k]小于或等于S/2 以及用于所有元件的总重量x[i] > x[k]小于或等于S/2.

从这个描述中,我们有一个非常直接的算法实现.如果我们开始k == 0,那么之前没有元素x[k],因此元素的总重量x[i] < x[k]将小于S/2.根据数据,元素的总重量x[i] > x[k]可以小于或小于S/2.所以我们可以向前移动数组,直到第二个和小于或等于S/2:

#include <cstddef>
#include <numeric>
#include <iostream>

int main()
{
  std::size_t const N = 5;
  double x[N] = {0, 1, 2, 3, 4};
  double w[N] = {.1, .2, .3, .4, .5};

  double S = std::accumulate(w, w+N, 0.0); // the total weight

  int k = 0;
  double sum = S - w[0]; // sum is the total weight of all `x[i] > x[k]`

  while(sum > S/2)
  {
    ++k;
    sum -= w[k];
  }

  std::cout << x[k] << std::endl;
}

请注意,如果中位数是最后一个元素(medianIndex == N-1),则sum == 0条件sum > S/2失败.因此,k永远不会超出界限(除非N == 0!).此外,如果有两个元素满足条件,则算法始终选择第一个元素.