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

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

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

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

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

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

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

Что-то не дождусь реакции гуру.
Есть дедовский итерационный алгоритм последовательного отсечения недостоверных отсчётов.
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;
Иначе Выход.

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

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

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

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

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

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

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

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

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

Я делал так:
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) Брал среднее арифметическое по х и у.

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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", что совпадает с определением центра масс..

Как-то так..

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

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

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

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

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

Мода

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

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

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

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

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

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

Успехов.

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

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

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

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

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

Mathematica

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

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

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