# seqrep: 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.

`seqplot`, `plot.stslist.rep`, `dissrep`, `disscenter`
 ``` 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) ```