Вначале рассмотрим задачу вычисления минимаксной регрессии без аномальных точек.
Рассмотрим набор точек плоскости (xi, yi). Минимаксной регрессией называется прямая y=kx+b, минимизирующая наибольшее отклонение точек (xi, yi) от прямой, то есть это такая прямая y=kx+b, для которой функция
Задача вычисления минимаксной регрессии (без аномальных точек) хорошо известна, и её решение можно найти в интернете.
Теперь рассмотрим задачу вычисления минимаксной регрессии с точки зрения проектирования точек на ось ординат во всех возможных направлениях. Проведём через точку (xi, yi) прямую с угловым коэффициентом k. Точка пересечения данной прямой с осью ординат имеет ординату bi(k) = -xik + yi.
Можно показать, что
bi(k) - это линейные функции переменной k. Рассмотрим максимум и минимум набора линейных функций:
Графики функций bmax(k) и bmin(k) - это ломаные. Можно показать, что построить ломаную - график функции bmax(k) - это то же самое, что найти верхнюю оболочку, а построить ломаную - график функции bmin(k) - это то же самое, что найти нижнюю оболочку. А значит, для решения задачи построения выпуклой оболочки и задачи нахождения максимума и минимума набора линейных функций можно применять одни и те же алгоритмы.
Для построения выпуклой оболочки в вычислительной геометрии есть алгоритм Грэхема и алгоритм Джарвиса. Из этих алгоритмов можно получить алгоритмы нахождения максимума и минимума набора линейных функций.
Рассмотрим алгоритмы построения ломаной - графика функции bmax(k).
Рассмотрим алгоритм Джарвиса в двойственной формулировке.
Ломаная строится слева направо. Будем пересекать текущую прямую с другими прямыми и находить самую левую точку пересечения.
Теперь рассмотрим алгоритм Грэхема в двойственной формулировке. Точнее, это двойственная формулировка модификации алгоритма Грэхема, предложенной Эндрью (см.: Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.: Мир, 1989.).
Будем добавлять прямые по одной. Если максимум цветных прямых уже построен, то мы добавляем чёрную прямую и должны обновить максимум. Находим точку пересечения прямой с этой ломаной. То, что правее точки пересечения, обновляется. То, что левее, не обновляется.
Таким образом, первый результат заключается в том, что установлена связь между алгоритмами построения выпуклой оболочки множества точек и алгоритмами построения максимума и минимума набора линейных функций.
Второй результат заключается в обобщении двойственной формулировки алгоритма Грэхема для решения задачи вычисления ломаных maxj (j-й по максимальности) и minj (j-й по минимальности).
Обозначим через maxj zi и minj zi j-й по максимальности и j-й по минимальности элементы последовательности z1, z2, ..., zn.
Минимаксной регрессией с учётом
аномальных точек называется прямая y=kx+b, для которой функция
достигает минимального значения. Можно показать, что
Рассмотрим функции
Графики этих функций - это ломаные. Для построения ломаных - графиков этих функций - можно применить обобщённый алгоритм Грэхема.
Красным цветом выделена ломаная-максимум. Синим цветом выделена ломаная-второй по максимальности. Мы добавляем чёрную прямую и должны обновить ломаную-второй по максимальности. Находим точку пересечения прямой с синей и красной ломаными. Новая ломаная сначала совпадает с синей ломаной, затем с чёрной прямой, а затем с красной ломаной.
Более подробно об этом можно прочитать моей статье: Гренкин Г.В. Методы вычислительной реализации рангового метода кластеризации // Информатика и системы управления. 2012. № 1(31). С. 71–79. Статью можно скачать здесь.
Ещё более подробные выкладки, чем в статье, приведены в моей курсовой работе, которую можно найти по этому адресу.
Рассмотрим набор точек плоскости (xi, yi). Минимаксной регрессией называется прямая y=kx+b, минимизирующая наибольшее отклонение точек (xi, yi) от прямой, то есть это такая прямая y=kx+b, для которой функция
достигает минимума.
Задача вычисления минимаксной регрессии (без аномальных точек) хорошо известна, и её решение можно найти в интернете.
Задачу вычисления минимаксной регрессии можно рассматривать как задачу нахождения многочлена наилучшего равномерного приближения первой степени. Из условия альтернанса вытекает, что искомая прямая параллельна одному из рёбер выпуклой оболочки.
Выпуклой оболочкой множества точек называется наименьший выпуклый многоугольник, содержащий все точки данного множества.
Таким образом, для вычисления минимаксной регрессии нужно построить выпуклую оболочку, перебрать все её рёбра и для каждого ребра провести прямую, параллельную этому ребру, такую, что наибольшее отклонение точек от этой прямой минимально.
Теперь рассмотрим задачу вычисления минимаксной регрессии с точки зрения проектирования точек на ось ординат во всех возможных направлениях. Проведём через точку (xi, yi) прямую с угловым коэффициентом k. Точка пересечения данной прямой с осью ординат имеет ординату bi(k) = -xik + yi.
Можно показать, что
bi(k) - это линейные функции переменной k. Рассмотрим максимум и минимум набора линейных функций:
Рассмотрим алгоритмы построения ломаной - графика функции bmax(k).
Рассмотрим алгоритм Джарвиса в двойственной формулировке.
Теперь рассмотрим алгоритм Грэхема в двойственной формулировке. Точнее, это двойственная формулировка модификации алгоритма Грэхема, предложенной Эндрью (см.: Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.: Мир, 1989.).
Таким образом, первый результат заключается в том, что установлена связь между алгоритмами построения выпуклой оболочки множества точек и алгоритмами построения максимума и минимума набора линейных функций.
Второй результат заключается в обобщении двойственной формулировки алгоритма Грэхема для решения задачи вычисления ломаных maxj (j-й по максимальности) и minj (j-й по минимальности).
Обозначим через maxj zi и minj zi j-й по максимальности и j-й по минимальности элементы последовательности z1, z2, ..., zn.
Минимаксной регрессией с учётом
аномальных точек называется прямая y=kx+b, для которой функция
Более подробно об этом можно прочитать моей статье: Гренкин Г.В. Методы вычислительной реализации рангового метода кластеризации // Информатика и системы управления. 2012. № 1(31). С. 71–79. Статью можно скачать здесь.
Ещё более подробные выкладки, чем в статье, приведены в моей курсовой работе, которую можно найти по этому адресу.
Комментарии
Отправить комментарий