|
|
|
empter |
|
|||
Фанат Профиль Группа: Участник Сообщений: 224 Регистрация: 20.5.2005 Репутация: нет Всего: 4 |
Здравствуйте!
Необходимо решение следующей задачи. Имеется массив значений, представляюший из себя значения некоторой функции в точках от 0 до N. Необходимо провести анализ массива на наличие неправильных значений (т.е. некоторые значения в массиве могут быть случайными выбросами и портить график функции). Такие значения необходимо выявить и заменить на предполагаемые правильные значения (интерполяцией, апроксимацией). Какие алгоритмы посоветуете ??? |
|||
|
||||
sergejzr |
|
|||
Un salsero Профиль Группа: Админ Сообщений: 13285 Регистрация: 10.2.2004 Где: Германия г .Ганновер Репутация: 4 Всего: 360 |
Похоже на median cut. иёшь маской в три точки средняя - рабочая, в неё записываешь медиан - среднее значение (но не путать со средним арифметическим!) Работает хорошо, если случайные значения не идут несколько подряд. Края (первое и последнее значение) не обрабатываются
пример: //-- начало алгоритма Исходный массив, по которому идём маской: 2 3 30 5 7 Край не обрабатывается, записываем первое число как есть: ответ: 2 начинаем с 3 на её место записываем медиан(2,3,30) = 3 ответ: 2 3 следующая 30, на её место записываем медиан(3,30,5)=5 ответ: 2 3 5 следующая 5, на её место записываем медиан(30,5,7)=5 ответ: 2 3 5 5 Край не обрабатывается, записываем последнее число как есть: ответ: 2 3 5 5 7 //----Конец алгоритма Числа, которые не совпадают в исходном массиве и ответе - наш мусор. Как модификацию можно после фильтрации сравнить с исходным массивом и заменить числа, которые отличаются средним арифметическим соседей ответа. пример: //-- начало алгортма исходный массив: 2 3 30 5 7 фильтрованный массив: 2 3 5 5 7 2==2 - оставляем ответ: 2 3==3 - оставляем ответ: 2 3 30 != 5 решаем (3+5)/2 = 4 ответ: 2 3 4 5==5 - оставляем ответ: 2 3 4 5 7==7 - оставляем ответ: 2 3 4 5 7 //---- конец алгоритма Преимущество модификации - более сглаженный график. Недостатки - появляются значения, которых вообще не было (грубо говоря выдуманные) Алгоритм сохраняет контуры - резкие перепады значений, если это действительно ступенька. пример: исходный массив: 2 3 4 10 11 15 не измениться, хотя с 4 на десятку прыжок. Добавлено @ 00:41 PS: длину маски можно увеличить. |
|||
|
||||
Фантом |
|
|||
Вы это прекратите! Профиль Группа: Участник Клуба Сообщений: 1516 Регистрация: 23.3.2008 Репутация: 2 Всего: 49 |
В общем случае - уже предложенная медианная фильтрация, а также сплайн-аппроксимация.
А всерьез такой вопрос бессмысленно рассматривать без информации о том, что это за данные. Признаться сможете? Если сможете, признайтесь заодно, есть ли какие-нибудь теоретические представления о том, как эта зависимость должна выглядеть? Если есть - какие? |
|||
|
||||
podval |
|
|||
Где я? Кто я? Профиль Группа: Экс. модератор Сообщений: 3094 Регистрация: 25.3.2002 Где: СПб Репутация: 18 Всего: 62 |
Вообще-то, если имеется какая-то выборка, то ещё до начала построения каких-либо зависимостей проводят статистический анализ данных как раз на предмет обнаружения аномальных наблюдений (измерений). Такие наблюдения вообще удаляют для обеспечения робастности оценок.
|
|||
|
||||
ksili |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2069 Регистрация: 3.11.2005 Где: Красноярск Репутация: 2 Всего: 17 |
Что значит удаляют? Может их на что-то заменяют? -------------------- Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с) |
|||
|
||||
GoldFinch |
|
|||
Профиль Группа: Завсегдатай Сообщений: 2141 Регистрация: 30.11.2008 Репутация: нет Всего: 26 |
||||
|
||||
empter |
|
||||||||
Фанат Профиль Группа: Участник Сообщений: 224 Регистрация: 20.5.2005 Репутация: нет Всего: 4 |
sergejzr Спасибо за идею!!, прикинул алгоритм, в некоторых случаях очень даже неплохо (когда случайные значения не идут подряд), однако встречается и именно такой случай, когда подряд сразу несколько значений являются не верными, так что проблема остается!!!
С апроксимацией в принципе понятно, но необходимо найти ряд неправильных значений, чтобы знать где апроксимировать!
В общих словах имеется система видеонаблюдения за некоторым объектом, одной из функций которой является вычисление углов отклонения этого объекта от горизонтального положения. Т.к. все это происходит на открытой местности, из за погодных условий и т.д ПО выдает неверные значения (в худшем случае до 10% значений неверные). Решили исправлять ошибки при анализе, для чего и нужен фильтр, восстанавливающий ошибочные значения.
Нету!. объекты разные, колебляться по разному, близко к синусойде канешно. но не обязательно. Да!, но надо еще статистику набрать.
Во во!!! |
||||||||
|
|||||||||
sergejzr |
|
|||
Un salsero Профиль Группа: Админ Сообщений: 13285 Регистрация: 10.2.2004 Где: Германия г .Ганновер Репутация: 4 Всего: 360 |
||||
|
||||
Severyanin |
|
|||
Исследователь Профиль Группа: Участник Сообщений: 554 Регистрация: 31.7.2007 Где: Россия, Омск Репутация: нет Всего: 9 |
Существует много реализаций такой фильтрации. Если вам надо сгладить аномальность таких значений, уменьшить их отклонение, советую вам применить цифровой фильтр нижних частот (интегратор). Теория и реализация в среде MatLab описана здесь. Если не подойдет- поищите информацию по цифровой фильтрации. А какой тип фильтра брать - КИХ или БИХ зависит от значений вашей функции
-------------------- "Звонким вереском скроются наши следы, и не вспомнят о них. Кто поверит нам, рыцарям павшей звезды из отвергнутых книг? Пусть в узоре времен ни стихов. ни имен, но напомнит забывшим их полуночный крик." Тэм Гринхилл "Ужели суслик твоего коварства нагадит в плов доверья моего?". Л.Филатов |
|||
|
||||
ksili |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2069 Регистрация: 3.11.2005 Где: Красноярск Репутация: 2 Всего: 17 |
Медианный фильтр или фильтр скользящего среднего - это частные случаи КИХ-фильтра -------------------- Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с) |
|||
|
||||
GoldFinch |
|
|||
Профиль Группа: Завсегдатай Сообщений: 2141 Регистрация: 30.11.2008 Репутация: нет Всего: 26 |
||||
|
||||
empter |
|
|||
Фанат Профиль Группа: Участник Сообщений: 224 Регистрация: 20.5.2005 Репутация: нет Всего: 4 |
Severyanin спасибо. думаю в этом направлении и надо искать, никто не встречал реализаций ФНЧ на C++??? чето погуглил, результатов немного.
|
|||
|
||||
Фантом |
|
|||
Вы это прекратите! Профиль Группа: Участник Клуба Сообщений: 1516 Регистрация: 23.3.2008 Репутация: 2 Всего: 49 |
Т.е. зависимость периодическая или близкая к периодической? Обычный Фурье-анализ тогда не годится? Считаете преобразование Фурье, принудительно срезаете высокочастотную компоненту и делаете обратное преобразование. Ошибки и мелкая "тряска" при этом пропадут. |
|||
|
||||
ksili |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 2069 Регистрация: 3.11.2005 Где: Красноярск Репутация: 2 Всего: 17 |
GoldFinch, то как описал median cut sergejzr (по крайней мере как его понял я) выглядит будто результат каждого шага (то есть заново пересчитываемое значение i-го отсчета) зависит от его теперешнего отсчёта, предыдущего и позапрошлого:
y[i] = 1/3*(x[i] + x[i-1] + x[i-2]) Чем не КИХ-фильтр? Если бы в формулу входили игреки, т.е. рез-ты предыдущих вычислений, то получился бы БИХ-фильтр. В принципе можно и так было реализовать. Правда может тогда он уже будет по-другому называться (не медианный фильтр) Есть старая книга - Хэмминг. "Цифровые фильтры". кажется 1980. Там в самом начале как раз идут вот такие примеры ЦФ, для того, чтобы люди которые раньше ничего не знали о ЦФ, поняли, что они на самом деле уже ими пользовались. -------------------- Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с) |
|||
|
||||
W4FhLF |
|
|||
found myself Профиль Группа: Участник Клуба Сообщений: 2831 Регистрация: 2.12.2006 Репутация: 5 Всего: 121 |
Я так и не понял. Обработка должна идти в режиме реального времени или у нас имеется выборка и нужно сделать постанализ?
-------------------- "Бог умер" © Ницше "Ницше умер" © Бог |
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |