zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Time series clustering with ARMA mixtures. (English) Zbl 1117.62488
Summary: Clustering problems are central to many knowledge discovery and data mining tasks. However, most existing clustering methods can only work with fixed-dimensional representations of data patterns. We study the clustering of data patterns that are represented as sequences or time series possibly of different lengths. We propose a model-based approach to this problem using mixtures of autoregressive moving average (ARMA) models. We derive an expectation-maximization (EM) algorithm for learning the mixing coefficients as well as the parameters of the component models. To address the model selection problem, we use the Bayesian information criterion (BIC) to determine the number of clusters in the data. Experiments are conducted on a number of simulated and real datasets. Results from the experiments show that our method compares favorably with other methods proposed previously by others for similar time series clustering tasks.

MSC:
62M10Time series, auto-correlation, regression, etc. (statistics)
62H30Classification and discrimination; cluster analysis (statistics)
WorldCat.org
Full Text: DOI
References:
[1] Jain, A. K.; Dubes, R. C.: Algorithms for clustering data. (1988) · Zbl 0665.62061
[2] Mclachlan, G. J.; Basford, K. E.: Mixture models: inference and applications to clustering. (1988) · Zbl 0697.62050
[3] Poulsen, C. S.: Mixed Markov and latent Markov modelling applied to brand choice behaviour. Int. J. Res. marketing 7, No. 1, 5-19 (1990)
[4] G. Ridgeway, Finite discrete Markov process clustering, Technical Report MSR-TR-97-24, Microsoft Research, Redmond, WA, USA, September 1997.
[5] P. Smyth, Probabilistic model-based clustering of multivariate and sequential data, in: Proceedings of the Seventh International Workshop on Artificial Intelligence and Statistics, Fort Lauderdale, FL, USA, 4--6 January 1999, pp. 299--304.
[6] I.V. Cadez, S. Gaffney, P. Smyth, A general probabilistic framework for clustering individuals and objects, in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, MA, USA, 20--23 August 2000, pp. 140--149.
[7] I. Cadez, D. Heckerman, C. Meek, P. Smyth, S. White, Model-based clustering and visualization of navigation patterns on a web site, Technical Report MSR-TR-00-18, Microsoft Research, Redmond, WA, USA, March 2000; Revised September 2001.
[8] I. Cadez, D. Heckerman, C. Meek, P. Smyth, S. White, Visualization of navigation patterns on a web site using model-based clustering, in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, MA, USA, 20--23 August 2000, pp. 280--284.
[9] Dempster, A. P.; Laird, N. M.; Rubin, D. B.: Maximum likelihood from incomplete data via the EM algorithm (with discussion). J. R. Statist. soc. Ser. B 39, 1-38 (1977) · Zbl 0364.62022
[10] P. Sebastiani, M. Ramoni, P. Cohen, J. Warwick, J. Davis, Discovering dynamics using Bayesian clustering, in: Proceedings of the Third International Symposium on Intelligent Data Analysis, Amsterdam, Netherlands, 9--11 August 1999, pp. 199--209.
[11] M. Ramoni, P. Sebastiani, P. Cohen, Multivariate clustering by dynamics, in: Proceedings of the 17th National Conference on Artificial Intelligence, Austin, TX, USA, 30 July--3 August 2000, pp. 633--638.
[12] Ramoni, M.; Sebastiani, P.; Cohen, P.: Bayesian clustering by dynamics. Mach learning 47, No. 1, 91-121 (2002) · Zbl 1012.68154
[13] Kullback, S.; Leibler, R. A.: On information and sufficiency. Ann. math. Statist. 22, 79-86 (1951) · Zbl 0042.38403
[14] Rabiner, L. R.: A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, No. 2, 257-286 (1989)
[15] L.R. Rabiner, C.H. Lee, B.H. Juang, J.G. Wilpon, HMM clustering for connected word recognition, in: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 1, Glasgow, UK, 23--26 May 1989, pp. 405--408.
[16] Oates, T.; Firoiu, L.; Cohen, P. R.: Using dynamic time warping to bootstrap HMM-based clustering of time series. Sequence learning: paradigms, algorithms, and applications, 35-52 (2001)
[17] Krogh, A.; Brown, M.; Mian, I. S.; Sjölander, K.; Haussler, D.: Hidden Markov models in computational biologyapplications to protein modeling. J. mol. Biol. 235, No. 5, 1501-1531 (1994)
[18] Owsley, L. M. D.; Atlas, L. E.; Bernard, G. D.: Self-organizing feature maps and hidden Markov models for machine-tool monitoring. IEEE trans. Signal process. 45, No. 11, 2787-2798 (1997)
[19] P. Smyth, Clustering sequences with hidden Markov models, in: Advances in Neural Information Processing Systems, Vol. 9, MIT Press, Cambridge, MA, 1997, pp. 648--654.
[20] C. Li, G. Biswas, A Bayesian approach to temporal data clustering using hidden Markov models, in: Proceedings of the 17th International Conference on Machine Learning, Stanford, CA, USA, 29 June--2 July 2000, pp. 543--550.
[21] M.P. Perrone, S.D. Connell, K-means clustering for hidden Markov models, in: Proceedings of the Seventh International Workshop on Frontiers in Handwriting Recognition, Amsterdam, Netherlands, 11--13 September 2000, pp. 229--238.
[22] M.H. Law, J.T. Kwok, Rival penalized competitive learning for model-based sequence clustering, in: Proceedings of the 15th International Conference on Pattern Recognition, Vol. 2, Barcelona, Spain, 3--7 September 2000, pp. 195--198.
[23] Desarbo, W. S.; Cron, W. L.: A maximum likelihood methodology for clusterwise linear regression. J. classification 5, No. 1, 249-282 (1988) · Zbl 0692.62052
[24] S. Gaffney, P. Smyth, Trajectory clustering with mixtures of regression models, in: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, 15--18 August 1999, pp. 63--72.
[25] S. Gaffney, P. Smyth, Curve clustering with random effects regression mixtures, in: Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, Key West, FL, USA, 3--6 January 2003.
[26] Box, G. E. P.; Jenkins, G. M.: Time series analysis: forecasting and control. (1970) · Zbl 0249.62009
[27] Box, G. E. P.; Jenkins, G. M.; Reinsel, G. C.: Time series analysis: forecasting and control. (1994) · Zbl 0858.62072
[28] H.Y. Kwok, C.M. Chen, L. Xu, Comparison between mixture of ARMA and mixture of AR model with application to time series forecasting, in: Proceedings of the Fifth International Conference on Neural Information Processing, Kitakyushu, Japan, 21--23 October 1998, pp. 1049--1052.
[29] Ramoni, M. F.; Sebastiani, P.; Kohane, I. S.: Cluster analysis of gene expression dynamics. Proc. natl. Acad. sci. 99, No. 14, 9121-9126 (2002) · Zbl 1023.62110
[30] K. Kalpakis, D. Gada, V. Puttagunta, Distance measures for effective clustering of ARIMA time-series, in: Proceedings of the IEEE International Conference on Data Mining, San Jose, CA, USA, 29 November--2 December 2001, pp. 273--280.
[31] Y. Xiong, D.Y. Yeung, Mixtures of ARMA models for model-based time series clustering, in: Proceedings of the IEEE International Conference on Data Mining, Maebashi City, Japan, 9--12 December 2002, pp. 717--720.
[32] Redner, R. A.; Walker, H. F.: Mixture densities, maximum likelihood and the EM algorithm. SIAM rev. 26, No. 2, 195-239 (1984) · Zbl 0536.62021
[33] Celeux, G.; Diebolt, J.: The SEM algorithma probabilistic teacher algorithm derived from the EM algorithm for the mixture problem. Comput. statist. Quar. 2, 73-82 (1985)
[34] Celeux, G.; Govaert, G.: A classification EM algorithm for clustering and two stochastic versions. Comput. statist. Data anal. 14, 315-332 (1992) · Zbl 0937.62605
[35] Stone, M.: Cross-validatory choice and assessment of statistical predictions. J. R. Statist. soc. Ser. B 36, No. 1, 111-147 (1974) · Zbl 0308.62063
[36] Stone, M.: Asymptotics for and against cross-validation. Biometrika 64, No. 1, 29-35 (1977) · Zbl 0368.62046
[37] P. Smyth, Model selection for probabilistic clustering using cross-validated likelihood, Technical Report 98-09, Department of Information and Computer Science, University of California, Irvine, CA, USA, February 1998.
[38] Banfield, J. D.; Raftery, A. E.: Model-based Gaussian and non-Gaussian clustering. Biometrics 49, 803-821 (1993) · Zbl 0794.62034
[39] Kass, R. E.; Raftery, A. E.: Bayes factors. J. am. Statist. assoc. 90, 773-795 (1995) · Zbl 0846.62028
[40] Schwartz, G.: Estimating the dimension of a model. Ann. statist. 6, No. 2, 461-464 (1978) · Zbl 0379.62005
[41] Ljung, L.: System identification toolbox user’s guide. (2000)
[42] M. Gavrilov, D. Anguelov, P. Indyk, R. Motwani, Mining the stock market: which measure is best? in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, MA, USA, 20--23 August 2000, pp. 487--496.
[43] Keirn, Z. A.; Aunon, J. I.: A new mode of communication between man and his surroundings. IEEE trans. Biomed. eng. 37, No. 12, 1209-1214 (1990)
[44] S. Zhong, J. Ghosh, HMMs and coupled HMMs for multi-channel EEG classification, in: Proceedings of the 2002 International Joint Conference on Neural Networks, Hawaii, USA, 12--17 May 2002, pp. 1154--1159.