quasildr.utils

Functions:

count_degree(edge_list, N)

Compute degrees of all nodes in a graph.

extract_segments(edge_list, degree)

Extract segments from a graph.

extract_structural_backbone(t, data, s[, ...])

Construct simplified graphs connecting data points there have been projected to density ridges.

locCov(data, query, bw[, min_radius, ...])

Computes Local Covariance matrices.

make_mst(t)

Construct minimum spanning tree.

make_projected_mst(t, data[, radius])

Experimental function

make_trajectory(t[, output_prefix, ...])

Construct MST, prune minor branches, and segment.

mst(D)

Construct minimum spanning tree from dense matrix.

subspace_angles(A, B)

Fast computation of subspace angles given A and B are orthogonal basis matrices and only accuracy of small angles are of concern.
quasildr.utils.count_degree(edge_list, N)[source]

Compute degrees of all nodes in a graph.

Parameters

  • edge_list (2D array or list) – 2D array or list where each row or item has two values indicating start and end indices.

  • N (int) – Number of nodes in the graph.

Returns

degree – 1D array containing degrees of each node

Return type

1D array

quasildr.utils.extract_segments(edge_list, degree)[source]

Extract segments from a graph. It can be used for, for example, paritioning a graph into different branches.

Parameters

  • edge_list (2D array or list) – 2D array or list where each row or item has two values indicating start and end indices.

  • degree (1D array) – 1D array containing the degree of each node. This has to be consistent with edge_list.

Returns

segments – Partitioned segments represented by a list in which each item is a list containing indices in a segments.

Return type

list

quasildr.utils.extract_structural_backbone(t, data, s, max_angle=90, relaxation=0)[source]

Construct simplified graphs connecting data points there have been projected to density ridges.

Two graphs are constructed for different purposes. The first graph (g_simple) is constructed with two major steps:

  1. Construct nearest neighbor graph on both ridge positions

and raw data positions and combine. 2. Simplify graph so that each point is only connected to up to 2^ridge_dimensionality points with a set of filtering criteria.

The second graph (g_mst) has two extra steps: 3. If the graph is not fully connected, connect the components by nearest neigbors between all pairs of components. 4. Construct a minimum spanning tree of the graph.

Parameters

  • t (2D array) – Density ridge positions. Typically projected to density ridges with quasildr.dridge.Scms.

  • data (2D array) – Original data points.

  • s (object) – quasildr.dridge.Scms object which were used to produce t0.

  • max_angle (float, optional) – Maximum angle in degree for filtering graph edges. Default is 90.

  • relaxation (float, optional) – The relaxation parameter used to produce t0. See quasildr.dridge.Scms.scms documention.

Returns

  • g_simple (sparse matrix) – Simplified graph constructed without explicit shape or connectivity constraints (g_simple)

  • and the other one is from step 2

  • g_mst (sparse matrix) – A tree-shaped graph connecting all points (g_mst). from step 4.

quasildr.utils.locCov(data, query, bw, min_radius=0, shrinkage=False, cov_data=None)[source]

Computes Local Covariance matrices. Data points were weighted with a Gaussian kernel centered at the query point

Parameters

  • data (2D array) – Array containing data points of shape (N, p)

  • query (2D array) – Array containing the query point of shape (1, p)

  • bw (float) – Gaussian kernel bandwidth

  • min_radius (float, optional) – If specified, clip the bandwidth to the min_radius-th nearest neighbor.

  • shrinkage (bool, optional) – Apply OAS shrinkage for computing local covariance. Default is False.

  • cov_data (2D array, optional) – Array containing data points of shape (N, p), if specified will replace data for covariance calculations, while data is still used to define the local neighborhood.

quasildr.utils.make_mst(t)[source]

Construct minimum spanning tree. Takes input from Euclidean space and construct graph based on pairwise distances

Parameters

t (2D array) – Input data points.

Returns

edge_list – Edge list of the minimum spanning tree

Return type

2D array

quasildr.utils.make_projected_mst(t, data, radius=0.1)[source]

Experimental function

quasildr.utils.make_trajectory(t, output_prefix=None, prune_threshold=3)[source]

Construct MST, prune minor branches, and segment.

Parameters

  • t –

  • output_prefix –

  • prune_threshold –

quasildr.utils.mst(D)[source]

Construct minimum spanning tree from dense matrix.

Parameters

D (array or sparse matrix) – Edge data in 2D square array or matrix format. Non-zero values represent edges.

Returns

edge_list – Edge list of the minimum spanning tree

Return type

2D array

quasildr.utils.subspace_angles(A, B)[source]

Fast computation of subspace angles given A and B are orthogonal basis matrices and only accuracy of small angles are of concern. Large angle are not numerically accurate.

Parameters

  • A (3D array) – Array containing data points of shape (n, p, p).

  • B (3D array) – Array containing data points of shape (n, p, p).