Package {gSeg}


Version: 1.2-1
Date: 2026-11-15
Title: Graph-Based Change-Point Detection (g-Segmentation)
Depends: R (≥ 3.0.1)
Imports: stats, tools
Description: Uses similarity graphs to estimate change-points and their p-values. The main functions accept either observations or dissimilarities, construct a k-MST with k=floor(sqrt(N)) by default, and report the max-type scan. A supplied similarity graph and the generalized, original, and weighted scans remain available explicitly.
License: GPL-2 | GPL-3 [expanded from: GPL (≥ 2)]
NeedsCompilation: yes
SystemRequirements: C99
Author: Hao Chen ORCID iD [aut, cre], Nancy R. Zhang [aut], Lynna Chu [aut], Hoseung Song [aut]
Maintainer: Hao Chen <hxchen@ucdavis.edu>
Packaged: 2026-11-15 10:00:00 UTC; hao
Repository: CRAN
Date/Publication: 2026-11-15 16:00:08 UTC

An edge matrix representing a similarity graph

Description

This is the variable name for an edge matrix in the "Example" data. It is constructed from a sequence of n=200 observations with a change in mean at t = 100. E1 is a matrix with the number of rows the number of edges in the similarity graph and 2 columns. Each row contains the node indices of an edge.


An edge matrix representing a similarity graph

Description

This is the variable name for an edge matrix in the "Example" data. It is constructed from a sequence of n=200 observations with a change in mean starting at t=45. E2 is a matrix with the number of rows the number of edges in the similarity graph and 2 columns. Each row contains the node indices of an edge.


An edge matrix representing a similarity graph

Description

This is the variable name for an edge matrix in the "Example" data. It is constructed from a sequence of n=200 observations with a change in mean and variance starting at t = 145. E3 is a matrix with the number of rows the number of edges in the similarity graph and 2 columns. Each row contains the node indices of an edge.


An edge matrix representing a similiarity graph

Description

This is the variable name for an edge matrix in the "Example" data. It is constructed from a sequence of n=200 observations with a change in mean and variance starting at t=50. E4 is a matrix with the number of rows the number of edges in the similarity graph and 2 columns. Each row contains the node indices of an edge.


An edge matrix representing a similiarity graph

Description

This is the variable name for an edge matrix in the "Example" data. It is constructed from a sequence of n=200 observations with a change in mean on the interval t= 155 to t=185. E5 is a matrix with the number of rows the number of edges in the similarity graph and 2 columns. Each row contains the node indices of an edge.


Graph-Based Change-Point Detection

Description

The package detects distributional changes in sequences of multivariate or object-valued observations. The main functions accept either a numeric data matrix or a pairwise dissimilarity matrix. They construct a k-MST with k=floor(sqrt(N)) by default and report the max-type edge-count test (MET). Users may instead provide their own similarity graph or explicitly request GET, OET, WET, or all four statistics.

Use gseg1 when the sequence may contain one change-point and gseg2 when it may contain one changed interval. For repeated observations, use gseg1_discrete or gseg2_discrete.

Author(s)

Hao Chen, Nancy R. Zhang, Lynna Chu, and Hoseung Song

Maintainer: Hao Chen (hxchen@ucdavis.edu)

References

Chen, Hao, and Nancy Zhang. (2015). Graph-based change-point detection. The Annals of Statistics, 43(1), 139–176.

Chu, Lynna, and Hao Chen. (2019). Asymptotic distribution-free change-point detection for modern data. The Annals of Statistics, 47(1), 382–414.

Song, Hoseung, and Hao Chen. (2022). Asymptotic distribution-free change-point detection for data with repeated observations. Biometrika, 109(3), 783–798.

See Also

gseg1, gseg2, gseg1_graph, gseg2_graph, gseg1_discrete, gseg2_discrete, gseg_kmst, nnl

Examples

set.seed(500)
N <- 40
d <- 5
x <- rbind(matrix(rnorm(d * 20), 20),
           matrix(rnorm(d * 20, 1 / sqrt(d)), 20))

# The main call accepts the observations directly. It constructs the default
# k-MST and reports MET.
result <- gseg1(x, pval.appr = FALSE)
names(result$scanZ)
result$k

