Literature Review on Hidden Markov Model-Based Sequential Data Clustering

Abstract:

The purpose of this report is to investigate current existing algorithm to cluster sequential data based on hidden Markov model (HMM). Clustering is a classic technique that divides a set of objects into groups (called clusters) so that objects in the same cluster are similar in some sense. The clustering of sequential or time series data, however, draws lately more and more attention from researchers. Hidden Markov model (HMM)-based clustering of sequences is probabilistic model-based approach to clustering sequences. Generally, there are two kinds of methodologies: parametric and semi-parametric. The parametric methods make strict assumptions that each cluster is represented by a corresponding HMM, while the semi-parametric approaches relax this assumption and transform the problem to a similarity-based issue. Generally, the semi-parametric methods perform better than parametric approaches as reported by some researchers. Future research can be done in exploring new distance measures between sequences and extending current HMM-based methodologies by using other models.

• Periodical: Applied Mechanics and Materials (Volumes 713-715)
• Pages: 1750-1756
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.713-715.1750
• Online since: January 2015
• Authors: Ming Ji*, Fei Wang, Jia Ning Wan, Yuan Liu
• Keywords: Hidden Markov Model (HMM), Semi-Parametric Method, Sequence Clustering

References

[1] Liao, W. Clustering of time series data-a survey. Pattern Recognition, vol. 38 (2005), no. 11, pp.1857-74.

[2] Rabiner, L. A tutorial on hidden Markov models and selected applications in speech recognition. Readings in speech recognition, vol. 53 (1990), no. 3, pp.267-96.

DOI: 10.1016/b978-0-08-051584-7.50027-9

[3] Baldi, P. & Brunak, S. Bioinformatics: the machine learning approach, (2001).

[4] Wang, J.J.L. & Singh, S. Video analysis of human dynamics-a survey. Real-time imaging, vol. 9 (2003), no. 5, pp.321-46.

[5] Ghahramani, Z. Learning dynamic Bayesian networks. Adaptive Processing of Sequences and Data Structures, 1998, p.168.

[6] Baum, L.E. & Sell, G. Growth functions for transformations on manifolds', Pac. J. Math, vol. 27 (1968), no. 2, pp.211-27.

[7] Dempster, A.P., Laird, N.M. & Rubin, D.B. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological), vol. 39 (1977), no. 1, pp.1-38.

DOI: 10.1111/j.2517-6161.1977.tb01600.x

[8] Forney Jr, G.D. The viterbi algorithm. Proceedings of the IEEE, vol. 61 (1973), no. 3, pp.268-78.

[9] Johnson, S.C. Hierarchical clustering schemes. Psychometrika, vol. 32 (1967), no. 3, pp.241-54.

[10] Luxburg, U. A tutorial on spectral clustering. Statistics and Computing, vol. 17 (2007), no. 4, pp.395-416.

DOI: 10.1007/s11222-007-9033-z

[11] Smyth, P. Clustering sequences with hidden Markov models. Advances in Neural Information Processing Systems, vol. 9 (1997), Denver, CO, USA, pp.648-54.

[12] Oates, T., Firoiu, L. & Cohen, P.R. Clustering time series with hidden markov models and dynamic time warping. Proceedings of the IJCAI-99 Workshop on Neural, Symbolic and Reinforcement Learning Methods for Sequence Learning, Citeseer (1999).

DOI: 10.1007/3-540-44565-x_3

[13] Alon, J., Sclaroff, S., Kollios, G. & Pavlovic, V. Discovering clusters in motion time-series data. paper presented to the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2003).

DOI: 10.1109/cvpr.2003.1211378

[14] Garcia-Garcia, D., Hernandez, E.P. & Diaz de Maria, F. A new distance measure for model-based sequence clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31 (2009), no. 7, pp.1325-31.

DOI: 10.1109/tpami.2008.268

[15] Jebara, T., Song, Y. & Thadani, K. Spectral clustering and embedding with hidden Markov models. Machine Learning: ECML 2007, pp.164-75.

DOI: 10.1007/978-3-540-74958-5_18

[16] Panuccio, A., Bicego, M. & Murino, V. A Hidden Markov Model-Based Approach to Sequential Data Clustering, Springer-Verlag, pp.734-42. (2002).

DOI: 10.1007/3-540-70659-3_77

[17] Yin, J. & Yang, Q. Integrating hidden Markov models and spectral analysis for sensory time series clustering. Proceedings of the Fifth IEEE International Conference on Data Mining, Houston, Texas, USA, pp.8-15. (2005).

DOI: 10.1109/icdm.2005.82

[18] García-García, D., Hernandez, E. & Diaz-de-Maria, F. State-space dynamics distance for clustering sequential data. Pattern Recognition, vol. 44 (2011), pp.1014-22.

DOI: 10.1016/j.patcog.2010.11.018

[19] Bicego, M., Murino, V. & Figueiredo, M. Similarity-based clustering of sequences using hidden Markov models. Lecture Notes in Computer Science, vol. 2734(2003), pp.95-104.

DOI: 10.1007/3-540-45065-3_8