c++ - 加权中位数计算

Question

我正在寻找有关计算加权中值算法和/或 C++ 示例代码的良好学习 Material 。我的中位数权重是 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 documentation 中找到了对加权中位数的简洁描述。 ，它是这样描述的:

For the n elements x = c(x[1], x[2], ..., x[n]) with positive weights w = c(w[1], w[2], ..., w[n]) such that sum(w) = S, the weighted median is defined as the element x[k] for which initial the total weight of all elements x[i] < x[k] is less or equal to S/2 and for which the total weight of all elements x[i] > x[k] is less or equal to 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!)。另外，如果有两个元素满足条件，算法总是选择第一个。