Фильтрация массива чисел от шума

← →
abun © (2009-08-10 16:10) [0]

Есть упорядоченный массив чисел типа real. Нужно отфильтровать явно "левые" числа (т.е. видно, что они совсем другой величины). Длина массива не более 1000.
Пример массива:
90,100,2100,2120,2130,2135,2140,2160,2200,2300,2500,3500,4000,100000.
Результатом работы фильтра должно исключение из списка чисел 90, 100 и 100000. "Неправильных" чисел не может быть в массиве много. Точное количество их не указать. Но если очень принципиально, то пусть будет ограничение: не более 4-х.

Казалось бы, задача элементарная. Опробовал: входит ли в интервал
[матожидание*0,8..матожидание*1,2] (0,8 и 1,2 - т.е. -20 и +20% иначе говоря) - не помогает, т.к. матожидание серьезно искажается этими "неправильными" числами и выпадают правильные.
Пробовал и через среднее по разнице между соседними элементами.
Тогда 2 и более соседних "неправильных" чисел прикрывают друг дружку.

Такое ощущение, что задача вообще нерешаема строгим алгоритмом.

← →
Kolan © (2009-08-10 16:32) [1]

Среднеквадратичное отклонение попробуйте.

Вообще мат теории на это счет полно, сплайны там всякие и пр.

← →
Kolan © (2009-08-10 16:33) [2]

Еще есть фильтрация. Есть прямо готовые фильтры, оконные функции и т. п.

← →
sniknik © (2009-08-10 16:51) [3]

считаешь количество "длинн" чисел, т.е. Length(IntToStr(n[i])) каких больше те потом и оставляешь...
для "совсем другой величины"/т.е. порядка сойдет.

← →
KilkennyCat © (2009-08-10 17:01) [4]

> sniknik © (10.08.09 16:51) [3]

1,2,3,4,5,6,7,8,9,10,11,12...

← →
abun © (2009-08-10 17:15) [5]

> Среднеквадратичное отклонение попробуйте.

Я ж говорю, пробовал СКО. Ерунда получается - т.к. удаляется только 1 число за проход. Ну разве что попробую зациклить процесс фильтрации до тех пор, пока число удаленных не будет 0.

← →
Jeer © (2009-08-10 17:16) [6]

Почитать соответствующие книжки по мат.статистике и обработке данных.

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

СКО, сплайны, фильтры - это из другой оперы.

← →
Smile (2009-08-10 17:36) [7]

Отранжируй во временную переменную и отруби (по какой-нибудь дельте) "лишние" концы.
Затем "выкарябай" эти концы из своего упорядоченного массива
:)

← →
Jeer © (2009-08-10 17:38) [8]

Если совсем просто, то

t1 = abs( X[i] - Xav)/S <= t2

X[i] - проверяемый элемент
Xav - среднее значение
S - СКО = sum(X[i] - Xav)^2/(N-1)
t2 - квантиль распределения статистики t при уровне значимости p
Обычно используют уровень значимости p=0.05 ( 95% доверительная вероятность )
При N=25, t2 = 2.72 для p= 0.05
Если t1 <= t2, то элемент не отсеивают.
После каждого отсева перевычисляют Xav и S

← →
abun © (2009-08-10 17:57) [9]

> Если совсем просто, тоt1 = abs( X[i] - Xav)/S <= t2X[i]
> - проверяемый элементXav - среднее значениеS - СКО = sum(X[i]
> - Xav)^2/(N-1)t2 - квантиль распределения статистики t при
> уровне значимости pОбычно используют уровень значимости
> p=0.05 ( 95% доверительная вероятность )При N=25, t2 = 2.
> 72 для p= 0.05Если t1 <= t2, то элемент не отсеивают.После
> каждого отсева перевычисляют Xav и S

:) не поверите, но я уже экспериментальным путем начал выходить на что-то подобное!

← →
Jeer © (2009-08-10 18:13) [10]

Многое зависит от распределения чисел с которыми Вы работаете.
Если все это дело укладывается в нормальное распределение, то применимы хорошо себя зарекомендовавшие традиционные методы отбраковки ( Стьюдент и пр ).
Более робастная (устойчивая) оценка аномалий может быть сделана через медианную фильтрацию ( см. [[7] ), но работать надо не с самими числами, а, например, с той же относительной оценкой, что и в [8]

Ну и еще не мешало бы модель сигнала знать :)

← →
abun © (2009-08-10 19:51) [11]

Да тут не сигнал - тут просто список курсов валют. И эти курсы иногда с ошибками - хотелось бы их фильтровать в автоматическом режиме.

← →
KilkennyCat © (2009-08-10 20:00) [12]

не выйдет. Пример 98-года, когда курс изменился в разы.

← →
abun © (2009-08-10 20:13) [13]

