6
$\begingroup$

I know we can quantify the similarity between two sequences with the same length and same elements by rank order correlation. But how to measure similarity between two sequences of different length, and only having some elements in common?

For example, if I have three rank ordered numeric sequences like this:

sequence A: 1,2,3,4,5,6,7,8,9;

sequence B: 2,3,4,5,6,7,8,9,10,11,12,13

sequence C: 4,2,9,7,11,13,14,16,18

Intuitively, I guess sequence A and B are more similar, since they have more numbers in common and the common numbers have same order in both sequences. Sequence A and C are less similar since they have less number in common and the common numbers have difference orders in each sequence. Is there any quantitative measurement to capture both the order similarity in common elements and the percentage of common elements in two sequences?

$\endgroup$
  • 1
    $\begingroup$ Approaches and measures of similarity are so plenty. First of all, you should decide whether you want to compare these as sequences or as texts (documents). First means that not only co-occurences but also co-positions of the identical elements bother you. Search internet for document similarity measures, text similarity measures, sequences similarity measires, edit distance, DNA comparisons, alignment distances and so on. $\endgroup$ – ttnphns Aug 26 '15 at 19:16
  • $\begingroup$ I was just going to suggest edit distance but I see @ttnphns already mentioned it. $\endgroup$ – Enrique Aug 26 '15 at 19:35
  • $\begingroup$ To get meaningful answers to this question you will need to disclose more information about what "similarity" is intended to mean. What is the underlying statistical problem you are trying to solve? $\endgroup$ – whuber Aug 26 '15 at 20:41
1
$\begingroup$

As mentioned in @ttnphns' comment, there exist plenty of dissimilarity measures. Have a look at the review by Studer & Ritschard (2015) who examine the sensitivity of the measures to ordering, position (timing) and duration (how many times a state is repeated). The measures addressed in that paper are all provided in the seqdist2 R package currently available on the TraMineR R-Forge page.

If you are primarily interested in the uncommon part between your two sequences, an edit distance such as optimal matching may be the solution. Optimal matching measures the minimal cost of transforming one sequence into the other by means of indels (insert or delete) and substitutions and can account for indel and substitution costs. If the difference say between rank 1 and 3 is twice the difference between rank 1 and 2 you could set the substitution costs as the rank differences for example. Such a measure works for sequences of different length. It would just account for the cost of the indels necessary to make the sequences of equal length.

If you prefer to give more focus on the similarity in the ordering of the elements in the sequences, some other measures such as optimal matching of transitions for instance could be a better choice.

Hope this helps.

$\endgroup$
1
$\begingroup$

It sounds to me that you are seeking something like a sub-sequence similarity, am I right? If so: Imagine both sequences A and B as strings, then you could apply:

  1. Longest common substring
  2. Longest common subsequence

The length of the resulting string could be then divided by the maximum length regarding A and B. Would this be an option for you?

$\endgroup$
  • $\begingroup$ Not exactly, I also want to take into account the uncommon part between two sequence. The more uncommon part, the more different two sequences. But thanks anyway. $\endgroup$ – sgyf Aug 27 '15 at 13:44

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.