Detecting outlier sequences in clusters

My question is a general one: I have sequences of categorical variables (click stream) that I analyzed using TraMineR.

I now want to conduct cluster analysis (CA) using the WeightedCluster package. An important step in CA is detecting outliers (before or after clustering). I read the package's manual, but couldn't find any reference to outlier detection. How can this be done on categorical sequences?

• Please explain what you mean by outlier detection step in CA! I cannot figure out what you want to do and why this would require something specific for the clustering of sequences. Commented May 20, 2018 at 8:02
• According to Hair et. al. (2013), Cluster analysis is sensitive to outliers and can distort the final solution. One option they suggest for detecting outliers empirically is with inter-object similarity. I have 1400 sequences, so my dissimilarity matrix is very large. So how can I detect sequence outliers that I can then delete from the cluster analysis? Commented May 20, 2018 at 8:11
• So you are not interested in detecting outliers in clusters, but in filtering outliers out before running a clustering algorithm. Right? I would suggest you edit your title and your question to make that clear. Commented May 21, 2018 at 7:47
• It probably can be either way: or before clustering or afterwards. Commented May 21, 2018 at 12:31

A first solution would be to detect outliers from the distances between the sequences and a representative sequence such as the medoid. You get the distances from the medoid using for example the disscenter function of TraMineR. (See the help page of that function.) Once you have these distances, you can define outliers as those sequences that lie at more than say 2 or 2.5 times the pseudo standard deviation from the medoid. The pseudo standard deviation is obtained with the dissvar function.

Alternatively, you could consider multiple representatives instead of a single one. (See Gabadinho and Ritschard, 2013.) In that case you would retain the distance of each sequence to its closest representative. I illustrate below using the 2000 sequences in the biofam dataset that ships with TraMineR.

library(TraMineR)
data(biofam)
biofam.lab <- c("Parent", "Left", "Married", "Left+Marr",
"Child", "Left+Child", "Left+Marr+Child", "Divorced")
biofam.slab <- c("P","L","M","LM","C","LC","LMC","D")
biofam.seq <- seqdef(biofam, 10:25, labels=biofam.lab, states = biofam.slab)

## Computing an OM dissimilarity matrix using INDELSLOG costs
costs <- seqcost(biofam.seq, method="INDELSLOG")
biofam.om <- seqdist(biofam.seq, method="OM", indel=costs$indel, sm=costs$sm)

## Representative set using the neighborhood density criterion
##  20% of the maximal distance, and the number of representatives
##  is chosen so as 75% of the sequences lie in the neighborhood of
##  a representative.
biofam.rep <- seqrep(biofam.seq, diss=biofam.om, criterion="density",

rep.idx <- attr(biofam.rep, "Index") ## indexes of repreentatives
rep.seq <- biofam.seq[rep.idx,]
dist.to.rep <-attr(biofam.rep, "Distances")
min.dist <- apply(dist.to.rep, 1, min, na.rm=TRUE)

discrep <- dissvar(biofam.om)
q <- 2*discrep
outliers <- which(min.dist> q)

## Plot of representatives and outliers
par(mfrow=c(1,3))
seqiplot(rep.seq, sortv="from.end", with.legend=FALSE,
border=NA, main="Representatives")
seqIplot(biofam.seq[outliers,], sortv="from.end", with.legend=FALSE,
main="Outliers")
seqlegend(biofam.seq)


Here, we see that there are 29 outliers (out of 2000 sequences). They include people who continue staying with their parents after getting married, who live with a child without getting married, who marry early and don't have children, and people who divorce.