Усреднение двумерных выборок Опции

[minibrain]

Здравствуйте. Прошу помощи в решении такой задачи.
Имеется массив плоских координат [x, y]. Большинство значений колеблются вокруг одной точки, но часть значений находятся очень далеко. Как можно реализовать фильтрацию?
В данный момент находится среднее арифметическое по обеим координатам, но выбросы порождают большое смещение от точки, на которую указывает большинство измерений.
Хотелось бы как-то автоматически определять центр скопления точек (район максимальной плотности). Прошу подсказать подходящий алгоритм.
На прикрепленном рисунке зеленым цветом помечены выборки. Розовым - действительное значение (из модели), черным - среднее арифметическое.

Спасибо за внимание.


Сообщение отредактировал minibrain - Nov 19 2015, 15:09

Эскизы прикрепленных изображений

 

[ШСА]

Имеется массив плоских координат [x, y]. Большинство значений колеблются вокруг одной точки, но часть значений находятся очень далеко. Как можно реализовать фильтрацию?

Маленькое уточнение: координаты должны обрабатываться по мере поступления (в реальном времени) или обрабатывается сразу готовый массив?

[thermit]

Построить гистограмму. Выбрать x и y соответствующие максимуму гистограммы.

[Grizzzly]

Здравствуйте. Прошу помощи в решении такой задачи.
Имеется массив плоских координат [x, y]. Большинство значений колеблются вокруг одной точки, но часть значений находятся очень далеко. Как можно реализовать фильтрацию?

Решение "в лоб" - построить двумерную гистограмму, т.е. разбить плоскость сеткой, размеры которой определяются необходимой точностью определения координат.

[_pv]

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

[minibrain]

Маленькое уточнение: координаты должны обрабатываться по мере поступления (в реальном времени) или обрабатывается сразу готовый массив?

Готовый массив.

[ШСА]

Готовый массив.

Что-то не дождусь реакции гуру.
Есть дедовский итерационный алгоритм последовательного отсечения недостоверных отсчётов.
1. Вычисляем среднюю точку O1 усреднением всех точек;
2. Вычисляем радиус от O1 до каждой имеющейся точки и выявляем максимальный радиус отклонения Rmax;
3. Задаём радиус отсечения R0, меньший Rmax. Например R0 = Rmax/2;
4. Просматриваем все точки и подсчитываем число точек, для которых радиус отклонения от O1 превышает R0;
5. Если число таких точек превышает 10%, увеличиваем R0 на половину разницы между Rmax и R0. Переход к п.4.;
Если число таких точек равно нулю, уменьшаем R0, например, на 10%. Переход к п.4.;
6. Вычисляем среднюю точку O2 усреднением тех точек, для которых радиус отклонения от O1 не превышает R0;
7. Если расстояние между O1 и O2 превышает заданную точность, присваиваем O1 = O2; Переход к п.2;
Иначе Выход.

[minibrain]

Спасибо всем, кто ответил. Попробовал построить hist3 в матлабе. Очень хорошо, на первый взгляд.
Может, есть какая-то хорошая, проверенная библиотека на С/С++, которая решала бы эту задачу?

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

[_pv]

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

Давайте данные.

[minibrain]

_pv, реальных данных не сохранилось. Проверю тогда снова на сигмах моделированные данные, если результата не будет - выложу, чтобы ваше время зря сейчас не тратить.

[Grizzzly]

Может, есть какая-то хорошая, проверенная библиотека на С/С++, которая решала бы эту задачу?

В GSL есть функции гистограмм.

[minibrain]

_pv, Вы не могли бы дать ссылку на примерное описание (формулы, или программу в матлабе) того, что вы имели в виду? может, я что-то не верно делал просто.

[_pv]

_pv, реальных данных не сохранилось. Проверю тогда снова на сигмах моделированные данные, если результата не будет - выложу, чтобы ваше время зря сейчас не тратить.

я про исходные данные по которым картинка в первом посте нарисована.

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

а вообще, если вычислительной мощности не жалко, считайте двумерную корреляцию с гауссом,
или же вообще наименьшими квадратами его же на данные натягивайте, там отдельные удалённые точки на положение максимума особо влиять не будут.
либо вообще построить двумерную гистограмму, и по полученной пикселизированной картинке, что-то вроде преобразования Хафа с тем же Гауссом (сложить картинку саму с самой собой со смещениями и с весом по тому же Гауссу), оно всякие левые скопления точек не похожие по форме на Гаусса с заданной шириной хорошо отфильтрует, и потом уже искать среднее.

