Analyseren en ontwikkelen van algoritmen voor tijdgebonden gegevens
Jules Wulms, promovendus in de onderzoeksgroep Applied Geometric Algorithms van de faculteit Mathematics and Computer Science, heeft een nieuw theoretisch kader ontwikkeld voor de analyse van algoritmen voor tijdgebonden gegevens.
Tijdgebonden gegevens spelen een grote rol in ons dagelijks leven. De aandelenbeurs, weersverwachtingen en verkeersinformatie zijn allemaal gebaseerd op gegevens die voortdurend veranderen. Om deze gegevens effectief te kunnen gebruiken, moeten ze nauwkeuring geanalyseerd worden om zo inzicht te krijgen in onderliggende patronen en processen. Vervolgens kunnen deze inzichten gebruikt worden om goed onderbouwde voorspellingen en beslissingen te nemen. In dit hele proces worden algoritmes gebruikt, zowel voor de analyse van de beschikbare tijdsgebonden gegevens, als voor het berekenen van voorspellingen en visualisaties die helpen bij het nemen van datagestuurde beslissingen.
Om effectief gebruik te kunnen maken van een algoritme voor het analyseren en visualiseren van tijdgebonden gegevens is het belangrijk dat bepaalde eigenschappen van de data behouden blijven, zoals de hoeveelheid verandering in de tijd. Tijdgebonden gegevens veranderen meestal continu, zonder veel grote en/of plotselinge wijzigingen. Om recht te doen aan deze continuïteit moet een algoritme ervoor zorgen dat kleine wijzigingen in de invoerdata leiden tot kleine wijzigingen in de output. Algoritmen die deze eigenschap hebben, noemen we stabiel. De stabiliteit van een algoritme kan als maatstaf dienen voor hoe goed dat algoritme de continue veranderingen in de gegevens kan behouden.
Raamwerk
Het analyseren van de stabiliteit van een algoritme is niet eenvoudig, aangezien stabiliteit op veel verschillende manieren kan worden gedefinieerd. In dit onderzoek hebben we een raamwerk van definities ontwikkeld dat het mogelijk maakt stabiliteit op verschillende manieren te meten. Voor sommige algoritmen zal de output niet continu veranderen, maar we kunnen wel het aantal discontinuïteiten meten en deze proberen te verminderen om zo de stabiliteit te verbeteren.
Aan de andere kant wordt stabiliteit anders gemeten wanneer de output continu is, maar we moeten wel letten op de snelheid waarmee veranderingen plaatsvinden. Als we de hoeveelheid toegestane wijzigingen in een korte tijdsspanne beperken, komen we tot een definitie die heel dicht bij de bovenstaande intuïtieve definitie ligt. Het wordt dan echter ook moeilijker (of soms zelfs aantoonbaar onmogelijk) om stabiliteit te bereiken. De andere definities van stabiliteit versoepelen de beperkingen, zodat we in die gevallen toch inzicht kunnen krijgen in de stabiliteit van een algoritme.
Het stabiliteitskader dient als hulpmiddel bij de theoretische analyse van het algoritme voor tijdgebonden gegevens. Het wordt toegepast op verschillende problemen binnen de rekenkundige meetkunde om zo tot nieuwe theoretische resultaten en inzichten te komen in de stabiliteit van deze geometrische problemen.
Vissen
Naast deze theoretische resultaten zijn we ook geïnteresseerd in het verbeteren van de stabiliteit van technieken voor praktische toepassingen die profiteren van stabiele algoritmen. In dit onderzoek hebben we nieuwe algoritmes ontwikkeld voor het automatisch genereren van overzichtsvisualisaties voor bewegingsgegevens (zie figuur).
Een manier om de beweging van dieren, in dit geval vissen, te visualiseren is door een overzicht te maken. Een expert kan zo’n overzicht gebruiken om de meest opvallende momenten in tijd te identificeren voor verdere studie.. Het overzicht sorteert de vissen op ieder moment en plaatst de rangschikkingen verticaal op een tijdlijn. Elke vis wordt weergegeven door een pixel die gekleurd wordt naar een kenmerk van die vis, zoals de zwemhoek of de snelheid. Voor de uiteindelijke rangschikking is het belangrijk dat vissen die dicht bij elkaar zwemmen, ook dicht bij elkaar in de rangschikking staan omdat ze vergelijkbare kenmerken hebben.
Echter, het is heel belangrijk dat de volgorde van de rangschikking vergelijkbaar is, anders is het moeilijk om de veranderingen van de vissen in de loop van de tijd te volgen. We hebben nu algoritmen ontwikkeld die minimaal gelijk of zelfs beter zijn dan de bestaande technieken om vissen weer te geven, maar die de stabiliteit van de bestaande technieken sterk verbeteren.
Meer info: Jules J.H.M. Wulms, Stability of geometric algorithms (pdf). Begeleiders: Wouter Meulemans, TU/e, Bettina Speckmann, TU/e, Kevin Verbeek, TU/e. Andere belangrijke betrokken partijen: eScience Center.