טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAsaf Even-Paz
SubjectKnowledge Discovery from Databases (KDD) of Dynamic Spatial
Patterns
DepartmentDepartment of Civil and Environmental Engineering
Supervisors Full Professor Shoshany Maxim
Full Professor Bekhor Shlomo


Abstract

Our research aims at finding how to analyze dynamic point patterns by:

1.      Identification of clusters in dynamic point patterns using Data Mining methods

2.      Identification of disturbances to the clusters using linear programming methods

Since dynamic geographic data is scarcely available for public or academic use our research focused on a test-case which is readily available, widely researched and easy to interpret: ant motion. Several data mining algorithms were tested using different input data configurations. The results were compared using a common data mining criterion known as “Silhouette Value” and they showed that a reasonable clustering method is k-means clustering using location input data accompanied by an additional re-clustering of the resulting clusters using directional data.

Next, each cluster was monitored over time using linear programming to “connect” between subsequent time epochs and several tests were conducted to determine which distance metric and input data configuration is the best - Mahalanobis distance measure with both location and directional data as input. Additionally, the algorithm "tracked down” each cluster's evolution through time and also monitored the cluster's spatial parameters over time, which eventually signified the change in the objects movement.

            The proposed algorithm was tested on real-life data composed from video sequences of pedestrians crossing a street and showed satisfactory results. The application which we have developed can help many experts in the fields of transportation, pedestrian monitoring and modeling, crowd management and evacuation planning.