InstanceSpace Python v0.4.1

instancespace.stages.trace

TRACE Stage Module for Performance-Based Footprint Estimation.

This module implements the TRACE stage, which analyzes the performance of multiple algorithms by generating geometric footprints. These footprints represent the areas of good, best, and beta performance based on the clustering of instance data. The footprints are further evaluated for their density and purity in relation to the performance metrics of the algorithms.

This module provides the historical DBSCAN-based TRACE implementation and MATLAB's current two- or three-dimensional TRACE3 alpha-shape implementation.

The TRACE stage has several key steps:

  1. Cluster the instance data using DBSCAN to identify regions of interest.
  2. Generate geometric footprints representing algorithm performance.
  3. Detect and resolve contradictions between algorithm footprints.
  4. Compute performance metrics such as area, density, and purity for each footprint.
  5. Optionally smoothen the polygonal boundaries for more refined footprint shapes.

This module is structured around the Trace class, which encapsulates the entire process of footprint estimation and performance evaluation. Methods are provided to cluster data, generate polygons, resolve contradictions between footprints, and compute statistical metrics.

Dependencies:

  • multiprocessing
  • numpy
  • pandas
  • scipy
  • shapely
  • sklearn
Classes

Trace : The primary class that implements the TRACE stage, providing methods to generate footprints and compute performance-based metrics.

Footprint : A dataclass representing a footprint with geometric and statistical properties.

Functions

from_polygon(polygon, z, y_bin, smoothen=False): A function to create a Footprint object from a given polygon and corresponding instance data, optionally smoothing the polygon borders.

POLYGON_MIN_POINT_REQUIREMENT = 3
TRACE_ARRAY_DIMENSIONS = 2
TRACE_2D_COORDINATES = 2
TRACE_3D_COORDINATES = 3
TRACE_COORDINATE_COUNTS = (2, 3)
MIN_ALPHA_SPECTRUM_SIZE = 2
TRACE_SUMMARY_DECIMALS = 3
type TraceGeometry = shapely.geometry.polygon.Polygon | shapely.geometry.multipolygon.MultiPolygon | instancespace.utils.alpha_shape.TetrahedralMesh
class TraceInputs(typing.NamedTuple):

A named tuple to encapsulate the inputs required for the TRACE analysis.

Attributes
  • z (NDArray[np.double]): The space of instances, represented as an array of data points (features).
  • selection0 (NDArray[np.int_]): PYTHIA selections as zero-based algorithm indices; -1 means that no algorithm was selected.
  • p (NDArray[np.int_]): PRELIM selections as MATLAB-compatible one-based algorithm indices.
  • beta (NDArray[np.bool_]): A binary array indicating specific beta thresholds for the footprint.
  • algo_labels (list[str]): A list of labels for each algorithm, represented as strings.
  • y_hat (NDArray[np.bool_]): A binary array indicating performance of the Pythia algorithm, where each column corresponds to an algorithm's performance.
  • y_bin (NDArray[np.bool_]): A binary array indicating performance of the data-driven approach, where each column corresponds to an algorithm's performance.
  • trace_options (TraceOptions): Configuration options for the TRACE analysis, determining specific behaviour for footprint construction and evaluation.
  • general_options (GeneralOptions): General options (e.g. verbosity), not specific to any one stage.
TraceInputs( z: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], selection0: numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]], p: numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]], beta: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], algo_labels: list[str], y_hat: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], trace_options: instancespace.data.options.TraceOptions, parallel_options: instancespace.data.options.ParallelOptions, general_options: instancespace.data.options.GeneralOptions, executor: concurrent.futures.thread.ThreadPoolExecutor | None = None, pythia_options: instancespace.data.options.PythiaOptions = PythiaOptions(cv_folds=5, is_poly_krnl=False, use_weights=False, params=None, classifier='svm', tuning='sobol', n_tuning_iter=20, skip=False))

Create new instance of TraceInputs(z, selection0, p, beta, algo_labels, y_hat, y_bin, trace_options, parallel_options, general_options, executor, pythia_options)

z: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]]

Alias for field number 0

selection0: numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]]

Alias for field number 1

p: numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]]

Alias for field number 2

beta: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]

Alias for field number 3

