Ändringsdetektering

Årlig volym av Nilen vid Aswan , ett exempel på tidsseriedata som ofta används för att upptäcka förändringar. Prickad linje anger en detekterad ändringspunkt.

I statistisk analys försöker ändringsdetektering eller ändringspunktsdetektering identifiera tidpunkter när sannolikhetsfördelningen för en stokastisk process eller tidsserie ändras . Generellt handlar problemet både om att upptäcka om en förändring har skett eller inte, eller om flera förändringar kan ha skett, och att identifiera tidpunkter för sådana förändringar.

Specifika tillämpningar, som stegdetektering och kantdetektering , kan handla om förändringar i processens medelvärde , varians , korrelation eller spektraltäthet . Mer allmänt ändringsdetektering inkluderar även upptäckt av avvikande beteende: anomalidetektering .

Introduktion

En tidsserie mäter utvecklingen av en eller flera kvantiteter över tiden. Till exempel visar figuren ovan vattennivån i Nilen mellan 1870 och 1970. Förändringspunktsdetektering handlar om att identifiera om och i så fall när seriens beteende förändras avsevärt. I exemplet med Nilen ändras vattenvolymen avsevärt efter att en damm byggts i floden. Viktigt är att avvikande observationer som skiljer sig från det pågående beteendet i tidsserien i allmänhet inte anses vara förändringspunkter så länge som serien återgår till sitt tidigare beteende efteråt.

Matematiskt kan vi beskriva en tidsserie som en ordnad sekvens av observationer $(x_{1},x_{2},\ldots )$ . Vi kan skriva den gemensamma fördelningen av en delmängd $x_{a:b}=(x_{a},x_{a+1} ,\ldots ,x_{b})$ av tidsserien som $p(x_{a:b})$ . Om målet är att avgöra om en förändringspunkt inträffade vid en tidpunkt $\tau$ i en ändlig tidsserie med längden $T$ , så frågar vi verkligen om $p(x_{1:\tau })$ är lika med $p(x_{\tau +1:T})$ . Detta problem kan generaliseras till fallet med mer än en förändringspunkt.

Problemet med ändringspunktsdetektering kan begränsas ytterligare till mer specifika problem. I offline- ändringspunktsdetektering antas det att en sekvens med längden $T$ är tillgänglig och målet är att identifiera om någon ändringspunkt(er) inträffade i serien. Detta är ett exempel på post hoc-analys och närmar sig ofta med hjälp av hypotestestningsmetoder . Däremot online ändringspunktsdetektering om att detektera ändringspunkter i en inkommande dataström.

Algoritmer

Online förändringsdetektering

Genom att använda metoden för sekventiell analys ("online") måste varje förändringstest göra en avvägning mellan dessa vanliga mätvärden:

Falskt larmfrekvens
Felupptäcktsfrekvens
Detektionsfördröjning

I ett Bayes ändringsdetekteringsproblem är en tidigare distribution tillgänglig för ändringstiden.

Online förändringsdetektering görs också med hjälp av streamingalgoritmer .

Offline förändringsdetektering

Basseville (1993, avsnitt 2.6) diskuterar offline -detektering av medelvärde med hypotestestning baserad på Page och Picards arbeten och uppskattning av maximal sannolikhet av förändringstiden, relaterad till tvåfasregression . Andra tillvägagångssätt använder klustring baserat på maximal sannolikhetsuppskattning , ^{[ citat behövs ]} , använder optimering för att sluta sig till antalet och tidpunkterna för förändringar, via spektralanalys eller singulära spektrumanalys.

"Offline"-metoder kan inte användas på strömmande data eftersom de behöver jämföras med statistik för hela tidsserien och kan inte reagera på förändringar i realtid men ger ofta en mer exakt uppskattning av förändringens tid och storlek.

Tillämpningar av förändringsdetektering

Förändringstester används ofta inom tillverkning ( kvalitetskontroll ), intrångsdetektering , spamfiltrering , webbplatsspårning och medicinsk diagnostik.

Språklig förändringsdetektion

Språklig förändringsdetektering hänvisar till förmågan att upptäcka förändringar på ordnivå över flera presentationer av samma mening. Forskare har funnit att mängden semantisk överlappning (dvs. släktskap) mellan det ändrade ordet och det nya ordet påverkar hur lätt en sådan upptäckt görs (Sturt, Sanford, Stewart, & Dawydiak, 2004). Ytterligare forskning har funnit att det kan förbättra upptäckten genom att fokusera sin uppmärksamhet på ordet som kommer att ändras under den första läsningen av den ursprungliga meningen. Detta visades med hjälp av kursiv text för att fokusera uppmärksamheten, varvid ordet som kommer att förändras är kursivt i den ursprungliga meningen (Sanford, Sanford, Molle, & Emmott, 2006), samt att använda klyftkonstruktioner som " Det var trädet som behövde vatten." (Kennette, Wurm, & Van Havermaet, 2010). Dessa förändringsdetekteringsfenomen tycks vara robusta och förekommer även tvärspråkligt när tvåspråkiga läser den ursprungliga meningen på sitt modersmål och den ändrade meningen på sitt andra språk (Kennette, Wurm & Van Havermaet, 2010). Nyligen har forskare upptäckt förändringar på ordnivå i semantik över tid genom beräkningsanalys av tidskroppar (till exempel: ordet " gay" har fått en ny betydelse med tiden ) med hjälp av ändringspunktsdetektion.