[minibrain]

Я делал так:
1) сортировал массив по координате х.
2) брал из него медианное значение.
3) для каждого элемента в массиве вычислял значение delta = abs(X - Xmedian); delta2 = delta ^2;
4) Вычислял среднее значение delta2. Назовем его delta2Average.
5) Вычислял deviation = sqrt(delta2Average / size). size - количество усредняемых точек. В моем понимании это сигма.
6) Выкидывал все выборки, для которых delta > (deviation * 3).
7) Пункты 1-6 для координаты у.
8) Брал среднее арифметическое по х и у.

Расписал подробно потому что математик из меня тот еще. Мог грубо ошибиться.

[_pv]

Я делал так:
1) сортировал массив по координате х.
2) брал из него медианное значение.
3) для каждого элемента в массиве вычислял значение delta = abs(X - Xmedian); delta2 = delta ^2;
4) Вычислял среднее значение delta2. Назовем его delta2Average.
5) Вычислял deviation = sqrt(delta2Average / size). size - количество усредняемых точек. В моем понимании это сигма.
6) Выкидывал все выборки, для которых delta > (deviation * 3).
7) Пункты 1-6 для координаты у.
8) Брал среднее арифметическое по х и у.

Расписал подробно потому что математик из меня тот еще. Мог грубо ошибиться.

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

[minibrain]

Вот таблица для матлаба. Такой вариант приемлем?

Прикрепленные файлы

 matlab.zip ( 16.16 килобайт ) Кол-во скачиваний: 11

 

[_pv]

это некое жульничество, когда на картинке линия их нескольких точек, а на самом деле там не по одной точке, а по десять штук друг на дружке и в результате этих левых точек вообще больше чем тех положение которых посчитать надо.
соответственно там все эти левые точки получаются внутри 3х сигм.
тем не менее если выкинуть точки которые лежат за пределом эллипса из одной сигмы, можно даже пару раз подряд, потом посчитать среднее от оставшихся, и дальше среднеквадратичное отклонение считать уже относительно этого нового среднего, и после этого если выкинуть точки за пределами одной новой сигмы, на данной конкретной картинке получается довольно неплохо, координаты среднего {-5.57342, -7.20079}. ну и сколько именно сигм оставлять надо поподбирать будет, чтобы для других произвольных данных тоже нормально работало.

при этом наименьшие квадраты (последняя страница) дают почти то же самое {x0 -> -5.1126, y0 -> -7.91728}.

по поводу С/С++ библиотек можно еще alglib посмотреть, хотя только для фита наименьшими квадратами из своего приложения можно вообще gnuplotом обойтись.

Прикрепленные файлы

 hist.pdf ( 1.85 мегабайт ) Кол-во скачиваний: 14

 

[Fat Robot]

Вариантов много. Один из (вариация на тему того, что предложил ШСА):
1. Назначаем всем точкам равные веса, или, если есть информация о достоверности, то веса пропорциональные достоверности.
2. Находим координаты центра масс системы материальных точек.
3. 'Облегчаем' точки, более удаленные от центра масс. Самое простое: в гауссовской зависимости от расстояния между ц.м. и точкой.
4. Выполняем несколько итераций с п.2

Т.о. с количеством итераций удаленные точки будут уменьшать свой вклад в оценку.

[r_dot]

...Имеется массив плоских координат [x, y]. ... определять центр скопления точек (район максимальной плотности)....

Вообще-то "центр скопления" - это математическое ожидание. По-моему, его и надо тупо считать.
minibrain, почему вы уверены, что какие-то "далеко расположенные" точки надо отбрасывать? Раз они физически есть, то обязательно должны учитываться при расчёте матожидания. Если их отбрасывать, то точность определения вашей точки "центр скопления точек (район максимальной плотности)" наоборот, будет хуже.
Наберите в поисковике "Математическое ожидание случайной величины с дискретным распределением" и тупо считайте по этой формуле.

[Fat Robot]

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

Например, вы стреляете в мишень, но в некоторых патронах порох отсырел. Заранее сказать, что патрон плохой, вы не можете. Поэтому совсем уж нелепые результаты вы выбрасываете из оценки кучности стрельбы.

Раз они физически есть, то обязательно должны учитываться при расчёте матожидания. Если их отбрасывать, то точность определения вашей точки "центр скопления точек (район максимальной плотности)" наоборот, будет хуже.

