20

我有一个程序需要重复计算数据集的近似百分位数(顺序统计),以便在进一步处理之前删除异常值。我目前正在通过对值数组进行排序并选择适当的元素来做到这一点;这是可行的,但它在配置文件上是一个明显的亮点,尽管它只是该程序的一个相当小的部分。

更多信息:

  • 该数据集包含多达 100000 个浮点数,并假定为“合理”分布 - 在特定值附近不太可能出现重复或密度的巨大峰值;如果由于某种奇怪的原因分布是奇怪的,那么近似值不太准确是可以的,因为数据可能无论如何都搞砸了,进一步的处理也很可疑。但是,数据不一定是均匀分布或正态分布的;它不太可能退化。
  • 一个近似的解决方案会很好,但我确实需要了解近似如何引入错误以确保它是有效的。
  • 由于目标是消除异常值,我一直在计算相同数据的两个百分位数:例如,一个为 95%,一个为 5%。
  • 该应用程序在 C# 中,在 C++ 中进行了一些繁重的工作;伪代码或任何一个预先存在的库都可以。
  • 一种完全不同的去除异常值的方法也可以,只要它是合理的。
  • 更新:看来我正在寻找一个近似的选择算法

尽管这一切都是在一个循环中完成的,但数据每次都(略有)不同,因此像对这个问题所做的那样重用数据结构并不容易。

已实施的解决方案

使用 Gronim 建议的维基百科选择算法将这部分运行时间减少了大约 20 倍。

由于我找不到 C# 实现,这就是我想出的。即使对于小输入,它也比 Array.Sort 更快;在 1000 个元素时,它的速度提高了 25 倍。

public static double QuickSelect(double[] list, int k) {
    return QuickSelect(list, k, 0, list.Length);
}
public static double QuickSelect(double[] list, int k, int startI, int endI) {
    while (true) {
        // Assume startI <= k < endI
        int pivotI = (startI + endI) / 2; //arbitrary, but good if sorted
        int splitI = partition(list, startI, endI, pivotI);
        if (k < splitI)
            endI = splitI;
        else if (k > splitI)
            startI = splitI + 1;
        else //if (k == splitI)
            return list[k];
    }
    //when this returns, all elements of list[i] <= list[k] iif i <= k
}
static int partition(double[] list, int startI, int endI, int pivotI) {
    double pivotValue = list[pivotI];
    list[pivotI] = list[startI];
    list[startI] = pivotValue;

    int storeI = startI + 1;//no need to store @ pivot item, it's good already.
    //Invariant: startI < storeI <= endI
    while (storeI < endI && list[storeI] <= pivotValue) ++storeI; //fast if sorted
    //now storeI == endI || list[storeI] > pivotValue
    //so elem @storeI is either irrelevant or too large.
    for (int i = storeI + 1; i < endI; ++i)
        if (list[i] <= pivotValue) {
            list.swap_elems(i, storeI);
            ++storeI;
        }
    int newPivotI = storeI - 1;
    list[startI] = list[newPivotI];
    list[newPivotI] = pivotValue;
    //now [startI, newPivotI] are <= to pivotValue && list[newPivotI] == pivotValue.
    return newPivotI;
}
static void swap_elems(this double[] list, int i, int j) {
    double tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;
}

性能图

谢谢,Gronim,为我指明了正确的方向!

4

10 回答 10

9

Henrik 的直方图解决方案将起作用。您还可以使用选择算法在 O(n) 中的 n 个元素的数组中有效地找到 k 个最大或最小元素。要将其用于第 95 个百分位数,请设置 k=0.05n 并找到 k 个最大元素。

参考:

http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements

于 2010-09-23T15:29:24.767 回答
6

根据其创建者的说法, SoftHeap可用于:

以最佳方式计算准确或近似的中位数和百分位数。它对于近似排序也很有用...

于 2010-09-23T16:00:58.913 回答
5

我曾经通过计算标准差来识别异常值。距离大于平均值的标准偏差 2(或 3)倍的所有事物都是异常值。2 次 = 约 95%。

由于您正在计算平均值,因此计算标准偏差也非常容易,速度非常快。

您也可以仅使用数据的子集来计算数字。

于 2010-09-23T15:23:41.817 回答
4

您可以仅从数据集的一部分(例如前几千个点)估计百分位数。

如果您可以假设您的数据点是独立的,则Glivenko-Cantelli 定理确保这将是一个相当好的估计。

于 2010-09-23T15:22:57.927 回答
3

将数据的最小值和最大值之间的间隔划分为(例如)1000 个 bin 并计算直方图。然后建立部分总和并查看它们首先超过 5000 或 95000 的位置。

于 2010-09-23T15:16:19.540 回答
1

您的问题的一个很好的一般答案似乎是RANSAC。给定一个模型和一些噪声数据,该算法有效地恢复了模型的参数。
您将不得不选择一个可以映射您的数据的简单模型。任何光滑的东西都应该没问题。假设是几个高斯的混合体。RANSAC 将设置模型的参数并同时估计一组内联。然后扔掉任何不适合模型的东西。

于 2010-09-23T17:00:26.877 回答
1

我能想到几个基本的方法。首先是计算范围(通过找到最高和最低值),将每个元素投影到百分位数((x - min)/范围)并丢弃任何低于 0.05 或高于 0.95 的元素。

第二个是计算平均值和标准差。距平均值 2 个标准差的跨度(在两个方向上)将包含 95% 的正态分布样本空间,这意味着您的异常值将位于 <2.5 和 >97.5 百分位数。计算系列的平均值是线性的,标准 dev 也是线性的(每个元素的差值与平均值之和的平方根)。然后,从平均值中减去 2 个 sigma,然后在平均值上加上 2 个 sigma,您就得到了异常值限制。

这两者都将在大致线性的时间内计算;第一个需要两次通过,第二个需要三个(一旦你有你的限制,你仍然必须丢弃异常值)。由于这是一个基于列表的操作,我认为您不会找到任何具有对数或恒定复杂度的东西。任何进一步的性能提升都需要优化迭代和计算,或者通过对子样本(例如每三个元素)执行计算来引入错误。

于 2010-09-23T15:23:19.943 回答
1

即使数据不是正态分布,您也可以过滤掉 2 或 3 个标准差;至少,它将以一致的方式进行,这应该很重要。

当您删除异常值时,std dev 会发生变化,您可以循环执行此操作,直到 std dev 的变化最小。您是否要这样做取决于您为什么要以这种方式处理数据。一些统计学家对去除异常值持重大保留意见。但是有些人删除了异常值以证明数据是相当正态分布的。

于 2010-09-23T18:28:37.613 回答
0

一组 100k 个元素的数据几乎不需要时间来排序,所以我假设你必须重复这样做。如果数据集是刚刚稍微更新的同一集,则最好构建一O(N log N)棵树(否则,已经提到的第 th 大元素解决方案会为您提供每个数据集。O(K log N)KkO(N)

于 2010-09-23T17:30:58.690 回答
0

不是专家,但我的记忆表明:

  • 要准确确定百分位点,您需要排序和计数
  • 如果你能得到一个好的样本,从数据中抽取样本并计算百分位值听起来像是一个很好的近似值计划
  • 如果没有,正如 Henrik 所建议的那样,如果你做桶并计算它们,你可以避免完整的排序
于 2010-09-23T15:22:19.880 回答