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 m–l+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?