algo_labels: list[str]

Alias for field number 4

y_hat: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]

Alias for field number 5

y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]

Alias for field number 6

trace_options: instancespace.data.options.TraceOptions

Alias for field number 7

parallel_options: instancespace.data.options.ParallelOptions

Alias for field number 8

general_options: instancespace.data.options.GeneralOptions

Alias for field number 9

executor: concurrent.futures.thread.ThreadPoolExecutor | None

Alias for field number 10

pythia_options: instancespace.data.options.PythiaOptions

Alias for field number 11

class TraceOutputs(typing.NamedTuple):

A named tuple to encapsulate the outputs of the TRACE analysis.

Attributes
  • space (Footprint): The footprint representing the entire space of instances.
  • good (list[Footprint]): A list of footprints for the regions of good performance for each algorithm.
  • best (list[Footprint]): A list of footprints for the regions of best performance for each algorithm.
  • hard (Footprint): The footprint representing the region that fails to meet the beta threshold.
  • summary (pd.DataFrame): A pandas DataFrame containing the summary of the footprint analysis, including metrics such as area, density, and purity for both good and best performance regions.
TraceOutputs( space: instancespace.data.model.Footprint, good: list[instancespace.data.model.Footprint], best: list[instancespace.data.model.Footprint], hard: instancespace.data.model.Footprint, trace_summary: pandas.core.frame.DataFrame, trace_boundary_tolerance: float = 0.0)

Create new instance of TraceOutputs(space, good, best, hard, trace_summary, trace_boundary_tolerance)

space: instancespace.data.model.Footprint

Alias for field number 0

good: list[instancespace.data.model.Footprint]

Alias for field number 1

best: list[instancespace.data.model.Footprint]

Alias for field number 2

hard: instancespace.data.model.Footprint

Alias for field number 3

trace_summary: pandas.core.frame.DataFrame

Alias for field number 4

trace_boundary_tolerance: float

Alias for field number 5

class TracePredictInput(typing.NamedTuple):

Inputs for testing unseen projected instances against fitted footprints.

TracePredictInput( z: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], n_new_algos: int = 0)

Create new instance of TracePredictInput(z, n_new_algos)

z: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]]

Alias for field number 0

n_new_algos: int

Alias for field number 1

class TracePredictOutput(typing.NamedTuple):

Inclusive good/best footprint-membership matrices.

TracePredictOutput( in_good: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], in_best: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]])

Create new instance of TracePredictOutput(in_good, in_best)

in_good: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]

Alias for field number 0

in_best: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]

Alias for field number 1

class TraceStage(instancespace.stages.stage.Stage[instancespace.stages.trace.TraceInputs, instancespace.stages.trace.TraceOutputs], instancespace.stages.stage.PredictiveStage[instancespace.stages.trace.TracePredictInput, instancespace.data.model.TraceOut, instancespace.stages.trace.TracePredictOutput]):

A class to manage the TRACE analysis process for performance footprints.

The TRACE class is designed to analyze the performance of different algorithms by generating geometric footprints that represent areas of good, best, and beta performance. The footprints are constructed based on clustering of instance data and are evaluated for their density and purity relative to specific algorithmic performance metrics.

Attributes
  • z (NDArray[np.double]): The space of instances, represented as an array of data points (features).
  • y_bin (NDArray[np.bool_]): Binary indicators of performance, where each column corresponds to an algorithm's performance.
  • p (NDArray[np.int_]): Performance metrics for algorithms, represented as integers where each value corresponds to the index of an algorithm.
  • beta (NDArray[np.bool_]): Specific binary thresholds for footprint calculation.
  • algo_labels (list[str]): List of labels for each algorithm.
  • opts (TraceOptions): Configuration options for TRACE and its subroutines, controlling the behavior of the analysis.
TraceStage( z: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], p: numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]], beta: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], algo_labels: list[str], trace_opts: instancespace.data.options.TraceOptions, parallel_opts: instancespace.data.options.ParallelOptions, general_opts: instancespace.data.options.GeneralOptions, executor: concurrent.futures.thread.ThreadPoolExecutor | None = None, y_hat: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]] | None = None, pythia_skipped: bool = False)

Initialise the Trace analysis with provided data and options.

