Симплициальная глубина

Симплициальная глубина по отношению к шести красным точкам выборки с использованием модифицированного определения Burr et al. Большие черные цифры — это глубины внутри каждой области, а маленькие синие цифры — это глубины вдоль сегментов синей линии.

В робастной статистике и вычислительной геометрии симплициальная глубина — это мера центральной тенденции, определяемой симплексами , содержащими данную точку. Для евклидовой плоскости он подсчитывает количество треугольников точек выборки, содержащих данную точку.

Определение

Симплициальная глубина точки $p$ в $d$-мерное евклидово пространство по отношению к набору точек выборки в этом пространстве — это количество $d$-мерные симплексы ( выпуклые оболочки множеств $d+1$ точки выборки), которые содержат $p$.То же понятие можно обобщить на любое распределение вероятностей в точках плоскости, а не только на эмпирическое распределение, заданное набором точек выборки, определив глубину как вероятность того, что случайно выбранное $(d+1)$-кортеж точек имеет выпуклую оболочку, содержащую $p$. Эту вероятность можно вычислить по количеству симплексов, содержащих $p$, разделив на ${\tbinom {n}{d+1}}$ где $n$ количество точек выборки. ^{[Л88] [Л90]}

Согласно стандартному определению симплициальной глубины, симплексы, имеющие $p$ на их границах имеют такое же значение, как и симплексы с $p$ в их интерьерах. Чтобы избежать проблем с этим определением, Берр, Рафалин и Сувен (2004) предложили модифицированное определение симплициальной глубины, в котором симплексы с $p$ на их границах рассчитывают лишь вдвое меньше. Эквивалентно, их определение представляет собой среднее количество открытых симплексов и количества закрытых симплексов, содержащих $p$. ^[БРС]

Характеристики

Симплициальная глубина устойчива к выбросам: если набор точек выборки представлен точкой максимальной глубины, то до постоянной доли точек выборки можно произвольно исказить без существенного изменения местоположения репрезентативной точки. Он также инвариантен относительно аффинных преобразований плоскости. ^{[Д] [ЗС] [БРС]}

Однако симплициальная глубина не обладает некоторыми другими желательными свойствами для робастных мер центральной тенденции. Применительно к центрально-симметричным распределениям не обязательно существует единственная точка максимальной глубины в центре распределения. Причем по лучу из точки максимальной глубины симплициальная глубина не обязательно монотонно убывает. ^{[ЗС] [БРС]}

Алгоритмы

Для наборов $n$ точки выборки на евклидовой плоскости ( $d=2$), симплициальная глубина любой другой точки $p$ можно вычислить во времени $O(n\log n)$, ^{[КМ] [GSW] [RR]} оптимален в некоторых моделях вычислений. ^[АКГ] В трех измерениях ту же проблему можно решить за время $O(n^{2})$. ^[КО]

Можно построить структуру данных с использованием ε-сетей , которая может аппроксимировать симплициальную глубину точки запроса (с учетом либо фиксированного набора выборок, либо набора выборок, подвергающихся вставке точек) почти за постоянное время для каждого запроса в любом измерении. с аппроксимацией, погрешность которой составляет небольшую часть общего числа треугольников, определенных выборками. ^{[до н.э.]} В двух измерениях известен более точный алгоритм аппроксимации, для которого ошибка аппроксимации мала, кратна самой симплициальной глубине. Те же методы также приводят к быстрым алгоритмам аппроксимации в более высоких измерениях. ^[ЖОПА]

Сферическая глубина , $SphD(q;F)$ определяется как вероятность того, что точка $q$ содержится внутри случайного замкнутого гипершара, полученного из пары точек из $F\in \mathbb {R} ^{n}$. В то время как временная сложность большинства других глубин данных растет экспоненциально, сферическая глубина растет только линейно в измерении $d$ – простой алгоритм расчета сферической глубины занимает $O(dn^{2})$. Симплициальная глубина (SD) линейно ограничена сферической глубиной ( $SphD\geq {\frac {2}{3}}SD$). ^[БС]