# Pairwise dissimilarities can be supplied when observations are not vectors.
result.d <- gseg1(dissimilarity = as.matrix(dist(x)), pval.appr = FALSE)

# GET is available by explicit request.
result.get <- gseg1(x, statistics = "g", pval.appr = FALSE)

# A user-supplied graph can be analyzed explicitly.
result.graph <- gseg1_graph(N, result$graph, pval.appr = FALSE)

Graph-Based Detection of a Single Change-Point

Description

Detects a single distributional change in a sequence. Given observations or dissimilarities, the function constructs a k-MST and applies the max-type edge-count scan by default. A user-supplied similarity graph is also supported.

Usage

gseg1(x = NULL, dissimilarity = NULL, statistics = "m",
  n0 = NULL, n1 = NULL, pval.appr = TRUE, skew.corr = TRUE,
  pval.perm = FALSE, B = 100, k = NULL, n = NULL, E = NULL)

Arguments

x

A numeric matrix with observations in rows. For compatibility, the first positional argument may instead be the number of observations when the second positional argument is an edge matrix.

dissimilarity

A square symmetric dissimilarity matrix or a dist object. For compatibility, the second positional argument may instead be a two-column edge matrix. Supply exactly one of x and dissimilarity for a data-level call.

statistics

The scan statistic or statistics to compute. The default "m" reports only the max-type edge-count test (MET). Use "g" for the generalized edge-count test (GET), "o" for the original edge-count test, "w" for the weighted edge-count test, or "all" for all four. Long-form names are also accepted.

n0

First candidate change-point location. The default is 0.05 * N.

n1

Last candidate change-point location. The default is 0.95 * N.

pval.appr

Whether to calculate the analytic p-value approximation. This approximation requires at least nine observations.

skew.corr

Whether to include the skewness correction in the analytic p-value approximation.

pval.perm

Whether to calculate a permutation p-value.

B

Number of permutations.

k

Number of MST layers for a data-level call. The default is floor(sqrt(N)); the largest allowed value is floor(N/2).

n

Number of observations in a graph-level call. Both named and positional legacy graph arguments are supported.

E

Two-column edge matrix in a graph-level call. Do not supply k together with a supplied graph.

Details

The requested statistic must have positive permutation variance at each candidate location. Graphs for which a candidate score is undefined are rejected rather than silently omitted. For a single candidate location, set pval.appr = FALSE and use permutation calibration instead of the continuous-range analytic scan approximation.

Value

A list with scanZ and any requested p-values. Each requested component of scanZ contains the estimated change-point tauhat, maximum scan statistic Zmax, and scan path. Data-level calls additionally return the constructed graph and k.

Note

Analytic integrations are checked for convergence and finite probability outputs in [0,1]. An unavailable approximation raises an error rather than returning an invalid probability. Setting pval.appr = FALSE allows justified permutation calibration to be used instead. Scan components must be well-defined on the requested domain; undefined components are not replaced by zero.

See Also

gseg2, gseg1_graph, gseg1_discrete, gseg_kmst

Examples

set.seed(1)
x <- rbind(matrix(rnorm(40), 10), matrix(rnorm(40, 1), 10))

# Main interface: build the default k-MST and report MET.
ans <- gseg1(x, pval.appr = FALSE)
names(ans$scanZ)
ans$k

# A dissimilarity matrix may be supplied instead.
ans.d <- gseg1(dissimilarity = as.matrix(dist(x)), pval.appr = FALSE)

# Request GET explicitly.
ans.get <- gseg1(x, statistics = "g", pval.appr = FALSE)

# Earlier graph-level calls remain supported.
ans.graph <- gseg1(nrow(x), ans$graph, pval.appr = FALSE)

Data-Level Alias for gseg1

Description

A compatibility alias for the data-level gseg1 interface. New code may call gseg1 directly.

Usage

gseg1_data(x = NULL, dissimilarity = NULL, k = NULL,
  statistics = "m", ...)

Arguments

x

A numeric matrix with observations in rows.

dissimilarity

A square symmetric dissimilarity matrix or a dist object. Supply exactly one of x and dissimilarity.

k

Number of MST layers. The default is floor(sqrt(N)).

statistics

Scan statistic or statistics; see gseg1.

...

Additional arguments passed to gseg1.

Value

The result from gseg1.

See Also

