Package {transitiontrees}


Type: Package
Title: Transition Trajectories and Dynamics of Variable-Length Pathways or Sequences
Version: 0.2.0
Description: Analyzes transition trajectories in event, sequence, and ordered data, focusing on how states follow one another, how far processes unfold, and where pathways branch or converge. Trajectories are modeled using variable-order prediction suffix trees (Ron, Singer, & Tishby, 1996) <doi:10.1023/A:1026490906255>, implemented in both frequency-based and prediction-based forms. The framework includes multiple pruning, validation, and smoothing techniques to ensure model robustness. Visualization options include transition trees, radial sunburst diagrams, transition heatmaps, and forward trajectory trees.
License: GPL-3
URL: https://github.com/mohsaqr/transitiontrees, https://pak.dynasite.org/transitiontrees/
BugReports: https://github.com/mohsaqr/transitiontrees/issues
Encoding: UTF-8
Language: en-US
LazyData: true
LazyDataCompression: xz
Depends: R (≥ 4.1)
Imports: ggplot2 (≥ 3.5.0), grDevices, stats, utils
Suggests: testthat (≥ 3.0.0), knitr, rmarkdown, visNetwork, tna, Nestimate
VignetteBuilder: knitr
Config/Needs/website: TraMineR
Config/testthat/edition: 3
Config/roxygen2/version: 8.1.1
NeedsCompilation: no
Packaged: 2026-11-17 14:16:35 UTC; mohammedsaqr
Author: Mohammed Saqr ORCID iD [aut, cre, cph], Sonsoles López-Pernas ORCID iD [aut]
Maintainer: Mohammed Saqr <saqr@saqr.me>
Repository: CRAN
Date/Publication: 2026-11-17 17:50:11 UTC

transitiontrees: Transition Trajectories and Dynamics of Variable-Length Pathways or Sequences

Description

transitiontrees models how categorical processes unfold: how one state follows another in learning sessions, collaborative work, care pathways or any other ordered record of events. Its model is the variable-order transition tree, known as a prediction suffix tree (Ron, Singer & Tishby, 1996) or variable-length Markov chain (Bühlmann & Wyner, 1999). A first-order Markov chain predicts the next state from the current state alone, and a chain of fixed order m from the last m states, with a number of parameters that grows exponentially in m. A transition tree lets the length of the relevant history vary: it keeps a longer context only where the data show that the extra history changes what comes next.

Each node of the tree is a pathway, a run of recent states written from oldest to newest ("A -> B -> C"), with the distribution of the state that followed it. The package treats these pathways as the unit of analysis. It reports which pathways occur, which of them change the prediction relative to a shorter history, how stable they are under resampling, and whether they differ between groups, and it uses the fitted tree to predict, score, simulate and impute sequences. All results are returned as data frames with one row per pathway, sequence or group, and all plots are ggplot2 objects.

Details

With the default floor smoothing, the fitted counts and probabilities match those of the PST package (Gabadinho & Ritschard, 2016). The smoothing schemes other than the floor, the pruning criteria, cross-validated tuning, the bootstrap and the permutation tests are this package's own.

Data input

context_tree() accepts wide sequence tables, lists of sequences, long event logs (reshaped by prepare_input()), and transition network models from tna (Saqr et al., 2025) and Nestimate that carry their sequences. The bundled datasets are trajectories, engagement, group_regulation_long and ai_long.

Fitting and refining a tree

context_tree() fits a tree, or one tree per group. prune_tree() removes contexts that do not change the prediction, smooth_tree() re-estimates probabilities under another smoothing scheme, and compare_pruning() and compare_smoothing() tabulate the alternatives. tune_tree() chooses depth, minimum count, smoothing and pruning by cross-validated perplexity.

Reading pathways

tree_pathways() (also as.data.frame()) lists every pathway; common_pathways(), divergent_pathways() and sharp_pathways() rank them by frequency, divergence from the shorter history, and certainty of the next state. tree_dependence() adds entropies, state_frequencies() gives the state counts, and query_pathway(), pathway_exists(), subtree() and mine_contexts() look up individual pathways.

Fit, prediction and scoring

model_fit() returns log-likelihood, AIC, BIC and perplexity, in-sample or on new data (see also logLik.transitiontrees(), perplexity() and n_nodes()). predict.transitiontrees() predicts the next state, score_sequences(), score_positions() and mine_sequences() score observed sequences, generate_sequences() simulates new ones, and impute_sequences() fills gaps.

Reliability and comparison

bootstrap_pathways() resamples sequences to assess the stability of each pathway. compare_trees() and tree_distance() compare two trees, and compare_groups() tests group differences pathway by pathway with permutation tests.

Visualization

plot.transitiontrees() draws the tree; plot_pathways(), plot_divergence() and plot_distributions() show pathways and their next-state distributions; plot_pruning() shows the pruning decision along one pathway; plot_predictive() shows predictive performance on new data; plot_trajectories() draws the forward tree of sequence beginnings; and plot_difference() and plot_pathway_resamples() show group differences and bootstrap distributions.

Author(s)

Maintainer: Mohammed Saqr saqr@saqr.me (ORCID) [copyright holder]

Authors:

References

Bühlmann, P., & Wyner, A. J. (1999). Variable length Markov chains. The Annals of Statistics, 27(2), 480-513. doi:10.1214/aos/1018031204

Gabadinho, A., & Ritschard, G. (2016). Analyzing state sequences with probabilistic suffix trees: The PST R package. Journal of Statistical Software, 72(3). doi:10.18637/jss.v072.i03

Ron, D., Singer, Y., & Tishby, N. (1996). The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning, 25(2-3), 117-149. doi:10.1023/A:1026490906255