Parameters
  • z (NDArray[np.double]): The space of instances, represented as an array of data points (features).
  • y_bin (NDArray[np.bool_]): Binary indicators of performance for each algorithm.
  • p (NDArray[np.int_]): Performance metrics for algorithms, where each value corresponds to the index of an algorithm.
  • beta (NDArray[np.bool_]): Specific binary thresholds for footprint calculation.
  • algo_labels (list[str]): List of labels for each algorithm.
  • trace_opts (TraceOptions): Configuration options for TRACE and its subroutines.
  • parallel_opts (ParallelOptions): Configuration options for parallel processing in Matilda.
  • general_opts (GeneralOptions): General options (e.g. verbosity), not specific to any one stage.
  • executor (ThreadPoolExecutor | None): A caller-owned, already-running pool to submit footprint work to instead of creating and tearing down a fresh one. None (the default) preserves the previous per-call pool behaviour.
  • y_hat (NDArray[np.bool_] | None): Optional PYTHIA predictions used only by TRACE3.
  • pythia_skipped (bool): Whether PYTHIA intentionally returned placeholder predictions.
z
y_bin
p
beta
algo_labels
opts
parallel_opts
general_opts
executor
y_hat
pythia_skipped
@staticmethod
def predict( inputs: TracePredictInput, fitted: instancespace.data.model.TraceOut) -> TracePredictOutput:

Apply trained TRACE geometry without rebuilding or mutating it.

@staticmethod
def trace( z: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], p: numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]], beta: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], algo_labels: list[str], trace_opts: instancespace.data.options.TraceOptions, parallel_opts: instancespace.data.options.ParallelOptions, general_opts: instancespace.data.options.GeneralOptions, executor: concurrent.futures.thread.ThreadPoolExecutor | None = None, *, y_hat: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]] | None = None, pythia_skipped: bool = False) -> TraceOutputs:

Perform the TRACE footprint analysis.

Parameters
  • z (NDArray[np.double]): The space of instances.
  • y_bin (NDArray[np.bool_]): Binary indicators of performance.
  • p (NDArray[np.int_]): Performance metrics for algorithms.
  • beta (NDArray[np.bool_]): Specific beta threshold for footprint calculation.
  • algo_labels (list[str]): Labels for each algorithm.
  • trace_opts (TraceOptions): Configuration options for TRACE and its subroutines.
  • parallel_opts (ParallelOptions): Configuration options for parallel processing in Matilda.
  • general_opts (GeneralOptions): General options for all stages, for example verbosity.
  • executor (ThreadPoolExecutor | None): A caller-owned pool to reuse instead of creating a fresh one.
  • y_hat (NDArray[np.bool_] | None): Optional PYTHIA predictions used only by TRACE3.
  • pythia_skipped (bool): Whether PYTHIA intentionally returned placeholder predictions.
Returns
  • TraceOutputs: The analysis results. These include the footprints and the summary statistics.
@staticmethod
def rescore( trained: instancespace.data.model.TraceOut, z: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], p: numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]], beta: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], algo_labels: list[str]) -> instancespace.data.model.TraceOut:

Re-evaluate trained geometry against new truth without rebuilding it.

def build( self, y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]) -> instancespace.data.model.Footprint:

Construct a footprint polygon using DBSCAN clustering.

Parameters
  • y_bin (NDArray[np.bool_]): Binary indicator vector indicating which data points are of interest.
Returns
  • Footprint: The constructed footprint with calculated area, density, and purity.
def contra( self, base: instancespace.data.model.Footprint, test: instancespace.data.model.Footprint, y_base: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], y_test: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]) -> tuple[instancespace.data.model.Footprint, instancespace.data.model.Footprint]:

Detect and resolve contradictions between two footprint polygons.

Parameters
  • base (Footprint): The base footprint polygon.
  • test (Footprint): The test footprint polygon.
  • y_base (NDArray[np.bool_]): Binary array indicating the points corresponding to the base footprint.
  • y_test (NDArray[np.bool_]): Binary array indicating the points corresponding to the test footprint.
Returns
  • tuple: Updated base and test footprints after resolving contradictions.
