Theil–Sen estimator

Theil–Sen-estimatorn för en uppsättning provpunkter med extremvärden (svart linje) jämfört med den icke-robusta vanliga minsta kvadratlinjen för samma uppsättning (blå). Den streckade gröna linjen representerar marksanningen från vilken proverna genererades.

I icke-parametrisk statistik är Theil -Sen-estimatorn en metod för att robust anpassa en linje till provpunkter i planet ( enkel linjär regression ) genom att välja medianen för lutningarna för alla linjer genom par av punkter. Den har också kallats Sens lutningsuppskattare , lutningsval , enkelmedianmetoden , Kendalls robusta linjeanpassningsmetod och Kendall–Theil robusta linje . Den är uppkallad efter Henri Theil och Pranab K. Sen , som publicerade artiklar om denna metod 1950 respektive 1968, och efter Maurice Kendall på grund av dess förhållande till Kendall tau rank korrelationskoefficienten .

Denna estimator kan beräknas effektivt och är okänslig för extremvärden . Det kan vara betydligt mer exakt än icke-robust enkel linjär regression (minsta kvadrater) för skeva och heteroskedastiska data, och konkurrerar bra mot minsta kvadrater även för normalfördelade data när det gäller statistisk styrka . Det har kallats "den mest populära icke-parametriska tekniken för att uppskatta en linjär trend".

Definition

Enligt definitionen av Theil (1950) är Theil–Sen-uppskattaren för en uppsättning tvådimensionella punkter $(x i, y i)$ medianen $m$ för sluttningarna $(y j - y i)/(x j - x i)$ bestäms av alla par av provpunkter. Sen (1968) utökade denna definition för att hantera fallet där två datapunkter har samma $x$ -koordinat. I Sens definition tar man medianen för sluttningarna definierade endast från par av punkter som har distinkta $x$ -koordinater.

När väl lutningen $m$ har bestämts kan man bestämma en linje från provpunkterna genom att sätta $y$ - avsnittet $b$ till medianen för värdena $y i - mx i$ . Anpassningslinjen är då linjen $y = mx + b$ med koefficienterna $m$ och $b$ i lutning–skärningsform . Som Sen observerade gör detta val av lutning att Kendall tau-rankkorrelationskoefficienten blir ungefär noll, när den används för att jämföra värdena $x i$ med deras tillhörande residualer $y i - mx i - b$ . Intuitivt antyder detta att hur långt passningslinjen passerar över eller under en datapunkt inte är korrelerad med om den punkten är på vänster eller höger sida av datamängden. Valet av $b$ påverkar inte Kendall-koefficienten, men gör att medianresten blir ungefär noll; det vill säga passningslinjen passerar över och under lika många punkter.

Ett konfidensintervall för lutningsuppskattningen kan bestämmas som intervallet som innehåller de mellersta 95 % av lutningarna av linjer som bestäms av punkterpar och kan uppskattas snabbt genom att sampla punkter av punkter och bestämma 95 %-intervallet för de samplade lutningarna. Enligt simuleringar räcker cirka 600 sampelpar för att fastställa ett korrekt konfidensintervall.

Variationer

En variant av Theil–Sen-estimatorn, den upprepade medianregressionen av Siegel (1982), bestämmer för varje provpunkt $(x i, y i)$ medianen $mi för$ sluttningarna $(y j - y i)/(x j - x i)$ av linjer genom den punkten och bestämmer sedan den övergripande estimatorn som medianen för dessa medianer. Den kan tolerera ett större antal extremvärden än Theil–Sen-skattaren, men kända algoritmer för att beräkna det effektivt är mer komplicerade och mindre praktiska.

En annan variant parar ihop provpunkter efter rangordningen av deras $x$ -koordinater: punkten med den minsta koordinaten paras ihop med den första punkten ovanför mediankoordinaten, den näst minsta punkten paras med nästa punkt ovanför medianen, och så på. Den beräknar sedan medianen för lutningarna på linjerna som bestäms av dessa punktpar, och ökar hastigheten genom att undersöka betydligt färre par än Theil–Sen-uppskattaren.

Variationer av Theil–Sen-estimatorn baserade på viktade medianer har också studerats, baserat på principen att par av prover vars $x$ -koordinater skiljer sig mer mycket är mer benägna att ha en exakt lutning och därför bör få en högre vikt.

