Yo quiero estimar los cuantiles de algunos datos. Los datos son tan grandes que no pueden ser atendidas en la memoria. Y los datos no son estáticos, los nuevos datos que siguen llegando. ¿Alguien conoce un algoritmo para controlar los cuantiles de los datos observados hasta ahora con muy limitada de la memoria y de cálculo? Me parece P2 algoritmo útil, pero no funciona muy bien para mi de datos, los cuales son extremadamente pesado de cola distribuida.
Respuestas
¿Demasiados anuncios?
jldugger
Puntos
7490
El P2 algoritmo es un agradable encontrar. Funciona mediante la realización de varias estimaciones de la cuantil, actualizar periódicamente, y utilizando cuadrática (no lineal, no se cúbicos) de interpolación para estimar los cuantiles. Los autores afirman interpolación cuadrática funciona mejor en las colas de la interpolación lineal y cúbico sería demasiado exigente y difícil.
Usted no indican exactamente cómo este enfoque no por su "heavy-tailed de datos", pero es fácil de adivinar: estimaciones de extrema cuantiles para el pesado de cola de las distribuciones será inestable hasta que una gran cantidad de datos recolectados. Pero esto va a ser un problema (en menor medida), incluso si se va a almacenar todos los datos, así que no esperes milagros!
En cualquier caso, ¿por qué no se establece auxiliar marcadores-vamos a llamarlos $x_0$ $x_6$--dentro de la cual usted está muy seguro de que el cuantil van a mentir, y almacenar todos los datos que se encuentran entre el$x_0$$x_6$? Cuando el buffer se llena, usted tendrá que actualizar estos marcadores, siempre manteniendo $x_0 \le x_6$. Un algoritmo simple para hacer esto puede ser concebido a partir de una combinación de (a) la corriente P2 estimación de los cuantiles y (b) que se almacenan cuenta de que el número de datos menos de $x_0$ y el número de datos mayor que $x_6$. De esta manera usted puede, con la certeza de alta, la estimación de los cuantiles tan bien como si tuviera todo el conjunto de datos siempre disponibles, pero usted sólo necesita un relativamente pequeño búfer.
Específicamente, estoy proponiendo una estructura de datos $(k, \mathbf{y}, n)$ para mantener la información parcial acerca de una secuencia de $n$ datos de los valores de $x_1, x_2, \ldots, x_n$. Aquí, $\mathbf{y}$ es una lista enlazada
$$\mathbf{y} = (x^{(n)}_{[k+1]} \le x^{(n)}_{[k+2]} \le \cdots \le x^{(n)}_{[k+m]}).$$
En esta notación $x^{(n)}_{[i]}$ indica el $i^\text{th}$ más pequeño de la $n$ $x$ los valores leídos hasta ahora. $m$ es una constante, el tamaño del búfer $\mathbf{y}$.
El algoritmo comienza rellenando $\mathbf{y}$ con el primer $m$ los valores de los datos encontrados y colocarlos en orden, del más pequeño al más grande. Deje $q$ ser el cuantil para ser estimado; por ejemplo, $q$ = 0.99. Tras la lectura de $x_{n+1}$ hay tres posibles acciones:
Si $x_{n+1} \lt x^{(n)}_{[k+1]}$, incremento $k$.
Si $x_{n+1} \gt x^{(n)}_{[k+m]}$, no hacer nada.
De lo contrario, inserte $x_{n+1}$ a $\mathbf{y}$.
En cualquier caso, el incremento de $n$.
La inserción procedimiento pone a $x_{n+1}$ a $\mathbf{y}$ ordenados y, a continuación, elimina uno de los valores extremos en $\mathbf{y}$:
Si $k + m/2 \lt n q$, a continuación, retire $x^{(n)}_{[k+1]}$ $\mathbf{y}$ e incremento $k$;
De lo contrario, quite $x^{(n)}_{[k+m]}$$\mathbf{y}$.
Siempre $m$ es lo suficientemente grande, este procedimiento soporte de la verdadera cuantil de la distribución, con alta probabilidad. En cualquier etapa de la $n$ se calcula de la forma habitual en términos de$x^{(n)}_{[\lfloor{q n}\rfloor]}$$x^{(n)}_{[\lceil{q n}\rceil]}$, lo que probablemente se encuentran en $\mathbf{y}$. (Creo $m$ sólo tiene a escala, como la raíz cuadrada de la cantidad máxima de datos ($N$), pero no he llevado a cabo un análisis riguroso para demostrar que.) En cualquier caso, el algoritmo detectar si ha tenido éxito (comparando $k/n$$(k+m)/n$$q$).
Pruebas con hasta 100.000 valores, el uso de $m = 2\sqrt{N}$ $q=.5$ (el caso más difícil) indica que este algoritmo tiene un 99.5% de tasa de éxito en la obtención del valor correcto de $x^{(n)}_{[\lfloor{q n}\rfloor]}$. Para una secuencia de a $N=10^{12}$ a los valores, que requeriría un búfer de sólo dos millones de dólares (pero tres o cuatro millones sería una mejor opción). El uso de un criterio de lista doblemente vinculada para el búfer requiere $O(\log(\sqrt{N}))$ = $O(\log(N))$ esfuerzo, mientras que la identificación y eliminación de los max o min se $O(1)$ operaciones. La relativamente caro de inserción, normalmente debe ser hecho sólo $O(\sqrt{N})$ veces. Así, el cómputo de los costes de este algoritmo se $O(N + \sqrt{N} \log(N)) = O(N)$ en tiempo y $O(\sqrt{N})$ en el almacenamiento.
Krzysztof Kowalczyk
Puntos
1995
Creo que whuber sugerencia es genial y me gustaría tratar de que la primera. Sin embargo, si usted encuentra que usted realmente no puede dar cabida a las $O(\sqrt N)$ o de almacenamiento no funciona por algún otro motivo, he aquí una idea para una generalización de la P2. No es tan detallada como lo whuber sugiere - más como una idea de investigación, en lugar de como una solución.
En vez de seguimiento de los cuantiles en $0$, $p/2$, $p$, $(1+p)/2$, y $1$, mientras que el original P2 algoritmo sugiere, usted podría simplemente seguir la pista de más de cuantiles (pero sigue siendo un número constante). Parece que el algoritmo permite que de una manera muy sencilla; todo lo que necesita hacer es calcular la correcta "cubo" para entrantes puntos, y la manera correcta de actualizar los cuantiles (cuadráticamente el uso de números adyacentes).
Dicen seguir la pista de las $25$ puntos. Usted podría tratar de seguimiento de los cuantiles en $0$, $p/12$, $\dotsc$, $p \cdot 11/12$, $p$, $p + (1-p)/12$, $\dotsc$, $p + 11\cdot(1-p)/12$, $1$ (recoger los puntos de forma equidistante entre las $0$$p$, y entre el$p$$1$), o incluso con $22$ Nodos de Chebyshev de la forma$p/2 \cdot (1 + \cos \frac{(2 i - 1)\pi}{22})$$p + (1 - p)/2 \cdot (1 + \cos \frac{(2i-1)\pi}{22})$. Si $p$ está cerca de a $0$ o $1$, usted podría tratar de poner menos puntos en el lado donde hay menos probabilidad de masas y más en el otro lado.
Si usted decide seguir con esto, yo (y posiblemente a otros en este sitio) estaría interesado en saber si funciona...
MattSayar
Puntos
723
Presione et al., Recetas numéricas 8.5.2 "Single-pass estimación de cuantiles arbitraria" p. 435, dar una clase de c ++ IQAgent que actualiza un cdf aproximado por trozos linear.
user3595
Puntos
29
Esto puede ser adaptado de algoritmos que determinan la mediana de un conjunto de datos en línea. Para obtener más información, vea este stackoverflow post - http://stackoverflow.com/questions/1387497/find-median-value-from-a-growing-set
Jesse Rusak
Puntos
33702
Yo los miraba a los cuantiles de regresión. Se puede utilizar para determinar una estimación paramétrica de cualquiera de cuantiles que usted quiere ver. Que hacer ninguna suposición acerca de la normalidad, por lo que se encarga de heterocedasticidad bastante bien y se puede utilizar un rodillo de la ventana de la base. Se trata básicamente de un L1-Norma penalizado de regresión, por lo que no es demasiado numéricamente intensivo y hay una muy completa de R, SAS y SPSS paquetes, además de un par de implementaciones en matlab por ahí. Aquí está el principal y el R paquete de wikis para obtener más información.
Editado:
Retirar las matemáticas de intercambio de la pila de reticulación: Alguien situado a un par de papeles que, esencialmente, exponer la idea muy simple de usar un rodillo de la ventana de estadísticas de orden para la estimación de cuantiles. Literalmente, todo lo que tienes que hacer es ordenar los valores de menor a mayor, seleccione la que cuantil desea, y seleccione el valor más alto dentro de ese cuantil. Usted, evidentemente, puede dar más peso a las observaciones más recientes si usted cree que son más representativas de la corriente real de las condiciones. Probablemente esto da una estimación aproximada, pero es bastante simple de hacer y usted no tiene que ir a través de los movimientos cuantitativos de levantar objetos pesados. Sólo un pensamiento.
