Comment calculer efficacement l'estimateur de Theil-Sen?

8

L'estimateur de Theil-Sen m'intéresse, mais lorsque je l'implémente moi-même, je me retrouve avec quelque chose qui évolue comme O (n ^ 2). Selon wikipedia, il peut être calculé exactement en O (n log (n)). Quelqu'un peut-il m'orienter vers une implémentation efficace (python ou mathématique serait préférable, Matlab ou R serait tolérable) ou expliquer autrement en termes simples comment fonctionnent les versions efficaces?

regression robust mdeceglie
la source

Réponses:

3

Selon wikipedia, il peut être calculé exactement en O (n log (n)).

Wikipedia pointe pas moins de six articles détaillant différents algorithmes déterministes ou randomisés avec des performances , juste dans la section où ils mentionnent l'existence de tels algorithmes (ainsi que mentionner un encore plus rapide dans des circonstances particulières).O(nlog⁡n)

Déterministe:

Cole, Richard; Salowe, Jeffrey S .; Steiger, WL; Szemerédi, Endre (1989), An optimal-time algorithm for slection selection, SIAM Journal on Computing 18 (4): 792–810, doi: 10.1137 / 0218055, MR 1004799.

Katz, Matthew J .; Sharir, Micha (1993), Optimal pente selection via expanders, Information Processing Letters 47 (3): 115-122, doi: 10.1016 / 0020-0190 (93) 90234-Z, MR 1237287.

Brönnimann, Hervé; Chazelle, Bernard (1998), Sélection optimale des pentes par déblais, Théorie et applications de la géométrie numérique 10 (1): 23-29, doi: 10.1016 / S0925-7721 (97) 00025-4, MR 1614381.

 

Randomisé:

Dillencourt, Michael B .; Mount, David M .; Netanyahu, Nathan S. (1992), A randomized algorithm for slection selection, International Journal of Computational Geometry & Applications 2 (1): 1–27, doi: 10.1142 / S0218195992000020, MR 1159839.

Matoušek, Jiří (1991), Algorithme optimal randomisé pour la sélection des pentes, Information Processing Letters 39 (4): 183–187, doi: 10.1016 / 0020-0190 (91) 90177-J, MR 1130747.

Blunck, Henrik; Vahrenhold, Jan (2006), "In-place randomized pente selection", International Symposium on Algorithms and Complexity, Lecture Notes in Computer Science 3998, Berlin: Springer-Verlag, pp. 30–41, doi: 10.1007 / 11758471_6, MR 2263136 .

Que vouliez-vous?

Glen_b -Reinstate Monica
la source
3
Oui, je sais comment remarquer les références. J'aimerais celui qui peut être expliqué ICI en termes relativement simples. Alternativement celui qui a été implémenté pour que l'on puisse simplement utiliser le code.
mdeceglie
Je préfère une méthode qui la calcule exactement plutôt que quelque chose qui donne une réponse légèrement différente à chaque fois.
mdeceglie
Pourquoi le downvote?
COOLSerdash
3
Italien, vous vous méprenez sur le sens d'un "algorithme randomisé": ce sont des algorithmes qui randomisent leur entrée afin d'éviter les rares situations les plus défavorables. Ils ontO(nlog⁡(n)) temps de calcul prévu - mais ils produisent des solutions optimales exactes, correctes et reproductibles . Les algorithmes déterministes que Glen_b cite ici ont tendance à être compliqués, alors que certains des algorithmes randomisés sont relativement simples. Le commentaire initial du dernier article (Henrik Blunck et Jan Vahrenhold) explique cela et donne un aperçu de plusieurs des algorithmes.
whuber
2
italianice - Aucun des algorithmes n'est très simple; les documents les expliquant omettent plusieurs détails (comme étant suffisamment évidents pour qu'un expert puisse remplir les détails omis); tout cela devrait être expliqué - je ne vois même pas le plus simple être couvert en moins de plusieurs milliers de mots (probablement des dizaines de milliers, plus des diagrammes). Pour autant que je puisse voir, tous impliquent la géométrie de calcul d'une manière ou d'une autre. Les algorithmes randomisés ont tendance à être un peu plus simples, mais cela ne veut pas dire grand-chose. Si vous en avez vraiment besoin, votre meilleur pari pourrait être de rechercher une implémentation.
Glen_b -Reinstate Monica