En estadística robusta y geometría computacional , la profundidad simplicial es una medida de tendencia central determinada por los simplices que contienen un punto dado. Para el plano euclidiano , cuenta el número de triángulos de puntos muestrales que contienen un punto dado.
Definición
La profundidad simplicial de un punto en -espacio euclidiano dimensional , con respecto a un conjunto de puntos muestrales en ese espacio, es el número de-simplices dimensionales (los cascos convexos de conjuntos de puntos de muestra) que contienen . La misma noción se puede generalizar a cualquier distribución de probabilidad en puntos del plano, no solo a la distribución empírica dada por un conjunto de puntos muestrales, definiendo la profundidad como la probabilidad de que un-tupla de puntos tiene un casco convexo que contiene. Esta probabilidad se puede calcular a partir del número de simples que contienen, dividiendo por dónde es el número de puntos muestrales. [L88] [L90]
Bajo la definición estándar de profundidad simplicial, los simplices que tienen en sus límites cuentan tanto como los simples con en sus interiores. Para evitar algún comportamiento problemático de esta definición, Burr, Rafalin & Souvaine (2004) propusieron una definición modificada de profundidad simplicial, en la que los simplices conen sus límites cuentan solo la mitad. De manera equivalente, su definición es el promedio del número de simples abiertos y el número de simples cerrados que contienen. [BRS]
Propiedades
La profundidad simple es robusta frente a valores atípicos: si un conjunto de puntos de muestra está representado por el punto de profundidad máxima, entonces hasta una fracción constante de los puntos de muestra puede corromperse arbitrariamente sin cambiar significativamente la ubicación del punto representativo. También es invariante bajo afines transformaciones del plano. [D] [ZS] [BRS]
Sin embargo, la profundidad simplicial no tiene otras propiedades deseables para medidas robustas de tendencia central. Cuando se aplica a distribuciones centralmente simétricas, no es necesariamente el caso de que haya un punto único de profundidad máxima en el centro de la distribución. Y, a lo largo de un rayo desde el punto de máxima profundidad, no es necesariamente el caso de que la profundidad simplicial disminuya monótonamente. [ZS] [BRS]
Algoritmos
Para conjuntos de puntos muestrales en el plano euclidiano (), la profundidad simplicial de cualquier otro punto se puede calcular a tiempo , [KM] [GSW] [RR] óptimo en algunos modelos de cálculo. [ACG] En tres dimensiones, el mismo problema se puede resolver a tiempo. [CO]
Es posible construir una estructura de datos utilizando redes ε que pueden aproximarse a la profundidad simple de un punto de consulta (dado un conjunto fijo de muestras o un conjunto de muestras sometidas a inserciones de puntos) en un tiempo casi constante por consulta, en cualquier dimensión. , con una aproximación cuyo error es una pequeña fracción del número total de triángulos determinados por las muestras. [BCE] En dos dimensiones, se conoce un algoritmo de aproximación más preciso, para el cual el error de aproximación es un pequeño múltiplo de la profundidad simplicial misma. Los mismos métodos también conducen a algoritmos de aproximación rápida en dimensiones superiores. [CULO]
Profundidad esférica , se define como la probabilidad de que un punto está contenido dentro de una hiperbola cerrada aleatoria obtenida de un par de puntos de. Mientras que la complejidad temporal de la mayoría de las otras profundidades de datos crece exponencialmente, la profundidad esférica crece solo linealmente en la dimensión - el algoritmo sencillo para calcular la profundidad esférica toma . La profundidad simple (SD) está limitada linealmente por la profundidad esférica (). [BS]
Referencias
CULO. | Afshani, Peyman; Sheehy, Donald R .; Stein, Yannik (2015), Aproximación de la profundidad simplicial , arXiv : 1512.04856 , Bibcode : 2015arXiv151204856A |
ACG. | Aloupis, Greg; Cortés, Carmen; Gómez, Francisco; Soss, Michael; Toussaint, Godfried (2002), " Límites inferiores para calcular la profundidad estadística", Estadística computacional y análisis de datos , 40 (2): 223–229, doi : 10.1016 / S0167-9473 (02) 00032-4 , MR 1924007 |
AEC. | Bagchi, Amitabha; Chaudhary, Amitabh; Eppstein, David ; Goodrich, Michael T. (2007), "Muestreo determinista y recuento de rangos en flujos de datos geométricos", Transacciones ACM sobre algoritmos , 3 (2): Art. 16, 18, arXiv : cs / 0307027 , doi : 10.1145 / 1,240,233.1240239 , MR 2335299 |
BRS. | Burr, Michael A .; Rafalin, Eynat; Souvaine, Diane L. (2004), "Simplicial depth: Una definición, análisis y eficiencia mejorados para el caso de muestra finita" (PDF) , Actas de la 16ª Conferencia Canadiense sobre Geometría Computacional, CCCG'04, Concordia University, Montreal, Québec, Canadá, 9-11 de agosto de 2004 , págs. 136-139 |
BS. | Bremner, David; Shahsavarifar, Rasoul (2017), Un algoritmo óptimo para calcular la profundidad esférica de puntos en el plano , arXiv : 1702.07399 , Bibcode : 2017arXiv170207399B |
CO. | Cheng, Andrew Y .; Ouyang, Ming (2001), "Sobre algoritmos para profundidad simplicial" , Actas de la 13ª Conferencia Canadiense sobre Geometría Computacional, Universidad de Waterloo, Ontario, Canadá, 13-15 de agosto de 2001 , págs. 53–56 |
D. | Dümbgen, Lutz (1992), "Teoremas del límite para la profundidad simplicial", Estadística y letras de probabilidad , 14 (2): 119-128, doi : 10.1016 / 0167-7152 (92) 90075-G , MR 1173409 |
GSW. | Gil, Joseph; Steiger, William; Wigderson, Avi (1992), "Medianas geométricas", Matemáticas discretas , 108 (1-3): 37-51, doi : 10.1016 / 0012-365X (92) 90658-3 , MR 1189827 |
KM. | Khuller, Samir ; Mitchell, Joseph SB (1990), "Sobre un problema de conteo de triángulos", Information Processing Letters , 33 (6): 319–321, doi : 10.1016 / 0020-0190 (90) 90217-L , MR 1045522 |
L88. | Liu, Regina Y. (1988), "Sobre una noción de profundidad simplicial", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 85 (6): 1732-1734, Bibcode : 1988PNAS ... 85.1732L , doi : 10.1073 / pnas.85.6.1732 , MR 0.930.658 , PMC 279 852 , PMID 16578830 |
L90. | Liu, Regina Y. (1990), "Sobre una noción de profundidad de datos basada en simplices aleatorios", Annals of Statistics , 18 (1): 405–414, doi : 10.1214 / aos / 1176347507 , MR 1041400 |
RR. | Rousseeuw, Peter J .; Ruts, Ida (1996), "Algoritmo AS 307: Profundidad de ubicación bivariada", Estadísticas aplicadas , 45 (4): 516, doi : 10.2307 / 2986073 |
ZS. | Zuo, Yijun; Serfling, Robert (2000), "Nociones generales de la función de profundidad estadística", Annals of Statistics , 28 (2): 461–482, CiteSeerX 10.1.1.27.7358 , doi : 10.1214 / aos / 1016218226 , MR 1790005 |