I clustered my dataset of several thousand first-order Markov chains into about 10 clusters.

Is there some recommended way how I can evaluate these clusters and find out what the items in the clusters share and how they differ from other clusters? So I can make statement like "Processes in cluster A tend to stay in state Y once they get there, which is not true for processes in other clusters."

The transition matrices of those Markov chains are too large to just "look and see". They are relatively sparse, if that can help.

My idea was to take all the transition matrices in a cluster, sum them and plot it as intensity in a picture (in a scale from 0 to 255). Is there something more "professional" I should try out?

  • $\begingroup$ Do you know that these processes are first-order Market chains (and, if so, how)? Assuming the answer to this is affirmative, then what additional a priori information do you know about the structure? I'm trying to identify why you are interested in clustering in the first place; I suspect knowing this will help our readers guide you more efficiently to a solution. $\endgroup$
    – cardinal
    Commented Sep 16, 2012 at 21:57
  • $\begingroup$ The original data were clickstreams generated by users on my site. I created the markov processes so each process is to describe the clickstream of one user. I know there are books and papers that say that markov chains are inadequate for this, but my data do not include exact URL the user requested, just the "application" the URL belongs to. (My site is an Information system that is divided into 105 so called "applications" which are mostly self contained parts of the site, linked through a home page and side menu on every page) $\endgroup$
    – user7610
    Commented Sep 17, 2012 at 7:03
  • $\begingroup$ I am interested in clustering because I want to reveal groups of users that have similar patterns in using the site. I hypothesized that patterns that Markov chain captures is enough to distinguish such groups. I checked how the clusters I created correspond to roles users have on the site and it always looks the way that in a cluster there is a lot of users from one role and only a couple from other roles, so that looks promising. Hope that helps $\endgroup$
    – user7610
    Commented Sep 17, 2012 at 7:06
  • $\begingroup$ Hi, I am running into the same issue. Finally, how did you solve the problem? $\endgroup$
    – nan
    Commented Jun 3, 2014 at 7:39
  • $\begingroup$ @nan I did not, I needed this just in a term project, so I simply did something else. If I had to solve it now, I'd try looking at en.wikipedia.org/wiki/… for the initial clustering. t-SNE is super popular nowadays and IMO suitable. I'd hope that the result I'd get would be more meaningful than the results I got with my ad-hoc approach. And using relatively new super-cool thing would satisfy the teacher ;) $\endgroup$
    – user7610
    Commented Feb 26, 2017 at 19:33

2 Answers 2


To make a statement about the steady state behaviour of each cluster you could compute the steady state distributions of each transition matrix by eigenvectors, then compare box-plots by cluster. You're likely to run into issues in the computation of steady state without applying some sort of smoothing first.

How are you clustering the transition matrices? If it were me, I'd apply additive smoothing to each row then take the centered log-ratio transform of each row then flatten the matrices.

If you're clustering with K-means or a variant, you could analyze the normalized cluster centers. Or just pick a few observations from each cluster and analyze them.


First, to get an idea, are your matrices of dimension 105 x 105, corresponding with the applications that you mention? When you say 'stay in state Y' does that mean stick around application Y?

Then, I would assume that outcomes such as "Processes in cluster A tend to stay in state Y once they get there, which is not true for processes in other clusters" are a bit too fine-grained with just 10 clusters. Have you tried a clustering of the application domain -- if I understand correctly you could cluster the 105 applications based on user behaviour. Next, have you looked at simple presence of users rather than transition, i.e. look at profiles of users across the 105 applications? It sounds as if you could use Pearson coefficient between user profiles; either on clusters of applications, or on the applications themselves. This could perhaps be extended towards transitions between applications, but currently I feel there is a huge mismatch between the number of clusters and the type of outcome you are interested in.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.