elbow_helper.multi_segmentation module

Phase M1: piecewise-linear segmentation for elbow_helper.robust_knees().

Ported from the validated research/multiknee/segmentation.py (see research/multiknee/RESULTS.md and ELBOW-en.tex for the derivation and the empirical comparison against greedy binary segmentation). Segments are independent OLS lines, not the continuous broken line elbow_helper.segmented uses for the single-knee pipeline; see ELBOW-en.tex section 5 for why that difference is deliberate.

Author

Warith Harchaoui, <warith.harchaoui@deraison.ai>

class elbow_helper.multi_segmentation.SegmentCostTable(x, y)[source]

Bases: object

O(1)-per-query OLS segment cost, via prefix sums of sufficient statistics.

Parameters:

  • x (numpy.ndarray) – The curve, already cleaned and sorted by x.

  • y (numpy.ndarray) – The curve, already cleaned and sorted by x.

cost(i, j)[source]

RSS of the best OLS line on points i..j-1.

Parameters:

  • i (int) – Half-open segment bounds into the original x, y arrays.

  • j (int) – Half-open segment bounds into the original x, y arrays.

Returns:

The residual sum of squares of the best-fit line on that segment.

Return type:

float

fit(i, j)[source]

OLS (intercept, slope) on points i..j-1.

Parameters:

  • i (int) – Half-open segment bounds into the original x, y arrays.

  • j (int) – Half-open segment bounds into the original x, y arrays.

Returns:

(intercept, slope) of the best-fit line on that segment.

Return type:

tuple of float

class elbow_helper.multi_segmentation.Segmentation(breakpoints, boundaries, sse, n)[source]

Bases: object

A concrete k-breakpoint segmentation of x, y.

Parameters:

  • breakpoints (tuple of int) – Interior cut indices, one per breakpoint.

  • boundaries (tuple of int) – Segment boundaries, (0, *breakpoints, n).

  • sse (float) – Total residual sum of squares summed over all segments.

  • n (int) – Number of points in the curve this segmentation was fit to.

boundaries: Tuple[int, ...]
breakpoints: Tuple[int, ...]
property k: int

Number of breakpoints (segments = k + 1).

n: int
property segment_lengths: Tuple[int, ...]

Length, in points, of each segment in boundaries order.

sse: float
elbow_helper.multi_segmentation.dp_optimal_partition(x, y, k_max, min_seg=3)[source]

Exact optimal-partitioning DP: the best segmentation for every k = 0..k_max.

See ELBOW-en.tex section 7 for the recursion and complexity, and research/multiknee/RESULTS.md for why this is used instead of greedy binary segmentation.

Parameters:

  • x (numpy.ndarray) – The curve, already cleaned and sorted by x.

  • y (numpy.ndarray) – The curve, already cleaned and sorted by x.

  • k_max (int) – Largest number of breakpoints to solve for.

  • min_seg (int, optional) – Minimum number of points per segment. Defaults to 3.

Returns:

One optimal Segmentation per achievable k from 0 up to min(k_max, (n // min_seg) - 1), in increasing order of k.

Return type:

list of Segmentation