# Which distance metric to use to cluster categorical sequences (clickstreams or clickpaths)?

For my research, I want to cluster website visitors based on their clickstreams to understand different information behavior patterns (i.e., customer/visitor journeys). The data can be characterized as a number of sequences of predefined states (e.g., product information, product applications, offered services, ...) of different lengths (see below). Most importantly, I'm in search of a procedure that provides me with interpretable results and not "just" an assignment of sequences to different clusters. I think I might go with distance based clustering - but as I see that there may be smarter solutions to my problem, I'll give you some more context and hope this is ok (I'm new to stack exchange - let me know if my question is better asked elsewhere).

My main questions are:

1. Which distance metric is most appropriate for clickstream sequences...?
2. while being able to handle a lot of data in reasonable time...?
3. ...and help generating interpretable clustering results?

I am working with R and I am aware of the ClickClust package and the clusterClickstreams function of the clickstream package. Both packages cluster clickstreams based on first-order markov chain transition matrices. ClickClust identyfies clusters based on mixture (markov) modeling, the clusterClickstreams function performes k-means clustering using the first-order transition matrices.
While using first order-markov chains actually keeps some of the sequential nature of the data it does not account for a longer "history" of the clickstreams (other than "one state back"). Additionally, both packages take a lot of time to come up with a result.

At the moment, I am thinking the best way to identify longer (common) information behavior patterns is to cluster clickstreams based on common subsequences.

Data

I want to run the analysis using all sequences available to me to identify information patterns overarching several firms.
Timestamps are available for every click, but at the moment I want to keep it simple. I may think about including timestamps at a later point.

What I think may (not) be suited

(A) Optimal matching/EDIT/Levenshtein distance measures do not seem appropriate to me. As this post points out, it can lead to misleading results in the realm of clickpaths. For example, {ABC} would be more distant from {ABCDEFGH} than from {IJK}. At the same time, this distance metric does not provide much insight in what actually makes the sequences (dis)similar.

(B) Some measure of the longest common subsequence (dividided by the maximum length of the sequences being compared?) seems an appropriate distance metric to me, as sequence order is taken into account. Now, my problem is, that coming up with the subsequences contained in every sequence takes a lot of time. Apriori pattern mining algorithms seem unsuited as all possible subsequences are identified and then (multiple) data base scans are conducted. Pattern growth approaches like PrefixSpan or CloSpan are said to be faster but still need ages when running them on my ~250.000 sequences. I tried to run PrefixSpan using this code but had to abord it as it did not terminate over night.

(C) I think it would also be good to compute distances based on a subsequence vector representation of the sequences (e.g. Elzinga/Studer 2015). For this, however, I would not only need to come up with the longest common subsequence but with all common subsequences.

I'd be happy hearing your thoughts on (a) are there better distance metrics than the subsequence based ones given the data I have and if not, (b) which pattern mining algorithm should be used to come up with the subsequences in reasonable time?

Thanks a lot! :)