Como calcular com eficiência o estimador Theil-Sen?

8

O estimador de Theil-Sen é interessante para mim, no entanto, quando eu o implemento, acabo com algo que escala como O (n ^ 2). Segundo a wikipedia, ele pode ser calculado exatamente em O (n log (n)). Alguém pode me indicar uma implementação eficiente (python ou mathematica seria melhor, Matlab ou R seria tolerável) ou, de outra forma, explicar em termos simples como as versões eficientes funcionam?

regression robust mdeceglie
fonte

Respostas:

3

Segundo a wikipedia, ele pode ser calculado exatamente em O (n log (n)).

A Wikipedia aponta para nada menos que seis trabalhos detalhando diferentes algoritmos determinísticos ou aleatórios com desempenho , exatamente na seção em que mencionam a existência de tais algoritmos (além de mencionar um ainda mais rápido em determinadas circunstâncias).O(nlog⁡n)

Determinístico:

Cole, Richard; Salowe, Jeffrey S .; Steiger, WL; Szemerédi, Endre (1989), Um algoritmo de tempo ideal para seleção de declives, SIAM Journal on Computing 18 (4): 792–810, doi: 10.1137 / 0218055, MR 1004799.

Katz, Matthew J .; Sharir, Micha (1993), Seleção ótima de declive via expansores, Information Processing Letters 47 (3): 115-122, doi: 10.1016 / 0020-0190 (93) 90234-Z, MR 1237287.

Brönnimann, Hervé; Chazelle, Bernard (1998), Seleção ótima de declive por meio de estacas, Teoria e aplicações da geometria computacional 10 (1): 23–29, doi: 10.1016 / S0925-7721 (97) 00025-4, MR 1614381.

 

Randomizado:

Dillencourt, Michael B .; Mount, David M .; Netanyahu, Nathan S. (1992), Um algoritmo randomizado para seleção de declive, International Journal of Computational Geometry & Applications 2 (1): 1–27, doi: 10.1142 / S0218195992000020, MR 1159839.

Matoušek, Jiří (1991), algoritmo ótimo randomizado para seleção de declive, Information Processing Letters 39 (4): 183–187, doi: 10.1016 / 0020-0190 (91) 90177-J, MR 1130747.

Blunck, Henrik; Vahrenhold, Jan (2006), "Seleção aleatória no declive no local", Simpósio Internacional sobre Algoritmos e Complexidade, Notas de Aula em Ciência da Computação 3998, Berlim: Springer-Verlag, pp. 30–41, doi: 10.1007 / 11758471_6, MR 2263136 .

Qual você queria?

Glen_b -Reinstate Monica
fonte
3
Sim, eu sei como perceber quando são feitas referências. Eu gostaria do que pode ser explicado AQUI em termos relativamente SIMPLES. Alternativamente, o que foi implementado para que se possa usar apenas o código.
mdeceglie
Prefiro um método que o calcule exatamente do que algo que dê uma resposta ligeiramente diferente a cada vez.
mdeceglie
Por que o voto negativo?
COOLSerdash
3
O(nlog⁡(n))
2
italianice - Nenhum dos algoritmos é muito simples; os documentos que os explicam deixam de fora alguns detalhes (como sendo óbvios o suficiente para que um especialista pudesse preencher os detalhes omitidos); tudo isso precisaria ser explicado - não consigo ver nem o mais simples sendo coberto em menos de muitas milhares de palavras (provavelmente dezenas de milhares, mais diagramas). Tanto quanto posso ver, todos envolvem geometria computacional de alguma forma. Os algoritmos aleatórios tendem a ser um pouco mais simples, mas isso não significa muito. Se você realmente precisa disso, sua melhor aposta pode ser procurar uma implementação.
Glen_b -Reinstala Monica