Question summary

This question pertains to analyzing dissimilarities between discrete state sequences (e.g., using TraMineR), more specifically to classifying new, previously unseen sequences based on the cluster solution from earlier analytical steps.

What we have

The analytical situation at hand is as follows:

  1. We have a number of sequences (e.g., life course) with a defined alphabet. For example, family situation at year 1, year 2, and so forth.
  2. We have computed a dissimilarity matrix $D$ between our sequences, e.g., using Optimal Matching (OM).
  3. We have clustered the sequences at hand into $K$ clusters, e.g., using Partitioning Around Medoids (PAM).

What we want to have

Suppose we have a new, previously unseen sequence $s$, and we want to assign it to one of the $K$ clusters. The most straightforward strategy would probably be to re-run the entire cluster analysis and examine to which cluster $s$ belongs and whether it influenced the clustering solution. A problem with this approach is that the entire dissimilarity matrix $D'$ and the entire clustering solution need to be constructed from scratch, and for larger samples (e.g., $N > 30000$) this is computationally unfeasible.

Possible avenues

From a cursory review of available information in this respect, it seems that there are K-means family algorithms that can assign new observations to classes. However, these seem to work with raw data to obtain distances, and not with distance/dissimilarity matrices that OM produces. This question offers a workaround to obtain Euclidean distances from the dissimilarity matrix $D$. I'm not sure whether this is a robust method, though, and would love to hear some comments on it.

Another, perhaps very primitive approach would be to calculate OM distances between $s$ and $K$ medoid sequences from the initial solution, and pick the shortest one. Again, I feel that there might be complexities there, that this approach cannot account for (aside the fact that $s$ itself may change the structure of the solution).

Any suggestions are welcome. Thank you in advance for your thoughts.


1 Answer 1


Alongside the solutions you are suggesting, you can also determine the membership of a new sequence on the basis of the mean distance to group members. This is easily done with TraMineR if you use one of the metric that supports the refseq argument. This is the case of OM. I illustrate using the actcal data:

lab <- c("Full-time", "Part-time", "Short Part-time", "Unemployed")
## sequences of first 1000 sequences
s <- seqdef(actcal[1:1000,13:24],labels = lab)

## OM distances using data-driven costs based on "INDELSLOG"
cost <- seqcost(s, method="INDELSLOG")
diss <- seqdist(s, method="OM", indel = cost$indel, sm = cost$sm)

## 4 cluster solution based on PAM
pam4 <- wcKMedoids(diss, k=4)
summary(cl <- factor(pam4$clustering))
# group labels correspond to indexes of the medoids
## 979  994  996 1000 
##  90  166  418  326 

## compute dissimlarities of sequence 1001 to the first 1000.
s.1001 <- seqdef(actcal[1001,13:24],alphabet=alphabet(s),labels = lab)
diss.1001 <- seqdist(s, method="OM", indel = cost$indel, sm = cost$sm, refseq=s.1001)

(mean.d <- aggregate(diss.1001, by=list(cl), FUN = mean))

##   Group.1         x
## 1     979 11.252927
## 2     994  8.824404
## 3     996  1.855171
## 4    1000  9.389470

The membership would then be

mean.d$Group.1[mean.d$x == min(mean.d$x)]

which returns "996". Medoid of group 996 is

## 847  A-A-A-A-A-A-A-A-A-A-A-A

and supplementary sequence is

## 3399 A-A-A-A-A-A-A-A-A-A-B-B
  • $\begingroup$ Thank you for the response! I'm getting an error ('refseq' must be less than the number of sequences in 'seqdata'), since there are only 1000 sequences in s, and refseq = 1001 points to NULL. The idea is clear, nevertheless, and the error can probably be solved by defining another sequence set s.1001, and then eliminate the last element of diss.1001 (equal to zero) to keep it conform to the size of cl. Alternatively, perhaps, supply a sequence object to refseq. Thanks again! $\endgroup$
    – Maxim.K
    Feb 16, 2018 at 9:30
  • $\begingroup$ Of course, you are right. Thanks. I have fixed the code. $\endgroup$
    – Gilbert
    Feb 16, 2018 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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