Efficiently detecting clusters of mobile objects in the presence of dense noise
James Rosswog, Kanad Ghose · 2010
We address the problem of detecting and tracking clusters of moving objects in very noisy environments. Monitoring a crowded football stadium for small groups of individuals acting suspiciously is an example of one such environment. In this scenario the vast majority of individuals are not part of suspicious groups and are considered noise. Existing spatio-temporal clustering algorithms are either incapable of detecting small clusters in extreme noise, or have high computation and storage requirements that prohibit their use in real-time alerting systems. We propose a technique called Dynamic Density Based Clustering (DDBC) that utilizes the relational history of the moving objects to increase the accuracy of the clustering algorithm. The incorporation of this information into the clustering algorithm is done efficiently and implicitly by using a relationship graph. The relationship graph incrementally estimates the strength of the relationships between moving objects. A modified DBSCAN algorithm is then used to find clusters of highly related objects from the relationship graph. We evaluate the DDBC technique experimentally on a number of data sets of mobile objects. The experiments show that DDBC outperforms both Trajectory Mining and Moving Cluster Mining techniques in terms of accuracy, memory usage, and computation time as the density of noise increases.