Prosta głębia

Prosta głębokość w odniesieniu do sześciu czerwonych punktów próbkowania, przy użyciu zmodyfikowanej definicji Burra i in. Duże czarne liczby to głębokości w każdym regionie, a małe niebieskie liczby to głębokości wzdłuż segmentów niebieskich linii.

W solidnych statystykach i geometrii obliczeniowej głębokość symplicalna jest miarą tendencji centralnej określonej przez uproszczenia zawierające dany punkt . W przypadku płaszczyzny euklidesowej zlicza liczbę trójkątów punktów próbkowania, które zawierają dany punkt.

Definicja

Uproszczona głębokość punktu $, w odniesieniu do zestawu punktów próbkowania w tej przestrzeni,$ -wymiarowej przestrzeni euklidesowej to liczba -wymiarowych uproszczeń ( $displaystyle$$d}$ wypukłe kadłuby zestawów punktów $próbkowania$ ), które zawierają $p}$ To samo pojęcie można uogólnić na dowolny rozkład prawdopodobieństwa w punktach płaszczyzny, a nie tylko na rozkład empiryczny $ma$ przez zbiór punktów próbkowania, poprzez zdefiniowanie głębokości jako prawdopodobieństwa, że ​​​​losowo wybrana -krotka kadłub, który p $displaystyle p}$ . To prawdopodobieństwo można obliczyć na podstawie liczby uproszczeń, które $}$ , dzieląc przez $}}$ gdzie jest $.$ punktów próbkowania

Zgodnie ze standardową definicją uproszczonej głębi, uproszczenia, które mają $granice na swoich granicach, liczą się$ samo, jak uproszczenia z ${\ displaystyle p}$ w swoich wnętrzach. Aby uniknąć problematycznego zachowania tej definicji, Burr, Rafalin i Souvaine (2004) zaproponowali zmodyfikowaną definicję uproszczonej głębi, w której uproszczenia z $liczą$ się tylko o połowę mniej. Równoważnie, ich definicja jest średnią liczby otwartych uproszczeń i liczby zamkniętych uproszczeń, które zawierać ${\ displaystyle p}$ .

Nieruchomości

Uproszczona głębokość jest odporna na wartości odstające: jeśli zbiór punktów próbkowania jest reprezentowany przez punkt o maksymalnej głębokości, to nawet stała część punktów próbkowania może zostać dowolnie uszkodzona bez znaczącej zmiany położenia reprezentatywnego punktu. Jest również niezmiennikiem przy przekształceniach afinicznych płaszczyzny.

Jednak uproszczona głębokość nie ma innych pożądanych właściwości dla solidnych miar tendencji centralnej. W przypadku rozkładów centralnie symetrycznych niekoniecznie jest tak, że w środku rozkładu znajduje się unikalny punkt o maksymalnej głębokości. I wzdłuż promienia od punktu maksymalnej głębokości niekoniecznie jest tak, że uproszczona głębokość zmniejsza się monotonicznie.

Algorytmy

$Dla$ zestawów $próbkowania$ na ( ), $n$ euklidesowej głębokość dowolnego innego punktu ${\ Displaystyle O (n \ log n)}$ , w optymalne w niektórych modelach obliczeniowych. W trzech wymiarach ten sam problem można rozwiązać w czasie ${\ Displaystyle O (n ^ {2})}$ .

Możliwe jest skonstruowanie struktury danych za pomocą sieci ε , które mogą przybliżać uproszczoną głębokość punktu zapytania (biorąc pod uwagę stały zestaw próbek lub zestaw próbek poddawanych wstawianiu punktów) w prawie stałym czasie na zapytanie, w dowolnym wymiarze , z przybliżeniem, którego błąd jest małym ułamkiem całkowitej liczby trójkątów określonych przez próbki. W dwóch wymiarach znany jest dokładniejszy algorytm aproksymacji, dla którego błąd aproksymacji jest niewielką wielokrotnością samej głębokości uproszczonej. Te same metody prowadzą również do algorytmów szybkiej aproksymacji w wyższych wymiarach.