För säsongsdata kan det vara lämpligt att jämna ut säsongsvariationer i data genom att endast ta hänsyn till par av provpunkter som båda tillhör samma månad eller samma årstid, och hitta medianen för linjernas lutning bestämt av denna mer restriktiva uppsättning par.

Statistiska egenskaper

Theil–Sen-estimatorn är en opartisk skattare av den sanna lutningen i enkel linjär regression . För många distributioner av svarsfelet har denna estimator hög asymptotisk effektivitet i förhållande till minsta kvadraters estimering. Estimatorer med låg effektivitet kräver mer oberoende observationer för att uppnå samma urvalsvarians av effektiva opartiska skattare.

Theil–Sen-uppskattaren är mer robust än skattaren med minsta kvadrater eftersom den är mycket mindre känslig för extremvärden . Den har en nedbrytningspunkt av

1-{\frac {1}{\sqrt {2}}}\approx 29,3\%,

vilket innebär att den kan tolerera godtycklig korruption av upp till 29,3 % av indatapunkterna utan försämring av dess noggrannhet. Emellertid minskar nedbrytningspunkten för högredimensionella generaliseringar av metoden. En högre nedbrytningspunkt, 50 %, gäller för en annan robust linjeanpassningsalgoritm, Siegels upprepade medianuppskattning .

Theil–Sen-estimatorn är ekvivariant under varje linjär transformation av dess svarsvariabel, vilket betyder att omvandling av data först och sedan anpassa en linje, eller att först anpassa en linje och sedan transformera den på samma sätt, båda ger samma resultat. Det är dock inte ekvivariant under affina transformationer av både prediktorn och svarsvariablerna.

Algoritmer och implementering

Medianlutningen för en uppsättning av $n$ sampelpunkter kan beräknas exakt genom att beräkna alla $O (n 2)$ linjer genom par av punkter, och sedan tillämpa en linjär tidsmedianfyndalgoritm . Alternativt kan det uppskattas genom sampling av poängpar. Detta problem är likvärdigt, under projektiv dualitet , med problemet att hitta korsningspunkten i ett arrangemang av linjer som har median $x$ -koordinaten bland alla sådana korsningspunkter.

Problemet med att utföra lutningsval exakt men mer effektivt än den brute force kvadratiska tidsalgoritmen har studerats omfattande i beräkningsgeometri . Flera olika metoder är kända för att beräkna Theil–Sen-estimatorn exakt i $O (n log n)$ tid, antingen deterministiskt eller med hjälp av randomiserade algoritmer . Siegels upprepade median estimator kan också konstrueras i samma tidsgräns. I beräkningsmodeller där indatakoordinaterna är heltal och där bitvisa operationer på heltal tar konstant tid, kan Theil–Sen-estimatorn konstrueras ännu snabbare, i randomiserad förväntad tid $O( n{\sqrt {\log n}})$ .

En estimator för lutningen med ungefär medianrankning, med samma nedbrytningspunkt som Theil-Sen-estimatorn, kan bibehållas i dataströmsmodellen (där sampelpunkterna bearbetas en efter en av en algoritm som inte har tillräckligt med beständighet lagring för att representera hela datamängden) med hjälp av en algoritm baserad på ε-nets .

I R- statistikpaketet är både Theil–Sen-estimatorn och Siegels upprepade medianestimator tillgängliga via mblm -biblioteket. En gratis fristående Visual Basic- applikation för Theil–Sen-uppskattning, KTRLine , har gjorts tillgänglig av US Geological Survey . Theil–Sen-estimatorn har också implementerats i Python som en del av SciPy- och scikit-learn- biblioteken.

Ansökningar

Theil-Sen-uppskattning har tillämpats på astronomi på grund av dess förmåga att hantera censurerade regressionsmodeller . Inom biofysik föreslår Fernandes & Leblanc (2005) dess användning för fjärranalysapplikationer såsom uppskattning av bladarea från reflektansdata på grund av dess "enkelhet i beräkning, analytiska uppskattningar av konfidensintervall, robusthet mot extremvärden, testbara antaganden om rester och . .. begränsad a priori information angående mätfel". För att mäta säsongsbetonade miljödata som vattenkvalitet , har en säsongsjusterad variant av Theil–Sen-estimatorn föreslagits som att föredra framför minsta kvadratuppskattning på grund av dess höga precision i närvaro av skeva data. Inom datavetenskap har Theil-Sen-metoden använts för att uppskatta trender i mjukvarans åldrande . Inom meteorologi och klimatologi har det använts för att uppskatta de långsiktiga trenderna för vindförekomst och hastighet.

