|M.Sc Student||Asaf Even-Paz|
|Subject||Knowledge Discovery from Databases (KDD) of Dynamic Spatial|
|Department||Department of Civil and Environmental Engineering||Supervisors||Full Professor Shoshany Maxim|
|Full Professor Bekhor Shlomo|
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.