gseg1, gseg_kmst

Examples

set.seed(1)
x <- matrix(rnorm(60), nrow = 20)
ans <- gseg1_data(x, pval.appr = FALSE)

Graph-Based Change-Point Detection for Single Change-Point for Data with Repeated Observations

Description

This function finds a break point in the sequence where the underlying distribution changes when data has repeated observations. It provides four graph-based test statistics.

Usage

gseg1_discrete(n, E, id, statistics="m", n0=0.05*n, n1=0.95*n, 
   pval.appr=TRUE, skew.corr=TRUE, pval.perm=FALSE, B=100)

Arguments

n

The number of observations in the sequence; it must be at least 6.

E

The edge matrix (a "number of edges" by 2 matrix) for the similarity graph. Each row contains the node indices of an edge.

id

The index of observations (order of observations).

statistics

The scan statistics to be computed. The default is "m", which reports the max-type scan.

"all": specifies to compute all of the scan statistics: original, weighted, generalized, and max-type;

"o", "ori" or "original": specifies the original edge-count scan statistic;

"w" or "weighted": specifies the weighted edge-count scan statistic;

"g" or "generalized": specifies the generalized edge-count scan statistic; and

"m" or "max": specifies the max-type edge-count scan statistic.

n0

The starting index to be considered as a candidate for the change-point.

n1

The ending index to be considered as a candidate for the change-point.

pval.appr

If it is TRUE, the function outputs a p-value approximation based on asymptotic properties. The analytic approximation requires n >= 9.

skew.corr

This argument is useful only when pval.appr=TRUE. If skew.corr is TRUE, the p-value approximation would incorporate skewness correction.

pval.perm

If it is TRUE, the function outputs p-value from doing B permutations, where B is another argument that you can specify. Doing permutation could be time consuming, so use this argument with caution as it may take a long time to finish the permutation.

B

This argument is useful only when pval.perm=TRUE. The default value for B is 100.

Details

The requested statistic must have positive permutation variance at each candidate location. Graphs for which a candidate score is undefined are rejected rather than silently omitted. For a single candidate location, set pval.appr = FALSE and use permutation calibration instead of the continuous-range analytic scan approximation.

Value

Returns a list scanZ with tauhat, Zmax, and a vector of the scan statistics for each type of scan statistic specified. See below for more details.

tauhat_a

An estimate of the location of the change-point for averaging approach.

tauhat_u

An estimate of the location of the change-point for union approach.

Z_a_max

The test statistic (maximum of the scan statistics) for averaging approach.

Z_u_max

The test statistic (maximum of the scan statistics) for union approach.

Zo_a

A vector of the original scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "o".

Zo_u

A vector of the original scan statistics (standardized counts) for union approach if statistic specified is "all" or "o".

Zw_a

A vector of the weighted scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "w".

Zw_u

A vector of the weighted scan statistics (standardized counts) for union approach if statistic specified is "all" or "w".

S_a

A vector of the generalized scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "g".

S_u

A vector of the generalized scan statistics (standardized counts) for union approach if statistic specified is "all" or "g".

M_a

A vector of the max-type scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "m".

M_u

A vector of the max-type scan statistics (standardized counts) for union approach if statistic specified is "all" or "m".

Ro_a

A vector of raw counts of the original scan statistic for averaging approach. This output only exists if the statistic specified is "all" or "o".

Ro_u

A vector of raw counts of the original scan statistic for union approach. This output only exists if the statistic specified is "all" or "o".

Rw_a

A vector of raw counts of the weighted scan statistic for averaging approach. This output only exists if statistic specified is "all" or "w".

Rw_u

A vector of raw counts of the weighted scan statistic for union approach. This output only exists if statistic specified is "all" or "w".

pval.appr

The approximated p-value based on asymptotic theory for each type of statistic specified.

pval.perm

This output exists only when the argument pval.perm is TRUE . It is the permutation p-value from B permutations and appears for each type of statistic specified (same for perm.curve, perm.maxZs, and perm.Z).

perm.curve

A B by 2 matrix with the first column being critical values corresponding to the p-values in the second column.

perm.maxZs

A sorted vector recording the test statistics in the B permutaitons.

perm.Z

A B by n matrix with each row being the scan statistics from each permutaiton run.

Note