Se även

Regression spädning , för ett annat problem som påverkar uppskattade trendlutningar

Anteckningar

Akritas, Michael G.; Murphy, Susan A. ; LaValley, Michael P. (1995), "Theil-Sen estimator with double censured data and applications to astronomy", Journal of the American Statistical Association , 90 (429): 170–177, doi : 10.1080/01621459.197491 047491 . 2291140 , MR 1325124 .
Bagchi, Amitabha; Chaudhary, Amitabh; Eppstein, David ; Goodrich, Michael T. (2007), "Deterministic sampling and range counting in geometric data streams", ACM Transactions on Algorithms , 3 (2): Art. nr 16, arXiv : cs/0307027 , doi : 10.1145/1240233.1240239 , MR 2335299 , 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, s. 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, s. 30–41, doi : 10.1007/11758471_6 , ISBN 978-3-540-34375-2 , MR 2263136 .
Brönnimann, Hervé; Chazelle, Bernard (1998), "Optimal slope selection via cuttings", Computational Geometry Theory and Applications , 10 (1): 23–29, doi : 10.1016/S0925-7721(97)00025-4 , MR 1614381 .
Chan, Timothy M .; Pătraşcu, Mihai (2010), "Counting inversions, offline ortogonal range counting, and related problems", Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10) (PDF) , s. 161–173 .
Cole, Richard; Salowe, Jeffrey S.; Steiger, WL; Szemerédi, Endre (1989), "An optimal-time algorithm for slope selection", SIAM Journal on Computing , 18 (4): 792–810, doi : 10.1137/0218055 , MR 1004799 .
De Muth, E. James (2006), Basic Statistics and Pharmaceutical Statistical Applications , Biostatistics, vol. 16 (andra upplagan), CRC Press, sid. 577, ISBN 978-0-8493-3799-4 .
Dillencourt, Michael B.; Mount, David M .; Netanyahu, Nathan S. (1992), "A randomized algorithm for slope selection", International Journal of Computational Geometry & Applications , 2 (1): 1–27, doi : 10.1142/S0218195992000020 , MR 1159839 .
Dytham, Calvin (2011), Choosing and Using Statistics: A Biologist's Guide (3:e upplagan), John Wiley and Sons, sid. 230, ISBN 978-1-4051-9839-4 .
El-Shaarawi, Abdel H.; Piegorsch, Walter W. (2001), Encyclopedia of Environmetrics, Volym 1 , John Wiley and Sons, sid. 19, ISBN 978-0-471-89997-6 .
Fernandes, Richard; Leblanc, Sylvain G. (2005), "Parametriska (modifierade minsta kvadrater) och icke-parametriska (Theil–Sen) linjära regressioner för att förutsäga biofysiska parametrar i närvaro av mätfel", Remote Sensing of Environment , 95 ( 3 ) : 303 –316, Bibcode : 2005RSEnv..95..303F , doi : 10.1016/j.rse.2005.01.005 .
Gilbert, Richard O. (1987), "6.5 Sen's Nonparametric Estimator of Slope", Statistical Methods for Environmental Pollution Monitoring , John Wiley and Sons, s. 217–219, ISBN 978-0-471-28878-7 .
Granato, Gregory E. (2006), "Kapitel A7: Kendall–Theil Robust Line (KTRLine—version 1.0)—Ett visuellt grundläggande program för att beräkna och rita robusta icke-parametriska uppskattningar av linjär-regressionskoefficienter mellan två kontinuerliga variabler", Hydrologisk analys och Tolkning , US Geological Survey Techniques and Methods, vol. 4, US Geological Survey .
Hirsch, Robert M .; Slack, James R.; Smith, Richard A. (1982), "Techniques of trend analysis for monthly water quality data", Water Resources Research , 18 (1): 107–121, Bibcode : 1982WRR....18..107H , doi : 10.1029/ WR018i001p00107 .
Jaeckel, Louis A. (1972), "Estimating regression coefficients by minimizing the dispersion of the residuals", Annals of Mathematical Statistics , 43 (5): 1449–1458, doi : 10.1214/aoms/1177692377 3 , MR 3007 , MR 300 .
Katz, Matthew 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 .
Logan, Murray (2010), Biostatistical Design and Analysis Using R: A Practical Guide , ISBN 9781444362473
Massart, DL; Vandeginste, BGM; Buydens, LMC; De Jong, S.; Lewis, PJ; 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, s. 355–356, ISBN 978-0-444-89724-4 .
Matoušek, Jiří (1991), "Randomiserad optimal algoritm för val av lutning", Information Processing Letters , 39 (4): 183–187, doi : 10.1016/0020-0190(91)90177-J , MR 1130747 .
Matoušek, Jiří ; Mount, David M .; Netanyahu, Nathan S. (1998), "Efficient randomized algorithms for the repeated median line estimator", Algorithmica , 20 (2): 136–150, doi : 10.1007/PL00009190 , MR 1484533 , 17 S6CID 9 .
Osborne, Jason W. (2008), Best Practices in Quantitative Methods , Sage Publications, Inc., sid. 273, ISBN 9781412940658 .
Persson, Magnus Vilhelm; Martins, Luiz Felipe (2016), Mastering Python Data Analysis , Packt Publishing, sid. 177, ISBN 9781783553303
Romanić, Djordje; Ćurić, Mladjen; Jovičić, Ilija; Lompar, Miloš (2014), "Långsiktiga trender av 'Koshava'-vinden under perioden 1949–2010", International Journal of Climatology , 35 (2): 288–302, Bibcode : 2015IJCli..35..288R , doi : 10.1002/joc.3981 , S2CID 129402302 .
Rousseeuw, Peter J. ; Leroy, Annick M. (2003), Robust Regression and Outlier Detection , Wiley Series in Probability and Mathematical Statistics, vol. 516, Wiley, sid. 67 , ISBN 978-0-471-48855-2 .
Scholz, Friedrich-Wilhelm (1978), "Weighted median regression estimates", The Annals of Statistics , 6 (3): 603–609, doi : 10.1214/aos/1176344204 , JSTOR 2958563 , MR 446800 .
SciPy community (2015), "scipy.stats.mstats.theilslopes" , SciPy v0.15.1 Referensguide
Sen, Pranab Kumar (1968), "Estimates of the regression coefficient based on Kendall's tau", Journal of the American Statistical Association , 63 ( 324): 1379–1389, doi : 10.2307 / 2285891 , JSTOR 2285891 .
Siegel, Andrew F. (1982), "Robust regression using repeated medians", Biometrika , 69 (1): 242–244, doi : 10.1093/biomet/69.1.242 .
statistics for simple linear regression", Journal of the American Statistical Association , 73 (363): 628–631, doi : 10.1080/01621459.1978.10480067 , J61322 8 , J61322 .
Sokal, Robert R .; Rohlf, F. James (1995), Biometri: The Principles and Practice of Statistics in Biological Research (3:e upplagan), Macmillan, sid. 539, ISBN 978-0-7167-2411-7 .
Theil, H. (1950), "A rank-invariant method of linear and polynomial regressions analysis. I, II, III", Nederl. Akad. Wetensch., Proc. , 53 : 386-392 , 521-525 , 1397-1412 , 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, doi : 10.1109/TDSC.2005.15 , S2CID 15105 .
Vannest, Kimberly J.; Davis, John L.; Parker, Richard I. (2013), Single Case Research in Schools: Practical Guidelines for School-Based Professionals , Routledge, sid. 55, ISBN 9781136173622
Wang, Xueqin; Yu, Qiqing (2005), "Unbiasedness of the Theil–Sen estimator", Journal of Nonparametric Statistics , 17 (6): 685–695, doi : 10.1080 /10485250500039452 , MR 1215C 10ID 6,1250C 9
Wilcox, Rand R. (1998), "En anteckning om Theil–Sen-regressionskalkylatorn när regressorn är slumpmässig och feltermen är heteroskedastisk", Biometrical Journal , 40 (3): 261–268, doi : 10.1002/(SICI) )1521-4036(199807)40:3<261::AID-BIMJ261>3.0.CO;2-V .
Wilcox, Rand R. (2001), "Theil–Sen estimator", Fundamentals of Modern Statistical Methods: Substantially Improving Power and Accuracy , Springer-Verlag, s. 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, s. 423–427, ISBN 978-0-12-751542-7 .