¿Cómo calcular eficientemente el estimador Theil-Sen?

8

El estimador Theil-Sen me interesa, sin embargo, cuando lo implemento yo mismo termino con algo que se escala como O (n ^ 2). Según Wikipedia, se puede calcular exactamente en O (n log (n)). ¿Puede alguien señalarme hacia una implementación eficiente (Python o Mathica sería lo mejor, Matlab o R serían tolerables) o explicar en términos simples cómo funcionan las versiones eficientes?

regression robust mdeceglie
fuente

Respuestas:

3

Según Wikipedia, se puede calcular exactamente en O (n log (n)).

Wikipedia señala no menos de seis documentos que detallan diferentes algoritmos deterministas o aleatorios conO(nlog⁡n) rendimiento, justo en la sección donde mencionan la existencia de tales algoritmos (además de mencionar uno aún más rápido en circunstancias particulares).

Determinista:

Cole, Richard; Salowe, Jeffrey S .; Steiger, WL; Szemerédi, Endre (1989), Un algoritmo de tiempo óptimo para la selección de pendientes, SIAM Journal on Computing 18 (4): 792–810, doi: 10.1137 / 0218055, MR 1004799.

Katz, Matthew J .; Sharir, Micha (1993), Selección óptima de pendientes mediante expansores, Information Processing Letters 47 (3): 115–122, doi: 10.1016 / 0020-0190 (93) 90234-Z, MR 1237287.

Brönnimann, Hervé; Chazelle, Bernard (1998), Selección de pendiente óptima a través de esquejes, Teoría y aplicaciones de la geometría computacional 10 (1): 23–29, doi: 10.1016 / S0925-7721 (97) 00025-4, MR 1614381.

 

Aleatorizado:

Dillencourt, Michael B .; Mount, David M .; Netanyahu, Nathan S. (1992), Un algoritmo aleatorio para la selección de pendientes, International Journal of Computational Geometry & Applications 2 (1): 1–27, doi: 10.1142 / S0218195992000020, MR 1159839.

Matoušek, Jiří (1991), Algoritmo óptimo aleatorio para la selección de pendientes, Information Processing Letters 39 (4): 183–187, doi: 10.1016 / 0020-0190 (91) 90177-J, MR 1130747.

Blunck, Henrik; Vahrenhold, Jan (2006), "Selección de pendiente aleatoria en el lugar", Simposio internacional sobre algoritmos y complejidad, Lecture Notes in Computer Science 3998, Berlín: Springer-Verlag, pp. 30–41, doi: 10.1007 / 11758471_6, MR 2263136 .

Cual querias

Glen_b -Reinstate a Monica
fuente
3
Sí, sé cómo notar cuándo se hacen referencias. Me gustaría el que se puede explicar AQUÍ en términos relativamente SIMPLES. Alternativamente, el que se ha implementado para poder usar el código.
mdeceglie
Prefiero un método que lo calcule exactamente en lugar de algo que dé una respuesta ligeramente diferente cada vez.
mdeceglie
¿Por qué el voto negativo?
COOLSerdash
3
Italiano, confunde el significado de un "algoritmo aleatorio": estos son algoritmos que aleatorizan su entrada para evitar situaciones raras en el peor de los casos. Ellos tienenO(nlog⁡(n)) tiempo de cálculo esperado , pero producen soluciones óptimas exactas, correctas y repetibles . Los algoritmos deterministas que Glen_b cita aquí tienden a ser complicados, mientras que algunos de los algoritmos aleatorios son relativamente simples. El comentario inicial en el último artículo (Henrik Blunck y Jan Vahrenhold) explica esto y proporciona una visión general de varios de los algoritmos.
whuber
2
italianice: ninguno de los algoritmos es muy simple; los documentos que los explican dejan de lado algunos detalles (como lo suficientemente obvio como para que un experto pueda completar los detalles omitidos); todo eso necesitaría ser explicado: no puedo ver ni siquiera el más simple cubierto en menos de muchas, muchas miles de palabras (probablemente decenas de miles, más diagramas). Hasta donde puedo ver, todos implican geometría computacional de alguna manera. Los algoritmos aleatorios tienden a ser algo más simples, pero eso no dice mucho. Si realmente necesita esto, su mejor opción podría ser buscar una implementación.
Glen_b -Reinstalar Monica