TraMineR: predicting class membership of new sequences

Question

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.

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:

library(TraMineR)
data(actcal)
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
library(WeightedCluster)
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

s[996,]
## 847  A-A-A-A-A-A-A-A-A-A-A-A

and supplementary sequence is

s.1001
## 3399 A-A-A-A-A-A-A-A-A-A-B-B