Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 79

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 180 >> Следующая


4.2. Приложения в статистике

213

ЧАЛО; этот процесс продолжается до тех пор, пока из S не будут удалены все точки.

Более сложный и вместе с тем более эффективный алгоритм дает использование метода Овермарса — Ван Леювена поддержки выпуклой оболочки на плоскости (см. разд. 3.3.7). Напомним лишь, что первичной структурой данных, используемой в этом методе, является двоичное дерево поиска, узлы которого указывают на вторичные структуры данных, представляющие сцепляемые очереди. Кроме того, очередь, на которую указывает корень дерева, дает верхнюю оболочку исходного множества точек, а удаление каждой точки выполняется за время 0((logiV)2). Таким образом, используя одновременно структуры, соответствующие верхней и нижней оболочкам, получаем выпуклую оболочку глубины 1. Затем каждая точка построенной оболочки удаляется из обеих структур, из которых теперь можно получить оболочку глубины 2, и т. д. Оболочки получаются тривиальным образом за линейное время в результате прохождения сцепляемой очереди, а полное время, затрачиваемое на удаление всех вершин, равно 0(N\og2N).

Впоследствии эта идея была доведена до большого совершенства Чазелле [Chazelle (1983b)]. А именно общий метод Овермарса — Ван Леювена поддержки выпуклой оболочки рассчитан на произвольную последовательность операций вставки и удаления точек. Однако при построении выпуклых слоев последовательность операций удаления полностью управляется разработчиком алгоритма. Чазелле показал, как можно надлежащим образом сгруппировать операции по удалению точек, чтобы порождать слои более эффективно. Отсылаем читателя к первоисточнику, содержащему доказательство следующей интересной теоремы:

Теорема 4.14. Выпуклые слои, а следовательно, и глубина множества из N точек на плоскости могут быть найдены за оптимальное время Q(N\ogN).

4.2.2. Монотонная регрессия

Задачу о регрессии можно рассматривать как задачу поиска наилучшей аппроксимации данных в некотором подпространстве. Предположим, задано конечное множество точек в Ed, рассматриваемых как значения некоторой функции / от (d—\) переменных, и необходимо определить допустимый класс аппроксимирующих функций и норму для измерения ошибки1).

') В двумерном случае точки (xt,yt) представляют функцию yi = f(xt), и Xi называется независимой переменной. В 6-мерном случае имеем Хи = = f(*i, ..., **_,).

2)4 Гл. 4. Выпуклые оболочки' расширения и приложения

Функция регрессии — это некоторая функция /* от (d — 1) переменных, минимизирующая норму || f — f* ||.

Задача о монотонной регрессии заключается в поиске наилучшей монотонной (т. е. невозрастающей или неубывающей)

Рис. 4.15. Монотонная функция, аппроксимирующая (не лучшим образом) конечное множество точек.

аппроксимирующей функции для конечного множества точек. Обычно в качестве нормы берется норма пространства Ь2 или минимум суммы квадратов ввиду связи последней с методом максимального правдоподобия1). Другими словами, задано

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

множество точек {(xi,yi): i=\, N) и необходимо найти монотонную функцию /, минимизирующую

T,(yt-f (*.))2. i=i

На рис. 4.15 приведен пример монотонной аппроксимирующей функции.

') Более подробно монотонная регрессия рассматривается в книге [Barlow, Bartholomew, Bremner, Brunk (1972)].

4.2. Приложения в статистике

215

Приведенный выше рисунок вводит в некоторое заблуждение, так как он только усиливает интуитивное представление о том, что функция / должна быть непрерывной. В рамках метода наименьших квадратов, когда минимизируется сумма квадратов отклонений, наилучшее соответствие дает ступенчатая функция, пример которой показан на рис. 4.16. Остается «только» определить точки перехода со ступеньки на ступеньку и высоту каждой ступеньки.

Рис. 4.17. Нижняя выпуклая оболочка ДЧС определяет монотонную аппроксимирующую функцию.

Предположим, что данные упорядочены по значению х-ко-ординаты. (Обычно на практике нет необходимости производить сортировку данных, так как независимой переменной является время либо точки выбираются в порядке возрастания х.) Определим диаграмму частичных сумм (ДЧС) как множество точек Pi = (/> si)> Ро ~ (0> 0)> гДе si —эт0 частичная сумма ординат точек:

/

Sj = Z Ух ¦

Наклон отрезка прямой, соединяющего точки p;-_i на р/, как раз равен у,-. Предположим теперь, что построена нижняя оболочка Н множества точек {р0, Ри ¦¦•> Pn} (см. разд. 3.3.2). Между нижней оболочкой И и монотонной функцией регрессии существует замечательная связь: монотонная функция регрессии для

216 Гл. 4. Выпуклые оболочки: расширения и приложения

множества точек определяется наклоном отрезков нижней оболочки его диаграммы частичных сумм [Barlow (1972)] {рис. 4.17). Таким образом, имеет место следующий результат.

Теорема 4.15. Монотонная функция регрессии, определяемая методом наименьших квадратов, для множества из N точек на плоскости может быть найдена за время О (N log N). Если точки множества уже упорядочены по значению абсциссы, то достаточным оказывается время O(N).
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed