Быстрый алгоритм вычисления процентилей для удаления выбросов
У меня есть программа, которая должна многократно вычислять приблизительный процентиль (статистику порядка) набора данных, чтобы удалить выбросы перед дальнейшей обработкой. В настоящее время я делаю это, сортируя массив значений и выбирая соответствующий элемент; это выполнимо, но это заметная вспышка на профилях, несмотря на то, что это довольно незначительная часть программы.
Подробнее:
- набор данных содержит порядка 100000 чисел с плавающей запятой, и предполагается, что чтобы быть" разумно " распределенными-маловероятно, что будут дубликаты или огромные всплески плотности вблизи определенных значений; и если по какой-то странной причине распределение нечетное, это нормально для приближения, чтобы быть менее точным, так как данные, вероятно, перепутались так или иначе и дальнейшая обработка сомнительна. Однако данные не обязательно равномерно или нормально распределены; это просто очень маловероятно, что они вырождаются.
- приблизительное решение было бы прекрасно, но мне нужно понять как аппроксимация вводит ошибку, чтобы убедиться, что она верна.
- приложение находится в C# с битами тяжелого подъема в C++; псевдокод или уже существующая библиотека в любом из них были бы прекрасны.
- совершенно другой способ удаления выбросов тоже был бы хорош, если бы это было разумно.
обновление: кажется, я ... ищем приближенный алгоритм выбора .
Поскольку цель состоит в том, чтобы удалить выбросы, я вычисляю два процентиля по одним и тем же данным в любое время: например, один на 95% и один на 5%.
Хотя все это делается в цикле, данные (немного) отличаются каждый раз, поэтому нелегко повторно использовать структуру данных, как это было сделано для этого вопроса.
Реализованное Решение
Использование алгоритма выбора Википедии, предложенного Гронимом, сократило эту часть времени выполнения Примерно в 20 раз.
Поскольку я не смог найти реализацию C#, вот что я придумал. Это быстрее даже для небольших входов, чем массив.Сортировка; и при 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, для указывая мне в правильном направлении!
10 ответов:
Решение гистограммы от Хенрика будет работать. Вы также можете использовать алгоритм выбора, Чтобы эффективно найти k самых больших или самых маленьких элементов в массиве из n элементов в O (n). Чтобы использовать это для 95-го процентиля, установите k=0.05 n и найдите k самых больших элементов.
Ссылка:
Http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements
Вы можете оценить свои процентили только из части вашего набора данных, например из первых нескольких тысяч точек.
ТеоремаГливенко–Кантелли гарантирует, что это будет довольно хорошая оценка, если вы можете считать, что ваши точки данных независимы.
Я использовал для идентификации выбросов вычисление стандартного отклонения . Все, что имеет расстояние больше, чем в 2 (или 3) раза стандартное отклонение от среднего значения, является выбросом. 2 раза = около 95%.
Поскольку вы вычисляете среднее значение, его также очень легко вычислить стандартное отклонение очень быстро.
Вы также можете использовать только подмножество ваших данных для вычисления чисел.
Разделите интервал между минимумом и максимумом ваших данных на (скажем) 1000 ячеек и вычислите гистограмму. Затем постройте частичные суммы и посмотрите, где они впервые превышают 5000 или 95000.
Есть несколько основных подходов, которые я могу придумать. Во - первых, вычислить диапазон (найдя самые высокие и самые низкие значения), спроецировать каждый элемент на процентиль ((x-min) / диапазон) и выбросить любой, который оценивает ниже, чем .05 или выше .95.
Во-вторых, вычислить среднее и стандартное отклонение. Промежуток в 2 стандартных отклонения от среднего (в обоих направлениях) будет охватывать 95% нормально распределенного пространства выборки, что означает, что ваши выбросы будут находиться в 97,5 процентиля. Вычисление среднего ряда является линейным, как и стандартный dev (квадратный корень из суммы разности каждого элемента и среднего). Затем вычтите 2 Сигмы из среднего значения и добавьте 2 Сигмы к среднему значению, и вы получите свои пределы выбросов.Оба они будут вычисляться в приблизительно линейном времени; первый требует двух проходов, второй-трех (как только у вас есть свои пределы, вы все равно должны отбросить выбросы). Поскольку это операция на основе списка, Я не думаю, что вы найдете что-либо с логарифмической или постоянной сложностью; любой дальнейший прирост производительности потребует либо оптимизации итерации и вычисления, либо введения ошибки путем выполнения вычислений на подвыборке (например, каждый третий элемент).
Хорошим общим ответом на вашу проблему, по-видимому, являетсяRANSAC . Учитывая модель и некоторые зашумленные данные, алгоритм эффективно восстанавливает параметры модели.
Вы должны будете выбрать простую модель, которая может отображать ваши данные. Все гладкое должно быть в порядке. Скажем, смесь нескольких гауссов. RANSAC установит параметры вашей модели и оценит набор инлайнеров одновременно. Затем выбросьте все, что не соответствует модели должным образом.
Вы можете отфильтровать 2 или 3 стандартных отклонения, даже если данные не распределены нормально; по крайней мере, это будет сделано согласованным образом, что должно быть важно.
По мере удаления выбросов std dev будет меняться, вы можете делать это в цикле, пока изменение в std dev не станет минимальным. Хотите вы этого или нет, зависит от того, почему вы манипулируете данными таким образом. Некоторые статистики высказывают серьезные оговорки в отношении исключения выбросов. Но некоторые снимают выбросы, чтобы доказать, что данные распределены достаточно нормально.
Не специалист, но моя память подсказывает:
- чтобы точно определить процентильные точки, вам нужно отсортировать и посчитать
- взятие выборки из данных и вычисление значений процентилей звучит как хороший план для приличного приближения, если вы можете получить хорошую выборку
- если нет, как предложил Хенрик, вы можете избежать полной сортировки, если вы сделаете ведра и пересчитаете их
Один набор данных из 100k элементов почти не требует времени для сортировки, поэтому я предполагаю, что вам придется делать это неоднократно. Если набор данных является тем же самым набором, только слегка обновленным, вам лучше построить дерево (
O(N log N)), а затем удалить и добавить новые точки по мере их поступления (O(K log N), гдеK- количество измененных точек). В противном случае,k- е самое большое решение элемента, уже упомянутое, дает вамO(N)для каждого набора данных.
Comments