Time-Series Classificatie doormiddel van shapelets (3)

Zoals te lezen in deel 1 en 2 van onze blog blijken shapelets volgens ons een goede manier te zijn om classificatie op time-series data toe te passen. In deel 2 zijn we dieper ingegaan op de methodes welke je gebruikt om een shapelet classifier te trainen. Het trainen van een classifier blijkt in deel 2 vooral doormiddel van ‘Exhaustive Search’ te gebeuren. In dit laatste deel van onze blog zullen we dieper ingaan op de methodes om dit train proces slimmer en sneller te maken.

Zoals wellicht was op te maken uit de eerdere blog is een shapelet zoekopdracht enumeratief, er zijn altijd N(M-L+1) kandidaten voor een gegeven shapelet lengte L. Om de afstanden te vinden van Ds voor een enkele kandidaat vraagt een scan over de hele time serie. Dit loopt exponentieel op naarmate de timeseries langer wordt. Het is dan wellicht niet erg verbazend dat veel onderzoek wordt verricht naar het versnellen van de trainingsmethoden. Kort gezegd bestaan er drie belangrijke methoden om te versnellen:

Vroege uitsluiting van de afstandscalculaties voor shapelet S en serie Ti.Sinds Ds is een minimum van ml+1 sub sequentie afstand tussen S en Ti, individuele calculaties kunnen worde uitgesloten als ze langer zijn dan de best gevonden tot dan toe. Verdere snelheidswinst kan worden bereikt bij het normaliseren van de sub sequenties tijdens de afstandscalculatie, en bij het opnieuw sorteren van kandidaat s door de hoogste waarde vooraan te zetten. Hieronder is de bijbehorende psuedocode te vinden:

Precalculatie van de afstandswaardes tussen series.

Omdat alle sub sequenties worden vergeleken tot elke andere zit er duplicatie in de calculaties. Bijvoorbeeld: Een sub sequentie start op een gegeven positie a en word vergeleken tot een gegeven sub sequentie op positie b.
Veel van de calculaties eerder gedaan voor het vergelijken van A-1 tot de vergelijking B-1 worden hiervoor gekopieerd. Een methode om geheugen in te ruilen voor snelheid is voor elk timeseries paar (Ti,Tj) cumulatieve optelling , vierkantsoptelling en kruis product van Ti en Tj voor te berekenen. Met deze waardes kunnen afstanden tussen sub sequenties worden berekend in constante tijd. Echter vraagt deze voorberekening vaak meer geheugen dan de machine heeft. Een handige truc om dit op te lossen is om bij het inladen van elke losse serie dit te berekenen. Dit verhoogt helaas wel de overhead in tijd benodigd.

Vroege uitsluiting van een shapelet

Na de calculatie van elke waarde Ds,i wordt een bovengrens gekozen welke het beste aansluit met de meest optimistische toekomstige toepassing. Als de bovengrens lager is dan de best gevonden waarde tot dan toe kunnen de calculaties van Ds worden uitgesloten. Dit heeft een hoge potentie om het proces te versnellen omdat het zwakke shapelets uitsluit. Deze zwakke shapelets uitsluiten komt met een hele kleine overhead voor het berekenen van de beste split en de bovengrens voor elke nieuwe Ds,i. Echter voor problemen met meer dan een klasse kan een correcte bovengrens alleen worden gevonden door enumeratief taken te splitten voor elke mogelijke klasse, dit kan de overhead drastisch laten toenemen.

Hiermee sluiten we onze drieluik over time-series classificatie doormiddel van shapelets af. Natuurlijk is dit nog maar de punt van de ijsberg en hadden we hier makkelijk nog 10 blogs aan toe kunnen voegen. Hopelijk hebben we je interesse kunnen wekken om eens bij ons op kantoor hier verder over te praten, Mogen wij u ontvangen?

Meer artikelen

No code, low code of is er een beter alternatief?

No code, low code of is er een beter alternatief?

Volgens onderzoeksbureau Gartner zijn het grote internationale merken zoals OutSystems, Mendix, Microsoft en Salesforce die leidend zijn op het gebied van low code applicatie platformen. Door effectieve marketing, het geven van uitstekende demonstraties en een...

Nieuw: Open Circle Solutions introduceert de Inner Circle app

Nieuw: Open Circle Solutions introduceert de Inner Circle app

De beste ideeën voor het ontwikkelen van een nieuwe app komen vaak uit eigen uitdagingen. Zo liepen we ruim vier jaar geleden tegen een steeds groter wordend probleem aan: omdat we allemaal bij klanten aan het werk waren, verloren we elkaar als collega’s uit het oog....

Time-Series Classificatie doormiddel van shapelets  (2)

Time-Series Classificatie doormiddel van shapelets (2)

Zoals in deel 1 van deze drieluik te lezen hebben we een uiteenzetting gemaakt hoe complexe timeseries te vertalen zijn naar ‘shapelets’. Een mogelijk probleem wat geschikt zou zijn voor deze aanpak is het verbeteren van de uitleesbetrouwbaarheid van IoT apparaten....

Nieuwsbrief

Meld je nu aan voor Open Circle Stories en krijg een verzameling artikelen, tips, nieuws en verdiepingen in je mailbox.

Pin It on Pinterest

Share This