¿Cómo calcular de Rousseeuw y Croux' (1993) estimador de escala de Qn para muestras grandes?

Question

Vamos A Qn = Cqn.{|Xi-Xj|;i < j}_(k) por lo que para una muy breve muestra de como {1,3,6,2,7,5} se puede calcular a partir de la búsqueda de la kth estática orden de los pares de diferencias:

7 6 5 3 2 1

1 6 5 4 2 1

2 5 4 3 1

3 4 3 2

5 2 1

6 1

7

h=[n/2]+1=4

k=h(h-1)/2=8

Por Lo Tanto Qn=Cqn. 2

Obviamente, para muestras grandes diciendo que constan de 80.000 registros tenemos la memoria muy grande. Existe de todos modos para calcular Qn en 1D espacio en lugar de 2D?

Un enlace a la respuesta ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf aunque no puedo entenderlo completamente.

Answer 1

No, $O(n\log(n))$ es la más baja teórico obligado (ver (1)) para la selección de la $k^{th}$ elemento entre todos los $\frac{n(n-1)}{2}$$|x_i - x_j|: 1 \leq i \lt j \leq n$.

Usted puede obtener $O(1)$ espacio, pero sólo por ingenuamente la comprobación de todas las combinaciones de $x_i-x_j$ en el tiempo $O(n^2)$.

La buena noticia es que usted puede utilizar los $\tau$ estimador de escala (véase (2) y (3) para una versión mejorada y algo de tiempo comparaciones), implementado en la función scaleTau2() en la R paquete robustbase. La univariante $\tau$ estimador es una de dos pasos (es decir, re-ponderado) estimador de escala. Tiene 95 por ciento de Gauss de la eficiencia, el 50 por ciento de ruptura de punto, y la complejidad de $O(n)$ tiempo y $O(1)$ espacio (además de que se puede fácilmente ser 'online', a afeitarse la mitad de los costes computacionales en uso repetido, aunque usted tendrá que cavar en el R código para implementar esta opción, es bastante sencillo de hacer).

1. La complejidad de selección y clasificación en X + Y y matrices con columnas ordenadas G. N. Frederickson y D. B. Johnson, de Diario de la Computadora y del Sistema de Ciencias de la Volumen 24, Número 2, Abril De 1982, Páginas 197-208.
2. Yohai, V. y Zamar, R. (1988). Ruptura de alto punto de las estimaciones de la regresión por medio de la minimización de una escala eficiente. Revista de la Asociación Americana de Estadística 83 406-413.
3. Maronna, R. y Zamar, R. (2002). Estimaciones sólidas de ubicación y dispersión de alta dimensiones de los conjuntos de datos. Technometrics 44 307-317

Editar el uso De este

1. El fuego de R (es gratis y se puede descargar desde aquí)

2. instalar el paquete de inflexión

   instalar.paquetes("robustbase")

3. cargar el paquete de inflexión

   biblioteca("robustbase")

4. carga el archivo de datos y ejecutar la función:

   mydatavector<-read.tabla("dirección a mi archivo en formato de texto",header=T)

   scaleTau2(mydatavector)