что-то не хочет со стьюдентом совсем фильтровать... :(
может, че не так я понял

← →
abun © (2009-08-10 20:52) [14]

Надо было корень здесь:
S - СКО = sqrt(sum(X[i] - Xav)^2/(N-1))

← →
Дмитрий Белькевич (2009-08-10 21:01) [15]

Может медианную фильтрацию попробовать?

← →
abun © (2009-08-10 21:28) [16]

Читал, но не понял, как ее реализовывать.

← →
Дмитрий Белькевич (2009-08-10 21:45) [17]

для трёх чисел:

function Med(a, b, c: integer): integer; var t: Integer; begin if (a > b) then begin t := a; a := b; b := t; end; if (b > c) then b := c; if (a > b) then result := a else result := b; end;

Этим последовательно пройтись по всему массиву, помещая результат в новый массив:

for j := LeftBorder + 1 to RightBorder - 1 do lBuff8[j] := Med(FBuff8[j - 1], FBuff8[j], FBuff8[j + 1]);

Единичные выбросы эффективно режет, при этом не "блюрит" данные/картинку.

← →
abun © (2009-08-10 22:03) [18]

Итак, проверено: критерий Стьюдента не работает в данном случае.
Пробуем медианный алгоритм.

← →
abun © (2009-08-10 22:18) [19]

Тоже не ахти. Съедает только крайние элементы. Но если на конце будет два "левых" числа - фильтр не работает. :(

← →
Сергей М. © (2009-08-11 00:20) [20]

> курсы иногда с ошибками

> критерий Стьюдента не работает

> Пробуем медианный алгоритм

> Тоже не ахти

Ну вот нам и еще один новоявленный премьер-министр - курсы щелкает-пересчитвает как белка орехи : куда кривая-нелегкая выведет, туда и ..
)

← →
Дмитрий Белькевич (2009-08-11 00:47) [21]

> Но если на конце будет два "левых" числа - фильтр не работает.
> :(

Два раза последовательно проходить не пробовал?

← →
Дмитрий Белькевич (2009-08-11 00:51) [22]

> И эти курсы иногда с ошибками - хотелось бы их фильтровать
> в автоматическом режиме.

Пойдём другим путём. Откуда вообще известно, что данные ошибочны? Может проще каждое число на верность каким-то образом проверить или таки получить изначально верные данные?

← →
Вариант (2009-08-11 09:15) [23]

> abun © (10.08.09 22:18) [19]

Вообще-то для приведенного набора медианный фильтр прекрасно отработал, если медиану использовать для поиска "среднего", которое возьмем за якорь.

Приведу примерные шаги алгоритма

Есть список курсов валют
Дано
[90,100,2100,2120,2130,2135,2140,2160,2200,2300,2500,3500,4000,100000].

В данном случае список сортирован, но не будем закладываться на то, что получим сортированный список. А для медианной фильтрации надо работать с сортированным списком (массивом)
1)
сортируем массив

2)
Определим медиану. Медиана это центральный эелемент отсортированного массива (в случае четного числа элементов я беру ближайший к центру с меньшим индексом)
В нашем случае это 2140

3) В списке оставим только те элементы, отклонение которых от медианы не превышет 20% (или сколько надо) Res=100.0*abs(E-Med) /Med, где E - проверяемый элемент массива, а Med наша медиана, а Res отклонение от медианы и мы задались, что Res <= 20%.

В результате получим [2100,2120,2130,2135,2140,2160,2200,2300,2500], а отсеянные элементы [90,100,3500,4000,100000]

Теперь о курсе валют, есть вопрос - почему бы не получать курс например Центробанка и его не брать за основу(а не медиану), от которой допустимы отклонения на ту или иную величину?

← →
abun © (2009-08-11 10:11) [24]

Немножко не то... Мы пишем прогу мониторинга обменных пунктов. Разработку можно наблюдать здесь: http://www.bestchange.info/ru/download/counter.php?id=1 (ссылка для скачивания)
http://www.bestchange.info/prog.html (ссылка на описание программы)
Парсер на РНР, который занимается обработкой файлов курсов валют, пока не идеален, поэтому нужна вот такая очистка.
А привязка лишняя - в данном случае к Центробанку - не желательна, но в этом, возможно, и есть доля логики. Главная проблема, что там не найдутся курсы электронных валют (например, вебмани, дельтакей и др.)

> Дмитрий Белькевич (11.08.09 00:47) [21]
> > Но если на конце будет два "левых" числа - фильтр не работает.
> > :(Два раза последовательно проходить не пробовал?

Ну да, получается, конечно. Но как узнать, когда остановить проходы? Фишка этого фильтра в том, что у него на каждом проходе что-то отфильтровывается. Я написал:

var
i:integer;
t,b,a:areal;
d: integer;

begin
b:=a;
repeat
t:=Filtr(b);
d:=length(t)-length(b); // количество отсеянных
b:=t;
until d=0;

// вывод
memo2.Clear;
for i:=low(b) to high(b) do
memo2.lines.add(floattostr(b[i]));

Так вот этот repeat "съедает" весь массив! И как его остановить вовремя - я не знаю. А в этом, в принципе, было бы решение проблемы.

Единственное, что приходит в голову - считать дисперсию после каждого прохода и если она меньше определенного порога - выйти из цикла. Но как найти этот порог - опять вопрос.

> abun (11.08.2009 10:30:26) [26]

А сделать так, что бы в массиве изначально были только правильные данные?

ну так вот этот алгоритм и будет проверять на правильность.

А может просто импортировать значения из проверненного источника и не городить огород?

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

Согласен, случай неординарный и описать его функцией не представляется возможным. Но все же считаю, что можно найти алгоритм, который бы, например, в 95% принимал решение правильно и отфильтровывал бы "выпадающие" из общего правила числа.

← →
Smile (2009-08-11 16:10) [32]

Что-то мне "подсказывает", что после того как автор ветки "отфильтрует" (по его терминологии) свой упорядоченный массив, он займется прогнозированием этого курса валют на последующий период времени
:)
Пожелаем ему успеха
:)

> Что-то мне "подсказывает", что после того как автор ветки
> "отфильтрует" (по его терминологии) свой упорядоченный массив,
> он займется прогнозированием этого курса валют на последующий
> период времени:)Пожелаем ему успеха:)

Чушь! Мне это не нужно! Читайте, пожалуйста, сообщение №24. По-моему, там наглядно написано, что будет и для чего. Смысл мне в прогнозировании курсов? Для этого есть форекс и иже с ними.

Если существует корреляция между курсами ЦБ или иного "уважаемого" источника (а она должна быть, в общем-то), то можно делать отсев по корреляционным зависимостям.

Фильтрация массива чисел от шума Найти похожие ветки