[ViKo]

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

[r_dot]

...Причина их возниконвения - это отдельный вопрос...

Если ТС уверен, что это, например, результат сбоев при передаче данных, то возможно "да", но опять же не обязательно. Могут и точки "в самой гуще" тоже быть приняты с ошибкой. А в этом случае тоже ничего отбрасывать не нужно. Да, на закон распределения измеряемой величины наложится закон распределения ошибок. Но для большинства систем он близок к равномерному или гауссову, так что на точность расчёта матожидания повлияет гораздо меньше, чем отбрасывание крайних точек.
minibrain, есть возможность загнать на вход системы константу?

...неправильные точки создаются импульсными помехами (не имеющими нормального распределения). ...

Тогда надо приложить усилия и вычислить этот закон. Или хотя бы приблизительно его прикинув. Потом просто наложить его при вычислении матожидания. Это будет всё равно точнее, чем "отбрасывание".

[thermit]

Вообще-то "центр скопления" - это математическое ожидание. По-моему, его и надо тупо считать.

Вообще-то нет.

[r_dot]

Вообще-то нет.

У вас авторская секретная математическая школа?
Поделитесь тайными знаниями?

[ViKo]

Тогда надо приложить усилия и вычислить этот закон. Или хотя бы приблизительно его прикинув. Потом просто наложить его при вычислении матожидания. Это будет всё равно точнее, чем "отбрасывание".

Говоря грубо (более подходящего примера не пришло в голову) - вычисляя среднюю температуру по больнице, не нужно учитывать тех, кто уже "остыл". Совсем.

[Fat Robot]

100 точек с координатами (0,0)
1 точка с координатами (100,100)

У вас авторская математическая школа?
Поделитесь мудростью?

[r_dot]

100 точек с координатами (0,0)
1 точка с координатами (100,100)

И что?
Ну, например, толпа детишек ростом 100 см и один взрослый Валуев 210 см...

[thermit]

У вас авторская секретная математическая школа?
Поделитесь тайными знаниями?

Да какие там тайные знания... Матожидание не обязано совпадать с максимумом плотности (гистограммы).

[Fat Robot]

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

Ну, например, толпа детишек ростом 100 см и один взрослый Валуев 210 см...

[blackfin]

Поделитесь тайными знаниями?

Наверное, самое тайное знание здесь, это знание об эргодичности системы..

Потому как математическое ожидание координаты непрерывной случайной величины равно:

M{X} = Σx_i*P(x_i<X<x_i+1), где:

P(x_i<X<x_i+1) - вероятность того, что случайная величина "X" имеет значение в интервале "i" от x_i до x_i+1.

Ну и если случайная величина обладает свойством эргодичности, то эту вероятность можно оценить как:

P(x_i<X<x_i+1) = m_i/Σm_i, где:

m_i - число точек из выборки размером Σm_i, оказавшихся в интервале от x_i до x_i+1.

Соответственно:

M{X} = (Σx_i*m_i)/Σm_i, где суммирование по всем интервалам "i", или, с учетом того, что:

x_i*m_i = x_i*(1+1+...+1) = x_i+x_i+...+x_i, математическое ожидание равно:

M{X} = (Σx_n)/Σm_n, где суммирование по всем точкам "n", что совпадает с определением центра масс..

Как-то так..

[r_dot]

...максимумом плотности (гистограммы).

Ну и что это за величина, по-вашему?
А если ваша гистограмма имеет плоскую волнистую вершинку? Всё, хана, лапки вверх? Ничего не считается?

Матожидание имеет физический смысл. Это "центр тяжести". Ваш "максимум плотности" - это что?

[Fat Robot]

Целая куча "средних", и каждое с бездной физического смысла. Считайте на здоровье!

https://en.wikipedia.org/wiki/Average#Summary_of_types

Например, если вы оцениваете среднюю зарплату, то ваше любимое мат. ожидание никакого смысла не имеет. Может оказаться, что не существует человека, получающего даже близко к мат. ожиданию. Медиана или мода (максимум плотности, о котором вы спрашивали) - куда более ценные показатели в этом случае.

Ну и что это за величина, по-вашему?
А если ваша гистограмма имеет плоскую волнистую вершинку? Всё, хана, лапки вверх? Ничего не считается?

Матожидание имеет физический смысл. Это "центр тяжести". Ваш "максимум плотности" - это что?

[thermit]

