# 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 |

### Arguments

`seqdata` |
a state sequence object as defined by the |

`criterion` |
the representativeness criterion for sorting the candidate list. One of |

`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 |

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

`nrep` |
number of representative sequences. If |

`tsim` |
neighborhood
radius as a percentage of the maximum (theoretical)
distance |

`dmax` |
maximum theoretical distance. Used to derive the neighborhood radius as |

`dist.matrix` |
matrix of pairwise dissimilarities between sequences in |

`weighted` |
logical: Should weights assigned to the state sequence object be accounted for? (See |

`...` |
optional arguments to be passed to the |

### 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)
``` |