<<
>>

Задача

При работе с научными и статистическими данными, нанесенными на плоскость, аналитики часто пытаются найти «линию наилучшего соответствия» для этих данных (рис. 6.6).

Рис.

6.6. Линия наилучшего соответствия

Эта основополагающая задача из области статистики и вычислительной ма- тематики формулируется следующим образом. Допустим, данные представляют собой множество P из n точек на плоскости, обозначаемых (xpy), (x2,y2), ..., (xn,yn); предполагается, что x < x2 < ... < xn. Для линии L, определяемой уравнением у = ax + b, погрешностью L относительно P называется сумма возведенных в ква- драт «расстояний» от точек до P:

Естественной целью в такой ситуации будет нахождение линии с минималь- ной погрешностью.

Оказывается, у этой задачи существует компактное решение, которое легко вычисляется методами математического анализа. Опуская про- межуточные выкладки, приведем результат: линия минимальной погрешности определяется формулой у = ax + b, где

Но существует проблема, для которой эти формулы не подойдут. Часто набор данных выглядит примерно так, как показано на рис. 6.7. В таком случае нам хоте- лось бы сделать утверждение вида «Точки лежат приблизительно на серии из двух линий». Как формализовать такое понятие?

Рис.

6.7. Набор точек, расположенных приблизительно вдоль двух линий

Для любой одиночной линии погрешность у точек на рисунке будет запредель- ной; но если использовать две линии, ошибка может быть относительно невелика. Итак, новую задачу можно попытаться сформулировать следующим образом: вместо того, чтобы искать одну линию наилучшего соответствия, мы ищем набор линий, обеспечивающий минимальную погрешность. Но такая формулировка за- дачи никуда не годится, потому что у нее имеется тривиальное решение: при сколь угодно большом наборе линий можно добиться идеального соответствия, соединив линиями каждую пару последовательных точек в P.

С противоположной стороны можно жестко «запрограммировать» число 2 в задаче — искать лучшее соответствие не более чем с двумя линиями. Но и та- кая формулировка противоречит здравому смыслу: изначально не было никакой априорной информации о том, что точки лежат приблизительно на двух линиях; мы пришли к такому выводу, взглянув на иллюстрацию. Вероятно, большинство людей также скажет, что точки на рис. 6.8 лежат приблизительно на трех линиях.

Рис. 6.8. Набор точек, расположенных приблизительно вдоль трех линий

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии