加权中位数计算

Question

加权中位数计算

c++algorithm

10

我正在寻找有关计算加权中位数算法的良好学习资料和/或C++样例代码。我的中位数权重是介于0和1之间的值。您能否推荐一些链接？

- Viper

你是否有一组值[x，y]并且想要计算加权中位数，其中y是权重？请详细说明你的问题。 - Filip Roséen - refp

我已经尝试使用Boost库实现，但我想更加了解这个算法，因为在我的情况下，我需要设计这个解决方案的一个特殊变体。 - Viper

我需要找到最小化所谓的加权分类误差的值。因此，我有一对值[错误、权重]，其中值是自然数但权重是0到1之间的分数。我已经阅读到可以使用加权中位数算法在线性时间内找到最小值... - Viper

2个回答

2

这是一个针对未排序向量的加权中位数实现。它基于@Ken Wayne VanderLinde关于中位数计算的非常好的答案，并且使用该帖子中给出的索引排序器。请注意保留HTML标签。

    template <typename VectorType>
    auto sort_indexes(VectorType const& v)
    {
        std::vector<int> idx(v.size());
        std::iota(std::begin(idx), std::end(idx), 0);

        std::sort(std::begin(idx), std::end(idx), [&v](int i1, int i2) {return v[i1] < v[i2];});

        return idx;
    }

    template<typename VectorType1, typename VectorType2>
    auto weightedMedian(VectorType1 const& x, VectorType2 const& weight)
    {
        double totalWeight = 0.0;
        for (int i = 0; i < static_cast<int>(x.size()); ++i)
        {
            totalWeight += weight[i];
        }

        auto ind = sort_indexes(x);

        int k = ind[0];
        double sum = totalWeight - weight[k];

        for (int i = 1; i < static_cast<int>(ind.size()); ++i)
        {
            k = ind[i];
            sum -= weight[k];

            if (sum <= 0.5 * totalWeight)
            {
                break;
            }
        }
        return x[k];
    }

它适用于任何支持operator[](int)和size()的向量类型（因此不使用std::accumulate等）。

- davidhigh

1

以下情况无法正常工作：elements=[1,2]，weights=[100, 50]。这意味着，如果结果应该是第一个元素，则无法正常工作。您可以通过从0开始循环，将sum初始化为totalWeight，仅在循环外部声明k并验证向量不为空来轻松解决此问题。 - Jonathan

@Jonathan：感谢你的测试和建议的更正 -- 请随意将其编辑到代码中。 - davidhigh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ken Wayne VanderLinde · Accepted Answer

加权中位数的定义如下：

如果 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文档中找到了一个关于加权中位数的清晰描述，如下所述：

对于正权重w = c(w[1], w[2], ..., w[n])的n个元素x = c(x[1], x[2], ..., x[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！）。此外，如果有两个元素满足条件，则算法总是选择第一个元素。