| 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 |
| 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 |
statistics |
The scan statistic or statistics to compute. The default
|
n0 |
First candidate change-point location. The default is
|
n1 |
Last candidate change-point location. The default is
|
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
|
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
|
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 |
k |
Number of MST layers. The default is |
statistics |
Scan statistic or statistics; see |
... |
Additional arguments passed to |
Value
The result from gseg1.
See Also
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
|
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 |
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 |
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
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 |
statistics |
The scan statistic or statistics to compute. The default
|
l0 |
Minimum candidate interval length. The default is |
l1 |
Maximum candidate interval length. The default is |
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
|
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
|
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 |
k |
Number of MST layers. The default is |
statistics |
Scan statistic or statistics; see |
... |
Additional arguments passed to |
Value
The result from gseg2.
See Also
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
|
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 |
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 |
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
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 |
k |
Number of complete MST layers. The default is |
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)