Saqr, M., López-Pernas, S., Törmänen, T., Kaliisa, R., Misiejuk, K., & Tikka, S. (2025). Transition network analysis: A novel framework for modeling, visualizing, and identifying the temporal patterns of learners and learning processes. In Proceedings of the 15th International Learning Analytics and Knowledge Conference (LAK '25) (pp. 351-361). doi:10.1145/3706468.3706513

See Also

Useful links:


AI turns in human-AI programming sessions (long event log)

Description

ai_long is a coded dataset of the turns of an AI coding assistant in 428 human-AI pair-programming sessions across 34 projects, held between 5 February and 8 March 2026, one row per code. A turn (message) can carry several codes, in the order given by code_order. Each code is one of eight assistant actions (Ask, Delegate, Execute, Explain, Investigate, Plan, Repair, Report), grouped into three clusters (Action, Communication, Repair).

Timestamps have day resolution (midnight, UTC+2, of the session date), so the order of events within a day comes from order_in_session, which counts the human turns of the session as well and therefore has gaps. Use actor = "session_id" with order = "order_in_session" for one sequence per session, or time = "timestamp" to split sequences at changes of day.

Usage

ai_long

Format

A data.frame with 8,551 rows (codes) and 9 columns:

message_id

Integer identifier of the turn; the codes of one turn share it.

project

Project identifier, "Project_1" to "Project_34".

session_id

Session identifier, a 12-character hash.

timestamp

Integer Unix time in seconds (day resolution).

session_date

Date of the row, "YYYY-MM-DD".

code

The assistant action, the state of the sequence.

cluster

The cluster of the code.

code_order

Order of the code within its turn, from 1.

order_in_session

Position of the row in its session, counting human and AI rows together.

Source

Bundled example dataset. The same data are distributed with the Nestimate package as ai_long.

See Also

prepare_input(), context_tree().

Examples

tree <- context_tree(ai_long, actor = "session_id",
                     order = "order_in_session", action = "code",
                     max_depth = 2)
state_frequencies(tree)
common_pathways(tree, top = 5, depth = 2)

Convert a fitted transition tree to a data frame of contexts

Description

as.data.frame() returns the contexts of a fitted tree as a table with one row per context, the same table that tree_pathways() returns. Each row gives the context, its depth and count, the most likely next state and its probability, and how much the context's prediction departs from that of its shorter suffix.

Usage

## S3 method for class 'transitiontrees'
as.data.frame(x, row.names = NULL, optional = FALSE, ...)

Arguments

x

A transitiontrees object.

row.names, optional

Not used.

...

Passed to tree_pathways(): min_count, sort_by and decreasing.

Value

A data.frame with one row per context and columns pathway, depth, count, likely_next, next_probability, divergence and changes_prediction, described in tree_pathways().

See Also

tree_pathways(), common_pathways(), divergent_pathways(), tree_dependence().

Examples

tree <- context_tree(trajectories, max_depth = 2)
as.data.frame(tree)
as.data.frame(tree, sort_by = "divergence")

Convert a pathway bootstrap to a data frame

Description

as.data.frame() returns the per-pathway summary of a bootstrap_pathways() result, or the values of one statistic in every resample.

Usage

## S3 method for class 'transitiontrees_bootstrap'
as.data.frame(
  x,
  row.names = NULL,
  optional = FALSE,
  what = c("summary", "resamples"),
  stat = c("count", "next_probability", "divergence", "G2", "changes_prediction"),
  ...
)

Arguments

x

A transitiontrees_bootstrap object.

row.names, optional

Ignored.

what

"summary" (default) for one row per pathway, or "resamples" for one row per resample and pathway.

stat

For what = "resamples", the statistic: "count" (default), "next_probability", "divergence", "G2" or "changes_prediction".

...

Ignored.

Value

A data frame. For what = "summary", one row per pathway with the columns described in bootstrap_pathways(). For what = "resamples", one row per resample and pathway with columns resample, pathway, stat and value (NA where the statistic is undefined in that resample).

Conditions

transitiontrees_no_data

(error) what = "resamples" for a bootstrap run with keep_resamples = FALSE.

See Also

bootstrap_pathways(), plot_pathway_resamples().

Examples

boot <- bootstrap_pathways(context_tree(trajectories, max_depth = 2),
                           iter = 50)
head(as.data.frame(boot))
head(as.data.frame(boot, what = "resamples", stat = "G2"))

Convert a two-tree comparison to a data frame

Description

as.data.frame() returns the per-context divergence table or the permutation null distribution of a compare_trees() result.

Usage

## S3 method for class 'transitiontrees_comparison'
as.data.frame(
  x,
  row.names = NULL,
  optional = FALSE,
  what = c("pathways", "null"),
  ...
)

Arguments

x

A transitiontrees_comparison object.

row.names, optional

Ignored.

what

"pathways" (default) for the per-context table, or "null" for the permuted distances.

...

Ignored.

Value

A data frame. For what = "pathways", one row per context present in either tree, sorted by divergence_sym (largest first), with columns pathway, count_a and count_b (the context's count in each tree, 0 when absent), divergence_ab and divergence_ba (the two directed Kullback-Leibler divergences, nats) and divergence_sym (their mean). For what = "null", one row per permutation with columns permutation and distance.

See Also

compare_trees(), summary.transitiontrees_comparison.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
cmp <- compare_trees(grp, iter = 20)
as.data.frame(cmp)
head(as.data.frame(cmp, what = "null"))

Convert a group of transition trees to one data frame of contexts

Description

as.data.frame() stacks the context table of each tree in a transitiontrees_group, as returned by tree_pathways(), under a leading group column, so that the contexts of all groups can be read, filtered or plotted together.

Usage

## S3 method for class 'transitiontrees_group'
as.data.frame(x, row.names = NULL, optional = FALSE, ...)

Arguments

x

A transitiontrees_group object.

row.names, optional

Not used.

...

Passed to tree_pathways(): min_count, sort_by and decreasing.

Value

A data.frame with one row per group and context: a group column followed by the columns of tree_pathways().

See Also

tree_pathways(); compare_groups() to test group differences context by context.

Examples

groups <- context_tree(group_regulation_long, actor = "Actor",
                       time = "Time", action = "Action",
                       group = "Achiever", max_depth = 2)
head(as.data.frame(groups, min_count = 50))

Convert a group comparison to a data frame

Description

as.data.frame() returns one of the three tables of a compare_groups() result: the per-context tests, the omnibus tests, or the pairwise distances between groups.

Usage

## S3 method for class 'transitiontrees_group_comparison'
as.data.frame(
  x,
  row.names = NULL,
  optional = FALSE,
  what = c("pathways", "omnibus", "distance"),
  ...
)

Arguments

x

A transitiontrees_group_comparison object.

row.names, optional

Ignored.

what

"pathways" (default), "omnibus" or "distance".

...

Ignored.

Value

A data frame. For what = "pathways", one row per tested context, with the columns described in compare_groups(). For what = "omnibus", one row per axis with columns axis, statistic, value and p_value. For what = "distance", one row per unordered pair of groups with columns group_a, group_b and distance (the count-weighted symmetric Kullback-Leibler divergence of tree_distance(), nats).

See Also

compare_groups(), summary.transitiontrees_group_comparison.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
cmp <- compare_groups(grp, iter = 20)
as.data.frame(cmp)
as.data.frame(cmp, what = "omnibus")
as.data.frame(cmp, what = "distance")

Convert a tuning grid to a data frame

Description

as.data.frame() returns the cross-validation grid, or only the selected configuration, as a plain data frame.

Usage

## S3 method for class 'transitiontrees_tune'
as.data.frame(
  x,
  row.names = NULL,
  optional = FALSE,
  what = c("grid", "best"),
  ...
)

Arguments

x

A transitiontrees_tune object.

row.names, optional

Ignored.

what

"grid" (default) for every configuration, or "best" for the selected one.

...

Ignored.

Value

A data frame. For what = "grid", one row per configuration, sorted by held-out perplexity, with the columns described in tune_tree(). For what = "best", one row: the configuration with the lowest held-out perplexity among those that scored on every fold, or zero rows when none did.

See Also

tune_tree(), summary.transitiontrees_tune.

Examples

tuned <- tune_tree(trajectories, max_depth = 1:3, min_count = 5,
                   prune = FALSE, folds = 3)
as.data.frame(tuned, what = "best")

Bootstrap the stability and informativeness of pathways

Description

bootstrap_pathways() assesses, by resampling sequences, whether each context of a fitted tree is stable and informative: whether a sample of the same size would reproduce it, and whether its departure from the shorter history is reproducible. The procedure extends the edge-level bootstrap of transition network analysis (Saqr et al., 2025) from single transitions to variable-length pathways, and separates pathways that reflect a regularity of the process from those that reflect only the particular sequences that were sampled.

Each iteration resamples whole sequences with replacement (Efron & Tibshirani, 1993) and recounts every pathway of the original tree from raw counts, without smoothing or a minimum count. A pathway is stable when the chosen statistic (its count by default, or the probability of its most likely next state, or its divergence from its parent) stays within consistency_range times the observed value in enough resamples: p_stability is the share of resamples outside that band, counting the observed sample once ((b + 1) / (iter + 1)), and the pathway is stable when it is below 1 - stability_threshold. A pathway is informative when its likelihood-ratio statistic G^2 against its parent context exceeds the chi-square critical value at alpha (|A| - 1 degrees of freedom for alphabet A) in at least informative_threshold of the resamples. Percentile intervals are reported for the count, the next-state probability, the divergence and G^2.

The two flags are read together. A stable and informative pathway is reproducible and predicts differently from its shorter history; a stable pathway that is not informative recurs but adds nothing to its parent's prediction; an informative pathway that is not stable is distinctive but carried by a subset of sequences; a pathway that is neither is fragile. The result is a transitiontrees_bootstrap object, read with as.data.frame() (one row per pathway) and drawn with plot().

The bootstrap evaluates the pathways of one tree; to choose the depth use tune_tree(), to remove contexts that do not differ from their parent use prune_tree(), and to compare groups use compare_groups().

Usage

bootstrap_pathways(
  tree,
  iter = 1000L,
  stat = c("count", "next_probability", "divergence"),
  consistency_range = c(0.5, 1.5),
  stability_threshold = 0.95,
  informative_threshold = 0.8,
  alpha = 0.05,
  ci_level = 0.05,
  seed = 1L,
  keep_resamples = TRUE,
  progress = FALSE
)

Arguments

tree

An unweighted transitiontrees object that carries its sequences (any tree from context_tree()).

iter

Number of bootstrap resamples. Default 1000.

stat

Statistic used for stability: "count" (default), "next_probability" (probability of the most likely next state) or "divergence" (divergence from the parent context, bits).

consistency_range

Lower and upper multiples of the observed value that bound a consistent resample. Default c(0.5, 1.5).

stability_threshold

A pathway is stable when p_stability < 1 - stability_threshold. Default 0.95.

informative_threshold

A pathway is informative when the share of resamples with a significant G^2 is at least this. Default 0.80.

alpha

Significance level of the G^2 test against the parent context. Default 0.05.

ci_level

Total tail probability of the percentile intervals. Default 0.05 (95% intervals).

seed

Seed for the resampling, or NULL to use the current random-number state. Default 1. A non-NULL seed sets the session's random-number state.

keep_resamples

Keep the per-resample values (default TRUE); needed by as.data.frame(x, what = "resamples") and plot_pathway_resamples(). FALSE saves memory and leaves the summary table unchanged.

progress

Show a progress bar. Default FALSE.

Value

An object of class transitiontrees_bootstrap. as.data.frame(x) (or summary(x)) returns one row per pathway of the original tree, stable and informative pathways first, with columns pathway, depth, count, likely_next, next_probability, divergence (bits), changes_prediction, G2 (NA for the root), p_stability, stability_rate, stable, informative_rate, informative, flip_consistency (share of resamples reproducing changes_prediction), and for each of count, next_probability, divergence and G2 the bootstrap mean_*, sd_*, ci_*_lo and ci_*_hi. as.data.frame(x, what = "resamples") returns the per-resample values; plot() draws the G^2 intervals.

Conditions

transitiontrees_bad_input

(error) tree is not a transitiontrees object, or has no pathways.

transitiontrees_weighted_unsupported

(error) the tree was fitted with weights, which resampling would drop.

transitiontrees_no_data

(error) the tree does not carry its sequences.

References

Saqr, M., López-Pernas, S., Törmänen, T., Kaliisa, R., Misiejuk, K., & Tikka, S. (2025). Transition network analysis: A novel framework for modeling, visualizing, and identifying the temporal patterns of learners and learning processes. In Proceedings of the 15th International Learning Analytics and Knowledge Conference (LAK '25) (pp. 351-361). doi:10.1145/3706468.3706513

Efron, B., & Tibshirani, R. J. (1993). An Introduction to the Bootstrap. Chapman & Hall/CRC. doi:10.1201/9780429246593

See Also

as.data.frame.transitiontrees_bootstrap, plot.transitiontrees_bootstrap and plot_pathway_resamples() for the result; tree_pathways() for the observed pathway table; prune_tree() for significance-based pruning.

Examples

tree <- context_tree(trajectories, max_depth = 2)
boot <- bootstrap_pathways(tree, iter = 50)
boot
head(as.data.frame(boot))

List the most frequent pathways of a tree

Description

common_pathways() returns the pathways that occurred most often, optionally at one depth. Frequent pathways are the typical routes through the process: the histories most learners or sessions actually pass through, and the state each of them most often leads to. Frequency says nothing about whether a pathway's prediction differs from that of its shorter suffix; for that, see divergent_pathways().

Usage

common_pathways(tree, top = 10L, depth = NULL, min_count = 1L)

Arguments

tree

A transitiontrees object.

top

Number of pathways to return. Default 10.

depth

Return only pathways of this depth. NULL (default) returns all depths.

min_count

Keep pathways that occurred at least this many times. Default 1.

Value

A data.frame with the columns of tree_pathways(), one row per pathway, sorted by count in decreasing order, at most top rows.

Conditions

transitiontrees_bad_input when tree is not a fitted tree.

See Also

tree_pathways(), divergent_pathways(), sharp_pathways(), plot_pathways().

Examples

tree <- context_tree(trajectories, max_depth = 3)
common_pathways(tree, top = 5)
common_pathways(tree, top = 5, depth = 3)

Test where groups of sequences differ, context by context

Description

compare_groups() tests where groups of sequences, such as high and low achievers or two phases of a course, differ, context by context and for the trees as a whole. Groups can differ in two distinct ways: they can reach the same history and then continue differently (a behavioral difference), or they can reach some histories more often than others do (a usage difference). Both are tested for every context represented in the groups' trees and for the trees as a whole, so that a difference can be located in specific pathways rather than reported as one number.

The behavioral difference at a context is the Jensen-Shannon divergence (Lin, 1991), in bits, between the groups' next-state distributions, each group weighted by its count at that context. The usage difference is a G^2 homogeneity statistic on the context's prevalence: its count against the other windows of the same length in each group. The omnibus statistics are the count-weighted sum of the divergences and the sum of the G^2 values. All p-values come from one label permutation: sequences are pooled, group labels are shuffled with group sizes fixed, and every statistic is recomputed from raw counts. Per-context p-values are adjusted for false discovery rate with the Benjamini-Hochberg (1995) procedure, separately for each axis. When one person contributes several sequences, a block identifier restricts the shuffle to within persons, so the null distribution respects that nesting. The result is a transitiontrees_group_comparison object whose tables are read with as.data.frame(); summary() gives a one-row overview and plot() the largest behavioral differences.

compare_groups() handles two or more groups. For one overall distance between two trees with a permutation test, use compare_trees(); it measures the symmetric Kullback-Leibler divergence, not the Jensen-Shannon divergence used here. plot_difference() maps the per-context differences of two groups next state by next state.

Usage

compare_groups(group, iter = 999L, min_count = 1L, seed = 1L, block = NULL)

Arguments

group

A transitiontrees_group of unweighted trees, from context_tree(..., group = ).

iter

Number of label permutations. Default 999.

min_count

Contexts with a total count across groups below this are dropped from the table. Default 1.

seed

Seed for the permutations, or NULL to use the current random-number state. Default 1. A non-NULL seed sets the session's random-number state.

block

Block identifiers for a stratified permutation, one per sequence in group-then-row order. Default NULL: the block stored by context_tree(..., block = ) is used when present, and labels are shuffled freely otherwise.

Value

An object of class transitiontrees_group_comparison. Its tables are returned by as.data.frame(): what = "pathways" gives one row per tested context with columns pathway, depth, count_total, one count_<group> and one modal_<group> column per group (the most likely next state), flips (whether the groups' modal next states differ), jsd_bits, jsd_p, jsd_padj, usage_g2, usage_p and usage_padj (NA for the root, which has no usage test), sorted by jsd_bits; what = "omnibus" gives one row per axis; and what = "distance" gives one row per pair of groups with their tree_distance(). summary() returns a one-row overview and plot() the largest behavioral differences.

Conditions

transitiontrees_bad_input

(error) group is not a transitiontrees_group, has fewer than two groups, or block does not have one entry per sequence.

transitiontrees_weighted_unsupported

(error) a member tree was fitted with weights; the permutation recounts the raw sequences and would drop them.

transitiontrees_degenerate_permutation

(warning) no block contains more than one group, so the stratified shuffle cannot move any label.

References

Lin, J. (1991). Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1), 145-151. doi:10.1109/18.61115

Benjamini, Y., & Hochberg, Y. (1995). Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society: Series B (Methodological), 57(1), 289-300. doi:10.1111/j.2517-6161.1995.tb02031.x

See Also

summary.transitiontrees_group_comparison, as.data.frame.transitiontrees_group_comparison and plot.transitiontrees_group_comparison for the result; compare_trees() for the pairwise test; plot_difference() for the next-state difference map.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
cmp <- compare_groups(grp, iter = 20)
cmp
summary(cmp)

Compare pruning criteria on one tree

Description

compare_pruning() prunes one fitted tree under each of several criteria and reports how many contexts each keeps. The table shows how strongly the criteria differ on the data at hand before one of them is applied with prune_tree(); the criteria themselves are described there. A smaller tree is not by itself a better one: to compare pruned trees by how well they predict new sequences, use tune_tree().

Usage

compare_pruning(
  tree,
  criterion = c("G2", "KL", "AIC", "BIC"),
  alpha = 0.05,
  threshold = 0.005
)

Arguments

tree

A transitiontrees object, usually unpruned.

criterion

Criteria to compare. Default all four: "G2", "KL", "AIC", "BIC".

alpha

Significance level for "G2". Default 0.05.

threshold

Minimum divergence in nats for "KL". Default 0.005.

Value

A data.frame with one row per criterion, in the order of criterion, and columns criterion, n_nodes (contexts kept, root included) and reduction_pct (percentage of the original contexts removed).

Conditions

transitiontrees_bad_input when tree is not a fitted tree, criterion is not a non-empty character vector, or alpha or threshold is invalid.

See Also

prune_tree(), plot_pruning(), tune_tree(), compare_smoothing().

Examples

tree <- context_tree(trajectories, max_depth = 4)
compare_pruning(tree)
compare_pruning(tree, criterion = c("G2", "BIC"), alpha = 0.01)

Compare smoothing schemes on one dataset

Description

compare_smoothing() fits a tree under each of several smoothing schemes, with every other setting held fixed, and reports one row per scheme with the size of the tree and its in-sample perplexity. Given an already fitted tree, it re-smooths that tree under each scheme instead, which keeps its contexts, for example after pruning.

The number of contexts is the same for every scheme, because smoothing changes probabilities, not which contexts exist. In-sample perplexity favors schemes that stay close to the observed proportions and therefore is not a criterion for choosing one; tune_tree() compares schemes on held-out data. See smooth_tree() for the definitions of the schemes.

Usage

compare_smoothing(
  data,
  smoothing = c("floor", "laplace", "kneser_ney", "witten_bell", "jelinek_mercer"),
  ...
)

Arguments

data

Sequences in any form accepted by context_tree(), fitted afresh under each scheme, or a fitted transitiontrees, re-smoothed under each scheme.

smoothing

Names of the schemes to compare. Default all five: "floor", "laplace", "kneser_ney", "witten_bell", "jelinek_mercer", each with its default hyperparameters.

...

Further arguments to context_tree(), such as max_depth and min_count, held fixed across schemes. Not used when data is a fitted tree.

Value

A data.frame with one row per scheme, in the order of smoothing, and columns smoothing, n_nodes (number of contexts) and perplexity (in-sample).

Conditions

transitiontrees_bad_input when smoothing is not a non-empty character vector of known methods, or when data cannot be fitted (see context_tree()).

References

Chen, S. F., & Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech and Language, 13(4), 359-393. doi:10.1006/csla.1999.0128

See Also

smooth_tree() for the schemes; tune_tree() for cross-validated selection; compare_pruning() for the analogous comparison of pruning criteria.

Examples

compare_smoothing(trajectories, max_depth = 3)
compare_smoothing(trajectories, smoothing = c("floor", "kneser_ney"),
                  max_depth = 2, min_count = 10)

Test whether two context trees differ, with a permutation test

Description

compare_trees() tests whether two fitted context trees, one per group, predict differently overall, with a permutation test. The test statistic is the count-weighted symmetric Kullback-Leibler divergence between the trees' next-state distributions, the quantity returned by tree_distance(); two groups of sequences can pass through the same states and still differ in what tends to follow a given history.

The divergence has no known sampling distribution and is positive even when both groups come from one process, so the reference distribution is built by permutation. The sequences of the two trees are pooled, reassigned at random to two groups of the original sizes, and two trees are refitted with each original tree's depth, minimum count, smoothing and pruning; this is repeated iter times. The p-value is the share of permuted distances at least as large as the observed one, counting the observed value once ((1 + b) / (iter + 1)). A per-context table shows which histories contribute most to the distance. The result is a transitiontrees_comparison object, read with as.data.frame() and summary() and drawn with plot().

The comparison is pairwise and treats sequences as exchangeable. For more than two groups, for separate tests of what follows a context and how often it is reached, for per-context p-values with false discovery rate control, or for a permutation stratified by person when one person contributes several sequences, use compare_groups().

Usage

compare_trees(tree_a, tree_b = NULL, iter = 200L, seed = 1L, symmetric = TRUE)

Arguments

tree_a, tree_b

Unweighted transitiontrees objects fitted to the two groups. Alternatively a transitiontrees_group with two groups as tree_a and tree_b = NULL (default); its two trees are compared in group order.

iter

Number of permutations. Default 200.

seed

Seed for the permutations. Default 1. The call sets the session's random-number state.

symmetric

TRUE (default) for the symmetric divergence; FALSE for D_{KL}(A \| B) alone.

Value

An object of class transitiontrees_comparison. Its tables are returned by as.data.frame(x, what = "pathways") (one row per context in either tree: counts in each tree and the two directed and the symmetric divergence) and as.data.frame(x, what = "null") (one row per permutation); summary() gives one row with the observed distance, the null mean, standard deviation and 95th percentile, and the p-value; plot() draws the null distribution.

Conditions

transitiontrees_bad_input

(error) an argument is not a transitiontrees object; tree_b missing; a transitiontrees_group without exactly two groups, or given together with tree_b; iter not a positive number.

transitiontrees_weighted_unsupported

(error) a tree was fitted with weights; the permutation refits from the raw sequences and would drop them.

transitiontrees_alphabet_mismatch

(error) the trees have different alphabets.

See Also

summary.transitiontrees_comparison, as.data.frame.transitiontrees_comparison and plot.transitiontrees_comparison for the result; tree_distance() for the distance alone; compare_groups() for several groups and per-context tests.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
cmp <- compare_trees(grp, iter = 20)
cmp
summary(cmp)

Fit a variable-order transition tree

Description

context_tree() fits a variable-order transition tree to a set of sequences. The tree, known in the literature as a prediction suffix tree (Ron, Singer & Tishby, 1996) or a variable-length Markov chain (Bühlmann & Wyner, 1999), describes how the next state of a process depends on the states that precede it, while letting the amount of history that matters differ from one history to another. Each node of the tree is a context, or pathway: the most recent states, read from oldest to newest ("A -> B -> C"). The root holds the marginal distribution of states; its children condition on the last state, their children on the last two states, and so on. The tree shows how much of the past is needed to predict what comes next, and along which pathways a longer history changes the prediction.

It counts every context of up to max_depth states that occurs at least min_count times and estimates, for each, the conditional distribution of the next state, smoothed so that unobserved continuations keep a small probability. Sequences may be given as a wide table or matrix (one row per sequence, one column per time point), a list of character vectors, a long event log (one row per event; name the state column in action), or a fitted network object from tna or Nestimate that carries its sequences. With group, or with a grouped network object, one tree is fitted per group over a shared set of states. With the default floor smoothing, the fitted counts and probabilities match those of the PST package (Gabadinho & Ritschard, 2016). It returns a transitiontrees object, or a transitiontrees_group with one tree per group.

The tree is returned unpruned: every context that clears min_count is kept. Use prune_tree() to retain only the contexts whose prediction differs from that of their shorter suffix, tune_tree() to choose max_depth, min_count and the smoothing scheme by cross-validation, and tree_pathways() or as.data.frame() to read the fitted contexts as a table. Group differences are tested with compare_groups(), and the stability of individual pathways with bootstrap_pathways().

Usage

context_tree(
  data,
  max_depth = 5L,
  min_count = 5L,
  smoothing = "floor",
  alphabet = NULL,
  weights = NULL,
  group = NULL,
  block = NULL,
  actor = NULL,
  time = NULL,
  action = NULL,
  order = NULL,
  session = NULL,
  time_threshold = 900
)

Arguments

data

Sequences: a wide data.frame or character matrix (one row per sequence, one column per time point), a list of character vectors, a long event log (with action), or a tna or Nestimate model object that carries its sequence data. NA, "" and the TraMineR codes "%" and "*" mark positions without an observation and are dropped. Numeric matrices are not accepted; convert them to character first.

max_depth

Longest context, in states, that the tree may contain. Default 5.

min_count

Minimum number of occurrences for a context to become a node. Default 5.

smoothing

Smoothing scheme for the next-state probabilities: a method name or a list of the method name and its hyperparameters. Methods are "floor" (default; ymin = 0.001, rule = "interpolate" or "cap"), "laplace" (alpha = 1), "kneser_ney" (discount = 0.75), "witten_bell" and "jelinek_mercer" (lambda = 0.5). See smooth_tree().

alphabet

Character vector of states. NULL (default) uses the states observed in data (for a network object, its node labels). Supply it when new data may contain states unseen here.

weights

Non-negative weight per sequence, one per row or list element of data. NULL (default) fits unweighted.

group

Grouping for one tree per group: a vector with one value per sequence, the name of a column of data (long format) or of a network object's metadata. NULL (default) fits a single tree.

block

Optional block (stratum) identifier in the same forms as group, kept with the fitted group and used by compare_groups() for a stratified permutation test. Default NULL.

actor, time, order, session, time_threshold

Long-format arguments passed to prepare_input(): the column identifying whose events form a sequence, the timestamp column, an ordering column, a session column, and the gap in seconds that starts a new session (default 900). Each defaults to NULL.

action

Name of the state column of a long event log. Giving it reshapes data with prepare_input() before fitting. Default NULL (data is already in sequence form).

Value

An object of class transitiontrees, the fitted tree. Read it through its accessors: as.data.frame() or tree_pathways() for one row per context, state_frequencies() for the state counts, model_fit() for the log-likelihood, information criteria and perplexity, and n_nodes() for the number of contexts. With group, or a grouped input, an object of class transitiontrees_group: one transitiontrees per group, in group order, summarized by summary() with one row per group and flattened by as.data.frame() to one row per group and context.

Conditions

transitiontrees_bad_input when max_depth or min_count is not a single valid number, data has an unsupported type or no usable sequence, a named column is absent, weights, group or block do not have one entry per sequence, a network object carries no sequence data, or the smoothing specification is invalid.

References

Bühlmann, P., & Wyner, A. J. (1999). Variable length Markov chains. The Annals of Statistics, 27(2), 480-513. doi:10.1214/aos/1018031204

Gabadinho, A., & Ritschard, G. (2016). Analyzing state sequences with probabilistic suffix trees: The PST R package. Journal of Statistical Software, 72(3). doi:10.18637/jss.v072.i03

Ron, D., Singer, Y., & Tishby, N. (1996). The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning, 25(2-3), 117-149. doi:10.1023/A:1026490906255

See Also

prune_tree() and smooth_tree() to refine a fitted tree; tune_tree() to choose its settings; tree_pathways() to read it; plot.transitiontrees() to draw it; compare_groups() to compare groups.

Examples

# Wide sequences: one learner per row, one time point per column
tree <- context_tree(trajectories, max_depth = 3)
tree
as.data.frame(tree)

# A long event log, split into sessions at gaps over 15 minutes
context_tree(group_regulation_long, actor = "Actor", time = "Time",
             action = "Action", max_depth = 2)

# One tree per achievement group over a shared set of states
groups <- context_tree(group_regulation_long, actor = "Actor",
                       time = "Time", action = "Action",
                       group = "Achiever", max_depth = 2)
summary(groups)


List the pathways whose history most changes the prediction

Description

divergent_pathways() returns the pathways whose next-state distribution departs most from that of their parent, the same pathway without its oldest state, measured by the Kullback-Leibler divergence in bits. These are the places where remembering one more state of history changes what is expected next, and therefore where the process depends on more than its most recent state. With flips_only = TRUE, only pathways whose most likely next state differs from the parent's are returned.

Divergence is computed from smoothed probabilities and can be large for rare pathways; set min_count to exclude them, and use bootstrap_pathways() to check whether a divergence is stable under resampling. The root, which has no parent, is never returned.

Usage

divergent_pathways(tree, top = 10L, min_count = 1L, flips_only = FALSE)

Arguments

tree

A transitiontrees object.

top

Number of pathways to return. Default 10.

min_count

Keep pathways that occurred at least this many times. Default 1.

flips_only

Return only pathways whose most likely next state differs from the parent's. Default FALSE.

Value

A data.frame with the columns of tree_pathways(), one row per pathway, sorted by divergence in decreasing order, at most top rows.

Conditions

transitiontrees_bad_input when tree is not a fitted tree.

See Also

tree_pathways(), tree_dependence(), plot_divergence(), bootstrap_pathways().

Examples

tree <- context_tree(trajectories, max_depth = 3)
divergent_pathways(tree, top = 5, min_count = 20)
divergent_pathways(tree, flips_only = TRUE)

Student engagement sequences (wide format)

Description

engagement is a synthetic dataset of the engagement states of 1,000 students over a study program, generated to resemble the engagement trajectories analyzed by Saqr, López-Pernas, Helske and Hrastinski (2023). It has one row per student and one column per time point (23 to 25 observed states per student). Each state is "Active", "Average" or "Disengaged"; missing values occur only at the end of a row.

Usage

engagement

Format

A data.frame with 1,000 rows (students) and 25 character columns T1 to T25, holding "Active", "Average", "Disengaged" or NA.

Source

The engagement sequence object of the tna package, converted to character with its void and missing codes set to NA (identical values).

References

Saqr, M., López-Pernas, S., Helske, S., & Hrastinski, S. (2023). The longitudinal association between engagement and achievement varies by time, students' profiles, and achievement state: A full program study. Computers & Education, 199, 104787. doi:10.1016/j.compedu.2023.104787

See Also

trajectories for a smaller engagement dataset; context_tree().

Examples

tree <- context_tree(engagement, max_depth = 3, min_count = 20)
tree
divergent_pathways(tree, top = 5)

Generate sequences from a fitted transition tree

Description

generate_sequences() draws new sequences from the process described by a fitted tree. Each sequence starts from a state drawn from the overall distribution of states (or from a given first state), and each further state is drawn from the next-state distribution of the longest context of the tree that matches the states generated so far. Generated sequences can be compared with the observed ones to check whether the tree reproduces features of the data that it was not fitted to directly, such as run lengths or the time spent in each state.

Draws use the session's random number generator; call set.seed() first, or use simulate.transitiontrees() with seed, for reproducible sequences. It returns one sequence per row, as a character matrix or, with tidy = TRUE, a data frame.

Usage

generate_sequences(tree, n = 5L, length = 10L, start = NULL, tidy = FALSE)

Arguments

tree

A transitiontrees object.

n

Number of sequences. Default 5.

length

Number of states in each sequence. Default 10.

start

First state of each sequence, a character vector of length n. NULL (default) draws it from the root distribution.

tidy

Return a data.frame rather than a matrix. Default FALSE.

Value

With tidy = TRUE, a data.frame with one row per sequence and columns T1 to T<length>, which context_tree() accepts as input. With tidy = FALSE, a character matrix with the same layout.

Conditions

transitiontrees_bad_input when tree is not a fitted tree, n or length is not a single positive number, or start does not have length n.

See Also

simulate.transitiontrees(), predict.transitiontrees().

Examples

tree <- context_tree(trajectories, max_depth = 3)
set.seed(1)
generate_sequences(tree, n = 5, length = 12, tidy = TRUE)

Regulation of collaborative learning (long event log)

Description

group_regulation_long is a coded dataset of the regulation actions of 2,000 students working in 200 small groups across three courses, one row per action with a timestamp. Each action is one of nine regulation moves: adapt, cohesion, consensus, coregulate, discuss, emotion, monitor, plan and synthesis. Each student is classified as a high or low achiever (1,000 each), which makes the data suited to comparing the regulation pathways of two groups.

The data are in long format. Name the columns in context_tree() (actor = "Actor", time = "Time", action = "Action") or reshape them with prepare_input(); with the default 15-minute session gap, each student's actions form one sequence of 2 to 26 actions.

Usage

group_regulation_long

Format

A data.frame with 27,533 rows (actions) and 6 columns:

Actor

Integer student identifier, 1 to 2,000.

Achiever

Achievement level, "High" or "Low", constant within a student.

Group

Numeric collaboration group, 1 to 200; each student belongs to one group.

Course

Course, "A", "B" or "C".

Time

POSIXct timestamp of the action.

Action

The regulation move, the state of the sequence.

Source

Identical to group_regulation_long in the tna package (there a tibble), where it is described as generated synthetically from that package's group_regulation data.

See Also

compare_groups(), prepare_input().

Examples

groups <- context_tree(group_regulation_long, actor = "Actor",
                       time = "Time", action = "Action",
                       group = "Achiever", max_depth = 2)
summary(groups)

Fill in missing states of incomplete sequences

Description

impute_sequences() fills in the missing states of incomplete sequences from a fitted tree. Sequences recorded over time often have gaps: positions at which the state was not observed although the sequence continues afterwards. The tree gives, for each gap, a distribution of the missing state conditional on the states observed before it, which is used to fill the gap with the most likely state or with a random draw.

Gaps are filled from left to right. Each gap is predicted from the longest context of the tree that matches the states before it, and a filled state becomes part of the history for the gaps that follow. Only gaps followed by an observed state are filled: missing positions at the end of a sequence mark where it stops, and a sequence with no observed state is returned unchanged. The prediction uses past states only; the states observed after a gap do not inform it.

With method = "modal" the result is deterministic and the filled states are the single most likely ones, which understates the variability of the process; with method = "prob" the states are drawn from the predicted distribution, and repeated imputations with different seeds reflect the uncertainty of the filled values. It returns newdata in the same form with its internal gaps filled.

Usage

impute_sequences(tree, newdata, method = c("modal", "prob"), seed = NULL)

Arguments

tree

A transitiontrees object.

newdata

Sequences with gaps, marked by NA or "": a list of character vectors, a character matrix or data.frame with one sequence per row, or a single character vector.

method

"modal" (default) fills each gap with the most likely state; "prob" draws it from the predicted distribution.

seed

Random seed for method = "prob", set locally without changing the session's random number stream. NULL (default) uses the current stream.

Value

newdata in the same form (list, matrix, data.frame or vector) with its internal gaps filled.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or newdata is not a list, matrix, data.frame or character vector.

See Also

predict.transitiontrees(), generate_sequences().

Examples

tree <- context_tree(trajectories, max_depth = 3)
gappy <- list(c("Active", NA, "Active", "Average"),
              c("Disengaged", "Disengaged", NA, NA, "Average", NA))
impute_sequences(tree, gappy)
impute_sequences(tree, gappy, method = "prob", seed = 1)

Compute the log-likelihood of a transition tree

Description

logLik() computes the log-likelihood of a fitted tree: the sum, over every observed position, of the log probability that the tree assigned to the state that occurred, given the longest context of the tree that matches the preceding history. It is the basis of the information criteria and of perplexity, and allows trees with different depths, pruning or smoothing to be compared on the same data.

Without newdata, the log-likelihood is computed in-sample from the fitted counts. With newdata, the sequences are scored under the fitted tree, which gives the held-out log-likelihood. A state that is not among the tree's states is not scored, and the position after it is predicted from the root; the reported number of observations counts only scored positions. The number of parameters is the number of contexts times k - 1, for k states.

The result is a logLik object and works with AIC() and BIC(). model_fit() returns log-likelihood, AIC, BIC and perplexity together as a table.

Usage

## S3 method for class 'transitiontrees'
logLik(object, newdata = NULL, ...)

Arguments

object

A transitiontrees object.

newdata

Sequences to score, in any form accepted by context_tree(). NULL (default) gives the in-sample log-likelihood.

...

Not used.

Value

An object of class logLik: the log-likelihood (natural logarithm), with attributes df (number of parameters) and nobs (number of scored positions).

Conditions

transitiontrees_bad_input when newdata has an unsupported type or no usable sequence.

See Also

model_fit(), perplexity(), score_sequences(), nobs.transitiontrees().

Examples

tree <- context_tree(trajectories, max_depth = 2)
logLik(tree)
AIC(tree)
logLik(tree, newdata = engagement)

Find the contexts that make a given next state likely or unlikely

Description

mine_contexts() finds the contexts that make a given next state likely or unlikely. It scans every context of a fitted tree for the probability it gives one chosen next state and returns the contexts whose probability lies in a requested range, from the highest probability down. This serves questions about one outcome state, such as after which histories disengagement is most likely, or after which histories a learner almost never returns to planning.

Each row reports the context, its depth and count, the probability of the chosen state after it, and whether that state is the context's most likely next state. Probabilities in rare contexts are imprecise; set min_count to keep only contexts with enough occurrences. To compare the state's probability across groups, fit a grouped tree and use compare_groups().

Usage

mine_contexts(tree, state, min_prob = NULL, max_prob = NULL, min_count = 1L)

Arguments

tree

A transitiontrees object.

state

The next state of interest, one of the tree's states.

min_prob, max_prob

Keep contexts whose probability of state is at least min_prob and at most max_prob. NULL (default) leaves that bound open.

min_count

Keep contexts that occurred at least this many times. Default 1.

Value

A data.frame with one row per context and columns pathway, depth, count, state, prob (probability of state after the context) and is_modal (whether state is the most likely next state), sorted by prob and then count, both decreasing. No matching context gives a zero-row table with these columns.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or state is not a single one of its states.

See Also

query_pathway(), sharp_pathways(), mine_sequences().

Examples

tree <- context_tree(trajectories, max_depth = 3)
mine_contexts(tree, state = "Disengaged", min_prob = 0.4, min_count = 10)
mine_contexts(tree, state = "Active", max_prob = 0.05)

Find the least and most typical sequences

Description

mine_sequences() ranks sequences by how well a fitted tree predicts them and returns the top n. With which = "surprising", the sequences with the highest perplexity come first: those whose transitions the tree finds least expected, which are candidates for atypical cases or for patterns that the fitting data did not contain. With which = "expected", the sequences with the lowest perplexity come first: the most typical sequences under the tree.

The ranking is by per-sequence perplexity from score_sequences(), which adjusts for sequence length. When newdata are the fitting sequences themselves, the ranking describes typicality within the data; with other sequences it describes how well the tree generalizes to them. To find where within a sequence the unexpected moves occur, use score_positions().

Usage

mine_sequences(tree, newdata, n = 10L, which = c("surprising", "expected"))

Arguments

tree

A transitiontrees object.

newdata

Sequences to rank, in any form accepted by context_tree().

n

Number of sequences to return. Default 10.

which

"surprising" (default; highest perplexity first) or "expected" (lowest perplexity first).

Value

A data.frame with the columns of score_sequences() (sequence_id, n_scored, log_lik, perplexity), one row per sequence, at most n rows.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or newdata has no usable sequence.

See Also

score_sequences(), score_positions(), mine_contexts().

Examples

tree <- context_tree(trajectories, max_depth = 2)
mine_sequences(tree, engagement, n = 5)
mine_sequences(tree, engagement, n = 5, which = "expected")

Summarize the fit of a transition tree

Description

model_fit() returns the fit statistics of a tree as one row: log-likelihood, number of parameters, number of scored positions, AIC, BIC and perplexity. The row puts trees with different depths, pruning or smoothing on a common footing, and for a group of trees gives one row per group.

Without newdata the statistics are in-sample. With newdata every statistic is computed on those sequences, with AIC and BIC formed from the held-out log-likelihood and the tree's number of parameters. The number of parameters is the number of contexts times k - 1, for k states (see logLik.transitiontrees()).

Usage

model_fit(tree, newdata = NULL)

Arguments

tree

A transitiontrees or transitiontrees_group object.

newdata

Sequences to evaluate the tree on. NULL (default) evaluates it in-sample.

Value

A data.frame with columns logLik, df, nobs, AIC, BIC and perplexity: one row for a tree, or one row per group, with a leading group column, for a transitiontrees_group. When no position can be scored, the statistics are NA.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or group, or newdata has no usable sequence.

See Also

logLik.transitiontrees(), perplexity(), summary.transitiontrees_group(), tune_tree().

Examples

tree <- context_tree(trajectories, max_depth = 3)
model_fit(tree)
model_fit(prune_tree(tree))

Count the contexts of a transition tree

Description

n_nodes() returns the number of contexts (nodes) in a fitted tree, the root included: the number shown in the printed header and a direct measure of the tree's complexity, for example before and after pruning.

Usage

n_nodes(tree)

Arguments

tree

A transitiontrees or transitiontrees_group object.

Value

A single integer; for a transitiontrees_group, a named integer vector with one count per group.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or group.

See Also

prune_tree(), compare_pruning(), summary.transitiontrees_group().

Examples

tree <- context_tree(trajectories, max_depth = 3)
n_nodes(tree)
n_nodes(prune_tree(tree))

Count the observations a transition tree was fitted on

Description

nobs() returns the number of observed positions in the sequences the tree was fitted on, the number used by BIC(). For a weighted fit it is the weighted total. A held-out log-likelihood, logLik(tree, newdata), carries its own count of scored positions.

Usage

## S3 method for class 'transitiontrees'
nobs(object, ...)

Arguments

object

A transitiontrees object.

...

Not used.

Value

A single integer.

See Also

logLik.transitiontrees(), model_fit().

Examples

tree <- context_tree(trajectories, max_depth = 2)
nobs(tree)

Test whether a pathway is a context of the tree

Description

pathway_exists() reports whether a history is itself a context (node) of the fitted tree, that is, whether it occurred at least min_count times and, for a pruned tree, survived pruning. A history that is not a context is still predicted, from its longest suffix in the tree; see query_pathway().

Usage

pathway_exists(tree, pathway)

Arguments

tree

A transitiontrees object.

pathway

The history, oldest state first: a string in arrow notation or a character vector.

Value

A single logical value.

Conditions

transitiontrees_bad_input when tree is not a fitted tree.

See Also

query_pathway(), subtree(), tree_pathways().

Examples

tree <- context_tree(trajectories, max_depth = 3)
pathway_exists(tree, "Active -> Disengaged -> Active")
pathway_exists(prune_tree(tree), "Active -> Disengaged -> Active")

Compute the perplexity of a transition tree

Description

perplexity() computes the perplexity of a fitted tree: the exponential of the negative mean log-likelihood per observed position, \exp(-\ell / n). It reads as an effective number of equally likely next states: a perplexity of k for k states means the tree predicts no better than chance, and a perplexity of 1 means every next state is predicted with certainty. Lower values indicate better prediction.

In-sample perplexity (without newdata) favors deep, lightly smoothed trees that reproduce the fitting data; held-out perplexity, computed on sequences not used for fitting, measures how well the tree generalizes. It returns a single number. tune_tree() uses cross-validated perplexity to choose a tree's settings.

Usage

perplexity(tree, newdata = NULL)

Arguments

tree

A transitiontrees object.

newdata

Sequences to score, in any form accepted by context_tree(). NULL (default) gives in-sample perplexity.

Value

A single number; NA when no position could be scored.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or newdata has no usable sequence.

See Also

model_fit(), score_sequences(), tune_tree(), plot_predictive().

Examples

tree <- context_tree(trajectories, max_depth = 2)
perplexity(tree)
perplexity(tree, newdata = engagement)

Plot a context tree

Description

plot() draws a fitted context tree. A context tree organizes the histories that precede each state: the root holds the overall distribution of states; each child extends its parent's history by one earlier state; and every node carries the distribution of the next state given that history. A drawing of the tree shows which histories occur often enough to be modeled, how far back the model's memory reaches along each branch, and where branches stop because a longer history was too rare or, after pruning, added nothing to the prediction.

Four drawings are available. "horizontal" (the default) is a left-to-right tree with depth on the x-axis; each node is labeled with its full history and, by default, its most likely next state and that state's probability, and is filled by the most recent state of the history. "dendrogram" is a radial tree with the root at the center, each node filled by the state its depth adds to the history. "icicle" is a sunburst: rings are depths, the angular width of an arc is proportional to the summed count of the deepest histories beneath it, and the fill is the state the ring adds to the history. "interactive" is a visNetwork widget with draggable nodes and a tooltip that gives each node's count and full next-state distribution. In the node-link drawings, node size is the count of the history and edge width the count of the child history. The first three drawings are ggplot objects; the interactive one is an htmlwidget.

The context tree reads backwards in time: every history ends at the moment of prediction. For the forward view, sequences followed from their first state, use plot_trajectories(). The next-state probabilities of many pathways are compared more easily in plot_pathways() or plot_distributions(), and differences between two groups in plot_difference().

Usage

## S3 method for class 'transitiontrees'
plot(
  x,
  style = c("horizontal", "dendrogram", "icicle", "interactive"),
  point_size_range = NULL,
  edge_size_range = NULL,
  ...
)

Arguments

x

A transitiontrees object.

style

"horizontal" (default), "dendrogram", "icicle" or "interactive".

point_size_range

Smallest and largest node size. Default NULL: c(4, 14) for "horizontal", c(5, 16) for "dendrogram", c(10, 45) pixels for "interactive". Not used by "icicle".

edge_size_range

Thinnest and thickest edge. Default NULL: c(0.3, 2.5) for the static drawings, c(1, 10) pixels for "interactive". Not used by "icicle".

...

Options of the chosen drawing. "horizontal": show_prediction (default TRUE) adds the most likely next state to each label. "icicle": label_min_fraction (default 0.03) and label_abbrev_fraction (default 0.08), the arc shares below which a label is omitted or abbreviated; abbrev_len (default 2) or abbrev_fun (default NULL) for the abbreviation; gap_size (default 5) and gap_size_within (default 0.3), the widths of the white lines between first-level wedges and between arcs; jitter (default 0.04) and jitter_seed (default 1), a small random variation of the outer edge (0 for none). "interactive": width and height of the widget.

Value

A ggplot object for "horizontal", "dendrogram" and "icicle"; a visNetwork htmlwidget for "interactive".

Conditions

transitiontrees_empty_result

(error) the tree has no nodes.

transitiontrees_missing_package

(error) "interactive" without the visNetwork package installed.

See Also

plot.transitiontrees_group for one plot per group; plot_trajectories() for the forward tree; plot_pathways(), plot_distributions() and plot_pruning() for next-state distributions.

Examples

tree <- context_tree(trajectories, max_depth = 2)
plot(tree)
plot(tree, show_prediction = FALSE)
plot(tree, style = "dendrogram")
plot(tree, style = "icicle")
if (requireNamespace("visNetwork", quietly = TRUE)) {
  widget <- plot(tree, style = "interactive")
}

Plot bootstrap intervals of pathway informativeness

Description

plot() draws a forest plot of each pathway's likelihood-ratio statistic G^2 against its parent context: the bootstrap mean with its percentile interval, one row per pathway, colored and ordered by whether the pathway is stable, informative, both or neither. A dashed line marks the chi-square critical value used by the bootstrap; a pathway whose interval lies wholly to its right departs reproducibly from its shorter history.

Usage

## S3 method for class 'transitiontrees_bootstrap'
plot(x, top = 25L, min_stability = NULL, ...)

Arguments

x

A transitiontrees_bootstrap object.

top

Maximum number of pathways shown. Default 25.

min_stability

Smallest stability_rate shown. Default NULL: the stability_threshold of the bootstrap.

...

Ignored.

Value

A ggplot object: one row per pathway with the mean G^2 and its interval.

Conditions

transitiontrees_empty_result

(error) no pathway with a G^2 reaches min_stability.

See Also

bootstrap_pathways(), plot_pathway_resamples() for the resample distributions.

Examples

boot <- bootstrap_pathways(context_tree(trajectories, max_depth = 2),
                           iter = 50)
plot(boot, min_stability = 0.5)

Plot the permutation distribution of a two-tree comparison

Description

plot() draws the permutation null distribution of the distance between two context trees as a histogram, with the observed distance as a vertical line and the permutation p-value in the subtitle. An observed line far in the right tail indicates that the two groups predict differently beyond what random reassignment of sequences produces.

Usage

## S3 method for class 'transitiontrees_comparison'
plot(x, bins = 30L, ...)

Arguments

x

A transitiontrees_comparison object from compare_trees().

bins

Number of histogram bins. Default 30.

...

Ignored.

Value

A ggplot object: a histogram of the permuted distances with the observed distance marked.

See Also

compare_trees(), as.data.frame.transitiontrees_comparison for the permuted values.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
plot(compare_trees(grp, iter = 20), bins = 10)

Plot the context tree of each group

Description

plot() draws every tree of a transitiontrees_group with plot.transitiontrees, one figure per group with the group name as caption, so that the memory structure of the groups can be compared side by side. Each figure is printed as it is made. To test or map the differences between groups use compare_groups() and plot_difference().

Usage

## S3 method for class 'transitiontrees_group'
plot(x, ...)

Arguments

x

A transitiontrees_group object.

...

Passed to plot.transitiontrees, such as style.

Value

Invisibly, a named list with one plot per group, in group order: ggplot objects, or htmlwidgets for style = "interactive".

See Also

plot.transitiontrees; plot_difference() and compare_groups() for the differences between groups.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
plot(grp, show_prediction = FALSE)

Plot the context-level differences between groups

Description

plot() draws a compare_groups() result in one of two ways. The default lollipop chart ranks the contexts by the Jensen-Shannon divergence between the groups' next-state distributions, with point size for the context's count and color separating contexts whose adjusted p-value is below alpha; it shows where, given the same history, the groups continue differently. style = "matrix" draws the pairwise distances between groups as a labeled heatmap.

Usage

## S3 method for class 'transitiontrees_group_comparison'
plot(x, style = c("divergence", "matrix"), top = 15L, alpha = 0.05, ...)

Arguments

x

A transitiontrees_group_comparison object.

style

"divergence" (default) for the ranked contexts, or "matrix" for the between-group distance heatmap.

top

Number of contexts shown by "divergence". Default 15.

alpha

False discovery rate cutoff for highlighting. Default 0.05.

...

Ignored.

Value

A ggplot object: for "divergence", one row per context with its divergence in bits; for "matrix", one tile per pair of groups with its symmetric Kullback-Leibler distance printed.

Conditions

transitiontrees_empty_result

(error) for "divergence", no context has a positive divergence.

See Also

compare_groups(); plot_difference() for the next-state differences within each context.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
cmp <- compare_groups(grp, iter = 20)
plot(cmp, alpha = 0.1)
plot(cmp, style = "matrix")

Plot the cross-validated perplexity of a tuning grid

Description

plot() draws the held-out perplexity surface of a tune_tree() grid: perplexity against maximum depth, one line per minimum count, with one panel per smoothing method (and per pruning choice when both were tried). The selected configuration is marked with a star. The plot shows where added depth stops lowering held-out perplexity and how sensitive that point is to the other settings.

Usage

## S3 method for class 'transitiontrees_tune'
plot(x, ...)

Arguments

x

A transitiontrees_tune object from tune_tree().

...

Ignored.

Value

A ggplot object: held-out perplexity (y) against max_depth (x), colored by min_count, faceted by smoothing and pruning.

See Also

tune_tree(), summary.transitiontrees_tune.

Examples

tuned <- tune_tree(trajectories, max_depth = 1:3, min_count = c(5, 10),
                   prune = FALSE, folds = 3)
plot(tuned)

Map the next-state differences between two groups

Description

plot_difference() maps the next-state differences between two groups of a transitiontrees_group: where the groups share a history and still continue from it differently. The map has one row per context the groups share and one column per next state. With depth = 1 the map is the difference between the two first-order transition matrices; deeper contexts show whether the difference depends on a longer history.

By default each cell is the Pearson residual of the first group's count of that next state against the count expected if both groups continued alike from that context, (O - E) / \sqrt{E}, with E from the margins of the context's two-group table. Residuals take the context's count into account, and an absolute value above about 2 is notable. measure = "probability" shows the plain difference of next-state probabilities instead. Rows are ordered by their total absolute difference, largest at the top. With a compare_groups() result as comparison, contexts with a significant behavioral difference are starred.

layout = "tree" draws a different quantity: the context tree of the pooled sequences, each node and branch colored by which group reaches that context more often, as a share of the group's observations. The map describes differences; the permutation tests are in compare_groups().

Usage

plot_difference(
  group,
  groups = NULL,
  depth = NULL,
  min_count = 1L,
  comparison = NULL,
  alpha = 0.05,
  annotate = TRUE,
  layout = c("tile", "tree"),
  measure = c("residual", "probability")
)

Arguments

group

A transitiontrees_group object.

groups

The two groups to compare, first minus second. Default NULL: the two groups of a two-group object; required for more groups.

depth

Only contexts of this depth. Default NULL: all shared contexts.

min_count

Contexts with a count below this in either group are dropped. Default 1.

comparison

A transitiontrees_group_comparison from compare_groups(), used to star contexts with jsd_padj < alpha. Default NULL.

alpha

False discovery rate cutoff for the stars. Default 0.05.

annotate

Print the value in each cell ("tile" only). Default TRUE.

layout

"tile" (default) for the heatmap, or "tree" for the pooled tree colored by prevalence difference.

measure

For "tile": "residual" (default) or "probability".

Value

A ggplot object: a heatmap of contexts by next states, or a tree colored by prevalence difference.

Conditions

transitiontrees_bad_input

(error) group is not a transitiontrees_group; groups is missing for more than two groups or does not name two of them; no context is shared at depth and min_count; comparison is not a transitiontrees_group_comparison.

transitiontrees_empty_result

(error) for layout = "tree", the pooled tree is empty.

See Also

compare_groups() for the tests; plot.transitiontrees_group for each group's tree.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
plot_difference(grp)
plot_difference(grp, measure = "probability")
plot_difference(grp, comparison = compare_groups(grp, iter = 20),
                alpha = 0.1)
plot_difference(grp, layout = "tree")

Plot the next-state distribution of each context

Description

plot_distributions() draws the full next-state distribution P(\mathrm{next} \mid \mathrm{context}) of selected contexts as small multiples, one bar chart per context with the most likely next state in a darker shade. The display shows, for each history, whether the next state is close to determined (one tall bar) or open (bars of similar height), and which alternatives remain. By default the most frequent contexts are shown.

The same probabilities are shown for many contexts at once as a heatmap by plot_pathways(), and along one history's chain of shorter suffixes by plot_pruning().

Usage

plot_distributions(tree, contexts = NULL, top = 12L, min_count = 1L)

Arguments

tree

A transitiontrees object.

contexts

Contexts to show, in arrow notation. Default NULL: the top most frequent contexts.

top

Number of contexts when contexts is NULL. Default 12.

min_count

Contexts with a lower count are dropped. Default 1.

Value

A ggplot object with one bar-chart panel per context.

Conditions

transitiontrees_bad_input

(error) tree is not a transitiontrees object.

transitiontrees_empty_result

(error) no context is left to plot.

See Also

plot_pathways(), plot_pruning(); tree_pathways() for the table of contexts.

Examples

tree <- context_tree(trajectories, max_depth = 2)
plot_distributions(tree, top = 6)
plot_distributions(tree, contexts = c("Active", "Active -> Disengaged"))

Plot the pathways whose history changes the prediction most

Description

plot_divergence() ranks pathways by the Kullback-Leibler divergence, in bits, between their next-state distribution and that of their shorter suffix, the context without the earliest state. In a variable-order model a longer history matters only where it changes what is expected next. Each pathway is a lollipop whose point size is its count; points are colored by whether the most likely next state differs from the suffix's, and those pathways are annotated with the new most likely state and its probability. The chart identifies the histories that carry information a shorter memory would lose.

The pathways are those returned by divergent_pathways(). A large divergence on a small count can be a sampling accident; check reproducibility with bootstrap_pathways(), and the pruning decision for one pathway with plot_pruning().

Usage

plot_divergence(tree, top = 15L, min_count = 5L, title = NULL, ...)

Arguments

tree

A transitiontrees object.

top

Number of pathways shown. Default 15.

min_count

Pathways with a lower count are dropped. Default 5.

title

Plot title. Default NULL: a title giving the number of pathways.

...

Ignored.

Value

A ggplot object: one lollipop per pathway, divergence (bits) on the x-axis.

Conditions

transitiontrees_bad_input

(error) tree is not a transitiontrees object.

transitiontrees_empty_result

(error) no pathway reaches min_count.

See Also

divergent_pathways() for the table; plot_pathways(), plot_pruning(), bootstrap_pathways().

Examples

tree <- context_tree(trajectories, max_depth = 3)
plot_divergence(tree, top = 10)

Plot the bootstrap distribution of pathway statistics

Description

plot_pathway_resamples() draws, for each selected pathway, a histogram of one statistic across the bootstrap resamples. The spread of a histogram shows how much the statistic depends on which sequences were sampled; a count histogram with mass near zero marks a pathway that a different sample may not contain.

Usage

plot_pathway_resamples(
  x,
  pathways = NULL,
  stat = c("count", "next_probability", "divergence", "G2"),
  top = 6L,
  bins = 30L
)

Arguments

x

A transitiontrees_bootstrap object fitted with keep_resamples = TRUE.

pathways

Pathways to show, in arrow notation. Default NULL: the first top pathways of the summary table.

stat

"count" (default), "next_probability", "divergence" or "G2".

top

Number of pathways when pathways is NULL. Default 6.

bins

Number of histogram bins. Default 30.

Value

A ggplot object with one histogram panel per pathway.

Conditions

transitiontrees_bad_input

(error) x is not a transitiontrees_bootstrap; the resamples were not kept; a requested pathway is not in the bootstrap.

See Also

bootstrap_pathways(), as.data.frame.transitiontrees_bootstrap for the values.

Examples

boot <- bootstrap_pathways(context_tree(trajectories, max_depth = 2),
                           iter = 50)
plot_pathway_resamples(boot, stat = "count", top = 4, bins = 15)

Plot pathways as a heatmap of next-state probabilities

Description

plot_pathways() draws the pathway table of a context tree as a heatmap: one row per pathway, one column per next state, and the fitted probability P(\mathrm{next} \mid \mathrm{pathway}) as fill. The pathway table lists, for every history, how often it occurs and what tends to follow it. The most likely next state of each row is printed in bold, other probabilities of at least 0.05 in plain text, and pathways whose most likely next state differs from that of their shorter suffix are marked with a leading >. One display then shows which pathways are common, which lead almost always to one state, which leave the next state open, and where a longer history changes the prediction that a first-order model would make.

Rows are the top pathways by count, by divergence from the shorter suffix, or by depth (the root is not shown). For the full distribution of a few contexts as bar charts use plot_distributions(); to rank pathways by how much their history matters use plot_divergence().

Usage

plot_pathways(
  tree,
  top = 20L,
  sort_by = c("count", "divergence", "depth"),
  min_count = 5L,
  show_flips = TRUE,
  title = NULL,
  ...
)

Arguments

tree

A transitiontrees object.

top

Maximum number of pathways shown. Default 20.

sort_by

Order of the rows: "count" (default), "divergence" or "depth" (deepest first).

min_count

Pathways with a lower count are dropped. Default 5.

show_flips

Mark pathways whose most likely next state differs from their parent's. Default TRUE.

title

Plot title. Default NULL: a title naming the ordering.

...

Ignored.

Value

A ggplot object: a heatmap of pathways by next states.

Conditions

transitiontrees_bad_input

(error) tree is not a transitiontrees object.

transitiontrees_empty_result

(error) no pathway reaches min_count.

See Also

tree_pathways() for the table; plot_distributions(), plot_divergence().

Examples

tree <- context_tree(trajectories, max_depth = 3)
plot_pathways(tree, top = 12)
plot_pathways(tree, sort_by = "divergence", top = 12)

Plot how well a context tree predicts new sequences

Description

plot_predictive() plots how much probability a context tree gives to what happens next in sequences it has not seen, the measure of its value as a predictive model. It scores every transition of held-out sequences with score_positions() and shows where the model is confident and where it is surprised.

type = "position" plots the probability given to each observed next state against its position in the sequence. type = "ecdf" plots the empirical cumulative distribution of those probabilities, showing how often the model gives high or low probability to what actually happened. type = "logloss" plots the per-transition log-loss -\log_2 P(\mathrm{observed}) in bits against position, with the mean at each position and the overall mean; 0 bits is a certain and correct prediction.

For one number summarizing held-out prediction use perplexity(), and to choose the settings that minimize it use tune_tree().

Usage

plot_predictive(tree, newdata, type = c("position", "ecdf", "logloss"))

Arguments

tree

A transitiontrees object.

newdata

Held-out sequences in any format accepted by context_tree().

type

"position" (default), "ecdf" or "logloss".

Value

A ggplot object of the scored transitions.

Conditions

transitiontrees_bad_input

(error) tree is not a transitiontrees object.

transitiontrees_empty_result

(error) newdata has no transitions to score.

See Also

score_positions() for the scored transitions as a table; perplexity(); tune_tree().

Examples

tree <- context_tree(trajectories, max_depth = 2)
held_out <- head(engagement, 40)
plot_predictive(tree, held_out)
plot_predictive(tree, held_out, type = "ecdf")
plot_predictive(tree, held_out, type = "logloss")

Plot how much memory one pathway needs

Description

plot_pruning() plots how much memory one pathway needs: how many past states are needed to predict what follows it. A context tree keeps a longer history only when it predicts the next state differently from its shorter suffix, and the plot makes that decision visible for one pathway. It follows the pathway's suffix chain (the full history, then the history without its earliest state, and so on down to the root) and draws the next-state distribution at every link as its own panel, deepest history on the left and the root on the right.

Each context is classified by the G^2 rule of prune_tree(): the likelihood-ratio statistic of its next-state counts against its one-shorter parent is compared with the chi-square critical value at alpha. A context whose own G^2 exceeds it adds memory and is drawn solid; a context below it that is kept only because a deeper context exceeds it is drawn at medium opacity; a context below it with no deeper context exceeding it is pruned and drawn faded. Each panel title gives the context, the decision and G^2. The distributions are the node values reported by tree_pathways() and query_pathway().

Pass an unpruned tree so that the whole chain is visible. To prune the whole tree use prune_tree(); to compare pruning rules use compare_pruning().

Usage

plot_pruning(tree, pathway, alpha = 0.05)

Arguments

tree

A transitiontrees object, usually unpruned.

pathway

One fitted context in arrow notation ("A -> B -> C", earliest state on the left).

alpha

Significance level of the G^2 test. Default 0.05.

Value

A ggplot object with one panel per context of the suffix chain.

Conditions

transitiontrees_bad_input

(error) tree is not a transitiontrees object; alpha is not in (0, 1); pathway is not a context of the tree.

See Also

prune_tree(), compare_pruning(), plot_distributions().

Examples

tree <- context_tree(trajectories, max_depth = 3)
plot_pruning(tree, "Average -> Active -> Active")

Draw a forward trajectory tree

Description

plot_trajectories() draws a forward trajectory tree of the sequences a tree was fitted on: it starts from a common root and follows each sequence state by state from its beginning, so every node is a prefix (the first state, the first two states, and so on) and its position on the x-axis is the move number. A context tree reads sequences backwards, each node a history that ends at the moment of prediction; the trajectory tree reads them forwards. It shows how sequences fan out from their first state, which opening paths are common, and where they diverge.

The tree is colored in one of two ways. With measure = "frequency" the color of a node is the number of sequences that share the prefix. With measure = "predictability" it is the probability the fitted model gives to the node's last state after the preceding prefix, P(\mathrm{state} \mid \mathrm{history}), with the history truncated to the tree's maximum depth and read through query_pathway(); the root distribution is used for first states. Edge width is the number of sequences in both cases, and darker color is a higher value. A pruned tree shows predictability under the pruned model.

Only prefixes shared by at least min_count sequences are drawn. For the backward context tree use plot.transitiontrees; for the memory needed by one pathway use plot_pruning().

Usage

plot_trajectories(
  tree,
  measure = c("frequency", "predictability"),
  min_count = 4L
)

Arguments

tree

A transitiontrees object that carries its sequences.

measure

"frequency" (default) or "predictability".

min_count

Smallest number of sequences sharing a prefix for it to be drawn. Default 4.

Value

A ggplot object: the prefix tree, move number on the x-axis.

Conditions

transitiontrees_bad_input

(error) tree is not a transitiontrees object, or carries no sequences.

transitiontrees_empty_result

(error) no prefix is shared by min_count sequences.

See Also

plot.transitiontrees for the backward context tree; plot_pruning(); query_pathway().

Examples

tree <- context_tree(trajectories, max_depth = 3)
plot_trajectories(tree, min_count = 10)
plot_trajectories(prune_tree(tree), measure = "predictability",
                  min_count = 10)

Predict the next state after each history

Description

predict() predicts the state that follows each history from the longest context of a fitted tree that matches the end of that history. Histories longer than the tree's depth are read only as far back as the tree remembers, and histories whose recent states never formed a context fall back to a shorter suffix or to the root. The prediction is therefore always defined, and it uses as much of the past as the data supported when the tree was fitted.

It returns, for each history, the probability of every next state, or the most likely next state with type = "class". With tidy = TRUE it returns one row per history with the history, the context that was matched, the most likely next state and its probability, and the probability of every state.

To score observed sequences rather than predict from given histories, use score_positions(); to look up a single pathway, use query_pathway(); to fill in missing states, use impute_sequences().

Usage

## S3 method for class 'transitiontrees'
predict(object, newdata, type = c("prob", "class"), tidy = FALSE, ...)

Arguments

object

A transitiontrees object.

newdata

Histories, oldest state first: a list of character vectors, a wide data.frame or matrix with one history per row (missing or empty cells are dropped), or a single character vector. A history given as one arrow-notation string ("A -> B") is split into its states.

type

"prob" (default) for next-state probabilities or "class" for the most likely next state.

tidy

Return a data.frame with one row per history. Default FALSE.

...

Not used.

Value

With tidy = TRUE, a data.frame with one row per history and columns id (position in newdata), history (arrow notation; "(start)" when empty), context (the matched context), predicted (most likely next state), probability (its probability) and one column per state with the next-state probabilities. With tidy = FALSE and type = "prob", a numeric matrix with one row per history and one column per state, or a named vector when newdata is a single character vector; with type = "class", a character vector of most likely next states.

Conditions

transitiontrees_bad_input when newdata is not a list, data frame, matrix or character vector. A warning of class transitiontrees_unknown_state when a history contains a state outside the tree's alphabet; the prediction then uses the longest context after the last unknown state.

See Also

query_pathway(), score_positions(), impute_sequences(), generate_sequences().

Examples

tree <- context_tree(trajectories, max_depth = 3)
histories <- list(c("Active", "Active"),
                  c("Average", "Disengaged", "Disengaged"),
                  character(0))
predict(tree, newdata = histories, tidy = TRUE)
predict(tree, newdata = histories, type = "class")

Reshape a long event log into one sequence per row

Description

prepare_input() reshapes a long event log into one sequence per row: the wide table that context_tree() fits. Process data are usually recorded as event logs, one row per event with the actor, a timestamp and the action or state, while sequence models need the events of each actor, or of each working session, in temporal order as one sequence.

Events are grouped by actor and ordered by time (ties broken by order, then by row order). When time is given, each actor's events are split into sessions wherever the gap between consecutive events exceeds time_threshold seconds, so that a sequence covers one continuous episode of activity rather than all of an actor's events over days or weeks. A session column, when given, defines the sessions directly, and events within a session are then ordered by order or row order, not by time. Without time or session, each actor contributes one sequence in the order of order or of the rows.

context_tree() calls prepare_input() itself when its action argument is set, so the reshaping is needed separately only to inspect the sequences or to pass them to other functions. The choice of time_threshold defines what counts as a sequence and changes every result fitted on it; it is worth checking that conclusions hold for neighboring thresholds.

Usage

prepare_input(
  data,
  actor = NULL,
  time = NULL,
  action = NULL,
  order = NULL,
  session = NULL,
  time_threshold = 900,
  format = NULL,
  is_unix_time = FALSE,
  unix_time_unit = c("seconds", "milliseconds", "microseconds"),
  meta = NULL
)

Arguments

data

A data.frame with one row per event.

actor

Name of the column, or columns, identifying whose events form a sequence. Several columns are combined. NULL (default) treats all rows as one actor.

time

Name of the timestamp column: date-times, dates, character timestamps, or numbers read as Unix time. NULL (default) orders by order or row order and does not split sessions.

action

Name of the column holding the state of each event. Required.

order

Name of a column giving the order of events within an actor, used without time or to break ties in time. NULL (default) uses row order.

session

Name of a column identifying sessions within an actor. When given, sessions are taken from it and time_threshold is not used. Default NULL.

time_threshold

Gap in seconds between consecutive events that starts a new session. Default 900 (15 minutes).

format

strptime format for a character time column. NULL (default) accepts ISO 8601 timestamps.

is_unix_time

Read time as Unix time. Default FALSE; numeric columns are read as Unix time in any case.

unix_time_unit

Unit of Unix time: "seconds" (default), "milliseconds" or "microseconds".

meta

Names of columns to carry over as one value per sequence (the value of its first event), used by context_tree() to align group and block with the sequences. Default NULL.

Value

A character data.frame with one row per sequence, named by actor and session, and columns T1, T2, ... holding the states in order; sequences shorter than the longest are padded with NA. It can be passed directly to context_tree().

Conditions

transitiontrees_bad_input when action or another named column is not in data, time_threshold is not a single non-negative number, or time cannot be parsed.

See Also

context_tree(), which accepts the same arguments.

Examples

sessions <- prepare_input(group_regulation_long, actor = "Actor",
                          time = "Time", action = "Action")
dim(sessions)
head(sessions, 3)

# Explicit session identifiers and within-session order
turns <- prepare_input(ai_long, actor = "session_id",
                       order = "order_in_session", action = "code")
dim(turns)

Print the summary of a transition tree

Description

print() prints the object returned by summary.transitiontrees(): a one-line header followed by the first n rows of the context table.

Usage

## S3 method for class 'summary.transitiontrees'
print(x, n = 10L, ...)

Arguments

x

A summary.transitiontrees object.

n

Number of context rows to print. Default 10.

...

Not used.

Value

x, invisibly.

See Also

summary.transitiontrees().

Examples

tree <- context_tree(trajectories, max_depth = 2)
print(summary(tree), n = 5)

Print a summary of a two-tree comparison

Description

print() prints the one-row summary of a compare_trees() result as a table.

Usage

## S3 method for class 'summary.transitiontrees_comparison'
print(x, digits = 3L, ...)

Arguments

x

A summary.transitiontrees_comparison object.

digits

Significant digits for numeric columns. Default 3.

...

Ignored.

Value

x, invisibly.

See Also

summary.transitiontrees_comparison.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
print(summary(compare_trees(grp, iter = 20)), digits = 2)

Print the summary of a group of transition trees

Description

print() prints the table returned by summary.transitiontrees_group() under a one-line header, with numeric columns rounded.

Usage

## S3 method for class 'summary.transitiontrees_group'
print(x, digits = 3L, ...)

Arguments

x

A summary.transitiontrees_group object.

digits

Number of significant digits for numeric columns. Default 3.

...

Not used.

Value

x, invisibly.

See Also

summary.transitiontrees_group().

Examples

groups <- context_tree(group_regulation_long, actor = "Actor",
                       time = "Time", action = "Action",
                       group = "Achiever", max_depth = 2)
print(summary(groups), digits = 2)

Print a summary of a group comparison

Description

print() prints the one-row summary of a compare_groups() result as a short verdict: the omnibus tests and the counts of contexts that differ.

Usage

## S3 method for class 'summary.transitiontrees_group_comparison'
print(x, ...)

Arguments

x

A summary.transitiontrees_group_comparison object.

...

Ignored.

Value

x, invisibly.

See Also

summary.transitiontrees_group_comparison.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
print(summary(compare_groups(grp, iter = 20)))

Print a summary of a tuning grid

Description

print() prints the number of configurations and failed configurations, then the selected configuration as a one-row table.

Usage

## S3 method for class 'summary.transitiontrees_tune'
print(x, digits = 4L, ...)

Arguments

x

A summary.transitiontrees_tune object.

digits

Significant digits for numeric columns. Default 4.

...

Ignored.

Value

x, invisibly.

See Also

summary.transitiontrees_tune.

Examples

tuned <- tune_tree(trajectories, max_depth = 1:2, min_count = 5,
                   prune = FALSE, folds = 3)
print(summary(tuned), digits = 3)

Print a fitted transition tree

Description

print() prints a header (numbers of contexts, depth and states, the data the tree was fitted on, the smoothing scheme and min_count, and the pruning criterion when the tree is pruned), followed by the tree drawn as text. Each line of the drawing is one context: the state it adds to its parent's history (the older state), its count n, and the most likely next state with its probability. Long trees are cut after max_lines lines; as.data.frame() gives every context.

Usage

## S3 method for class 'transitiontrees'
print(x, max_lines = 25L, digits = 2L, ...)

Arguments

x

A transitiontrees object.

max_lines

Maximum number of tree lines to print. Default 25.

digits

Decimal places for probabilities. Default 2.

...

Not used.

Value

x, invisibly.

See Also

summary.transitiontrees(), as.data.frame.transitiontrees(), plot.transitiontrees().

Examples

tree <- context_tree(trajectories, max_depth = 2)
print(tree, max_lines = 10)

Print a pathway bootstrap

Description

print() prints the number of resamples, the stability and informativeness criteria, the number of stable and informative pathways, and the first n pathways (stable and informative first).

Usage

## S3 method for class 'transitiontrees_bootstrap'
print(x, n = 10L, digits = 3L, ...)

Arguments

x

A transitiontrees_bootstrap object.

n

Number of pathways to print. Default 10.

digits

Rounding digits for the printed table. Default 3.

...

Ignored.

Value

x, invisibly.

See Also

bootstrap_pathways(), as.data.frame.transitiontrees_bootstrap for every pathway.

Examples

boot <- bootstrap_pathways(context_tree(trajectories, max_depth = 2),
                           iter = 50)
print(boot, n = 5)

Print a two-tree comparison

Description

print() prints the number of permutations, the observed distance, the mean of the null distribution, the p-value, and the n contexts that contribute most to the distance.

Usage

## S3 method for class 'transitiontrees_comparison'
print(x, digits = 3L, n = 6L, ...)

Arguments

x

A transitiontrees_comparison object.

digits

Significant digits for the distances and rounding digits for the per-context table. Default 3.

n

Number of contexts to print. Default 6.

...

Ignored.

Value

x, invisibly.

See Also

compare_trees(), as.data.frame.transitiontrees_comparison for every context.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
print(compare_trees(grp, iter = 20), n = 3)

Print a group of fitted transition trees

Description

print() prints one line per group of a transitiontrees_group: the number of contexts, the depth of the tree, and the numbers of sequences and observations it was fitted on.

Usage

## S3 method for class 'transitiontrees_group'
print(x, ...)

Arguments

x

A transitiontrees_group object.

...

Not used.

Value

x, invisibly.

See Also

summary.transitiontrees_group() for the fit of each group; context_tree().

Examples

groups <- context_tree(group_regulation_long, actor = "Actor",
                       time = "Time", action = "Action",
                       group = "Achiever", max_depth = 2)
print(groups)

Print a group comparison

Description

print() prints the groups and permutation design, the omnibus behavioral and usage tests, and the n contexts with the largest behavioral differences.

Usage

## S3 method for class 'transitiontrees_group_comparison'
print(x, n = 10L, digits = 3L, ...)

Arguments

x

A transitiontrees_group_comparison object.

n

Number of contexts to print. Default 10.

digits

Rounding digits for the printed tables. Default 3.

...

Ignored.

Value

x, invisibly.

See Also

compare_groups(), as.data.frame.transitiontrees_group_comparison for every context.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
print(compare_groups(grp, iter = 20), n = 3)

Print a tuning grid

Description

print() prints the number of configurations, the first n rows of the grid (lowest held-out perplexity first) and the selected configuration.

Usage

## S3 method for class 'transitiontrees_tune'
print(x, n = 10L, ...)

Arguments

x

A transitiontrees_tune object.

n

Number of configurations to print. Default 10.

...

Ignored.

Value

x, invisibly.

See Also

tune_tree(), as.data.frame.transitiontrees_tune for the full grid.

Examples

tuned <- tune_tree(trajectories, max_depth = 1:2, min_count = 5,
                   prune = FALSE, folds = 3)
print(tuned, n = 3)

Prune a transition tree to the contexts that change the prediction

Description

prune_tree() removes the contexts of a fitted tree that predict the next state no differently from their shorter suffix, so that the long contexts that remain are those in which the additional history changes the prediction. This is the principle behind the learning of prediction suffix trees (Ron, Singer & Tishby, 1996) and the context algorithm for variable-length Markov chains (Bühlmann & Wyner, 1999). A fitted tree holds every context that occurs often enough, and many such contexts add parameters without adding information about what comes next.

It compares each leaf with its parent, the context one state shorter, and removes the leaf when the comparison does not pass the chosen criterion; leaves exposed by a removal are tested in turn until no leaf can be removed. The root is never removed. With "G2" a leaf is kept when the likelihood-ratio statistic of its counts against the parent's distribution exceeds the chi-square critical value at alpha with k - 1 degrees of freedom (k states); each leaf is tested separately, without correction for multiple tests. With "KL" a leaf is kept when its Kullback-Leibler divergence from the parent, in nats, exceeds threshold. With "AIC" and "BIC" a leaf is kept when its log-likelihood, penalized by 2(k - 1) or \log(n)(k - 1) (n the leaf's count), is better than that of the parent's prediction (Akaike, 1974; Schwarz, 1978). The probabilities of the contexts that remain are not changed. It returns a tree of the same class with fewer contexts.

To see how strongly each criterion prunes a tree, use compare_pruning(); to choose between pruned and unpruned trees on held-out data, use tune_tree(); to draw the "G2" decision along the suffix chain of one pathway, use plot_pruning(). The divergence column of tree_pathways() is in bits, whereas the "KL" threshold is in nats; divide a threshold in nats by log(2) to read it in bits.

Usage

prune_tree(
  tree,
  criterion = c("G2", "KL", "AIC", "BIC"),
  alpha = 0.05,
  threshold = 0.005
)

Arguments

tree

A transitiontrees object, or a transitiontrees_group, whose trees are each pruned.

criterion

"G2" (default), "KL", "AIC" or "BIC".

alpha

Significance level for "G2", in (0, 1). Default 0.05.

threshold

Minimum divergence in nats for "KL". Default 0.005.

Value

An object of the same class as tree, with fewer contexts. A pruned tree prints [pruned] and the criterion in its header, and n_nodes() gives its size.

Conditions

transitiontrees_bad_input when tree is not a fitted tree, alpha is not a single number in (0, 1), or threshold is not a single non-negative number.

References

Akaike, H. (1974). A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19(6), 716-723. doi:10.1109/TAC.1974.1100705

Bühlmann, P., & Wyner, A. J. (1999). Variable length Markov chains. The Annals of Statistics, 27(2), 480-513. doi:10.1214/aos/1018031204

Ron, D., Singer, Y., & Tishby, N. (1996). The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning, 25(2-3), 117-149. doi:10.1023/A:1026490906255

Schwarz, G. (1978). Estimating the dimension of a model. The Annals of Statistics, 6(2), 461-464. doi:10.1214/aos/1176344136

See Also

compare_pruning(), plot_pruning(), tune_tree(), context_tree().

Examples

tree <- context_tree(trajectories, max_depth = 4)
prune_tree(tree, criterion = "G2", alpha = 0.05)
n_nodes(prune_tree(tree, criterion = "BIC"))

Look up the next-state distribution after a pathway

Description

query_pathway() returns the probability distribution that the fitted tree assigns to the next state after a given history, or the probability of one particular next state. For example, it gives the probability of Disengaged after the history Active, Average, read directly from the fitted model.

By default the history need not be a context of the tree: as in prediction, the longest suffix of the history that is in the tree is used, falling back to the root when no suffix matches. With exact = TRUE only a context of the tree is accepted, and other histories return NA. To find which context matched, use predict.transitiontrees() with tidy = TRUE; to test whether a pathway is a context, use pathway_exists().

Usage

query_pathway(tree, pathway, next_state = NULL, exact = FALSE)

Arguments

tree

A transitiontrees object.

pathway

The history, oldest state first: a single string in arrow notation ("A -> B") or a character vector (c("A", "B")). "(start)" or an empty vector denotes the root.

next_state

A state whose probability is returned. NULL (default) returns the whole distribution.

exact

Require pathway to be a context of the tree. Default FALSE (use the longest matching suffix).

Value

With next_state, a single probability. Otherwise a named numeric vector with one probability per state, in the order of the tree's states. NA for a pathway that is not a context when exact = TRUE.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or next_state is not one of its states.

See Also

pathway_exists(), subtree(), predict.transitiontrees(), tree_pathways().

Examples

tree <- context_tree(trajectories, max_depth = 3)
query_pathway(tree, "Active -> Average")
query_pathway(tree, c("Active", "Average"), next_state = "Disengaged")

Score each position of each sequence under a fitted tree

Description

score_positions() returns, for every position of every sequence, the context of the tree that was used to predict it, the state that occurred, the probability the tree gave that state, and its log-likelihood contribution. Low probabilities mark the moves the tree did not expect, which locates where in a sequence it departs from the typical pathways.

With worst, only the positions with the lowest predicted probability are returned, in increasing order of probability. Summed by sequence, the log-likelihood contributions give score_sequences().

Usage

score_positions(tree, newdata, worst = NULL)

Arguments

tree

A transitiontrees object.

newdata

Sequences to score, in any form accepted by context_tree().

worst

Number of least expected positions to return. NULL (default) returns all positions, in sequence order.

Value

A data.frame with one row per scored position and columns sequence_id, position, matched_context (the context used for the prediction; "(start)" for the root), observed (the state that occurred), predicted_prob (its probability) and log_lik (its natural logarithm).

Conditions

transitiontrees_bad_input when tree is not a fitted tree, worst is not a single positive number, or newdata has no usable sequence.

See Also

score_sequences(), predict.transitiontrees(), plot_predictive().

Examples

tree <- context_tree(trajectories, max_depth = 2)
score_positions(tree, engagement, worst = 5)

Score each sequence under a fitted tree

Description

score_sequences() scores each sequence by how well the fitted tree predicts it: its log-likelihood, the number of positions scored, and its perplexity (\exp(-\ell / n)). Sequences with high perplexity follow pathways the tree finds unlikely, which makes the score useful for finding atypical sequences or for checking how well a tree fitted on one group describes another.

Each position is predicted from the longest context of the tree that matches the preceding states, as in predict.transitiontrees(); states not among the tree's states are not scored. It returns one row per scored sequence. For the score of each position use score_positions(); for the most or least typical sequences directly, use mine_sequences().

Usage

score_sequences(tree, newdata)

Arguments

tree

A transitiontrees object.

newdata

Sequences to score, in any form accepted by context_tree().

Value

A data.frame with one row per scored sequence and columns sequence_id (position of the sequence among the non-empty sequences of newdata), n_scored (positions scored), log_lik (natural logarithm) and perplexity.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or newdata has an unsupported type or no usable sequence.

See Also

score_positions(), mine_sequences(), perplexity().

Examples

tree <- context_tree(trajectories, max_depth = 2)
head(score_sequences(tree, engagement))

List the pathways with the most certain next state

Description

sharp_pathways() returns the pathways whose most likely next state has the highest probability. A pathway with a next-state probability close to 1 is followed almost always by the same state, a near-deterministic step in the process; a probability close to 1/k (k states) means the next state is hard to predict from that history. Sharp pathways with small counts are often artefacts of few observations; set min_count accordingly.

Usage

sharp_pathways(tree, top = 10L, min_count = 1L)

Arguments

tree

A transitiontrees object.

top

Number of pathways to return. Default 10.

min_count

Keep pathways that occurred at least this many times. Default 1.

Value

A data.frame with the columns of tree_pathways(), one row per pathway, sorted by next_probability in decreasing order, at most top rows.

Conditions

transitiontrees_bad_input when tree is not a fitted tree.

See Also

tree_pathways(), common_pathways(), tree_dependence() for the entropy of each prediction.

Examples

tree <- context_tree(trajectories, max_depth = 3)
sharp_pathways(tree, top = 5, min_count = 20)

Simulate sequences from a fitted transition tree

Description

simulate() draws nsim sequences from a fitted tree as generate_sequences() does, and sets the random seed first when seed is given. It is the simulate() method for fitted trees.

Usage

## S3 method for class 'transitiontrees'
simulate(
  object,
  nsim = 5L,
  seed = NULL,
  length = 10L,
  start = NULL,
  tidy = FALSE,
  ...
)

Arguments

object

A transitiontrees object.

nsim

Number of sequences. Default 5.

seed

Random seed passed to set.seed(), or NULL (default) to use the current state of the generator.

length

Number of states in each sequence. Default 10.

start

First state of each sequence; see generate_sequences(). Default NULL.

tidy

Return a data.frame rather than a matrix. Default FALSE.

...

Not used.

Value

As generate_sequences(): with tidy = TRUE, a data.frame with one row per sequence and columns T1 to T<length>; otherwise a character matrix with the same layout.

Conditions

As generate_sequences().

See Also

generate_sequences().

Examples

tree <- context_tree(trajectories, max_depth = 2)
simulate(tree, nsim = 3, seed = 42, length = 8, tidy = TRUE)

Re-smooth the next-state probabilities of a fitted tree

Description

smooth_tree() re-estimates the next-state probabilities of every context of a fitted tree under a new smoothing scheme, without refitting. Smoothing moves part of the probability toward unobserved states or toward the distribution of the shorter context, the parent in the tree (Chen & Goodman, 1999). The next-state distribution of a context is estimated from the continuations observed after it; raw proportions give probability zero to every continuation that was not observed, which makes any new sequence containing such a continuation impossible under the model, and they are unstable in contexts with few occurrences.

Counts and the set of contexts stay as they are, and only the probabilities change. Parents are smoothed before their children, so the back-off schemes interpolate with an already smoothed parent. The five schemes are given under Details. It returns a tree of the same class with re-smoothed probabilities.

Smoothing changes predictions, perplexity and the divergence column of tree_pathways(), but never which contexts the tree contains; that is set by min_count and by pruning. To compare schemes on one dataset use compare_smoothing() (in-sample) or tune_tree() (cross-validated).

Usage

smooth_tree(tree, smoothing = "floor")

Arguments

tree

A transitiontrees object, or a transitiontrees_group, whose trees are each re-smoothed.

smoothing

A method name, or a list of the method name and its hyperparameters, such as list("kneser_ney", discount = 0.5). Methods and default hyperparameters: "floor" (default; ymin = 0.001, rule = "interpolate"), "laplace" (alpha = 1), "kneser_ney" (discount = 0.75), "witten_bell" (none) and "jelinek_mercer" (lambda = 0.5).

Details

For a context with counts n_s over k states, total n and parent distribution q_s (uniform for the root):

"floor"

With rule = "interpolate" (default), a distribution with an unobserved state becomes (1 - k\,y_{min}) p_s + y_{min}, so that each unobserved state has probability exactly ymin; distributions without zeros are left unchanged. ymin must be below 1/k. With rule = "cap", every probability is raised to at least ymin and the vector is renormalized.

"laplace"

Additive smoothing: (n_s + \alpha) / (n + k\alpha).

"kneser_ney"

Absolute discounting with back-off to the parent: \max(n_s - d, 0)/n plus the removed mass times q_s. The parent's smoothed distribution is used for the back-off, not the continuation counts of the original method (Kneser & Ney, 1995).

"witten_bell"

Interpolation with the parent, (1 - \lambda) n_s / n + \lambda q_s, with \lambda = r / (r + n) and r the number of distinct states observed after the context (Witten & Bell, 1991).

"jelinek_mercer"

Interpolation with the parent at a fixed weight: (1 - \lambda) n_s / n + \lambda q_s.

Value

An object of the same class as tree with re-smoothed probabilities; counts and contexts are unchanged.

Conditions

transitiontrees_bad_input when tree is not a fitted tree, the method is unknown, a hyperparameter is outside its range, or ymin is not below 1/k under rule = "interpolate".

References

Begleiter, R., El-Yaniv, R., & Yona, G. (2004). On prediction using variable order Markov models. Journal of Artificial Intelligence Research, 22, 385-421. doi:10.1613/jair.1491

Chen, S. F., & Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech and Language, 13(4), 359-393. doi:10.1006/csla.1999.0128

Kneser, R., & Ney, H. (1995). Improved backing-off for M-gram language modeling. In 1995 International Conference on Acoustics, Speech, and Signal Processing (Vol. 1, pp. 181-184). doi:10.1109/ICASSP.1995.479394

Witten, I. H., & Bell, T. C. (1991). The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory, 37(4), 1085-1094. doi:10.1109/18.87000

See Also

compare_smoothing() to compare schemes; context_tree(), whose smoothing argument applies a scheme at fit time; tune_tree().

Examples

tree <- context_tree(trajectories, max_depth = 3)
smooth_tree(tree, "kneser_ney")
smooth_tree(tree, list("laplace", alpha = 0.5))

Count how often each state occurs

Description

state_frequencies() tabulates the states of the sequences a tree was fitted on. The counts are those of the root context, which conditions on no history and counts every observed position once; they form the marginal distribution of states, against which every longer context is compared. For a transitiontrees_group, the table is computed for each group.

Usage

state_frequencies(tree)

Arguments

tree

A transitiontrees or a transitiontrees_group object.

Value

A data.frame with one row per state (per group and state, with a leading group column, for a transitiontrees_group) and columns state, count (observed positions, weighted for a weighted fit) and proportion, sorted by decreasing count, with ties in the order of the tree's states.

Conditions

transitiontrees_bad_input when tree is neither a fitted tree nor a group of them.

See Also

context_tree(), tree_pathways().

Examples

tree <- context_tree(trajectories, max_depth = 2)
state_frequencies(tree)

Extract the branch of a tree below one context

Description

subtree() returns the part of a fitted tree that lies below a given context: the context itself and every longer context that ends with it, that is, every history that extends it further into the past. The branch shows how the prediction after a given recent history is refined by what happened before it, and can be summarized, converted to a data frame and plotted like a full tree.

Contexts keep their full names, and the states, smoothing and other settings are those of the original tree. The printed header names the context at which the branch was cut.

Usage

subtree(tree, pathway)

Arguments

tree

A transitiontrees object.

pathway

The context at which to cut, oldest state first: a string in arrow notation or a character vector. It must be a context of the tree.

Value

A transitiontrees object holding pathway and its descendants.

Conditions

transitiontrees_bad_input when tree is not a fitted tree or pathway is not one of its contexts.

See Also

pathway_exists(), query_pathway(), plot.transitiontrees().

Examples

tree <- context_tree(trajectories, max_depth = 3)
branch <- subtree(tree, "Disengaged")
summary(branch)
as.data.frame(branch, sort_by = "depth")

Summarize a fitted transition tree

Description

summary() summarizes a fitted tree by its size (numbers of states and contexts, depth, pruned or not) and its table of contexts ordered by depth and, within depth, by decreasing count, so that the table reads from the root downward.

Usage

## S3 method for class 'transitiontrees'
summary(object, ...)

Arguments

object

A transitiontrees object.

...

Not used.

Value

An object of class summary.transitiontrees, which prints a header and the first rows of the context table (columns as in tree_pathways()). For the full table use as.data.frame() on the tree; for fit statistics use model_fit().

See Also

print.summary.transitiontrees(), tree_pathways(), model_fit().

Examples

tree <- context_tree(trajectories, max_depth = 2)
summary(tree)

Summarize a pathway bootstrap

Description

summary() returns the per-pathway table of a bootstrap_pathways() result; identical to as.data.frame(object).

Usage

## S3 method for class 'transitiontrees_bootstrap'
summary(object, ...)

Arguments

object

A transitiontrees_bootstrap object.

...

Ignored.

Value

A data frame with one row per pathway of the original tree; see bootstrap_pathways() for the columns.

See Also

bootstrap_pathways(), as.data.frame.transitiontrees_bootstrap.

Examples

boot <- bootstrap_pathways(context_tree(trajectories, max_depth = 1),
                           iter = 50)
summary(boot)

Summarize a two-tree comparison

Description

summary() reduces a compare_trees() result to one row: the observed distance between the two trees, the mean, standard deviation and 95th percentile of the permutation null distribution, and the permutation p-value.

Usage

## S3 method for class 'transitiontrees_comparison'
summary(object, ...)

Arguments

object

A transitiontrees_comparison object.

...

Ignored.

Value

An object of class summary.transitiontrees_comparison: a one-row data frame with columns distance, null_mean, null_sd, null_q95, p_value, iter and n_pathways (contexts in the per-context table).

See Also

compare_trees(), as.data.frame.transitiontrees_comparison.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
summary(compare_trees(grp, iter = 20))

Summarize a group of fitted transition trees

Description

summary() summarizes a transitiontrees_group with one row per group: the size of the data each tree was fitted on, the size and depth of the tree, and its in-sample fit (log-likelihood, number of parameters, AIC, BIC and perplexity, as returned by model_fit()). The in-sample fit describes each tree; to test whether the groups differ, use compare_groups().

Usage

## S3 method for class 'transitiontrees_group'
summary(object, ...)

Arguments

object

A transitiontrees_group object.

...

Not used.

Value

An object of class summary.transitiontrees_group, a data.frame with one row per group and columns group, n_seq, n_obs, n_nodes, max_depth, pruned, logLik, df, nobs, AIC, BIC and perplexity.

See Also

context_tree(), model_fit(), compare_groups().

Examples

groups <- context_tree(group_regulation_long, actor = "Actor",
                       time = "Time", action = "Action",
                       group = "Achiever", max_depth = 2)
summary(groups)

Summarize a group comparison

Description

summary() reduces a compare_groups() result to one row: the omnibus behavioral and usage tests, and the number of contexts whose adjusted p-value is below alpha on each axis or whose modal next state differs between groups.

Usage

## S3 method for class 'transitiontrees_group_comparison'
summary(object, alpha = 0.05, ...)

Arguments

object

A transitiontrees_group_comparison object.

alpha

False discovery rate cutoff used to count contexts. Default 0.05.

...

Ignored.

Value

An object of class summary.transitiontrees_group_comparison: a one-row data frame with columns groups (the group names joined by " vs "), n_contexts, iter, stratified, behavioral_jsd and behavioral_p (omnibus count-weighted Jensen-Shannon divergence, bits, and its permutation p-value), usage_g2 and usage_p (omnibus usage statistic and its p-value), alpha, n_behavioral and n_usage (contexts with adjusted p-value below alpha) and n_flips (contexts whose modal next state differs). It prints as a short verdict.

See Also

compare_groups(), as.data.frame.transitiontrees_group_comparison.

Examples

grp <- context_tree(group_regulation_long, actor = "Actor", time = "Time",
                    action = "Action", group = "Achiever", max_depth = 1)
summary(compare_groups(grp, iter = 20), alpha = 0.1)

Summarize a tuning grid

Description

summary() reduces a tune_tree() grid to one row: the number of configurations scored, the number with a failed cross-validation fold, and the settings, held-out perplexity and mean size of the selected configuration.

Usage

## S3 method for class 'transitiontrees_tune'
summary(object, ...)

Arguments

object

A transitiontrees_tune object.

...

Ignored.

Value

An object of class summary.transitiontrees_tune: a one-row data frame with columns n_configurations, n_failed, max_depth, min_count, smoothing, prune, perplexity and n_nodes_avg. The last six describe the selected configuration and are NA when no configuration scored on every fold.

See Also

tune_tree(), as.data.frame.transitiontrees_tune.

Examples

tuned <- tune_tree(trajectories, max_depth = 1:3, min_count = 5,
                   prune = c(FALSE, TRUE), folds = 3)
summary(tuned)

Student engagement trajectories

Description

trajectories is a coded dataset of the engagement states of 138 students at 15 successive time points, one row per student and one column per time point. Each state is "Active", "Average" or "Disengaged". Missing values occur only as a run at the end of a row and mark that the student's trajectory ended (drop-out); two rows are missing throughout and are ignored when a tree is fitted. The matrix has the wide layout that context_tree() fits directly, and is small enough for fast examples.

Usage

trajectories

Format

A character matrix with 138 rows (students) and 15 columns (time points, named "1" to "15"), holding "Active", "Average", "Disengaged" or NA. 118 rows are complete; 1870 states are observed in all.

Source

Bundled example dataset. The same matrix is distributed with the Nestimate package as trajectories.

See Also

engagement for a larger engagement dataset; context_tree().

Examples

tree <- context_tree(trajectories, max_depth = 3)
tree
state_frequencies(tree)

Measure how much each step of history changes the prediction

Description

tree_dependence() measures how much each step of history changes the prediction of a fitted tree, that is, where the process is path dependent. A process is path dependent where what happens next depends on more than the current state. In a transition tree this shows as a context whose next-state distribution differs from that of its parent, the same context without its oldest state. The difference has two sides: how far the distribution moves (its divergence) and whether it becomes more or less certain (its change in entropy).

It returns one row for every context other than the root, with the Kullback-Leibler divergence of its next-state distribution from its parent's, the Shannon entropy of both distributions and their difference, and the most likely next state under each (Cover & Thomas, 2006). A positive entropy_drop means the additional state of history makes the next state more predictable; a negative one means it makes it less predictable. The divergence is the quantity that prune_tree() compares with its threshold under criterion = "KL" (there in nats).

For the pathway table with counts and ranked views, use tree_pathways() and divergent_pathways(); to see the full next-state distributions along one pathway, use plot_pruning().

Usage

tree_dependence(
  tree,
  base = 2,
  sort_by = c("divergence", "entropy_drop", "entropy", "count", "depth"),
  top = NULL
)

Arguments

tree

A transitiontrees object.

base

Base of the logarithm: 2 (default) for bits, exp(1) for nats.

sort_by

Column to sort by, in decreasing order: "divergence" (default), "entropy_drop", "entropy", "count" or "depth".

top

Number of rows to keep after sorting. NULL (default) keeps all.

Value

A data.frame with one row per non-root context whose parent is in the tree, and columns pathway, depth, count, divergence (from the parent's distribution), entropy (of this context's distribution), entropy_before (of the parent's), entropy_drop (entropy_before minus entropy), likely_next, likely_before (the parent's most likely next state) and changes_prediction. A tree with only a root returns a zero-row table with these columns.

Conditions

transitiontrees_bad_input when tree is not a fitted tree.

References

Cover, T. M., & Thomas, J. A. (2006). Elements of information theory (2nd ed.). Wiley.

See Also

tree_pathways(), divergent_pathways(), prune_tree(), plot_divergence().

Examples

tree <- context_tree(trajectories, max_depth = 3)
tree_dependence(tree, top = 5)
tree_dependence(prune_tree(tree), sort_by = "entropy_drop")

Compute the divergence between two context trees

Description

tree_distance() computes the divergence between two context trees fitted to different sets of sequences, a measure of how differently they predict the next state. The distance is the Kullback-Leibler divergence between the two trees' next-state distributions (symmetric by default), computed for every context present in either tree and averaged with weights equal to the context's combined count in the two trees. A context missing from one tree is evaluated there at its longest fitted suffix, which is the distribution that tree would use for prediction. The value is 0 when the two trees predict identically and grows as their predictions separate.

It returns the distance only, in nats. It has no reference distribution, and it is positive even for two samples of one process; use compare_trees() for a permutation test and a per-context breakdown, or compare_groups() for more than two groups.

Usage

tree_distance(tree_a, tree_b, symmetric = TRUE)

Arguments

tree_a, tree_b

transitiontrees objects with the same alphabet.

symmetric

TRUE (default) for the symmetric divergence \frac{1}{2}(D_{KL}(A \| B) + D_{KL}(B \| A)); FALSE for D_{KL}(A \| B) alone.

Value

A single non-negative number, in nats. It is Inf when, at a context with a positive count, one tree gives probability zero to a next state that the other tree gives positive probability.

Conditions

transitiontrees_bad_input

(error) either argument is not a transitiontrees object.

transitiontrees_alphabet_mismatch

(error) the two trees have different alphabets.

See Also

compare_trees() for the permutation test; compare_groups() for several groups.

Examples

high <- context_tree(subset(group_regulation_long, Achiever == "High"),
                     actor = "Actor", time = "Time", action = "Action",
                     max_depth = 2)
low  <- context_tree(subset(group_regulation_long, Achiever == "Low"),
                     actor = "Actor", time = "Time", action = "Action",
                     max_depth = 2)
tree_distance(high, low)
tree_distance(high, low, symmetric = FALSE)

List the pathways of a fitted transition tree

Description

tree_pathways() lists the pathways of a fitted tree. A pathway is a context of the tree: the run of states that precedes a point at which the next state is predicted, written from oldest to newest ("A -> B -> C"). For each pathway the tree records how often it occurred and the distribution of the state that followed. The pathway table therefore shows which histories occur in the data, what tends to follow each of them, and where a longer history changes what is expected next.

It returns one row per pathway with its depth and count, its most likely next state and that state's probability, the Kullback-Leibler divergence of its next-state distribution from that of its parent (the pathway without its oldest state), and whether the most likely next state differs from the parent's. The divergence, in bits, measures how much information the additional state of history carries about the next state. The root, written "(start)", conditions on no history and holds the overall distribution of states.

The ranked views common_pathways(), divergent_pathways() and sharp_pathways() return the top rows of this table by count, divergence and next-state probability. tree_dependence() adds the entropy of each pathway's prediction, query_pathway() looks up one pathway, and bootstrap_pathways() assesses how stable each row is under resampling of sequences.

Usage

tree_pathways(
  tree,
  min_count = 1L,
  sort_by = c("count", "divergence", "depth"),
  decreasing = TRUE,
  ...
)

Arguments

tree

A transitiontrees object.

min_count

Keep pathways that occurred at least this many times. Default 1.

sort_by

Column to sort by: "count" (default), "divergence" or "depth".

decreasing

Sort in decreasing order. Default TRUE.

...

Not used.

Value

A data.frame with one row per pathway and columns

pathway

The context, oldest state first; "(start)" for the root.

depth

Number of states in the pathway.

count

Number of times the pathway was followed by a state (weighted for a weighted fit).

likely_next

Most likely next state.

next_probability

Its smoothed probability.

divergence

Kullback-Leibler divergence, in bits, of the pathway's next-state distribution from its parent's; NA for the root, and Inf when the pathway gives probability to a state that the parent gives probability zero.

changes_prediction

Whether likely_next differs from the parent's most likely next state; NA for the root.

A tree with no pathway returns a zero-row table with these columns.

Conditions

transitiontrees_bad_input when tree is not a fitted tree.

See Also

common_pathways(), divergent_pathways(), sharp_pathways(), tree_dependence(), plot_pathways(), bootstrap_pathways().

Examples

tree <- context_tree(trajectories, max_depth = 3)
tree_pathways(tree)
tree_pathways(tree, min_count = 20, sort_by = "divergence")

Select context tree settings by cross-validated perplexity

Description

tune_tree() selects the settings of a variable-order context tree by cross-validated perplexity. Four settings decide how much history the tree uses and how far it trusts sparse histories: the maximum depth, the minimum count a context needs to be kept, the smoothing of the next-state distributions, and whether the tree is pruned. A deeper, less smoothed tree reproduces the sequences it was fitted to more closely, but it does not necessarily predict new sequences better. Held-out perplexity measures the second property: it is the exponential of the mean negative log-likelihood per scored transition in sequences the model has not seen, and can be read as the effective number of next states the model is choosing between.

It fits a tree for every combination of the supplied values and scores it by k-fold cross-validation. Folds are formed from whole sequences, so a held-out sequence contributes no transitions to the fit, and every configuration is scored on the same folds. The selected configuration is the one with the lowest held-out perplexity among those that scored on every fold; a configuration with a failed fold is kept in the grid but is never selected. It returns the grid as a transitiontrees_tune data frame with one row per configuration, lowest held-out perplexity first.

The grid compares settings by out-of-sample prediction. To describe the fit of one tree to its own data use model_fit() or perplexity(); to compare smoothing methods or pruning rules on one data set without cross-validation use compare_smoothing() and compare_pruning().

Usage

tune_tree(
  data,
  max_depth = 2L:5L,
  min_count = c(3L, 5L, 10L),
  smoothing = "floor",
  prune = c(FALSE, TRUE),
  alpha = 0.05,
  folds = 5L,
  seed = 1L,
  actor = NULL,
  time = NULL,
  action = NULL,
  order = NULL,
  session = NULL,
  time_threshold = 900
)

Arguments

data

Sequences in any format accepted by context_tree().

max_depth

Maximum depths to try. Default 2:5.

min_count

Minimum context counts to try. Default c(3, 5, 10).

smoothing

Smoothing methods to try: a character vector of method names, each used with its default settings (default "floor"), or a list of specifications such as list(list("floor", ymin = 0.001), list("floor", ymin = 0.005)) to vary the settings of one method.

prune

Whether to prune with the G^2 criterion; both values are tried by default (c(FALSE, TRUE)).

alpha

Significance level of the G^2 pruning test. Default 0.05.

folds

Number of cross-validation folds. Default 5.

seed

Seed for the assignment of sequences to folds. Default 1. The call sets the session's random-number state.

actor, time, action, order, session, time_threshold

Column names and session gap for a long event log, as in context_tree(); the log is reshaped with prepare_input() before tuning. Default NULL (data already one row per sequence) and 900 seconds.

Value

An object of class transitiontrees_tune: a data frame with one row per configuration, sorted by held-out perplexity (lowest first), and columns max_depth, min_count, smoothing, prune, logLik (held-out log-likelihood summed over the folds that scored; NA when none did), n_scored (held-out transitions scored), perplexity, n_nodes_avg (mean number of contexts of the fitted trees) and folds_failed (folds that could not be fitted or scored). as.data.frame(x, what = "best") returns the selected configuration, summary() a one-row overview, and plot() the perplexity surface.

Conditions

transitiontrees_bad_input

(error) fewer sequences than folds; smoothing neither a character vector nor a list; data not in a sequence format.

transitiontrees_fold_failed

(warning) at least one configuration had a fold that could not be fitted or scored; the message gives the first error.

transitiontrees_no_best

(warning) no configuration scored on every fold, so none is selected.

See Also

summary.transitiontrees_tune, as.data.frame.transitiontrees_tune and plot.transitiontrees_tune for the result; context_tree() and prune_tree() to fit the selected configuration; perplexity() and model_fit() for the fit of one tree.

Examples

tuned <- tune_tree(trajectories, max_depth = 1:3, min_count = c(5, 10),
                   prune = c(FALSE, TRUE), folds = 3)
tuned
summary(tuned)