For the original and weighted scans, a nonpositive observed maximum returns the conservative analytic value 1. This is not an exact finite-sample p-value; permutation calibration remains available.

Analytic integrations are checked for convergence and finite probability outputs in [0,1]. An unavailable approximation raises an error rather than returning an invalid probability. Setting pval.appr = FALSE allows justified permutation calibration to be used instead. Scan components must be well-defined on the requested domain; undefined components are not replaced by zero.

See Also

gSeg, gseg1, nnl, gseg2_discrete

Examples

d = 50
mu = 2
tau = 100
n = 200

set.seed(500)
y1_temp = matrix(rnorm(d*tau),tau)
sam1 = sample(1:tau, replace = TRUE)
y1 = y1_temp[sam1,] 
y2_temp = matrix(rnorm(d*(n-tau),mu/sqrt(d)), n-tau)
sam2 = sample(1:tau, replace = TRUE)
y2 = y2_temp[sam2,] 

y = rbind(y1, y2)

# This data y has repeated observations
y_uni = unique(y)
E = nnl(dist(y_uni), 1)

cha = do.call(paste, as.data.frame(y))    
id = match(cha, unique(cha))

r1 = gseg1_discrete(n, E, id, statistics="all")
# output results based on all four statistics
# the scan statistics can be found in r1$scanZ
r1_a = gseg1_discrete(n, E, id, statistics="w")  
# output results based on the weighted edge-count statistic
r1_b = gseg1_discrete(n, E, id, statistics=c("w","g"))  
# output results based on the weighted edge-count statistic 
# and generalized edge-count statistic

Single-Change Scan with a Supplied Similarity Graph

Description

Applies the single-change graph scan to a supplied edge matrix.

Usage

gseg1_graph(n, E, statistics = "m", n0 = 0.05 * n,
  n1 = 0.95 * n, pval.appr = TRUE, skew.corr = TRUE,
  pval.perm = FALSE, B = 100)

Arguments

n

Number of observations in the sequence.

E

Two-column edge matrix for the similarity graph.

statistics

Scan statistic or statistics; see gseg1.

n0

First candidate change-point location.

n1

Last candidate change-point location.

pval.appr

Whether to calculate the analytic p-value approximation.

skew.corr

Whether to include its skewness correction.

pval.perm

Whether to calculate a permutation p-value.

B

Number of permutations.

Details

The requested statistic must have positive permutation variance at each candidate location. Graphs for which a candidate score is undefined are rejected rather than silently omitted. For a single candidate location, set pval.appr = FALSE and use permutation calibration instead of the continuous-range analytic scan approximation.

Value

A list containing scan statistics and requested p-values.

Note

Analytic integrations are checked for convergence and finite probability outputs in [0,1]. An unavailable approximation raises an error rather than returning an invalid probability. Setting pval.appr = FALSE allows justified permutation calibration to be used instead. Scan components must be well-defined on the requested domain; undefined components are not replaced by zero.

See Also

gseg1, gseg_kmst

Examples

set.seed(1)
x <- matrix(rnorm(80), nrow = 20)
E <- gseg_kmst(x)
ans <- gseg1_graph(nrow(x), E, pval.appr = FALSE)

Graph-Based Detection of a Changed Interval

Description

Detects an interval whose distribution differs from the remainder of a sequence. Given observations or dissimilarities, the function constructs a k-MST and applies the max-type edge-count scan by default. A user-supplied similarity graph is also supported.

Usage

gseg2(x = NULL, dissimilarity = NULL, statistics = "m",
  l0 = NULL, l1 = NULL, pval.appr = TRUE, skew.corr = TRUE,
  pval.perm = FALSE, B = 100, k = NULL, n = NULL, E = NULL)

Arguments

x

A numeric matrix with observations in rows. For compatibility, the first positional argument may instead be the number of observations when the second positional argument is an edge matrix.

dissimilarity

A square symmetric dissimilarity matrix or a dist object. For compatibility, the second positional argument may instead be a two-column edge matrix. Supply exactly one of x and dissimilarity for a data-level call.

statistics

The scan statistic or statistics to compute. The default "m" reports only the max-type edge-count test (MET). Use "g" for GET, "o" for the original edge-count test, "w" for the weighted edge-count test, or "all" for all four. Long-form names are also accepted.

