Theil–Sen estimator
In
Theil-Sen regression has several advantages over
Definition
As defined by Theil (1950), the Theil–Sen estimator of a set of two-dimensional points (xi, yi) is the median m of the slopes (yj − yi)/(xj − xi) determined by all pairs of sample points. Sen (1968) extended this definition to handle the case in which two data points have the same x coordinate. In Sen's definition, one takes the median of the slopes defined only from pairs of points having distinct x coordinates.[8]
Once the slope m has been determined, one may determine a line from the sample points by setting the
A confidence interval for the slope estimate may be determined as the interval containing the middle 95% of the slopes of lines determined by pairs of points[13] and may be estimated quickly by sampling pairs of points and determining the 95% interval of the sampled slopes. According to simulations, approximately 600 sample pairs are sufficient to determine an accurate confidence interval.[11]
Variations
A variation of the Theil–Sen estimator, the repeated median regression of Siegel (1982), determines for each sample point (xi, yi), the median mi of the slopes (yj − yi)/(xj − xi) of lines through that point, and then determines the overall estimator as the median of these medians. It can tolerate a greater number of outliers than the Theil–Sen estimator, but known algorithms for computing it efficiently are more complicated and less practical.[14]
A different variant pairs up sample points by the rank of their x-coordinates: the point with the smallest coordinate is paired with the first point above the median coordinate, the second-smallest point is paired with the next point above the median, and so on. It then computes the median of the slopes of the lines determined by these pairs of points, gaining speed by examining significantly fewer pairs than the Theil–Sen estimator.[15]
Variations of the Theil–Sen estimator based on weighted medians have also been studied, based on the principle that pairs of samples whose x-coordinates differ more greatly are more likely to have an accurate slope and therefore should receive a higher weight.[16]
For seasonal data, it may be appropriate to smooth out seasonal variations in the data by considering only pairs of sample points that both belong to the same month or the same season of the year, and finding the median of the slopes of the lines determined by this more restrictive set of pairs.[17]
Statistical properties
The Theil–Sen estimator is an
The Theil–Sen estimator is more
meaning that it can tolerate arbitrary corruption of up to 29.3% of the input data-points without degradation of its accuracy.[12] However, the breakdown point decreases for higher-dimensional generalizations of the method.[20] A higher breakdown point, 50%, holds for a different robust line-fitting algorithm, the repeated median estimator of Siegel.[12]
The Theil–Sen estimator is
Algorithms
The median slope of a set of n sample points may be computed exactly by computing all O(n2) lines through pairs of points, and then applying a linear time
The problem of performing slope selection exactly but more efficiently than the brute force quadratic time algorithm has been extensively studied in computational geometry. Several different methods are known for computing the Theil–Sen estimator exactly in O(n log n) time, either deterministically[3] or using randomized algorithms.[4] Siegel's repeated median estimator can also be constructed in the same time bound.[23] In models of computation in which the input coordinates are integers and in which bitwise operations on integers take constant time, the Theil–Sen estimator can be constructed even more quickly, in randomized expected time .[24]
An estimator for the slope with approximately median rank, having the same breakdown point as the Theil–Sen estimator, may be maintained in the data stream model (in which the sample points are processed one by one by an algorithm that does not have enough persistent storage to represent the entire data set) using an algorithm based on ε-nets.[25]
Implementations
In the R statistics package, both the Theil–Sen estimator and Siegel's repeated median estimator are available through the mblm
library.[26]
A free standalone
Applications
Theil–Sen estimation has been applied to astronomy due to its ability to handle censored regression models.[29] In biophysics, Fernandes & Leblanc (2005) suggest its use for remote sensing applications such as the estimation of leaf area from reflectance data due to its "simplicity in computation, analytical estimates of confidence intervals, robustness to outliers, testable assumptions regarding residuals and ... limited a priori information regarding measurement errors".[30] For measuring seasonal environmental data such as water quality, a seasonally adjusted variant of the Theil–Sen estimator has been proposed as preferable to least squares estimation due to its high precision in the presence of skewed data.[17] In computer science, the Theil–Sen method has been used to estimate trends in software aging.[31] In meteorology and climatology, it has been used to estimate the long-term trends of wind occurrence and speed.[32]
See also
- Median-median method
- Regression dilution, for another problem affecting estimated trend slopes
Notes
- ^ Gilbert (1987).
- ^ a b El-Shaarawi & Piegorsch (2001).
- ^ a b Cole et al. (1989); Katz & Sharir (1993); Brönnimann & Chazelle (1998).
- ^ a b Dillencourt, Mount & Netanyahu (1992); Matoušek (1991); Blunck & Vahrenhold (2006).
- ^ Massart et al. (1997)
- ^ Sokal & Rohlf (1995); Dytham (2011).
- ^ Granato (2006)
- ^ a b Theil (1950); Sen (1968)
- ^ a b Sen (1968); Osborne (2008).
- ^ Helsel, Dennis R.; Hirsch, Robert M.; Ryberg, Karen R.; Archfield, Stacey A.; Gilroy, Edward J. (2020). Statistical methods in water resources. Techniques and Methods. Reston, VA: U.S. Geological Survey. p. 484. Retrieved 2020-05-22.
- ^ a b Wilcox (2001).
- ^ a b c Rousseeuw & Leroy (2003), pp. 67, 164.
- with replacement; this means that the set of pairs used in this calculation includes pairs in which both points are the same as each other. These pairs are always outside the confidence interval, because they do not determine a well-defined slope value, but using them as part of the calculation causes the confidence interval to be wider than it would be without them.
- ^ Logan (2010), Section 8.2.7 Robust regression; Matoušek, Mount & Netanyahu (1998)
- ^ De Muth (2006).
- ^ Jaeckel (1972); Scholz (1978); Sievers (1978); Birkes & Dodge (1993).
- ^ a b Hirsch, Slack & Smith (1982).
- ^ Sen (1968), Theorem 5.1, p. 1384; Wang & Yu (2005).
- ^ Sen (1968), Section 6; Wilcox (1998).
- ^ a b Wilcox (2005).
- ^ Sen (1968), p. 1383.
- ^ Cole et al. (1989).
- ^ Matoušek, Mount & Netanyahu (1998).
- ^ Chan & Pătraşcu (2010).
- ^ Bagchi et al. (2007).
- ^ Logan (2010), p. 237; Vannest, Davis & Parker (2013)
- ^ Vannest, Davis & Parker (2013); Granato (2006)
- ^ SciPy community (2015); Persson & Martins (2016)
- ^ Akritas, Murphy & LaValley (1995).
- ^ Fernandes & Leblanc (2005).
- ^ Vaidyanathan & Trivedi (2005).
- ^ Romanić et al. (2014).
References
- Akritas, Michael G.; MR 1325124.
- Bagchi, Amitabha; Chaudhary, Amitabh; S2CID 123315817.
- Birkes, David; Dodge, Yadolah (1993), "6.3 Estimating the Regression Line", Alternative Methods of Regression, Wiley Series in Probability and Statistics, vol. 282, Wiley-Interscience, pp. 113–118, ISBN 978-0-471-56881-0.
- Blunck, Henrik; Vahrenhold, Jan (2006), "In-place randomized slope selection", International Symposium on Algorithms and Complexity, Lecture Notes in Computer Science, vol. 3998, Berlin: Springer-Verlag, pp. 30–41, MR 2263136.
- Brönnimann, Hervé; MR 1614381.
- Chan, Timothy M.; Pătraşcu, Mihai (2010), "Counting inversions, offline orthogonal range counting, and related problems", Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10) (PDF), pp. 161–173.
- Cole, Richard; Salowe, Jeffrey S.; Steiger, W. L.; MR 1004799.
- De Muth, E. James (2006), Basic Statistics and Pharmaceutical Statistical Applications, Biostatistics, vol. 16 (2nd ed.), CRC Press, p. 577, ISBN 978-0-8493-3799-4.
- Dillencourt, Michael B.; MR 1159839.
- Dytham, Calvin (2011), Choosing and Using Statistics: A Biologist's Guide (3rd ed.), John Wiley and Sons, p. 230, ISBN 978-1-4051-9839-4.
- El-Shaarawi, Abdel H.; Piegorsch, Walter W. (2001), Encyclopedia of Environmetrics, Volume 1, John Wiley and Sons, p. 19, ISBN 978-0-471-89997-6.
- Fernandes, Richard; Leblanc, Sylvain G. (2005), "Parametric (modified least squares) and non-parametric (Theil–Sen) linear regressions for predicting biophysical parameters in the presence of measurement errors", Remote Sensing of Environment, 95 (3): 303–316, .
- Gilbert, Richard O. (1987), "6.5 Sen's Nonparametric Estimator of Slope", Statistical Methods for Environmental Pollution Monitoring, John Wiley and Sons, pp. 217–219, ISBN 978-0-471-28878-7.
- Granato, Gregory E. (2006), "Chapter A7: Kendall–Theil Robust Line (KTRLine—version 1.0)—A visual basic program for calculating and graphing robust nonparametric estimates of linear-regression coefficients between two continuous variables", Hydrological Analysis and Interpretation, U.S. Geological Survey Techniques and Methods, vol. 4, U.S. Geological Survey.
- .
- Jaeckel, Louis A. (1972), "Estimating regression coefficients by minimizing the dispersion of the residuals", Annals of Mathematical Statistics, 43 (5): 1449–1458, MR 0348930.
- Katz, Matthew J.; MR 1237287.
- Logan, Murray (2010), Biostatistical Design and Analysis Using R: A Practical Guide, John Wiley & Sons, ISBN 9781444362473
- Massart, D. L.; Vandeginste, B. G. M.; Buydens, L. M. C.; De Jong, S.; Lewi, P. J.; Smeyers-Verbeke, J. (1997), "12.1.5.1 Single median method", Handbook of Chemometrics and Qualimetrics: Part A, Data Handling in Science and Technology, vol. 20A, Elsevier, pp. 355–356, ISBN 978-0-444-89724-4.
- MR 1130747.
- S2CID 17362967.
- Osborne, Jason W. (2008), Best Practices in Quantitative Methods, Sage Publications, Inc., p. 273, ISBN 9781412940658.
- Persson, Magnus Vilhelm; Martins, Luiz Felipe (2016), Mastering Python Data Analysis, Packt Publishing, p. 177, ISBN 9781783553303
- Romanić, Djordje; Ćurić, Mladjen; Jovičić, Ilija; Lompar, Miloš (2014), "Long-term trends of the 'Koshava' wind during the period 1949–2010", International Journal of Climatology, 35 (2): 288–302, S2CID 129402302.
- ISBN 978-0-471-48855-2.
- Scholz, Friedrich-Wilhelm (1978), "Weighted median regression estimates", The Annals of Statistics, 6 (3): 603–609, MR 0468054.
- SciPy community (2015), "scipy.stats.mstats.theilslopes", SciPy v0.15.1 Reference Guide
- MR 0258201.
- Siegel, Andrew F. (1982), "Robust regression using repeated medians", Biometrika, 69 (1): 242–244, .
- Sievers, Gerald L. (1978), "Weighted rank statistics for simple linear regression", Journal of the American Statistical Association, 73 (363): 628–631, JSTOR 2286613.
- ISBN 978-0-7167-2411-7.
- MR 0036489.
- Vaidyanathan, Kalyanaraman; Trivedi, Kishor S. (2005), "A Comprehensive Model for Software Rejuvenation", IEEE Transactions on Dependable and Secure Computing, 2 (2): 124–137, S2CID 15105513.
- Vannest, Kimberly J.; Davis, John L.; Parker, Richard I. (2013), Single Case Research in Schools: Practical Guidelines for School-Based Professionals, Routledge, p. 55, ISBN 9781136173622
- Wang, Xueqin; Yu, Qiqing (2005), "Unbiasedness of the Theil–Sen estimator", Journal of Nonparametric Statistics, 17 (6): 685–695, S2CID 121061001.
- Wilcox, Rand R. (1998), "A note on the Theil–Sen regression estimator when the regressor Is random and the error term Is heteroscedastic", Biometrical Journal, 40 (3): 261–268, .
- Wilcox, Rand R. (2001), "Theil–Sen estimator", Fundamentals of Modern Statistical Methods: Substantially Improving Power and Accuracy, Springer-Verlag, pp. 207–210, ISBN 978-0-387-95157-7.
- Wilcox, Rand R. (2005), "10.2 Theil–Sen Estimator", Introduction to Robust Estimation and Hypothesis Testing, Academic Press, pp. 423–427, ISBN 978-0-12-751542-7.