Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I have a 30x30 symmetric matrix that I would like to use as a substitution cost matrix in TraMineR to analyze sequences of length 10 with an alphabet of 30. When I try to perform OM with this matrix, however, I get an error about the triangle inequality (see below).

Other matrices that I have made by hand seem to work fine (see example below). I thought the subcost matrix could be set any way I want as long as it was symmetric and the dimensions reflected the size of the alphabet. Are there limitations on how I can set the subcosts? Or perhaps something else is causing the problem?

Thanks

> diss1vs <- seqdist(bhpsfup.seqw, method = "OM", indel = .1*maxsub, sm = upsubcosts)
 [>] 536 sequences with 30 distinct events/states
Error in checktriangleineq(sm, warn = FALSE, indices = TRUE, tol = tol) : 
  REAL() can only be applied to a 'numeric', not a 'integer'

Example matrix that works

zeroblock <- diag(6)
zeroblock[zeroblock == 1] <- 0
zeroblock

twoblock <- diag(6)
twoblock[twoblock == 0] <- 2
twoblock[twoblock == 1] <- 2
twoblock

submat.up1 <- cbind(zeroblock,twoblock,twoblock,twoblock,twoblock)
submat.up2 <- cbind(twoblock,zeroblock,twoblock,twoblock,twoblock)
submat.up3 <- cbind(twoblock,twoblock,zeroblock,twoblock,twoblock)
submat.up4 <- cbind(twoblock,twoblock,twoblock,zeroblock,twoblock)
submat.up5 <- cbind(twoblock,twoblock,twoblock,twoblock,zeroblock)
submat.up <- rbind(submat.up1, submat.up2, submat.up3, submat.up4, submat.up5)
submat.up
share|improve this question
1  
Defining the matrix within R improves things a bit. The OM will run, but I get a different message about the triangle inequality. –  JeremyR Dec 14 '12 at 18:35
1  
> diss1vs <- seqdist(bhpsfup.seqw, method = "OM", indel = .1*maxsub, sm = upsubcostsb) [>] 536 sequences with 30 distinct events/states [>] 536 distinct sequences [>] min/max sequence length: 10/10 [>] computing distances using OM metric [>] total time: 0.17 secs Warning messages: 1: [!] at least, one substitution cost doesn't respect the triangle inequality. [!] replacing 1 with 11 (cost=1) and then 11 with 4 (cost=1) [!] costs less than replacing directly 1 with 4 (cost=3) [!] total difference ([1=>11] + [11=>4] - [1=>4]): -1 –  JeremyR Dec 14 '12 at 18:39
    
Thanks for the bug report. It should work if you use the function "as.double" to transform your substition costs (sm <- as.double(sm)) –  Matthias Studer Dec 15 '12 at 12:38
add comment

2 Answers

The substitution costs should respect the triangle inequality, otherwise the resulting distance won't respect it (and won't be a distance but a dissimilarity).

The optimal matching algorithm can be interpreted (if it respects triangle inequality) as the minimum cost required to transform sequence A in sequence B. However, the algorithm (Needlman-Wunsch) does not try to make successive substitutions, but only one. Hence, if you have the following costs (with indel=5):

  A  B  C
A 0  1  3
B 1  0  1
C 3  1  0

Now consider computing the distance between sequences "A" and "C". The optimal matching distance will be 3 (substitution between A and C). But it would have cost less to first substitute A by B (cost 1) and then B by C (cost 1) for a total of 2.

This example illustrates why we should use substitution costs that respect triangle inequality. It ensures that the resulting distance is coherent. The distance between two points should always be equal or less than going through another one.

share|improve this answer
    
Thanks, Matthias. –  JeremyR Dec 15 '12 at 13:07
add comment

The triangle inequality requires that the distance between any three points $A$, $B$, and $C$ meets the criteria that the distance between $A$ and $C$ is not larger than the distance between $A$ and $B$ plus the distance between $B$ and $C$. That is, $D(A,C) \le D(A,B) + D(C,B)$.

To guarantee that the substitution cost matrix does not lead to a violation of this rule, the costs should be set so that zeros appear only on the diagonal and any combination of smaller costs is larger than the largest cost.

share|improve this answer
1  
Hi Jeremy. Could you please clarify this post? My concern is that (i) the triangle inequality is not what you've written and (ii) the equation does not match with either the triangle inequality or the description you've given. I suspect these mat just be typos. –  cardinal Dec 15 '12 at 14:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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