Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
210
Гл. 4. Выпуклые оболочки: расширения и приложения
4.2. Приложения в статистике
Между геометрией и статистикой имеется тесная связь, обусловленная тем, что многомерные статистические данные можно рассматривать как точки в евклидовом пространстве. В такой постановке задачи статистики превращаются в чисто геометрические задачи. Например, в задаче о линейной регрессии требуется найти наиболее подходящую в смысле заданной нормы гиперплоскость. Некоторые задачи в теории голосования можно интерпретировать как задачи поиска й-мерного полушария, содержащего наибольшее число точек множества. В работе [Shamos (1976)] дан обзор геометрических методов, применяемых в статистике. В некоторых задачах статистики построение выпуклой оболочки является основным моментом, и в нескольких последующих разделах мы рассмотрим некоторые из них.
4.2.1. Робастное оценивание
Основной задачей в статистике является оценивание параметров некоторой популяции, таких как среднее значение, на основе лишь небольшой случайной выборки. Будем говорить, что функция t является несмещенной оценкой для параметра р, если E[t] =р, т. е. математическое ожидание t в точности равно р
а = 0,2 (Удаляются 20 % пак верхние, так и нижних точек) Рис. 4.12. а-урезанное среднее.
[Hoel (1971)]. Так как среднее значение выборки является несмещенной оценкой для среднего значения популяции, то оно очень чувствительно к выбросам — наблюдениям, существенно выпадающим из основной массы. Желательно уменьшить влияние, оказываемое такими выбросами, так как они часто представляют неверные данные, которые иначе могли бы внести ошибки в анализ данных. Соответствующее свойство, которым должна обладать хорошая оценка, называется робастностью (устойчивостью), что означает нечувствительность к отклонениям от предполагаемого распределения популяции. Было предложено много методов, дающих такие оценки [Andrews (1972)]. Важный класс составляют методы оценивания, известные как методы Гэствирта [Gastwirth (1966)]. Эти методы основываются на идее, согласно которой наибольшее доверие оказывается данным, более близким к «центру» выборки.
4.2. Приложения в статистике
211
Рассмотрим N точек на прямой (рис. 4.12). Простой метод устранения предполагаемых выбросов заключается в удалении части точек с левого и правого краев — по aN точек с каждой стороны. Среднее значение вычисляется по оставшимся точкам. Это значение известно как а-урезанное среднее и является частным случаем оценки по методу Гэствирта:
Т =Yu WiX(i), X Wi=l,
где X(t) обозначает i-й наименьший из х,-. Для сс-урезанного среднего имеем
Wi= 1/[(1 — 2а) Д/J, aW</<(l —a)N. Любое урезанное среднее можно вычислить за время O(N) (используя алгоритм выборки линейной сложности), а любую оценку по методу Гэствирта можно вычислить за время 0(N\ogN) (используя сортировку). Теперь возникает вопрос: что представляет собой аналогичная процедура в случае более высокой размерности? Тьюки предложил процедуру, известную под названием «лущение» или «шелушение», состоящую в удалении выпуклой оболочки множества с последующим удалением выпуклой оболочки оставшегося множества, и так до тех пор, пока не останется лишь (1 — 2a)N точек [Huber (I972)]- Эта процедура приводит нас к следующим определению и задаче.
Определение 4.2. Глубиной точки р в множестве S называется число выпуклых оболочек (выпуклых слоев), которые должны быть удалены из 5 прежде, чем будет удалена точка р.
Глубина Z -
Рис. 4.13. Глубина точки а множестве.
Глубина множества S — это глубина его самой глубокой точки (рис. 4.13).
В связи со сказанным возникает следующая геометрическая задача, представляющая и самостоятельный интерес:
Задача В08 (ГЛУБИНА МНОЖЕСТВА). На плоскости задано множество из N точек. Требуется найти глубину каждой точки.
212 Гл. 4. Выпуклые оболочки: расширения и приложения
Теорема 4.13. Любой алгоритм, определяющий глубину каждой точки в множестве, в худшем случае должен выполнить Q{N\ogN) сравнений.
Доказательство. Воспользуемся методом сведения задачи СОРТИРОВКА. Рассмотрим одномерное множество. Зная глубину каждой точки, можно упорядочить множество, выполнив дополнительно лишь O(N) сравнений.
Лишь совсем недавно был разработан алгоритм, достигающий этой нижней оценки. Однако, прежде чем переходить к его описанию, интересно вкратце рассмотреть историю этой задачи.
Рис. 4.14. Определение глубины точек хода по методу Джарвиса. Вершины, НАЧАЛО, обведены кружком.
'Начало иачало
Решение задачи методом «грубой силы» сводится к последовательному построению выпуклой оболочки данного множества S, затем выпуклой оболочки точек, не вошедших в первую выпуклую оболочку, и т. д., на что потребуется в худшем случае 0(N2\og N) операций. (Эта оценка достигается в случае, когда множество получаемых выпуклых оболочек представляет LjV/3J вложенных треугольников.) В несколько более искусном подходе [Shamos (1978)] многократно используется метод обхода Джарвиса (см. разд. 3.3.3), а достигаемое при этом время работы алгоритма равно 0(N2). Рис. 4.14 иллюстрирует работу этого алгоритма. Для единообразия обработки вводится дополнительная фиктивная точка ро = (*о, Уо), координаты которой равны минимальным значениям абсциссы и ординаты точек множества S. Просмотр точек множества начинается с точки ро, и первая достигнутая точка маркируется меткой НАЧАЛО. Последующий обход точек выполняется в направлении против часовой стрелки. Каждая пройденная точка (за исключением НАЧАЛО) удаляется из 5. Когда вновь достигается точка НАЧАЛО, завершается построение выпуклой оболочки глубины 1. Точка НАЧАЛО удаляется из множества S, а роль точки ро принимает на себя точка, предшествующая точке НА-
