A new approach to the analysis of heterogeneous categorical sequences is proposed. The first-order Markov model is employed in a finite mixture setting with initial state and transition probabilities being expressed as functions of time. The expectation–maximization algorithm approach to parameter estimation is implemented in the presence of positive equivalence constraints that determine which observations must be placed in the same class in the solution. The proposed model is applied to a dataset from the British Household Panel Survey to evaluate the association between the education background and life outcomes of study participants. The analysis of the survey data reveals many interesting relationships between the level of education and major life events.
BanerjeeA and GhoshJ (2001) Clickstream clustering using weighted longest common subsequences. In Proceedings of the Web Mining Workshop at the 1st SIAM Conference on Data Mining, Vol. 143, page 144, Chicago, Illinois, USA.
3.
BasuS, DavidsonI and WagstaffK (2008) Constrained Clustering: Advances in Algorithms, Theory, and Applications. Boca Raton, FL: CRC Press.
4.
BiernackiC, CeleuxG and GovaertG (2003) Choosing starting values for the em algorithm for getting the highest likelihood in multivariate Gaussian mixture models. Computational Statistics & Data Analysis, 41, 561–75.
5.
ChangH-J, HungL-P and HoC-L (2007) An anticipation model of potential customers purchasing behavior based on clustering analysis and association rules analysis. Expert Systems with Applications, 32, 753–64.
6.
DempsterAP, LairdNM and RubinDB (1977) Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39, 1–22.
7.
DinlerD and TuralMK (2016) A survey of constrained clustering. In Unsupervised Learning Algorithms, pages 207–235. Cham: Springer.
8.
DurrettR (1999) Essentials of Stochastic Processes. Vol. 1. Berlin: Springer.
9.
GabadinhoA, RitschardG, MuellerNS and StuderM (2011) Analyzing and visualizing state sequences in R with TraMineR. Journal of Statistical Software, 40, 1–37.
10.
HartiganJA and WongMA (1979) Algorithm as 136: A K-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28, 100–108.
11.
HennigC, MeilaM, MurtaghF and RocciR (2015) Handbook of Cluster Analysis. CRC Press.
12.
HubertL and ArabieP (1985) Comparing partitions. Journal of Classification, 2, 193–218.
13.
Institute for Social Economic Research (2018) British Household Panel Survey: Waves 1–18, 1991–2009. URL http://doi.org/10.5255/UKDA-SN-5151-2(last accessed 18 January 2021).
14.
KrzanowskiW and MarriottF (1994) Multivariate Analysis: Part I, Distributions, Ordination and Inference. London: Arnold Publication.
15.
MacQueenJ (1967) Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium, 1, 281–97.
16.
McLachlanG and PeelD (2004) Finite Mixture Models. Hoboken, NJ: John Wiley & Sons.
17.
MelnykovI and MelnykovV (2020) A note on the formal implementation of the K-means algorithm with hard positive and negative constraints. Journal of Classification. doi: 10.1007/s00357-019-09349-x.
18.
MelnykovV (2016a) Model-based biclustering of clickstream data. Computational Statistics & Data Analysis, 93, 31–45.
19.
MelnykovV (2016b). Clickclust: An R package for model-based clustering of categorical sequences. Journal of Statistical Software, 74, 1–34.
20.
MelnykovV, MelnykovI and MichaelS (2016) Semi-supervised model-based clustering with positive and begative constraints. Advances in Data analysis and Classification, 10, 327–49.
21.
NelderJA and MeadR (1965) A simplex method for function minimization. The Computer Journal, 7, 308–13.
22.
NimmoDWR, HerrmannSJ, SubletteJE, MelnykovIV, HellandLK, RomineJA, CarsellaJS, Herrmann-HoesingLM, TurnerJA and Vanden HeuvelBD (2018) Occurrence of Chironomid species (Diptera: Chironomidae) in the high Se-78 concentrations and high pH of Fountain Creek Watershed, Colorado, USA. Western North American Naturalist, 78, 39–64. doi: 10.3398/064.078.0106.
23.
ScholzM (2016) R package clickstream: Analyzing clickstream data with Markov chains. Journal of Statistical Software, 74, 1–17.
24.
SchwarzG. (1978) Estimating the dimension of a model. The Annals of Statistics, 6, 461–64.
25.
ShentalN, Bar-HillelA, HertzT and WeinshallD (2003) Computing Gaussian mixture models with EM using equivalence constraints. In Advances in NIPS, edited by ThrunS., SaulL. K. and Sch–lkopfB.. Vol. 15, pages 465–472. Cambridge, MA: MIT Press.
26.
SneathP (1957) The application of computers to taxonomy. Journal of General Microbiology, 17, 201–26.
27.
SzekelyGJ and RizzoML (2005) Hierarchical clustering via joint between-within distances: Extending ward’s minimum variance method. Journal of Classification, 22, 151–83.
28.
TaylorMF, BriceJ, BuckN and Prentice-LaneE (2018) British Household Panel Survey User Manual Volume A: Introduction, Technical Report and Appendices. Colchester: University of Essex.
29.
University of Essex I. f. S. Research E. (2018). British household panel survey: Waves1-18, 1991-2009. http://doi.org/10.5255/UKDA-SN-5151-2.
30.
WardJH (1963) Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58, 236–44.
31.
ZhangY, MelnykovV and ZhuX (2020) Model-based clustering of time-dependent categorical sequences with application to the analysis of major life event patterns. Statistical Analysis and Data Mining. doi: 10.1002/sam.11502.
