如何从具有非均匀概率的列表中选择值？

Question

我正在研究k-means ++初始化算法.算法的以下两个步骤会产生不一致的概率:

对于每个数据点x,计算D(x),x与已经选择的最近中心之间的距离.

使用加权概率分布随机选择一个新数据点作为新中心,其中选择点x的概率与D(x)^ 2成比例.

如何在C++中用这个陈述的加权概率分布进行选择？

Answer 1

离散分布是一个更容易做C++ 11与随机头和使用 的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

Answer 2

对于一组有限的单独数据点 X，这需要离散概率分布。

最简单的方法是按顺序枚举点 X，并计算代表其累积概率分布函数的数组：（伪代码如下）

/* 
 * xset is an array of points X,
 * cdf is a preallocated array of the same size
 */
function prepare_cdf(X[] xset, float[] cdf)
{
   float S = 0;
   int N = sizeof(xset);
   for i = 0:N-1
   {
      float weight = /* calculate D(xset[i])^2 here */
      // create cumulative sums and write to the element in cdf array
      S += weight;
      cdf[i] = S;
   }

   // now normalize so the CDF runs from 0 to 1
   for i = 0:N-1
   {
      cdf[i] /= S;
   }
}

function select_point(X[] xset, float[] cdf, Randomizer r)
{
   // generate a random floating point number from a 
   // uniform distribution from 0 to 1
   float p = r.nextFloatUniformPDF();
   int i = binarySearch(cdf, p);
   // find the lowest index i such that p < cdf[i]

   return xset[i];
}

您调用prepare_cdf一次，然后根据需要多次调用select_point来生成随机点。