2
$\begingroup$

I know about Edit distance, Longest Common Subsequence and their normalized versions to measure the similarity between sequences But do we have any similarity measures other than the above ones?

$\endgroup$
1
$\begingroup$

There are multiple ways of measuring the (dis)similarity between sequences. In their comparative study of dissimilarity measures Studer & Ritschard (JRSSA 2016) for instance distinguish between:

  1. Distances between within-sequence state distributions.
  2. Measures based on the count of common attributes of the two sequences.
  3. Edit distances.

Euclidean or Chi-squared distances between state distributions include variants that sum up the distances computed on successive periods.

Measures based on the count of common attributes include among others the 'non-aligning' measures proposed by Elzinga that are based on the count of common subsequences. The most evolved version of the latter is the Subsequence Vector Representation‐based (SVRspell) metric. See Elzinga & Studer (SMR 2015).

Edit distances, also known as optimal matching distances, include a great number of variants depending on how the costs of the basic edit operations are set, but also edit distances for specific representations of the sequences such as the sequences of spells or the sequences of the state transitions.

In addition to these distances, which are all available in the TraMineR R package (traminer tag on this site), a possibility is to evaluate the distance between sequences by fitting a Markovian model or Probabilistic Suffix Tree (see for instance Gabadinho & Ritschard, 2016) on each sequence and then consider the distances between the models such as the distance between the estimated transition matrices or the probabilistic distance of Juang & Rabiner (1985).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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