I have a large dataset of spatio-temporal data. It has longitude and latitude coordinates, and a date for each observation. For example:

Long Lat Date
50 20.43 9-19-2010
51 19.5 10-4-2010
51 19.3 10-2-2010

And so on. I want to cluster the data so that the spatial clusters are small, but the temporal clusters are more spread out/have larger variance. Its equivalent to, if $\sigma_{\tau i}^2$ is the temporal variance and $\sigma_{\gamma i}^2$ is the spatial variance of cluster $i$ with cluster set $K$: $$\max_{K} (1 - \lambda) \sum_{i=1}^n \sigma_{\tau i}^2 + \lambda \sum_{i=1}^n \frac{1}{\sigma_{\gamma i}^2}$$ Where $\lambda$ can be used to determine the relative importance of the two. My current idea is relies on the fact that K-means maximumizes the between cluster variance, so if you perform K-means on the temporal variances and then assign the clusters as uniformly as possible, while maximizing distance after uniformity is not possible, you should have a maximal partition for temporal variance (I am not sure if this is correct).

An algorithm would look something like:

  1. Perform K means on the temporal data $\tau$, call the clusters $K$
  2. Initiate an empty set $T = \{\}$
  3. While $\bigcup T \neq \tau$:
    1. Initiate an empty set $B = \{\}$
    2. Try to add one element from each cluster to $B$ that is not already in $\bigcup T$. If it isn't possible, add one from each available cluster that maximizes the cluster variance.
    3. Set $T = T \cup \{ B \}$
  4. Perform Kmeans on the spatial data $S$, call the clusters $D$.
  5. Somehow tradeoff the differences between the two clustering patterns to obtain the final result?

Does this seem like I'm on the right path? Or is there already something that can do what I want? All help is really appreciated.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.