def tight( self, polygon: shapely.geometry.polygon.Polygon | shapely.geometry.multipolygon.MultiPolygon, y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]) -> shapely.geometry.polygon.Polygon | shapely.geometry.multipolygon.MultiPolygon:

Refine an existing polygon by removing slivers and improving its shape.

Parameters
  • polygon (Polygon | MultiPolygon): The polygon or multipolygon to be refined.
  • y_bin (NDArray[np.bool_]): Binary array indicating which data points belong to the polygon.
Returns
  • Polygon | MultiPolygon: The refined polygon, or an empty polygon if refinement fails.
def fit_poly( self, polydata: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]]) -> shapely.geometry.polygon.Polygon | shapely.geometry.multipolygon.MultiPolygon | None:

Fit a polygon to the given data points, following the purity constraints.

Parameters
  • polydata (NDArray[np.double]): The data points to fit the polygon to.
  • y_bin (NDArray[np.bool_]): Binary array indicating which data points should be considered for the polygon.
Returns
  • Polygon | MultiPolygon | None: The fitted polygon, or None if the fitting fails.
@staticmethod
def summary( footprint: instancespace.data.model.Footprint, space_area: float, space_density: float) -> list[float]:

Summarize the footprint metrics.

Parameters
  • footprint (Footprint): The footprint to summarize.
  • space_area (float): The total area of the space being analyzed.
  • space_density (float): The density of the entire space.
Returns
  • list: A list containing summarized metrics such as area, normalized area, density, normalized density, and purity.
def throw(self) -> instancespace.data.model.Footprint:

Generate a footprint with default values, indicating insufficient data.

Returns
  • Footprint: An instance of Footprint with default values.
@staticmethod
def run_dbscan( y_bin: numpy.ndarray[typing.Any, numpy.dtype[numpy.bool_]], data: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]]) -> numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]]:

Perform DBSCAN clustering on the dataset.

Parameters
  • y_bin (NDArray[np.bool_]): Binary indicator vector to filter the data points.
  • data (NDArray[np.double]): The dataset to cluster.
Returns
  • NDArray[np.int_]: Array of cluster labels for each data point.
@staticmethod
def epsilon( x: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], k: int) -> float:

Analytical way of estimating neighborhood radius for DBSCAN.

Parameters
  • x (NDArray[np.double]): data matrix (m, n); m-objects, n-variables
  • k (int): number of objects in a neighborhood of an object (minimal number of objects considered as a cluster)
Returns
  • float: The estimated neighborhood radius.
@staticmethod
def dist( i: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], x: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]]) -> numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]]:

Calculate the Euclidean distances between objects.

Parameters
  • i (NDArray[np.double]): an object (1, n)
  • x (NDArray[np.double]): data matrix (m, n); m-objects, n-variables
Returns
  • NDArray[np.double]: The Euclidean distances, with shape (m,).
@staticmethod
def dbscan( x: numpy.ndarray[typing.Any, numpy.dtype[numpy.float64]], k: int, eps: float) -> numpy.ndarray[typing.Any, numpy.dtype[numpy.int64]]:

Density-Based Spatial Clustering of Applications with Noise (DBSCAN).

Parameters
  • x (NDArray[np.double]): data matrix (m, n); m-objects, n-variables
  • k (int): minimum number of points to form a cluster
  • eps (float): neighborhood radius; if None, it will be estimated using the epsilon function
Returns
  • NDArray[np.int_]: Cluster assignments for each point (-1 for noise)
def process_algorithm( self, i: int) -> tuple[int, instancespace.data.model.Footprint, instancespace.data.model.Footprint]:

Process an algorithm to calculate its good and best performance footprints.

Parameters
  • i (int): Index of the algorithm to process.
Returns
  • tuple[int, Footprint, Footprint]: The index of the algorithm, and its good and best performance footprints.
def compute_algorithm_qualities( self, n_algos: int) -> tuple[list[instancespace.data.model.Footprint], list[instancespace.data.model.Footprint]]:

Perform parallel processing to calculate footprints for multiple algorithms.

Parameters
  • n_workers (int): Number of worker threads to use.
  • n_algos (int): Number of algorithms to process.
Returns
  • tuple[list[Footprint], list[Footprint]]: Lists of good and best performance footprints for each algorithm.