Как отбросить "из ряда вон выбивающиеся" точки?

Форум для обсуждения вопросов математики

Модератор: Admin

exStud
Сообщения: 1
Зарегистрирован: Ср июл 15, 2009 12:51 pm

Как отбросить "из ряда вон выбивающиеся" точки?

Сообщение exStud » Ср июл 15, 2009 1:33 pm

Доброго времени суток. Как ни была крепка моя вера, что после окончания университета высшая математика вообще и теория вероятности, матстат и вычмат в частности мне не понадобятся, встала передо мной задача самая что ни есть математическая.
Итак, дано: есть множество точек на декартовой плоскости, болшинство из которых скучковано, но есть сильно выбивающиеся из кучки точки. Требуется найти наименьшую прямоугольную область, в которой расположены все точки, кроме сильно выбивающихся. Причём сделать это надо программно. Т.е. нужен какой-то более менее строгий алгоритм или формула.
Помню, что решали подобные задачи на матстате. Даже помню, что там оперировали мат.ожиданием и дисперсией (с удивлением отметил, что до сих пор помню не только эти слова, но и их значение). Также крайние значения отбрасывали каким-то образом при интерполяции. Но как это делали не помню. Конспекты лекций преданы огню. А копание в Интернете с поднятием соответствующей литературы и освежением знаний (как вобщем-то и надо бы сделать по хорошему) займёт слишком много времени. Решить же задачу надо быстро. Что посоветуете?

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Re: Как отбросить "из ряда вон выбивающиеся" точки

Сообщение Kitonum » Чт июл 16, 2009 11:30 pm

exStud писал(а):Доброго времени суток. Как ни была крепка моя вера, что после окончания университета высшая математика вообще и теория вероятности, матстат и вычмат в частности мне не понадобятся, встала передо мной задача самая что ни есть математическая.
Итак, дано: есть множество точек на декартовой плоскости, болшинство из которых скучковано, но есть сильно выбивающиеся из кучки точки. Требуется найти наименьшую прямоугольную область, в которой расположены все точки, кроме сильно выбивающихся. Причём сделать это надо программно. Т.е. нужен какой-то более менее строгий алгоритм или формула.
Помню, что решали подобные задачи на матстате. Даже помню, что там оперировали мат.ожиданием и дисперсией (с удивлением отметил, что до сих пор помню не только эти слова, но и их значение). Также крайние значения отбрасывали каким-то образом при интерполяции. Но как это делали не помню. Конспекты лекций преданы огню. А копание в Интернете с поднятием соответствующей литературы и освежением знаний (как вобщем-то и надо бы сделать по хорошему) займёт слишком много времени. Решить же задачу надо быстро. Что посоветуете?

Могу предложить 2 варианта решения. Все шаги в указанных схемах легко программируются.
Первый вариант (более простой). Если у Вас есть основания считать, что точки распределены по нормальному закону (например, рассеяние при стрельбе и т.п.), то действуйте так:
1) Находите среднее арифметическое для всех точек по иксам и по игрекам. Обозначим эту точку через М.
2) Находите расстояние от точки М до каждой из точек. Получите набор чисел d[k], где k=1..n (n - количество точек).
3) Находите среднее квадратичное этих чисел по формуле sigma=(sum(d[k]^2,k=1..n)/n)^(1/2).
Согласно правилу трёх сигм круг с центром в точке М и радиуса 3*sigma содержит примерно 99,7% всех точек. Если такая высокая точность Вам не нужна, то можете взять круг радиуса 2*sigma. Он будет содержать примерно 95% точек.
4) Найдя этот круг, легко уменьшить его до прямоугольника, не потеряв ни одной точки, находя min и max координат тех точек, которые попали в этот круг.
Второй вариант (более громоздкий). Если никаких данных о характере закона распределения нет, кроме того, что Вы написали, то можете действовать так:
1) Находите минимальный прямоугольник, содержащий все точки. Обозначим его вершины через A, B, C, D.
2) Действуйте как в п.1) предыдущего варианта.
3) Соединим точку М с вершинами прямоугольника, найденного в п.1).
4) Начиная от точки М строим всё расширяющуюся последовательность подобных прямоугольников, вершины которых лежат на отрезках AM, BM, CM, DM, заканчивая прямоугольником ABCD. Думаю, что вполне достаточно взять, например, 10 прямоугольников.
5) На каждом шаге считаем количество точек, попавших в соответствующий прямоугольник.
6) Как только процент попавших точек превысит заданную Вами границу, например 95%, то фиксируйте соответствующий прямоугольник.
7) Границы этого прямоугольника можно ещё поджать, действуя как в п.1).

AlexxZ2
Сообщения: 138
Зарегистрирован: Вс ноя 05, 2006 9:05 pm

Сообщение AlexxZ2 » Сб июл 18, 2009 4:50 pm

Как шаблонный ответ для шаблонного задания, Kitonum написал все правильно.
Но по сути, когда мы отбрасываем хоть одну точку мы теряем какую-то часть информации (иногда очень важную) о происходящем процессе. Например, если выясняется, что иногда (хоть и редко) снаряд падает очень далеко от цели и вероятность этого значительно выходит за нормальное распределение. Следовательно существует достаточно вероятностное стечение факторов для такого результата. И нужно вменяемое объяснения для такого нашего поведения - отбрасывания непонравившихся точек.

nn910
Сообщения: 55
Зарегистрирован: Чт май 21, 2009 1:20 pm

Re: Как отбросить "из ряда вон выбивающиеся" точки

Сообщение nn910 » Ср июл 29, 2009 1:05 pm

exStud писал(а):Итак, дано: есть множество точек на декартовой плоскости, болшинство из которых скучковано, но есть сильно выбивающиеся из кучки точки. Требуется найти наименьшую прямоугольную область, в которой расположены все точки, кроме сильно выбивающихся. Причём сделать это надо программно. Т.е. нужен какой-то более менее строгий алгоритм или формула.?
Условие Вашей задачи надо сразу либо сильно упростить либо изменить.То что Вы ищете прямоугольник,показывает,что Вы подсознательно считаете 2 координаты каждой точки независимыми случайными величинами.Так Вот,если по происхождению задачи есть основания считать их независимыми, то надо решить две одинаковых одномерных задачи,для Х-координат и для У.Если же координаты зависимы то почему именно прямоугольник со сторонами параллельными осям? Информативнее (тк меньше площадью) будет параллелограмм -окрестность линии тренда, а также может круг,эллипс или окрестность нелинейного тренда.Уже видел этот Ваш вопрос на другом форуме но и там про независимость никто не стал переспрашивать.Лето...