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

IT-professionals ontmoeten elkaar bij Kwartaaldag OCS

IT-professionals ontmoeten elkaar bij Kwartaaldag OCS

Op donderdag 14 oktober 2021 organiseerde Open Circle Solutions voor het eerst in lange tijd weer een Kwartaaldag. Rob Cüsters, Project Manager bij Open Circle Solutions, vertelt ons in twee blogartikelen over deze bijzondere dag.De geschiedenis van de Kwartaaldagen...

Veiligheid en kwetsbaarheden in de cloud – deel 2

Veiligheid en kwetsbaarheden in de cloud – deel 2

Wij vroegen onze collega en cloudexpert Tommy Menheere ons meer te vertellen over veiligheid en de belangrijkste kwetsbaarheden in de cloud. In het eerste deel van deze blogserie vertelde hij ons welke aspecten je in de gaten moet houden om veilig in de cloud te...

Presenteren van ingewikkelde technische materie: dat kun je leren

Presenteren van ingewikkelde technische materie: dat kun je leren

OCS vindt het belangrijk dat medewerkers zich blijven ontwikkelen. Niet alleen onze developers, maar ook onze projectmanagers. Daarom volgden een aantal van hen de driedaagse training Influencing with Visuals. Roel van Rijn, IT Project Manager bij OCS, vertelt waarom...

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