l0

Minimum candidate interval length. The default is 0.05 * N.

l1

Maximum candidate interval length. The default is 0.95 * N.

pval.appr

Whether to calculate the analytic p-value approximation. This approximation requires at least nine observations.

skew.corr

Whether to include the skewness correction in the analytic p-value approximation.

pval.perm

Whether to calculate a permutation p-value.

B

Number of permutations.

k

Number of MST layers for a data-level call. The default is floor(sqrt(N)); the largest allowed value is floor(N/2).

n

Number of observations in a graph-level call. Both named and positional legacy graph arguments are supported.

E

Two-column edge matrix in a graph-level call. Do not supply k together with a supplied graph.

Details

An interval with boundaries (i, j) contains observations i + 1, ..., j. When there are r tied maximizing intervals, tauhat (or tauhat_a/tauhat_u) retains the earlier layout: its first r entries are the left boundaries and its last r entries are the corresponding right boundaries. All returned intervals satisfy the requested length range after the documented endpoint adjustments. The analytic approximation requires a nonzero length range; use permutation calibration for a single permitted interval length.

Value

A list with scanZ and any requested p-values. Each requested component of scanZ contains the estimated interval tauhat, maximum scan statistic Zmax, and scan surface. Data-level calls additionally return the constructed graph and k.

Note

Analytic integrations are checked for convergence and finite probability outputs in [0,1]. An unavailable approximation raises an error rather than returning an invalid probability. Setting pval.appr = FALSE allows justified permutation calibration to be used instead. Scan components must be well-defined on the requested domain; undefined components are not replaced by zero.

See Also

gseg1, gseg2_graph, gseg2_discrete, gseg_kmst

Examples

set.seed(2)
x <- matrix(rnorm(80), nrow = 20)
x[8:13, ] <- x[8:13, ] + 1

# Main interface: build the default k-MST and report MET.
ans <- gseg2(x, pval.appr = FALSE)
names(ans$scanZ)
ans$k

# Earlier graph-level calls remain supported.
ans.graph <- gseg2(nrow(x), ans$graph, pval.appr = FALSE)

Data-Level Alias for gseg2

Description

A compatibility alias for the data-level gseg2 interface. New code may call gseg2 directly.

Usage

gseg2_data(x = NULL, dissimilarity = NULL, k = NULL,
  statistics = "m", ...)

Arguments

x

A numeric matrix with observations in rows.

dissimilarity

A square symmetric dissimilarity matrix or a dist object. Supply exactly one of x and dissimilarity.

k

Number of MST layers. The default is floor(sqrt(N)).

statistics

Scan statistic or statistics; see gseg2.

...

Additional arguments passed to gseg2.

Value

The result from gseg2.

See Also

gseg2, gseg_kmst

Examples

set.seed(1)
x <- matrix(rnorm(60), nrow = 20)
ans <- gseg2_data(x, pval.appr = FALSE)

Graph-Based Change-Point Detection for Changed Interval for Data with Repeated Observations

Description

This function finds an interval in the sequence where their underlying distribution differs from the rest of the sequence when data has repeated observations. It provides four graph-based test statistics.

Usage

gseg2_discrete(n, E, id, statistics="m", l0=0.05*n, l1=0.95*n, 
   pval.appr=TRUE, skew.corr=TRUE, pval.perm=FALSE, B=100)

Arguments

n

The number of observations in the sequence; it must be at least 6.

E

The edge matrix (a "number of edges" by 2 matrix) for the similarity graph. Each row contains the node indices of an edge.

id

The index of observations (order of observations).

statistics

The scan statistics to be computed. The default is "m", which reports the max-type scan.

"all": specifies to compute all of the scan statistics: original, weighted, generalized, and max-type;

"o", "ori" or "original": specifies the original edge-count scan statistic;

"w" or "weighted": specifies the weighted edge-count scan statistic;

"g" or "generalized": specifies the generalized edge-count scan statistic; and

"m" or "max": specifies the max-type edge-count scan statistic.

l0

The minimum length of the interval to be considered as a changed interval.

l1

The maximum length of the interval to be considered as a changed interval.

pval.appr

If it is TRUE, the function outputs a p-value approximation based on asymptotic properties. The analytic approximation requires n >= 9.

