Looking for distance metrics for trajectories of state sequences, based on nearness in time

Question

I am working with data on individual trajectories, defined as a categorical state defined for each time period, using R's TraMineR package to visualize and calculate distances between each pair of trajectories for the sake of cluster analysis

One phenomenon I'm seeing is that trajectories like:

1: baaaa
2: abaaa
3: aaaab

all cluster together. For starters, we’re using the OM metric and, of course, each is just a distance of 2 to the other given an indel parameter of 1. The result is a cluster that is interpreted as "brief 'b'".

However, my hope was to find a metric that would return distances of:

1 between sequence 1 and 2, 
4 between sequence 1 and 3, and
3 between sequence 2 and 3.

That is: a distance that is based on swaps of adjacent values. My end goal would be clustering (as warranted by the data) of cases with "brief, and early 'b'" versus "brief, and early 'b'".

Answer 1

It sounds like you're looking for a type of edit distance, which measures the cost of transforming one object into another. Edit distances can be defined for many mathematical objects, including strings of symbols (as in your example). First, a set of operations is defined, such as inserting a symbol, deleting a symbol, swapping symbols, etc. Each operation is assigned a cost. The distance between two objects is then the minimum total cost of transforming one object to match the other, using the allowed operations. Computing edit distances requires solving an optimization problem, which is commonly done using dynamic programming.

In your example, you could define an operation that swaps adjacent symbols, with a cost of 1. The distances between your example sequences would then be exactly as you wanted. For example, transforming sequence 1 to sequence 3 uses 4 swap operations:

baaaa -> abaaa -> aabaa -> aaaba -> aaaab

Imagine it were also possible for 'spurious' symbols to randomly contaminate a sequence, or for some symbols to be randomly deleted. In that case, you might want to include insertion, deletion, or substitution operations (but perhaps with higher cost).

Answer 2

The Damereau-Levenshtein (DL) distance for instance accounts for swaps (also named transpositions). DL looks for the minimal cost for transforming one sequence into the other by means of insertions, deletions, substitutions, and transpositions. Of course, as stated by @user20160, for a transposition to intervene in the optimal transformation, it should have a low cost (less than an insert and a delete). Currently, this DL distance is not implemented in TraMineR. However, the stringdist package proposes it.

In your example, there are only binary sequences and the state distribution is the same in all sequences. In this case, it would make sense to just count the number of swaps required to transform one sequence into the other. You would get the corresponding distance with DL by setting arbitrarily high indel and substitution costs. The parametrization would be less evident when the state distribution differs among sequences, e.g., to measure the distance between baaaa and aabbb.

A TraMineR solution that would more or less reflect the number of swaps is "OMspell", i.e., the optimal matching distance between spells. (See Studer & Ritschard, 2016). I illustrate below with your small example.

library(TraMineR)
dat <- c("baaaa",
         "abaaa",
         "aaaab")
ds <- seqdecomp(dat,sep="")
(s <- seqdef(ds))

cost <- seqcost(s, method="CONSTANT")
(d.om <- seqdist(s, method="OM", sm=cost$sm, indel=cost$indel))
(d.omspell <- seqdist(s, method="OMspell", sm=cost$sm, indel=cost$indel,
                      tpow=.5, expcost=.5))

##      [,1] [,2] [,3]
## [1,] 0.00 1.13 2.00
## [2,] 1.13 0.00 1.87
## [3,] 2.00 1.87 0.00

As you can see, the distance between sequences 1 and 2 is smaller than between 1 and 3 as well as between 2 and 3.