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

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


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

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

Построить гистограмму. Выбрать 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) Брал среднее арифметическое по х и у.

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

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