Theil-Sen 估计器对我很感兴趣，但是当我自己实现它时，我最终得到的结果是 O(n^2)。根据维基百科，它可以在 O(n log(n)) 中精确计算。有人可以向我指出一个有效的实现方式（python 或mathematica 最好，Matlab 或 R 可以容忍）或者用简单的术语解释有效版本是如何工作的？
如何有效地计算 Theil-Sen 估计量？
机器算法验证
回归
强大的
2022-03-16 09:56:10
1个回答
根据维基百科，它可以在 O(n log(n)) 中精确计算。
维基百科指出不少于六篇性能的不同确定性或随机算法，就在他们提到此类算法存在的部分（以及在特定情况下提到更快的算法）。
确定性：
科尔，理查德；萨洛维，杰弗里 S.；斯泰格，WL；Szemerédi, Endre (1989), 坡度选择的最佳时间算法, SIAM Journal on Computing 18 (4): 792–810, doi:10.1137/0218055, MR 1004799。
卡茨，马修 J.；Sharir, Micha (1993), Optimal slope selection via expanders, Information Processing Letters 47 (3): 115–122, doi:10.1016/0020-0190(93)90234-Z, MR 1237287。
布隆尼曼，埃尔维；Chazelle, Bernard (1998)，通过岩屑优化坡度选择，计算几何理论和应用 10 (1): 23–29, doi:10.1016/S0925-7721(97)00025-4, MR 1614381。
随机：
迪伦考特，迈克尔 B.；芒特，大卫 M.；Netanyahu, Nathan S. (1992), 坡度选择的随机算法, International Journal of Computational Geometry & Applications 2 (1): 1–27, doi:10.1142/S0218195992000020, MR 1159839。
Matoušek, Jiří (1991), 用于斜率选择的随机最优算法，信息处理快报 39 (4): 183–187, doi:10.1016/0020-0190(91)90177-J, MR 1130747。
布伦克，亨里克；Vahrenhold, Jan (2006), “就地随机斜率选择”, 算法和复杂性国际研讨会, 计算机科学讲义 3998, 柏林: Springer-Verlag, pp. 30–41, doi:10.1007/11758471_6, MR 2263136 .
你想要哪个？