Nesting the earth mover's distance for effective cluster tracing

ABSTRACT

Cluster tracing algorithms are used to mine temporal evolutions of clusters. Generally, clusters represent groups of objects with similar values. In a temporal context like tracing, similar values correspond to similar behavior in one snapshot in time. Recently, tracing based on object-value-similarity was introduced. In this new paradigm, the decision whether two clusters are considered similar is based on the similarity of the clusters' object values. Existing approaches of this paradigm, however, have a severe limitation. The mapping of clusters between snapshots in time is performed pairwise, i.e. global connections between a temporal snapshot's clusters are ignored; thus, impacts of other clusters that may affect the mapping are not considered and incorrect cluster tracings may be obtained.

In this vision paper, we present our ongoing work on a novel approach for cluster tracing that applies the object-value-similarity paradigm and is based on the well-known Earth Mover's Distance (EMD). The EMD enables a cluster tracing that uses global mapping: in the mapping process, all clusters of compared snapshots are considered simultaneously. A special property of our approach is that we nest the EMD: we use it as a ground distance for itself to achieve most effective value-based cluster tracing.

References

1. M. Böttcher, F. Höppner, and M. Spiliopoulou. On exploiting the power of time in data mining. SIGKDD Explorations, 10(2):3--11, 2008.
2. S. Günnemann, H. Kremer, C. Laufkötter, and T. Seidl. Tracing evolving clusters by subspace and value similarity. In PAKDD (2), pages 444--456, 2011.
3. S. Günnemann, H. Kremer, C. Laufkötter, and T. Seidl. Tracing evolving subspace clusters in temporal climate data. DMKD, 24(2):387--410, 2012.
4. F. S. Hillier and G. J. Lieberman. Introduction to Operations Research. McGraw-Hill, 2001.
5. P. Kalnis, N. Mamoulis, and S. Bakiras. On discovering moving clusters in spatio-temporal data. In SSTD, pages 364--381, 2005.
6. J. Rosswog and K. Ghose. Detecting and tracking spatio-temporal clusters with adaptive history filtering. In ICDM Workshops, pages 448--457, 2008.
7. Y. Rubner, C. Tomasi, and L. J. Guibas. The earth mover's distance as a metric for image retrieval. Int. J. Comput. Vision, 40:99--121, November 2000.
8. M. Spiliopoulou, I. Ntoutsi, Y. Theodoridis, and R. Schult. MONIC: modeling and monitoring cluster transitions. In KDD, pages 706--711, 2006.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Cluster analysis

• Information systems

  • Information systems applications

    • Data mining