Extracting sets of representative sequences

Description

Returns either an as small as possible set of non redundant representatives covering (having in their neighborhood) a desired percentage of all sequences, or a given number of patterns with highest coverage. Special cases are single representatives such as the medoid or the sequence pattern with densest neighborhood. See plot.stslist.rep for the plot method and seqplot for other plot options.

Usage

1
2
3
 seqrep(seqdata, criterion="density", score=NULL,
    decreasing=TRUE, trep=0.25, nrep=NULL,
    tsim=0.1, dmax=NULL, dist.matrix=NULL, weighted=TRUE, ...)

Arguments

seqdata

a state sequence object as defined by the seqdef function.

criterion

the representativeness criterion for sorting the candidate list. One of "freq" (sequence frequency), "density" (neighborhood density), "mscore" (mean state frequency), "dist" (centrality) and "prob" (sequence likelihood). See details.

score

an optional vector of representativeness scores for sorting the sequences in the candidate list. The length of the vector must be equal to the number of sequences in the sequence object.

decreasing

if a score vector is provided, indicates whether the objects in the candidate list must be sorted in ascending or descending order of this score. Default is TRUE, i.e. descending. The first object in the candidate list is then supposed to be the most representative.

trep

coverage threshold, i.e., minimum proportion of sequences that should have a representative in their neighborhood (neighborhood radius is defined by tsim).

nrep

number of representative sequences. If NULL (default), the size of the representative set is controlled by trep.

tsim

neighborhood radius as a percentage of the maximum (theoretical) distance dmax. Defaults to 0.1 (10%). Sequence y is redundant to sequence x when it is in the neighborhood of x, i.e., within a distance tsim*dmax from x.

dmax

maximum theoretical distance. Used to derive the neighborhood radius as tsim*dmax. If NULL, the value of dmax is derived from the dissimilarity matrix.

dist.matrix

matrix of pairwise dissimilarities between sequences in seqdata. If NULL, the matrix is computed by calling the seqdist function. In that case, optional arguments to be passed to the seqdist function (see ... hereafter) should also be provided.

weighted

logical: Should weights assigned to the state sequence object be accounted for? (See seqdef.) Set as FALSE to ignore the weights.

...

optional arguments to be passed to the seqdist function, mainly dist.method specifying the metric for computing the distance matrix, norm for normalizing the distances, indel and sm for indel and substitution costs when Optimal Matching metric is chosen. See seqdist manual page for details.

Details

The representative set is obtained by an heuristic. Representatives are selected by successively extracting from the sequences sorted by their representativeness score those which are not redundant with already retained representatives. The selection stops when either the desired coverage or the wanted number of representatives is reached. Sequences are sorted either by the values provided as score argument or by specifying one of the following as criterion argument: "freq" (sequence frequency), "density" (neighborhood density), "mscore" (mean state frequency), "dist" (centrality) and "dist" (sequence likelihood).

With the sequence frequency criterion, the more frequent a sequence the more representative it is supposed to be. Therefore, sequences are sorted in decreasing frequency order.

The neighborhood density is the number—density—of sequences in the neighborhood of the sequence. This requires to set the neighborhood radius tsim. Sequences are sorted in decreasing density order.

The mean state frequency criterion is the mean value of the transversal frequencies of the successive states. Let s=(s_1, s_2, ..., s_l) be a sequence of length l and f(s_1), f(s_2), ..., f(s_l) the frequencies of the states at (time-)position t_1, t_2, ..., t_l. The mean state frequency is the sum of the state frequencies divided by the sequence length

MSF(s)=1/l sum f(s_i)

The lower and upper boundaries of MSF are 0 and 1. MSF is equal to 1 when all the sequences in the set are identical, i.e. when there is a single sequence pattern. The most representative sequence is the one with the highest score.

The centrality criterion is the sum of distances to all other sequences. The smallest the sum, the most representative the sequence.

The sequence likelihood P(s) is defined as the product of the probability with which each of its observed successive state is supposed to occur at its position. Let s_1, s_2, s_l be a sequence of length l. Then

P(s)=P(s_1,1) * P(s_2,2) * ... * P(s_l,l)

with P(s_t,t) the probability to observe state s_t at position t.
The question is how to determinate the state probabilities P(s_t,t). One commonly used method for computing them is to postulate a Markov Chain model, which can be of various order. The implemented criterion considers the probabilities derived from the first order Markov model, that is each P(s_t,t), t>1 is set to the transition rate p(s_t)|s_t-1 estimated across sequences from the observations at positions t and t-1. For t=1, we set P(s_1,1) to the observed frequency of the state s_1 at position 1.

The likelihood P(s) being generally very small, we use -\log P(s) as sorting criterion. The latter quantity reaches its minimum for P(s) equal to 1, which leads to sort the sequences in ascending order of their score.

Use criterion="dist" and nrep=1 to get the medoid and criterion="density" and nrep=1 to get the densest sequence pattern.

For more details, see Gabadinho & Ritschard, 2013.

Value

An object of class stslist.rep. This is actually a state sequence object (containing a list of state sequences) with the following additional attributes:

Scores

a vector with the representative score of each sequence in the original set given the chosen criterion.

Distances

a matrix with the distance of each sequence to its nearest representative.

Statistics

a data frame with quality measures for each representative sequence: number of sequences attributed to the representative, number of sequence in the representative's neighborhood, mean distance to the representative.

Quality

overall quality measure.

Print, plot and summary methods are available. More elaborated plots are produced by the seqplot function using the type="r" argument, or the seqrplot alias.

Author(s)

Alexis Gabadinho (with Gilbert Ritschard for the help page)

References

Gabadinho A, Ritschard G (2013). "Searching for typical life trajectories applied to child birth histories", In R Lévy, E. Widmer (eds.), Gendered Life Courses, pp. 287-312. Vienna: LIT.

Gabadinho A, Ritschard G, Studer M, Müller NS (2011). "Extracting and Rendering Representative Sequences", In A Fred, JLG Dietz, K Liu, J Filipe (eds.), Knowledge Discovery, Knowledge Engineering and Knowledge Management, volume 128 of Communications in Computer and Information Science (CCIS), pp. 94-106. Springer-Verlag.

See Also

seqplot, plot.stslist.rep, dissrep, disscenter

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
## Defining a sequence object with the data in columns 10 to 25
## (family status from age 15 to 30) in the biofam data set
data(biofam)
biofam.lab <- c("Parent", "Left", "Married", "Left+Marr",
"Child", "Left+Child", "Left+Marr+Child", "Divorced")
biofam.seq <- seqdef(biofam, 10:25, labels=biofam.lab)

## Computing the distance matrix
costs <- seqsubm(biofam.seq, method="TRATE")
biofam.om <- seqdist(biofam.seq, method="OM", sm=costs)

## Representative set using the neighborhood density criterion
biofam.rep <- seqrep(biofam.seq, dist.matrix=biofam.om, criterion="density")
biofam.rep
summary(biofam.rep)
plot(biofam.rep)

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker.