Szimpliciális mélység

A hat piros mintapont által meghatározott szimpliciális mélységek, Burr et al. módosított definíciója alapján. A nagyobb, fekete számok az egyes régiók mélységei, a kisebb, kék számok pedig a kék egyenes szakaszok menti mélységértékek.

A matematika, azon belül a robusztus statisztika és a számítási geometria területén a szimpliciális mélység vagy szimplexmélység (simplicial depth) adott pontokat tartalmazó szimplexek száma alapján meghatározott központi tendenciamérték. Az euklideszi síkon az adott pontot tartalmazó háromszögek száma határozza meg.

Definíció

A $d$-dimenziós euklideszi térben elhelyezkedő $p$ pont szimpliciális mélysége, az adott térben elhelyezkedő valamely mintapontok halmazát tekintve, azon $d$-dimenziós szimplexek száma (a $d+1$ mintapont halmazainak konvex burkai), melyek tartalmazzák $p$-t. Ugyanez az elgondolás általánosítható a sík pontjainak bármilyen valószínűségi eloszlására, nem csak a mintapontok által meghatározott empirikus eloszlásra, ha a mélységet annak a valószínűségeként definiáljuk, hogy egy véletlenszerűen kiválasztott pont-$(d+1)$-es konvex burka tartalmazza $p$-t. Ez a valószínűség kiszámítható a $p$-t tartalmazó szimplexek számát elosztva $(\genfrac{}{}{0ex}{}{n}{d+1})$-gyel, ahol $n$ a mintapontok száma. A szimpliciális mélység standard definíciója szerint ugyanolyan súlyozással kell figyelembe venni az olyan szimplexeket, melyeknek $p$ a határán helyezkedik el, mint azokat, melyeknek a belsejében. Ez problematikus viselkedést okozhat, melynek elkerülésére (Burr, Rafalin & Souvaine 2004) a szimpliciális mélység módosított definíciójára tett javaslatot, melyben $p$ a határán fekvő szimplexeket feleakkora súlyozással kell figyelembe venni. Ezzel ekvivalens definíció szerint a $p$-t tartalmazó nyitott szimplexek és zárt szimplexek számának átlagát veszik figyelembe.

Tulajdonságok

A szimpliciális mélység robusztus viselkedést mutat a kiugró értékekkel szemben: ha mintapontok egy halmazát egy maximális mélységű pont reprezentálja, akkor a mintapontok egy konstans százalékánál nem nagyobb számú pont tetszőlegesen elrontható anélkül, hogy a reprezentatív pont helyzete szignifikánsan megváltozna. A szimpliciális mélység továbbá a sík affin transzformációira invariáns. A szimpliciális mélység azonban nem rendelkezik néhány jellemzővel, melyek a centrális tendencia robusztus mértékével szemben elvárhatók lennének. Középpontosan szimmetrikus eloszlások esetén nem minden esetben található egyedi, maximális mélységű pont az eloszlás közepén. Továbbá, a maximális mélységű pontból kiinduló félegyenes mentén a szimpliciális mélység értéke nem feltétlenül monoton csökkenő.

Algoritmusok

Az euklideszi síkon ($d=2$) található $n$ mintapont esetén a tőlük különböző tetszőleges $p$ pont szimpliciális mélysége $O(n\log n)$ időben számítóható, egyes számítási modellekben optimálisan. Három dimenzióban ugyanez a probléma $O(n^2)$ időt vesz igénybe. Epszilon-hálók segítségével konstruálható olyan adatszerkezet, ami képes adott lekérdezési pont (akár egy fix minthahalmazon, akár pontbeillesztés alatt álló mintahalmazon tekintve) szimpliciális mélységét lekérdezésenként közel konstans időben közelíteni, akárhány dimenzióban, ahol az approximáció hibája a minták által meghatározott háromszögek számának kis százaléka. Két dimenzióban pontosabb közelítési algoritmus is ismert, melyben a közelítés hibája magának a szimpliciális mélységnek alacsony százaléka. Ugyanezek a módszerek magasabb dimenziókban is gyors approximációs algoritmusokhoz vezetnek.

Szferikus mélység

A szferikus mélység vagy gömbi mélység, $SphD(q;F)$ annak a valószínűsége, hogy a $q$ benne van az $F\in {\mathbb{ℝ}}^n$ pontpárja által meghatározott hipergömb belsejében. Bár az adatmélységek idő-komplexitása általában a $d$ dimenzió függvényében exponenciálisan növekszik, a szferikus mélysége csak lineárisan – az egyszerű, szferikus mélységet számító algoritmus csak $O(d{n}^2)$ időt vesz igénybe. A szimpliciális mélység (SD) lineáris távolságra található a szferikus mélységtől ($SphD\ge \frac{2}{3}SD$).

Fordítás

• Ez a szócikk részben vagy egészben a Simplicial depth című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

ASS. Afshani, Peyman; Sheehy, Donald R. & Stein, Yannik (2015), Approximating the simplicial depth

ACG. Aloupis, Greg; Cortés, Carmen & Gómez, Francisco et al. (2002), "Lower bounds for computing statistical depth", Computational Statistics & Data Analysis 40 (2): 223–229, DOI 10.1016/S0167-9473(02)00032-4

BCE. Bagchi, Amitabha; Chaudhary, Amitabh & Eppstein, David et al. (2007), "Deterministic sampling and range counting in geometric data streams", ACM Transactions on Algorithms 3 (2): Art. 16, 18, DOI 10.1145/1240233.1240239

BRS. Burr, Michael A.; Rafalin, Eynat & Souvaine, Diane L. (2004), "Simplicial depth: An improved definition, analysis, and efficiency for the finite sample case", Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG'04, Concordia University, Montréal, Québec, Canada, August 9-11, 2004, pp. 136–139

BS. Bremner, David & Shahsavarifar, Rasoul (2017), An Optimal Algorithm for Computing the Spherical Depth of Points in the Plane

CO. Cheng, Andrew Y. & Ouyang, Ming (2001), "On algorithms for simplicial depth", Proceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Canada, August 13-15, 2001, pp. 53–56

D. Dümbgen, Lutz (1992), "Limit theorems for the simplicial depth", Statistics & Probability Letters 14 (2): 119–128, DOI 10.1016/0167-7152(92)90075-G

GSW. Gil, Joseph; Steiger, William & Wigderson, Avi (1992), "Geometric medians", Discrete Mathematics 108 (1-3): 37–51, DOI 10.1016/0012-365X(92)90658-3

KM. Khuller, Samir & Mitchell, Joseph S. B. (1990), "On a triangle counting problem", Information Processing Letters 33 (6): 319–321, DOI 10.1016/0020-0190(90)90217-L

L88. Liu, Regina Y. (1988), "On a notion of simplicial depth", Proceedings of the National Academy of Sciences of the United States of America 85 (6): 1732–1734, DOI 10.1073/pnas.85.6.1732

L90. Liu, Regina Y. (1990), "On a notion of data depth based on random simplices", Annals of Statistics 18 (1): 405–414, DOI 10.1214/aos/1176347507

RR. Rousseeuw, Peter J. & Ruts, Ida (1996), "Algorithm AS 307: Bivariate Location Depth", Applied Statistics 45 (4): 516, DOI 10.2307/2986073

ZS. Zuo, Yijun & Serfling, Robert (2000), "General notions of statistical depth function", Annals of Statistics 28 (2): 461–482, DOI 10.1214/aos/1016218226