Knee Detection

knee_detection

Knee point detection for Pareto fronts.

Implements multiple methods for identifying "knee" points - solutions that represent the best compromise between competing objectives.

Functions

detect_knee_points

detect_knee_points(objectives: ndarray | DataFrame, method: str = 'angle', n_knees: int = 1, normalize: bool = True) -> ndarray

Detect knee points on Pareto front.

A knee point represents the best compromise - maximum trade-off benefit per unit sacrifice. These are often the most preferred solutions.

Parameters:

Name	Type	Description	Default
objectives	ndarray | DataFrame	Array or DataFrame of objective values (assumed minimization)	required
method	str	Detection method ('angle', 'distance', 'tradeoff', 'curvature')	'angle'
n_knees	int	Number of knee points to detect	1
normalize	bool	Whether to normalize objectives to [0,1]	True

Returns:

Type	Description
ndarray	Array of indices of knee points, sorted by knee quality (best first)

Source code in optiscope/analysis/knee_detection.py

def detect_knee_points(
    objectives: np.ndarray | pd.DataFrame,
    method: str = "angle",
    n_knees: int = 1,
    normalize: bool = True,
) -> np.ndarray:
    """
    Detect knee points on Pareto front.

    A knee point represents the best compromise - maximum trade-off benefit
    per unit sacrifice. These are often the most preferred solutions.

    Args:
        objectives: Array or DataFrame of objective values (assumed minimization)
        method: Detection method ('angle', 'distance', 'tradeoff', 'curvature')
        n_knees: Number of knee points to detect
        normalize: Whether to normalize objectives to [0,1]

    Returns:
        Array of indices of knee points, sorted by knee quality (best first)
    """
    # Convert to numpy array
    if isinstance(objectives, pd.DataFrame):
        obj_array = objectives.values
    else:
        obj_array = np.asarray(objectives)

    if obj_array.shape[1] != 2:
        raise ValueError("Knee detection currently only supports 2D objectives")

    n_points = len(obj_array)

    if n_points == 0:
        return np.array([], dtype=int)

    if n_points <= 2:
        return np.arange(n_points)

    # Normalize if requested
    if normalize:
        obj_min = obj_array.min(axis=0)
        obj_max = obj_array.max(axis=0)
        obj_range = obj_max - obj_min
        obj_range[obj_range < 1e-10] = 1.0
        obj_normalized = (obj_array - obj_min) / obj_range
    else:
        obj_normalized = obj_array.copy()

    # Sort by first objective for ordered Pareto front
    sort_idx = np.argsort(obj_normalized[:, 0])
    obj_sorted = obj_normalized[sort_idx]

    # Apply selected method
    if method == "angle":
        knee_scores = _angle_based_knee_detection(obj_sorted)
    elif method == "distance":
        knee_scores = _distance_based_knee_detection(obj_sorted)
    elif method == "tradeoff":
        knee_scores = _tradeoff_based_knee_detection(obj_sorted)
    elif method == "curvature":
        knee_scores = _curvature_based_knee_detection(obj_sorted)
    else:
        raise ValueError(f"Unknown method: {method}")

    # Get top n_knees
    top_knee_indices = np.argsort(knee_scores)[::-1][:n_knees]

    # Convert back to original indices
    original_indices = sort_idx[top_knee_indices]

    return original_indices

find_knee_region

find_knee_region(objectives: ndarray | DataFrame, width: float = 0.1, method: str = 'angle', normalize: bool = True) -> tuple[ndarray, float, float]

Find knee region instead of single point.

Returns a region around the knee point where solutions are similar.

Parameters:

Name	Type	Description	Default
objectives	ndarray | DataFrame	Objective values	required
width	float	Width of knee region (as fraction of normalized space)	0.1
method	str	Knee detection method	'angle'
normalize	bool	Normalize objectives	True

Returns:

Type	Description
tuple[ndarray, float, float]	Tuple of (indices in knee region, region_start, region_end)

Source code in optiscope/analysis/knee_detection.py

def find_knee_region(
    objectives: np.ndarray | pd.DataFrame,
    width: float = 0.1,
    method: str = "angle",
    normalize: bool = True,
) -> tuple[np.ndarray, float, float]:
    """
    Find knee region instead of single point.

    Returns a region around the knee point where solutions are similar.

    Args:
        objectives: Objective values
        width: Width of knee region (as fraction of normalized space)
        method: Knee detection method
        normalize: Normalize objectives

    Returns:
        Tuple of (indices in knee region, region_start, region_end)
    """
    # Find primary knee point
    knee_idx = detect_knee_points(objectives, method=method, n_knees=1, normalize=normalize)[0]

    # Convert to numpy
    if isinstance(objectives, pd.DataFrame):
        obj_array = objectives.values
    else:
        obj_array = np.asarray(objectives)

    # Normalize
    if normalize:
        obj_min = obj_array.min(axis=0)
        obj_max = obj_array.max(axis=0)
        obj_range = obj_max - obj_min
        obj_range[obj_range < 1e-10] = 1.0
        obj_normalized = (obj_array - obj_min) / obj_range
    else:
        obj_normalized = obj_array

    # Find points within width of knee point
    knee_point = obj_normalized[knee_idx]
    distances = np.linalg.norm(obj_normalized - knee_point, axis=1)

    region_indices = np.where(distances <= width)[0]

    # Calculate region bounds in normalized space
    if len(region_indices) > 0:
        region_points = obj_normalized[region_indices]
        region_start = region_points[:, 0].min()
        region_end = region_points[:, 0].max()
    else:
        region_start = region_end = knee_point[0]

    return region_indices, region_start, region_end

