如何在Apache Spark中计算百分位数

Question

我有一个整数rdd(即RDD[Int]),我想做的是计算以下十个百分位:[0th, 10th, 20th, ..., 90th, 100th].最有效的方法是什么？

Answer 1

您可以 :

1. 通过rdd.sortBy()对数据集进行排序
2. 通过rdd.count()计算数据集的大小
3. 使用索引进行压缩以便于检索百分位数
4. 通过rdd.lookup()检索所需的百分位数,例如第10百分位rdd.lookup(0.1*大小)

计算中位数和第99百分位数:getPercentiles(rdd,new double [] {0.5,0.99},size,numPartitions);

在Java 8中:

public static double[] getPercentiles(JavaRDD<Double> rdd, double[] percentiles, long rddSize, int numPartitions) {
    double[] values = new double[percentiles.length];

    JavaRDD<Double> sorted = rdd.sortBy((Double d) -> d, true, numPartitions);
    JavaPairRDD<Long, Double> indexed = sorted.zipWithIndex().mapToPair((Tuple2<Double, Long> t) -> t.swap());

    for (int i = 0; i < percentiles.length; i++) {
        double percentile = percentiles[i];
        long id = (long) (rddSize * percentile);
        values[i] = indexed.lookup(id).get(0);
    }

    return values;
}

请注意,这需要对数据集O(n.log(n))进行排序,并且在大型数据集上可能很昂贵.

另一个答案表明,简单地计算直方图不能正确计算百分位数:这里是一个反例:一个由100个数字组成的数据集,99个数字为0,一个数字为1.你最终得到了第一个中的所有99个0 bin,最后一个bin中的1,中间有8个空箱.

Answer 2

如何T-消化？

https://github.com/tdunning/t-digest

一种新的数据结构,用于准确在线累积基于排名的统计数据,例如分位数和修剪均值.t-digest算法也非常并行友好,使其在map-reduce和并行流应用程序中很有用.

t-digest构造算法使用一维k均值聚类的变体来产生与Q-摘要相关的数据结构.该t-摘要数据结构可用于估计分位数或计算其他秩统计数据.t-digest相对于Q-digest的优点是t-digest可以处理浮点值,而Q-digest仅限于整数.通过较小的更改,t-digest可以处理任何具有类似于均值的有序集合中的任何值.尽管t-digest存储在磁盘上时t-digest更紧凑,但由t-digest产生的分位数估计的准确性可以比Q-digest产生的精度高几个数量级.

总之,t-digest特别有趣的特征就是它

• 摘要小于Q-digest
• 适用于双打和整数.
• 为极端分位数提供百万分之一的精度,对于中等分位数,精度通常<1000 ppm
• 很快
• 非常简单
• 有一个参考实现具有> 90%的测试覆盖率
• 可以很容易地与map-reduce一起使用,因为可以合并摘要

使用Spark的参考Java实现应该相当容易.

Answer 3

将您的 RDD 转换为 Double 的 RDD，然后使用该.histogram(10)操作。请参阅DoubleRDD ScalaDoc