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

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



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

最佳答案

对于单个数据点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，以生成随机点。

关于c++ - 如何从具有不一致概率的列表中选择一个值？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8568203/