skew.corr

This argument is useful only when pval.appr=TRUE. If skew.corr is TRUE, the p-value approximation would incorporate skewness correction.

pval.perm

If it is TRUE, the function outputs p-value from doing B permutations, where B is another argument that you can specify. Doing permutation could be time consuming, so use this argument with caution as it may take a long time to finish the permutation.

B

This argument is useful only when pval.perm=TRUE. The default value for B is 100.

Details

An interval with boundaries (i, j) contains observations i + 1, ..., j. When there are r tied maximizing intervals, tauhat (or tauhat_a/tauhat_u) retains the earlier layout: its first r entries are the left boundaries and its last r entries are the corresponding right boundaries. All returned intervals satisfy the requested length range after the documented endpoint adjustments. The analytic approximation requires a nonzero length range; use permutation calibration for a single permitted interval length.

Value

Returns a list scanZ with tauhat, Zmax, and a vector of the scan statistics for each type of scan statistic specified. See below for more details.

tauhat_a

An estimate of the two ends of the changed interval for averaging approach.

tauhat_u

An estimate of the two ends of the changed interval for union approach.

Z_a_max

The test statistic (maximum of the scan statistics) for averaging approach.

Z_u_max

The test statistic (maximum of the scan statistics) for union approach.

Zo_a

A matrix of the original scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "o".

Zo_u

A matrix of the original scan statistics (standardized counts) for union approach if statistic specified is "all" or "o".

Zw_a

A matrix of the weighted scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "w".

Zw_u

A matrix of the weighted scan statistics (standardized counts) for union approach if statistic specified is "all" or "w".

S_a

A matrix of the generalized scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "g".

S_u

A matrix of the generalized scan statistics (standardized counts) for union approach if statistic specified is "all" or "g".

M_a

A matrix of the max-type scan statistics (standardized counts) for averaging approach if statistic specified is "all" or "m".

M_u

A matrix of the max-type scan statistics (standardized counts) for union approach if statistic specified is "all" or "m".

Ro_a

A matrix of raw counts of the original scan statistic for averaging approach. This output only exists if the statistic specified is "all" or "o".

Ro_u

A matrix of raw counts of the original scan statistic for union approach. This output only exists if the statistic specified is "all" or "o".

Rw_a

A matrix of raw counts of the weighted scan statistic for averaging approach. This output only exists if statistic specified is "all" or "w".

Rw_u

A matrix of raw counts of the weighted scan statistic for union approach. This output only exists if statistic specified is "all" or "w".

pval.appr

The approximated p-value based on asymptotic theory for each type of statistic specified.

pval.perm

This output exists only when the argument pval.perm is TRUE . It is the permutation p-value from B permutations and appears for each type of statistic specified (same for perm.curve, perm.maxZs, and perm.Z).

perm.curve

A B by 2 matrix with the first column being critical values corresponding to the p-values in the second column.

perm.maxZs

A sorted vector recording the test statistics in the B permutaitons.

perm.Z

A B by n-squared matrix with each row being the vectorized scan statistics from each permutaiton run.

Note

For the original and weighted scans, a nonpositive observed maximum returns the conservative analytic value 1. This is not an exact finite-sample p-value; permutation calibration remains available.

Analytic integrations are checked for convergence and finite probability outputs in [0,1]. An unavailable approximation raises an error rather than returning an invalid probability. Setting pval.appr = FALSE allows justified permutation calibration to be used instead. Scan components must be well-defined on the requested domain; undefined components are not replaced by zero.

See Also

gSeg, gseg2, nnl, gseg1_discrete

Examples

d = 50
mu = 2
tau = 100
n = 200

set.seed(500)
y1_temp = matrix(rnorm(d*tau),tau)
sam1 = sample(1:tau, replace = TRUE)
y1 = y1_temp[sam1,] 
y2_temp = matrix(rnorm(d*(n-tau),mu/sqrt(d)), n-tau)
sam2 = sample(1:tau, replace = TRUE)
y2 = y2_temp[sam2,] 

y = rbind(y1, y2)

# This data y has repeated observations
y_uni = unique(y)
E = nnl(dist(y_uni), 1)

cha = do.call(paste, as.data.frame(y))    
id = match(cha, unique(cha))

