Litteraturstudie och utvärdering av verktyg för datautvinning från rörelsebanedata

With the development of technologies such as Global Navigation Satellite Systems (GNSS), mobile computing, and Information and Communication Technology (ICT) the procedure of sampling positional data has lately been significantly simplified. This enables the aggregation of large amounts of moving objects data (i.e. trajectories) containing potential information about the moving objects. Within Knowledge Discovery in Databases (KDD), automated processes for realization of this information, called trajectory data mining, have been implemented. The objectives of this study is to examine 1) how trajectory data mining tasks are defined at an abstract level, 2) what type of information it is possible to extract from trajectory data, 3) what solutions trajectory data mining tools implement for different tasks, 4) how tools uses visualization, and 5) what the limiting aspects of input data are how those limitations are treated. The topic, trajectory data mining, is examined in a literature review, in which a large number of academic papers found trough googling were screened to find relevant information given the above stated objectives. The literature research found that there are several challenges along the process arriving at profitable knowledge about moving objects. For example, the discrete modelling of movements as polylines is associated with an inherent uncertainty since the location between two sampled positions is unknown. To reduce this uncertainty and prepare raw data for mining, data often needs to be processed in some way. The nature of pre-processing depends on sampling rate and accuracy properties of raw in-data as well as the requirements formulated by the specific mining method. Also a major challenge is to define relevant knowledge and effective methods for extracting this from the data. Furthermore are conveying results from mining to users an important function. Presenting results in an informative way, both at the level of individual trajectories and sets of trajectories, is a vital but far from trivial task, for which visualization is an effective approach. Abstractly defined instructions for data mining are formally denoted as tasks. There are four main categories of mining tasks: 1) managing uncertainty, 2) extrapolation, 3) anomaly detection, and 4) pattern detection. The recitation of tasks within this study provides a basis for an assessment of tools used for the execution of these tasks. To arrive at profitable results the dimensions of comparison are selected with the intention to cover the essential parts of the knowledge discovery process. The measures to appraise this are chosen to make results correctly reflect the 1) sophistication, 2) user friendliness, and 3) flexibility of tools. The focus within this thesis is freely available tools, for which the range is proven to be very small and fragmented. The selection of tools found and reported on are: MoveMine 2.0, MinUS, GeT_Move and M-Atlas. The tools are reviewed entirely through utilizing documentation of the tools. The performance of tools is proved to vary along all dimensional measures except visualization and graphical user interface which all tools provide. Overall the systems preform well considering user-friendliness, somewhat good considering sophistication and poorly considering flexibility. However, since the range of tasks, which tools intend to solve, overall is varying it might not be appropriate to compare the tools in term of better or worse. This thesis further provides some theoretical insights for users regarding requirements on their knowledge, both concerning the technical aspects of tools and about the nature of the moving objects. Furthermore is the future of trajectory data mining in form of constraints on information extraction as well as requirements for development of tools discussed, where a more robust open source solution is emphasised. Finally, this thesis can altogether be regarded to provide material for guidance in what trajectory mining tools to use depending on application. Work to complement this thesis through comparing the actual performance of tools, when using them, is desirable.I och med utvecklingen av tekniker så som Global Navigation Satellite systems (GNSS), mobile computing och Information and Communication Technology (ICT) har tillvägagångsätt för insamling av positionsdata drastiskt förenklats. Denna utveckling har möjliggjort för insamlandet av stora mängder data från rörliga objekt (i.e. trajecotries)(sv: rörelsebanor), innehållande potentiell information om dessa rörliga objekt. Inom Knowledge Discovery in Databases (KDD)(sv: kunskapsanskaffning i databaser) tillämpas automatiserade processer för att realisera sådan information, som kallas trajectory data mining (sv: utvinning från rörelsebanedata). Denna studie ämnar undersöka 1) hur trajectory data mining tasks (sv: utvinning från rörelsebanedata uppgifter) är definierade på en abstrakt nivå, 2) vilken typ av information som är möjlig att utvinna ur rörelsebanedata, 3) vilka lösningar trajectory data ming tools (sv: verktyg för datautvinning från rörelsebanedata) implementerar för olika uppgifter, 4) hur verktyg använder visualisering, och 5) vilka de begränsande aspekterna av input-data är och hur dessa begränsningar hanteras. Ämnet utvinning från rörelsebanedata undersöks genom en litteraturgranskning, i vilken ett stort antal och akademiska rapporter hittade genom googling granskas för att finna relevant information givet de ovan nämnda frågeställningarna. Litteraturgranskningen visade att processen som leder upp till en användbar kunskap om rörliga objekt innehåller dock flera utmaningar. Till exempel är modelleringen av rörelser som polygontåg associerad med en inbyggd osäkerhet eftersom positionen för objekt mellan två inmätningar är okänd. För att reducera denna osäkerhet och förbereda rådata för extraktion måste ofta datan processeras på något sätt. Karaktären av förprocessering avgörs av insamlingsfrekvens och exakthetsegenskaper hos rå indata tillsammans med de krav som ställs av de specifika datautvinningsmetoderna. En betydande utmaning är också att definiera relevant kunskap och effektiva metoder för att utvinna denna från data. Vidare är förmedlandet av resultat från utvinnande till användare en viktig funktion. Att presentera resultat på ett informativt sätt, både på en nivå av enskilda rörelsebanor men och grupper av rörelsebanor är en vital men långt ifrån trivial uppgift, för vilken visualisering är ett effektivt tillvägagångsätt. Abstrakt definierade instruktioner för dataextraktion är formellt betecknade som uppgifter. Det finns fyra huvudkategorier av uppgifter: 1) hantering av osäkerhet, 2) extrapolation, 3) anomalidetektion, and 4) mönsterdetektion. Sammanfattningen av uppgifter som ges i denna rapport utgör ett fundament för en utvärdering av verktyg, vilka används för utförandet av uppgifter. För att landa i ett givande resultat har jämförelsegrunderna för verktygen valts med intentionen att täcka de viktigaste delarna av processen för att förvärva kunskap. Måtten för att utvärdera detta valdes för att reflektera 1) sofistikering, 2) användarvänlighet, och 3) flexibiliteten hos verktygen. Fokuset inom denna studie har varit verktyg som är gratis tillgängliga, för vilka utbudet har visat sig vara litet och fragmenterat. Selektionen av verktyg som hittats och utvärderats var: MoveMine 2.0, MinUS, GeT_Move and M-Atlas. Verktygen utvärderades helt och hållet baserat på tillgänglig dokumentation av verktygen. Prestationen av verktygen visade sig variera längs alla jämförelsegrunder utom visualisering och grafiskt gränssnitt som alla verktyg tillhandahöll. Överlag presterade systemen väl gällande användarvänlighet, någorlunda bra gällande sofistikering och dåligt gällande flexibilitet. Hursomhelst, eftersom uppgifterna som verktygen avser att lösa varierar är det inte relevant att värdera dem mot varandra gällande denna aspekt. Detta arbete tillhandahåller vidare några teoretiska insikter för användare gällande krav som ställs på deras kunskap, både gällande de tekniska aspekterna av verktygen och rörliga objekts beskaffenhet. Vidare diskuteras framtiden för utvinning från rörelsebanedata i form av begränsningar på informationsutvinning och krav för utvecklingen av verktyg, där en mer robust open source lösning betonas. Sammantaget kan detta arbete anses tillhandahålla material för vägledning i vad för verktyg för datautvinning från rörelsebanedata som kan användas beroende på användningsområde. Arbete för att komplettera denna rapport genom utvärdering av verktygens prestation utifrån användning av dem är önskvärt.