Ссылки

ЖОПА.

Афшани, Пейман; Шихи, Дональд Р.; Штейн, Янник (2015), Аппроксимация симплициальной глубины , arXiv : 1512.04856 , Бибкод : 2015arXiv151204856A

АКГ.

Алупи, Грег; Кортес, Кармен; Гомес, Франциско; Сосс, Майкл; Туссен, Годфрид (2002), «Нижние границы вычисления статистической глубины», Computational Статистика и анализ данных , 40 (2): 223–229, doi : 10.1016/S0167-9473(02)00032-4 , MR   1924007 , S2CID   94060939

до нашей эры.

Багчи, Амитабха; Чаудхари, Амитабх; Эппштейн, Дэвид ; Гудрич, Майкл Т. (2007), «Детерминированная выборка и подсчет диапазонов в потоках геометрических данных», Транзакции ACM по алгоритмам , 3 (2): Ст. 16, 18, arXiv : cs/0307027 , doi : 10.1145/1240233.1240239 , MR   2335299 , S2CID   123315817

БРС.

Берр, Майкл А.; Рафалин, Эйнат; Сувен, Дайан Л. (2004), «Симплициальная глубина: улучшенное определение, анализ и эффективность для случая конечной выборки» (PDF) , Материалы 16-й Канадской конференции по вычислительной геометрии, CCCG'04, Университет Конкордия, Монреаль, Квебек, Канада, 9–11 августа 2004 г. , стр. 136–139.

БС.

Бремнер, Дэвид; Шахсаварифар, Расул (2017), Оптимальный алгоритм вычисления сферической глубины точек на плоскости , arXiv : 1702.07399 , Bibcode : 2017arXiv170207399B

КО.

Ченг, Эндрю Ю.; Оуян, Минг (2001), «Об алгоритмах симплициальной глубины» , Труды 13-й Канадской конференции по вычислительной геометрии, Университет Ватерлоо, Онтарио, Канада, 13–15 августа 2001 г. , стр. 53–56.

Д.

Дюмбген, Лутц (1992), «Предельные теоремы для симплициальной глубины», Статистика и вероятностные письма , 14 (2): 119–128, doi : 10.1016/0167-7152(92)90075-G , MR   1173409

ВШВ.

Гил, Джозеф; Штайгер, Уильям; Вигдерсон, Ави (1992), «Геометрические медианы», Дискретная математика , 108 (1–3): 37–51, doi : 10.1016/0012-365X(92)90658-3 , MR   1189827

КМ.

Хуллер, Самир ; Митчелл, Джозеф С.Б. (1990), «О проблеме подсчета треугольников», Information Processing Letters , 33 (6): 319–321, doi : 10.1016/0020-0190(90)90217-L , MR   1045522

Л88.

Лю, Регина Ю. (1988), «О понятии симплициальной глубины», Труды Национальной академии наук Соединенных Штатов Америки , 85 (6): 1732–1734, Бибкод : 1988PNAS...85.1732L , doi : 10.1073/pnas.85.6.1732 , MR   0930658 , PMC   279852 , PMID   16578830

Л90.

Лю, Регина Ю. (1990), «О понятии глубины данных, основанном на случайных симплексах», Annals ofStatistics , 18 (1): 405–414, doi : 10.1214/aos/1176347507 , MR   1041400

РР.

Руссиу, Питер Дж .; Рутс, Ида (1996), «Алгоритм AS 307: глубина двумерного местоположения», Applied Статистика , 45 (4): 516, doi : 10.2307/2986073 , JSTOR   2986073

ЗС.

Цзо, Ицзюнь; Серфлинг, Роберт (2000), «Общие понятия функции статистической глубины», Annals of Статистика , 28 (2): 461–482, CiteSeerX   10.1.1.27.7358 , doi : 10.1214/aos/1016218226 , MR   1790005