c++ - 如何从具有非均匀概率的列表中选择一个值？

Question

我正在查看 k-means++初始化算法。该算法的以下两步产生非均匀概率:

For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen.

Choose one new data point at random as a new center, using a weighted probability distribution where a point x is chosen with probability proportional to D(x)^2.

如何在 C++ 中使用这种规定的加权概率分布进行选择？

Answer 1

使用 random 在 C++11 中实现离散分布要容易得多 header 和使用 std::discrete_distribution .这是例子:

#include <iostream>
#include <map>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::discrete_distribution<> d({20,30,40,10});
    std::map<int, int> m;
    for(int n=0; n<10000; ++n) {
        ++m[d(gen)];
    }
    for(auto p : m) {
        std::cout << p.first << " generated " << p.second << " times\n";
    }
}

这是输出示例:

0 generated 2003 times
1 generated 3014 times
2 generated 4021 times
3 generated 962 times