Zhenhui Li, Jiawei Han, Bolin Ding, and Roland Kays
Periodicity is one of the most frequently occurring phenomena for moving objects. Animals usually have periodic movement behaviors, such as daily foraging behaviors or yearly migration behaviors. Such periodic behaviors are the keys to understand animal movement and they also reflect the seasonal, climate, or environmental changes of the ecosystem. However, periodic behaviors could be complicated, involving multiple interleaving periods, partial time span, and spatiotemporal noises and outliers. In this paper, we address the problem of mining periodic behaviors for moving objects. It involves two sub-problems: how to detect the periods in complex movements, and how to mine periodic behaviors. A period is usually a single value, such as 24 h. And a periodic behavior is a statistical description of the periodic movement for one specific period. For example, we could describe an animal’s daily behavior in the way that “From 6 pm to 6 am, it has 90% probability staying at location A and from 7 am to 5 pm, it has 70% probability staying at location B and 30% probability staying at location C”. So our tasks is to first detect the periods and then describe each periodic behavior according to different periods. Our main assumption is that the observed movement is generated from multiple interleaved periodic behaviors associated with certain reference locations. Based on this assumption, we propose a two-stage algorithm, Periodica, to solve the problem. At the first stage, the notion of reference spot is proposed to capture the reference locations. Through reference spots, multiple periods in the movement can be retrieved using a method that combines Fourier transform and autocorrelation. At the second stage, a probabilistic model is proposed to characterize the periodic behaviors. For a specific period, periodic behaviors are statistically generalized from partial movement sequences through hierarchical clustering. Finally, we show two extensions to the Periodica algorithm: (1) missing data interpolation, and (2) future movement prediction. Empirical studies on both synthetic and real data sets demonstrate the effectiveness of the proposed method.
In Journal of Data Mining and Knowledge Discovery (DMKD)