Ну и что это за величина, по-вашему?
А если ваша гистограмма имеет плоскую волнистую вершинку? Всё, хана, лапки вверх? Ничего не считается?

Матожидание имеет физический смысл. Это "центр тяжести". Ваш "максимум плотности" - это что?

Мода

Что касается лапок и пр шаманства - это вне моей компетенции.

[r_dot]

Целая куча "средних", и каждое с бездной физического смысла....

Ну так я-то предложил ТС-у наиболее подходящее, на мой взгляд, решение для его задачи.
А что вы предлагаете?
Может, всё-таки, ответите, что за "максимум плотности (диаграммы)" такой? В той "целой куча "средних", куда вы меня носом тычете - что-то такого нет...

[Fat Robot]

Ну как же нету?

https://en.wikipedia.org/wiki/Mode_(statistics)

Гнев и гордыня застилают вам обзор.

И да, решение вы предложили слабое. Оно не учитывает наличие outlier'ов, о которых говорилось в исходном сообщении. Посмотрите, в этой ветке много решений. в том числе и мое.

Успехов.

Ну так я-то предложил ТС-у наиболее подходящее, на мой взгляд, решение для его задачи.
А что вы предлагаете?
Может, всё-таки, ответите, что за "максимум плотности (диаграммы)" такой? В той "целой куча "средних", куда вы меня носом тычете - что-то такого нет...

[r_dot]

Мода

Ткнули вы неудачно.
В задаче ТС-а скорее всего получится мультимодальность - будет несколько разных, но одинаково часто встречающихся значений. Не подходит Мода.

[blackfin]

Ткнули вы неудачно.

Так ТС уже сказал, что среднее арифметическое его НЕ устраивает, а значит, НЕ устраивает его и математическое ожидание:

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

Оттого и предлагают ему другие решения..

[thermit]

Ткнули вы неудачно.
В задаче ТС-а скорее всего получится мультимодальность - будет несколько разных, но одинаково часто встречающихся значений. Не подходит Мода.

Не спорю. Однако тээсу это решение больше понравилось, чем ваше удачное.
Успехов.

[minibrain]

это некое жульничество, когда на картинке линия их нескольких точек, а на самом деле там не по одной точке, а по десять штук друг на дружке и в результате этих левых точек вообще больше чем тех положение которых посчитать надо.
соответственно там все эти левые точки получаются внутри 3х сигм.
тем не менее если выкинуть точки которые лежат за пределом эллипса из одной сигмы, можно даже пару раз подряд, потом посчитать среднее от оставшихся, и дальше среднеквадратичное отклонение считать уже относительно этого нового среднего, и после этого если выкинуть точки за пределами одной новой сигмы, на данной конкретной картинке получается довольно неплохо, координаты среднего {-5.57342, -7.20079}. ну и сколько именно сигм оставлять надо поподбирать будет, чтобы для других произвольных данных тоже нормально работало.

при этом наименьшие квадраты (последняя страница) дают почти то же самое {x0 -> -5.1126, y0 -> -7.91728}.

по поводу С/С++ библиотек можно еще alglib посмотреть, хотя только для фита наименьшими квадратами из своего приложения можно вообще gnuplotом обойтись.

Посмотрел ваш PDFник и...ничего не понял. Это тоже матлаб? Ни одного знакомого идентификатора

[Grizzzly]

Посмотрел ваш PDFник и...ничего не понял. Это тоже матлаб? Ни одного знакомого идентификатора

Mathematica

[Corner]

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

Сообщение отредактировал Corner - Nov 21 2015, 10:41

[_pv]

Посмотрел ваш PDFник и...ничего не понял. Это тоже матлаб? Ни одного знакомого идентификатора

This is SPARTAAAA Mathematica. Синтаксис да, с непривычки очень своеобразный местами.
Функция CleanData просто отбрасывает точки которые оказались за эллипсом с радиусами std_, и положением avg_.
Соответственно вызвав её пару раз по исходным данным с avg и std соответственно равным среднему и среднеквадратичному часть наиболее удалённых точек будут отброшены, после этого уже можно более менее нормально по оставшимся данным посчитать среднее, и затем посчитать среднеквадратичное отклонение относительно этого среднего, чтобы отбросить точки уже относительно более менее нормальной оценки среднего, по сравнению с исходной.

ну и как уже говорил тупо фит наименьшими квадратами двумерной функции Гаусса, отбрасывает не похожие на этот Гаусс точки тоже очень неплохо.