culebra.trainer.aco.heuristic module¶
Implementation of some heuristics for ACO algorithms.
Functions¶
- fs_accuracy_heuristic(training_fitness_func: FSClassificationScorer) tuple[ndarray[float], ...]¶
Compute a heuristic vector from the predictive performance of individual features.
The heuristic value of a feature is defined as the classification accuracy obtained when the feature is evaluated as a single-feature subset. The same classifier and evaluation settings used by the training fitness function are reused to compute the heuristic values.
- Parameters:
training_fitness_func (FSClassificationScorer) – Fitness function used during training.
- Returns:
A sequence of heuristic vectors for each feature.
- Return type:
- fs_information_theory_heuristic(training_fitness_func: FSClassificationScorer) tuple[ndarray[float], ...]¶
Compute a heuristic matrix based on information theory.
This heuristic is inspired by the information-theoretic heuristic proposed in [Wang2023]. The original work was developed for a Binary Ant Colony Optimization (BACO) algorithm, where each feature can be either selected or not selected and the heuristic is defined over transitions between such states.
This implementation adapts the original idea to a conventional ACO feature-selection algorithm where ants construct a subset by moving between features. Since the concept of feature selection states does not exist in this setting, a single heuristic matrix is used.
The heuristic between features \(i\) and \(j\) is defined as:
\[\eta_{ij} = SU(X_j, C) \left( 1 - |\rho(X_i, X_j)| \right)\]where:
\(SU(X_j, C)\) is the symmetric uncertainty between feature \(j\) and the class labels, measuring the relevance of the feature to the classification task.
\(\rho(X_i, X_j)\) is the Pearson correlation coefficient between features \(i\) and \(j\), measuring their redundancy.
Therefore, transitions towards features that are strongly related to the class labels and weakly correlated with the currently selected feature receive larger heuristic values.
Compared with the original BACO formulation, this adaptation:
Removes the notion of “selected” and “not selected” feature states.
Uses a single heuristic matrix instead of state-dependent heuristics.
Preserves the original relevance-redundancy trade-off proposed in [Wang2023].
Estimates feature relevance using symmetric uncertainty, as in the original work.
Estimates pairwise redundancy using Pearson correlation instead of symmetric uncertainty.
The redundancy term was modified to improve scalability on high-dimensional datasets. Computing symmetric uncertainty for every pair of features requires evaluating an information-theoretic measure for \(O(m^2)\) feature pairs, which becomes prohibitively expensive for datasets containing hundreds or thousands of features. Pearson correlation provides a substantially cheaper approximation of feature redundancy while preserving the original objective of discouraging the selection of highly redundant features.
- Parameters:
training_fitness_func (FSClassificationScorer) – Fitness function used during training.
- Returns:
A sequence of heuristic matrices.
- Return type:
[Wang2023] (1,2)Z. Wang, S. Gao, M. C. Zhou, S. Sato, J. Cheng, J. Wang. Information-theory-based nondominated sorting ant colony optimization for multiobjective feature selection in classification, IEEE Transactions on Cybernetics 53(8):5276-5289, 2023. DOI: https://doi.org/10.1109/TCYB.2022.3185554
- fs_pearson_heuristic(training_fitness_func: FSClassificationScorer) tuple[ndarray[float], ...]¶
Compute a heuristic matrix based on feature correlations.
It is computed as proposed in [Ghosh2020]. The heuristic between two features \(i\) and \(j\) is computed as:
\[\eta_{ij} = \frac{1}{1 + |\rho(i, j)|}\]where \(\rho(i, j)\) is the Pearson correlation coefficient between features \(i\) and \(j\).
Features with low correlation receive larger heuristic values, encouraging the construction of subsets with low redundancy.
- Parameters:
training_fitness_func (FSClassificationScorer) – Fitness function used during training.
- Returns:
A sequence of heuristic matrices.
- Return type:
[Ghosh2020]M. Ghosh, R. Guha, R. Sarkar, A. Abraham. A wrapper-filter feature selection technique based on ant colony optimization, Neural Computing and Applications, 32(12):7839-7857, 2020. https://doi.org/10.1007/s00521-019-04171-3.
- fs_rough_set_heuristic(training_fitness_func: FSClassificationScorer) tuple[ndarray[float], ...]¶
Compute a heuristic vector from the training dataset.
It is computed as proposed in [Ke2010]. For each feature \(c\), the heuristic is defined as:
\[\eta(c) = \exp\left(\frac{|POS_c(D)|}{|U|}\right)\]where \(POS_c(D)\) is the positive region induced by feature \(c\), \(D\) is the decision attribute, and \(U\) is the universe of samples. The term \(|POS_c(D)| / |U|\) corresponds to the rough-set dependency degree of the feature.
A sample belongs to the positive region if its equivalence class, induced by the feature value, contains samples from a single decision class only.
- Parameters:
training_fitness_func (FSClassificationScorer) – Fitness function used during training.
- Returns:
A sequence of heuristic vectors for each feature.
- Return type:
[Ke2010]L. Ke, Z. Feng, Z. Xu, K. Shang, Y. Wang. A multiobjective ACO algorithm for rough feature selection, in: 2010 2nd Pacific-Asia Conference on Circuits, Communications and System, PACCS 2010, Vol. 1, Beijing, China, 2010, pp. 207–210. https://doi.org/10.1109/paccs.2010.5627071.
- tsp_default_heuristic(training_fitness_func: TSPFitnessFunction) tuple[ndarray[float], ...]¶
Compute the default heuristic matrices for a TSP problem
Arcs from a node to itself have a heuristic value of 0. For the remaining arcs, the reciprocal of their nodes distance is used as heuristic.
- Parameters:
training_fitness_func (TSPFitnessFunction) – Fitness function used during training.
- Returns:
A sequence of heuristic matrices. One for each objective.
- Return type:
