Как выбрать непохожее число в массиве в C ++?

Question

Я использую C ++ для написания ROOT-скрипта для какой-то задачи. В какой-то момент у меня есть массив двойных, в которых многие очень похожи, а один или два разные. Я хочу, чтобы усреднить все числа, кроме этих болит палец. Как мне подойти к этому? Для примера рассмотрим:

x = [2.3, 2.4, 2.11, 10.5, 1.9, 2.2, 11.2, 2.1]

Я хочу как-то усреднить все числа, кроме 10.5 и 11.2, разнородных. Этот алгоритм будет повторяться несколько тысяч раз, и массив двойников имеет 2000 записей, поэтому оптимизация (при сохранении читабельности) желательна. Спасибо ТАК!

Выезд: http://tinypic.com/r/111p0ya/3 «Разные» числа значений y импульса.

Смысл этого в том, чтобы определить базовое значение для сигнала. Я сравниваю самое отрицательное значение с землей и надеялся получить лучший метод для заземления, чем усреднить первые N точек в выборке.

Answer 1

Если вы можете, сохранить отсортированный список; тогда вы можете легко отрубать голову и хвост списка каждый раз, когда вы вычисляете среднее значение.

Это очень похоже на удаление выбросов на основе медианы (т. Е. Вам понадобится два прохода по данным, один для нахождения медианы - который почти такой же медленный, как сортировка для данных с плавающей запятой, другой для вычисления среднее значение), но требует меньше накладных расходов во время разработки среднего значения за счет поддержания отсортированного списка. Какой из них самый быстрый, будет полностью зависеть от ваших обстоятельств. Конечно, может случиться так, что вы действительно хотите медиану!

Если бы у вас были дискретные данные (скажем, байты = 256 возможных значений), вы могли бы использовать 256 «гистограмм» гистограммы с одним проходом данных, подсчитывая значения, которые идут в каждом бине, тогда действительно легко найти медиана / приблизительное среднее / удаление выбросов и т. д. Это был бы мой предпочтительный вариант, если вы можете позволить себе потерять некоторую точность ваших данных с последующим поддержанием отсортированного списка, если это подходит для ваших данных.

Answer 2

Учитывая, что вы используете ROOT, вы можете рассмотреть классы TSpectrum, которые поддерживают извлечение фона из-под неопределенного числа пиков ...

Я никогда не использовал их с таким большим базовым шумом, но они должны быть крепкими.

Кстати: каков источник этих данных? Пик выглядит как импульс детектора частиц, но высокий уровень фонового дрожания говорит о том, что вы могли бы реально улучшить ситуацию с помощью довольно незначительных настроек аппаратного обеспечения DAQ, что может быть лучше, чем попытка решить сложную программную проблему.

Наконец, если вы не ограничены каким-то очень примитивным оборудованием (в таком случае, почему и как вы используете ROOT?), Если у вас есть только пара тысяч таких спектров, вы можете позволить себе довольно медленный алгоритм. Или это 2000 спектров на событие и высокая частота событий?

Answer 3

Вот быстрый и грязный метод, который я использовал раньше (работает хорошо, если в начале очень мало выбросов, и у вас нет очень сложных условий для того, что составляет выброс)

Алгоритм O (N). Единственная действительно дорогая часть - это деление.

Настоящее преимущество в том, что вы можете запустить его за пару минут.

avgX = Array[0]  // initialize array with the first point
N = length(Array)
percentDeviation = 0.3  // percent deviation acceptable for non-outliers
count = 1
foreach x in Array[1..N-1]
    if      x < avgX + avgX*percentDeviation
       and  x > avgX - avgX*percentDeviation
          count++
          sumX =+ x
          avgX = sumX / count
    endif
endfor

return avgX

Answer 4

Любой метод, который является статистически значимым и хорошим способом приблизиться к нему (Dark Eru, Daniel White), будет слишком сложным в вычислительном отношении, чтобы повторяться, и я думаю, что я нашел обходной путь, который позволит позже исправить (то есть оставить это необоснованно).

Спасибо за предложения. Я посмотрю на них, если у меня будет время, и хочу посмотреть, стоит ли их выигрыш замедления.

Answer 5

Хорошим эмпирическим правилом для определения вероятных выбросов является вычисление Межквартильного диапазона (IQR) , а затем любые значения, которые находятся на расстоянии 1,5 * IQR от ближайшего квартиля, являются выбросами.

Это основной метод, который многие статистические системы (например, R) используют для автоматического обнаружения выбросов.

Answer 6

Быстрый способ - взять медиану, а затем взять средние числа не так далеко от медианы.

«Не так уж и далеко», будучи зависимым от вашего проекта.