File size: 3,987 Bytes
cc5b175 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | 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
# ------------------------------
# Core scoring functions
# ------------------------------
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
# --------------------------------------
# Utility: instantiate complexity formula
# --------------------------------------
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"},
}
# Instantiate complexities
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}")
|