Se även

Strukturellt avbrott — Ändring av modellstruktur
Detektionsteori
Hypotestestning
Återkallningsfrekvens
Mottagarens funktionsegenskaper

^ van den Burg, Gerrit JJ; Williams, Christopher KI (26 maj 2020). "En utvärdering av algoritmer för upptäckt av ändringspunkter". arXiv : 2003.06222 [ stat.ML ].
^ Page, ES (juni 1957). "Om problem där en ändring av en parameter inträffar vid en okänd punkt". Biometrika . 44 (1/2): 248–252. doi : 10.1093/biomet/44.1-2.248 . JSTOR 2333258 .
^ Picard, Dominique (1985). "Testa och uppskatta förändringspunkter i tidsserier". Framsteg i tillämpad sannolikhet . 17 (4): 841–867. doi : 10.2307/1427090 . JSTOR 1427090 . S2CID 123026208 .
^ Yao, Yi-Ching (1988-02-01). "Uppskattning av antalet bytespunkter via Schwarz kriterium". Statistik & sannolikhetsbrev . 6 (3): 181–189. doi : 10.1016/0167-7152(88)90118-6 . ISSN 0167-7152 .
^ Ghaderpour, E.; Vujadinovic, T. (2020). "Ändringsdetektering inom fjärravkända satellitbilders tidsserier via spektralanalys" . Fjärravkänning . 12 (23): 4001. doi : 10.3390/rs12234001 .
^ Alanqary, Arwa (2021). "Change Point Detection via Multivariate Singular Spectrum Analysis". Framsteg inom neurala informationsbehandlingssystem . 34 : 23218-23230.
^ Kulkarni Vivek; Rfou Rami; Perozzi Bryan; Skiena Steven (2015). "Statistiskt signifikant upptäckt av språklig förändring" . WWW '15 Proceedings of the 24th International Conference on World Wide Web : 625–635. arXiv : 1411.3315 . doi : 10.1145/2736277.2741627 . ISBN 9781450334693 . S2CID 9298083 .

Vidare läsning

Michèle Basseville; Igor V. Nikiforov (april 1993). Upptäckt av plötsliga förändringar: teori och tillämpning . Prentice-Hall , Englewood Cliffs , NJ ISBN 0-13-126780-9 .
H. Vincent Poor; Olympia Hadjiliadis (2009). Snabbaste upptäckten . Cambridge University Press . ISBN 978-0-521-62104-5 .

[1] van den Burg, Gerrit JJ; Williams, Christopher KI (26 maj 2020). "En utvärdering av algoritmer för upptäckt av ändringspunkter". arXiv : 2003.06222 [ stat.ML ].

[2] Page, ES (juni 1957). "Om problem där en ändring av en parameter inträffar vid en okänd punkt". Biometrika . 44 (1/2): 248–252. doi : 10.1093/biomet/44.1-2.248 . JSTOR 2333258 .

[3] Picard, Dominique (1985). "Testa och uppskatta förändringspunkter i tidsserier". Framsteg i tillämpad sannolikhet . 17 (4): 841–867. doi : 10.2307/1427090 . JSTOR 1427090 . S2CID 123026208 .

[4] Yao, Yi-Ching (1988-02-01). "Uppskattning av antalet bytespunkter via Schwarz kriterium". Statistik & sannolikhetsbrev . 6 (3): 181–189. doi : 10.1016/0167-7152(88)90118-6 . ISSN 0167-7152 .

[5] Ghaderpour, E.; Vujadinovic, T. (2020). "Ändringsdetektering inom fjärravkända satellitbilders tidsserier via spektralanalys" . Fjärravkänning . 12 (23): 4001. doi : 10.3390/rs12234001 .

[6] Alanqary, Arwa (2021). "Change Point Detection via Multivariate Singular Spectrum Analysis". Framsteg inom neurala informationsbehandlingssystem . 34 : 23218-23230.

[7] Kulkarni Vivek; Rfou Rami; Perozzi Bryan; Skiena Steven (2015). "Statistiskt signifikant upptäckt av språklig förändring" . WWW '15 Proceedings of the 24th International Conference on World Wide Web : 625–635. arXiv : 1411.3315 . doi : 10.1145/2736277.2741627 . ISBN 9781450334693 . S2CID 9298083 .