rank_by_knee_distance

rank_by_knee_distance(objectives: ndarray | DataFrame, knee_indices: ndarray, normalize: bool = True) -> ndarray

Rank all solutions by distance to nearest knee point.

Parameters:

Name	Type	Description	Default
objectives	ndarray | DataFrame	Objective values	required
knee_indices	ndarray	Indices of knee points	required
normalize	bool	Normalize objectives	True

Returns:

Type	Description
ndarray	Array of ranks (0 = on knee, higher = farther from knee)

Source code in optiscope/analysis/knee_detection.py

def rank_by_knee_distance(
    objectives: np.ndarray | pd.DataFrame, knee_indices: np.ndarray, normalize: bool = True
) -> np.ndarray:
    """
    Rank all solutions by distance to nearest knee point.

    Args:
        objectives: Objective values
        knee_indices: Indices of knee points
        normalize: Normalize objectives

    Returns:
        Array of ranks (0 = on knee, higher = farther from knee)
    """
    if isinstance(objectives, pd.DataFrame):
        obj_array = objectives.values
    else:
        obj_array = np.asarray(objectives)

    # Normalize
    if normalize:
        obj_min = obj_array.min(axis=0)
        obj_max = obj_array.max(axis=0)
        obj_range = obj_max - obj_min
        obj_range[obj_range < 1e-10] = 1.0
        obj_normalized = (obj_array - obj_min) / obj_range
    else:
        obj_normalized = obj_array

    # Calculate distance to nearest knee
    knee_points = obj_normalized[knee_indices]
    distances = cdist(obj_normalized, knee_points)
    min_distances = distances.min(axis=1)

    # Rank by distance
    ranks = np.argsort(min_distances)

    return ranks

calculate_knee_quality_metrics

calculate_knee_quality_metrics(objectives: ndarray | DataFrame, knee_indices: ndarray, normalize: bool = True) -> dict

Calculate quality metrics for detected knee points.

Parameters:

Name	Type	Description	Default
objectives	ndarray | DataFrame	Objective values	required
knee_indices	ndarray	Detected knee point indices	required
normalize	bool	Normalize objectives	True

Returns:

Type	Description
dict	Dictionary with quality metrics

Source code in optiscope/analysis/knee_detection.py

def calculate_knee_quality_metrics(
    objectives: np.ndarray | pd.DataFrame, knee_indices: np.ndarray, normalize: bool = True
) -> dict:
    """
    Calculate quality metrics for detected knee points.

    Args:
        objectives: Objective values
        knee_indices: Detected knee point indices
        normalize: Normalize objectives

    Returns:
        Dictionary with quality metrics
    """
    if isinstance(objectives, pd.DataFrame):
        obj_array = objectives.values
    else:
        obj_array = np.asarray(objectives)

    if normalize:
        obj_min = obj_array.min(axis=0)
        obj_max = obj_array.max(axis=0)
        obj_range = obj_max - obj_min
        obj_range[obj_range < 1e-10] = 1.0
        obj_normalized = (obj_array - obj_min) / obj_range
    else:
        obj_normalized = obj_array

    knee_points = obj_normalized[knee_indices]

    # Distance from ideal point (origin in normalized space)
    ideal_point = np.zeros(obj_array.shape[1])
    distances_to_ideal = np.linalg.norm(knee_points - ideal_point, axis=1)

    # Distance from nadir point
    nadir_point = np.ones(obj_array.shape[1])
    distances_to_nadir = np.linalg.norm(knee_points - nadir_point, axis=1)

    # Balance score (how centered between ideal and nadir)
    balance_scores = 1 - abs(distances_to_ideal - distances_to_nadir)

    # Spread of knee points
    if len(knee_indices) > 1:
        knee_distances = cdist(knee_points, knee_points)
        np.fill_diagonal(knee_distances, np.inf)
        min_separation = knee_distances.min()
        max_separation = knee_distances.max()
    else:
        min_separation = max_separation = 0.0

    return {
        "n_knees": len(knee_indices),
        "avg_distance_to_ideal": float(distances_to_ideal.mean()),
        "avg_distance_to_nadir": float(distances_to_nadir.mean()),
        "avg_balance_score": float(balance_scores.mean()),
        "min_knee_separation": float(min_separation),
        "max_knee_separation": float(max_separation),
        "knee_indices": knee_indices.tolist(),
    }