${\ Displaystyle SphD (q; F)}$ p jest definiowana jako prawdopodobieństwo, że punkt jest zawarty wewnątrz losowej zamkniętej uzyskanej z pary punktów ${\ displaystyle q}$ od ${\ Displaystyle F \ w \ mathbb {R} ^ {n}}$ . Podczas gdy złożoność czasowa większości innych głębokości danych rośnie wykładniczo, sferyczna głębokość rośnie tylko liniowo w wymiarze ${\ displaystyle d}$ - prosty algorytm obliczania głębokości sferycznej trwa ${\ Displaystyle O (dn ^ {2})}$ . $($ przez głębokość sferyczną

TYŁEK.

Afshani, Peyman; Sheehy, Donald R.; Stein, Yannik (2015), Przybliżanie uproszczonej głębi , arXiv : 1512,04856 , Bibcode : 2015arXiv151204856A

ACG.

   Aloupis, Greg; Cortés, Carmen; Gomez, Franciszek; Soss, Michael; Toussaint, Godfried (2002), „Dolne granice obliczania statystycznej głębi”, Computational Statistics & Data Analysis , 40 (2): 223–229, doi : 10.1016 / S0167-9473 (02) 00032-4 , MR 1924007 , S2CID 94060939

pne.

   Bagchi, Amitabha; Chaudhary, Amitabh; Eppstein, David ; Goodrich, Michael T. (2007), „Deterministyczne próbkowanie i liczenie zakresów w strumieniach danych geometrycznych”, ACM Transactions on Algorithms , 3 (2): art. 16, 18, arXiv : cs/0307027 , doi : 10.1145/1240233.1240239 , MR 2335299 , S2CID 123315817

BRS.

Burr, Michael A.; Rafalin, Eynat; Souvaine, Diane L. (2004), „Uproszczona głębia: ulepszona definicja, analiza i wydajność dla przypadku skończonej próby” (PDF) , Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG'04, Concordia University, Montréal, Quebec, Kanada, 9-11 sierpnia 2004 , s. 136-139

BS.

Bremner, Dawid; Shahsavarifar, Rasoul (2017), optymalny algorytm obliczania głębokości sferycznej punktów na płaszczyźnie , arXiv : 1702,07399 , Bibcode : 2017arXiv170207399B

WSPÓŁ.

Cheng, Andrew Y.; Ouyang, Ming (2001), „O algorytmach dla uproszczonej głębi” , Proceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Kanada, 13-15 sierpnia 2001, s. 53–56

D.

  Dümbgen, Lutz (1992), „Twierdzenia graniczne dla uproszczonej głębi”, Statistics & Probability Letters , 14 (2): 119–128, doi : 10.1016/0167-7152 (92) 90075-G , MR 1173409

GSW.

  Gil, Józef; Steiger, William; Wigderson, Avi (1992), „Geometric medians”, Discrete Mathematics , 108 (1–3): 37–51, doi : 10.1016/0012-365X (92) 90658-3 , MR 1189827

KM.

  Khuller, Samir ; Mitchell, Joseph SB (1990), „O problemie liczenia trójkątów”, Information Processing Letters , 33 (6): 319–321, doi : 10.1016/0020-0190 (90) 90217-L , MR 1045522

L88.

    Liu, Regina Y. (1988), „O pojęciu uproszczonej głębi”, Proceedings of the National Academy of Sciences of the United States of America , 85 (6): 1732–1734, Bibcode : 1988PNAS ... 85.1732L , doi : 10.1073/pnas.85.6.1732 , MR 0930658 , PMC 279852 , PMID 16578830

L90.

  Liu, Regina Y. (1990), „O pojęciu głębi danych opartym na losowych uproszczeniach”, Annals of Statistics , 18 (1): 405–414, doi : 10.1214 / aos / 1176347507 , MR 1041400

RR.

  Rousseeuw, Peter J .; Ruts, Ida (1996), „Algorytm AS 307: Dwuwymiarowa głębokość lokalizacji”, Statystyki stosowane , 45 (4): 516, doi : 10,2307/2986073 , JSTOR 2986073

ZS.

   Zuo, Yijun; Serfling, Robert (2000), „Ogólne pojęcia statystycznej funkcji głębi”, Annals of Statistics , 28 (2): 461–482, CiteSeerX 10.1.1.27.7358 , doi : 10.1214/aos/1016218226 , MR 1790005