r1 = gseg2_discrete(n, E, id, statistics="all")

Changed-Interval Scan with a Supplied Similarity Graph

Description

Applies the changed-interval graph scan to a supplied edge matrix.

Usage

gseg2_graph(n, E, statistics = "m", l0 = 0.05 * n,
  l1 = 0.95 * n, pval.appr = TRUE, skew.corr = TRUE,
  pval.perm = FALSE, B = 100)

Arguments

n

Number of observations in the sequence.

E

Two-column edge matrix for the similarity graph.

statistics

Scan statistic or statistics; see gseg2.

l0

Minimum candidate interval length.

l1

Maximum candidate interval length.

pval.appr

Whether to calculate the analytic p-value approximation.

skew.corr

Whether to include its skewness correction.

pval.perm

Whether to calculate a permutation p-value.

B

Number of permutations.

Details

An interval with boundaries (i, j) contains observations i + 1, ..., j. When there are r tied maximizing intervals, tauhat (or tauhat_a/tauhat_u) retains the earlier layout: its first r entries are the left boundaries and its last r entries are the corresponding right boundaries. All returned intervals satisfy the requested length range after the documented endpoint adjustments. The analytic approximation requires a nonzero length range; use permutation calibration for a single permitted interval length.

Value

A list containing scan statistics and requested p-values.

Note

Analytic integrations are checked for convergence and finite probability outputs in [0,1]. An unavailable approximation raises an error rather than returning an invalid probability. Setting pval.appr = FALSE allows justified permutation calibration to be used instead. Scan components must be well-defined on the requested domain; undefined components are not replaced by zero.

See Also

gseg2, gseg_kmst

Examples

set.seed(1)
x <- matrix(rnorm(80), nrow = 20)
E <- gseg_kmst(x)
ans <- gseg2_graph(nrow(x), E, pval.appr = FALSE)

Construct a k-MST Similarity Graph

Description

Constructs the k-MST used by default in the data-level gSeg interface.

Usage

gseg_kmst(x = NULL, dissimilarity = NULL, k = NULL)

Arguments

x

Optional data matrix with observations in rows.

dissimilarity

Optional square dissimilarity matrix or a dist object. Supply exactly one of x and dissimilarity.

k

Number of complete MST layers. The default is floor(sqrt(N)); the largest allowed value is floor(N/2).

Details

All input forms require at least three observations. The counting bound k <= floor(N/2) is necessary but does not guarantee that greedy successive edge-disjoint spanning trees exist. The constructed graph is checked to contain exactly k * (N - 1) distinct edges. If previous layers exhaust a vertex's available edges, construction stops with an error instead of returning an incomplete union labelled as complete. Choose a smaller explicit k or supply a graph to a graph-level scan.

Value

A two-column edge matrix containing the union of the first k MST layers.

Note

A dist object must be supplied through dissimilarity, not x, to preserve its distance geometry.

Examples

set.seed(1)
x <- matrix(rnorm(60), nrow = 20)
E <- gseg_kmst(x = x)
attr(E, "k")

The Number of Observations in the Sequence

Description

This is the variable name for the number of observations in the sequences in the "Example" data.


Construct the Nearest Neighbor Link (NNL)

Description

This function provides a method to construct the NNL.

Usage

nnl(distance, K)

Arguments

distance

The distance matrix on the distinct values (a "number of unique observations" by "number of unique observations" matrix).

K

The value of k in "k-MST" or "k-NNL" to construct the similarity graph.

Details

Distances must be finite, nonnegative and symmetric, with zero diagonal. K must be an integer between 1 and floor(N/2). Zero-distance neighbours are allowed, but self-links are excluded. Successive layers use unused edges; a clear error is raised if another connected layer cannot be constructed, even when K satisfies the counting bound.

Value

E

The edge matrix representing the similarity graph on the distinct values with the number of edges in the similarity graph being the number of rows and 2 columns. Each row records the subject indices of the two ends of an edge in the similarity graph.

See Also

gSeg, gseg1_discrete, gseg2_discrete

Examples

n = 50
d = 10
dat = matrix(rnorm(d*n),n)
sam = sample(1:n, replace = TRUE)
dat = dat[sam,] 

# This data has repeated observations
dat_uni = unique(dat)
E = nnl(dist(dat_uni), 1)