| | import math
|
| | from typing import Dict, Optional
|
| |
|
| |
|
| | class ComplexityScorer:
|
| | """
|
| | Complexity scoring for feature selection algorithms
|
| | based on instantiated time and space complexity.
|
| | """
|
| |
|
| | def __init__(self, alpha: float = 0.7, log_base: float = math.e):
|
| | """
|
| | Parameters
|
| | ----------
|
| | alpha : float
|
| | Weight for time complexity in the final score.
|
| | Typical values: 0.6 ~ 0.8
|
| | log_base : float
|
| | Base of logarithm (default: natural log).
|
| | """
|
| | self.alpha = alpha
|
| | self.log_base = log_base
|
| |
|
| |
|
| |
|
| |
|
| |
|
| | def _log(self, x: float) -> float:
|
| | """Logarithm with configurable base."""
|
| | if self.log_base == math.e:
|
| | return math.log(x)
|
| | return math.log(x, self.log_base)
|
| |
|
| | def complexity_score(self, value: float, min_value: float) -> float:
|
| | """
|
| | Generic complexity-to-score mapping.
|
| |
|
| | Parameters
|
| | ----------
|
| | value : float
|
| | Instantiated complexity value of an algorithm.
|
| | min_value : float
|
| | Minimum complexity among all compared algorithms.
|
| |
|
| | Returns
|
| | -------
|
| | score : float
|
| | Normalized score in (0, 1].
|
| | """
|
| | if value <= 0 or min_value <= 0:
|
| | raise ValueError("Complexity values must be positive.")
|
| |
|
| | ratio = value / min_value
|
| | return 1.0 / (1.0 + self._log(ratio))
|
| |
|
| | def time_score(self, f_t: float, f_t_min: float) -> float:
|
| | """Time complexity score."""
|
| | return self.complexity_score(f_t, f_t_min)
|
| |
|
| | def space_score(self, f_s: float, f_s_min: float) -> float:
|
| | """Space complexity score."""
|
| | return self.complexity_score(f_s, f_s_min)
|
| |
|
| | def total_score(
|
| | self,
|
| | f_t: float,
|
| | f_t_min: float,
|
| | f_s: float,
|
| | f_s_min: float,
|
| | ) -> float:
|
| | """Combined complexity score."""
|
| | s_t = self.time_score(f_t, f_t_min)
|
| | s_s = self.space_score(f_s, f_s_min)
|
| | return self.alpha * s_t + (1.0 - self.alpha) * s_s
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| | def instantiate_complexity(
|
| | formula: str,
|
| | n: int,
|
| | d: int,
|
| | k: Optional[int] = None
|
| | ) -> float:
|
| | """
|
| | Instantiate asymptotic complexity formula.
|
| |
|
| | Supported variables: n, d, k
|
| |
|
| | Examples
|
| | --------
|
| | "n * d**2"
|
| | "n * d * k"
|
| | "d**2"
|
| | "d + k"
|
| | """
|
| | local_vars = {"n": n, "d": d}
|
| | if k is not None:
|
| | local_vars["k"] = k
|
| |
|
| | try:
|
| | return float(eval(formula, {"__builtins__": {}}, local_vars))
|
| | except Exception as e:
|
| | raise ValueError(f"Invalid complexity formula: {formula}") from e
|
| |
|
| |
|
| | n, d, k = 1000, 50, 10
|
| |
|
| | algorithms = {
|
| | "mRMR": {"time": "n * d**2", "space": "d**2"},
|
| | "JMIM": {"time": "n * d * k", "space": "d * k"},
|
| | "CFR": {"time": "n * d * k","space": "d + k"},
|
| | "DCSF": {"time": "n * d * k", "space": "d + k"},
|
| | "IWFS": {"time": "n * d * k", "space": "d + k"},
|
| | "MRI": {"time": "n * d * k", "space": "d + k"},
|
| | "MRMD": {"time": "n * d**2", "space": "d**2"},
|
| | "UCRFS": {"time": "n * d + n**2", "space": "n**2"},
|
| |
|
| |
|
| | }
|
| |
|
| |
|
| | time_vals = []
|
| | space_vals = {}
|
| |
|
| | for name, comp in algorithms.items():
|
| | f_t = instantiate_complexity(comp["time"], n, d, k)
|
| | f_s = instantiate_complexity(comp["space"], n, d, k)
|
| | time_vals.append(f_t)
|
| | space_vals[name] = (f_t, f_s)
|
| |
|
| | f_t_min = min(time_vals)
|
| | f_s_min = min(v[1] for v in space_vals.values())
|
| |
|
| | scorer = ComplexityScorer(alpha=0.7)
|
| |
|
| | for name, (f_t, f_s) in space_vals.items():
|
| | score = scorer.total_score(f_t, f_t_min, f_s, f_s_min)
|
| | print(f"{name}: complexity score = {score:.4f}")
|
| |
|
