resc-ga — choosing the resampling subset with a genetic algorithm

Imbalance resampling by sample concatenation, where the majority subset is chosen by optimising class overlap rather than by sampling.

On a synthetic credit-default-shaped problem (452 rows, 1:7 imbalance), all six GA variants beat both sampling baselines on the objective — and also on complexity measures the GA never sees.

method	selection	crossover	overlap ↓	N1 ↓	N3 ↓	CM minority ↓
GA1	tournament	gene pool	0.000000	0.0083	0.0000	0.078
GA5	roulette	1-point	0.000074	0.0150	0.0033	0.095
GA4	roulette	gene pool	0.000147	0.0133	0.0033	0.105
GA3	tournament	2-point	0.000147	0.0200	0.0100	0.125
GA6	roulette	2-point	0.000251	0.0183	0.0067	0.125
GA2	tournament	1-point	0.000443	0.0283	0.0083	0.122
weighted	–	–	0.002392	0.0267	0.0133	0.136
random	–	–	0.007128	0.0283	0.0133	0.156

Reproduce with make demo. Results on the real bankruptcy and loan datasets are in notebooks/.

Why the first column alone proves nothing. The GA minimises overlap, so winning there is close to tautological. The evidence is in the other three. N1 (MST boundary density), N3 (1-NN error) and CM (neighbourhood mismatch on the minority class) are computed independently of the objective, and all six variants beat both baselines on N3 and on minority CM. On N1 five of six do — GA2 ties random, which is the kind of detail that disappears if you only report the column you optimised.

---

The problem

Two things break a classifier on imbalanced data, and they pull in opposite directions:

• Class imbalance — too few minority samples to represent the class.
• Class overlap — a region where both classes are about equally likely, so no boundary separates them cleanly.

Conventional resampling trades one for the other. Undersampling the majority throws away information. Oversampling the minority (SMOTE and relatives) synthesises points into the overlap region and blurs the boundary further.

The method: Re-SC

Shi et al. (2022) avoid the trade by changing the space instead of the sample. Pair two samples with the same label and concatenate them into one row:

x = (x₁ … x_d)  and  x' = (x'₁ … x'_d),  y(x) = y(x')
        ↓
    [x₁ … x_d, x'₁ … x'_d, y]        — a point in 2d dimensions

Pairing the minority class with itself gives |P|² rows; pairing the majority against a chosen subset Set_N gives |N|·|Set_N|. So the ratio is controlled by |Set_N| — no majority row is discarded and no synthetic minority point is invented. Every original sample still participates.

The classes balance when

|Set_N| ≈ |P|² / |N|

The contribution: which rows go in Set_N

Re-SC says how big Set_N should be. It does not say which majority rows belong in it, and that choice decides how much the concatenated classes overlap.

This repository treats it as combinatorial optimisation. Minimise

f(Set_N) = ½·mean over P_C (share of k-NN that are majority)
         + ½·mean over N_C (share of k-NN that are minority)

over subsets of fixed size. The objective is non-differentiable, the search space is C(|search space|, |Set_N|), and candidates cannot be scored independently — overlap depends on how the chosen rows sit together. That combination is what motivates a population method rather than greedy ranking.

Both terms are needed. A one-sided measure is trivially driven to zero by a Set_N that pushes the majority cloud away from the minority one while leaving the minority side just as ambiguous.

Two design choices worth naming:

• The search space is pre-restricted to the purest half of the majority class (select_potential_indices) — points sitting inside the overlap region are ones the objective would reject anyway, so removing them up front halves the space for free.
• An individual is a set, not a sequence. Gene order carries no meaning, which is why the gene-pool operator — discarding position entirely — is competitive with positional n-point crossover, and why every operator has to re-establish distinctness and cardinality after splicing.

The six variants

v0 shipped GA1.py … GA6.py. They were byte-identical except for two import lines: a 2×3 factorial over selection and crossover.

	gene pool	1-point	2-point
tournament	GA1	GA2	GA3
roulette	GA4	GA5	GA6

Here that is one GeneticAlgorithm with two injected strategies. VARIANTS maps the old names onto it, so the original experiments stay addressable:

GAConfig.for_variant("GA3", individual_size=7)   # tournament + two_point

All variants are handed the same initial population, so a difference between them is a difference in operators rather than in starting luck.

---

Install

python -m venv .venv && source .venv/bin/activate
pip install -e ".[dev]"          # add "nn" for the PyTorch evaluation, "plots" for figures

Run

make demo                        # generate data, run the 2x3 grid + baselines
pytest                           # 64 tests

python -m resc_ga data.csv --no-classifier -o results.csv
python -m resc_ga data.csv --variants GA1 GA4 --pop-size 20 --generations 50

from resc_ga import GAConfig, GeneticAlgorithm, split_classes, balanced_set_n_size

majority, minority = split_classes(df)
cfg = GAConfig.for_variant("GA1",
                           individual_size=balanced_set_n_size(len(majority), len(minority)))
result = GeneticAlgorithm(cfg).run(majority, minority, df_train=df)
result.set_n, result.best_fitness

Layout

src/resc_ga/
  ga.py          GeneticAlgorithm + the GA1..GA6 variant table
  selection.py   tournament | roulette
  crossover.py   gene_pool | one_point | two_point
  mutation.py    cardinality-preserving gene replacement
  fitness.py     the k-NN class-overlap objective
  population.py  search-space restriction and seeding
  concat.py      the Re-SC concatenation primitive
  complexity.py  F2 / N1 / N2 / N3 / CM / T1, with per-class variants
  baselines.py   random and purity-weighted Set_N selection
  classifier.py  the MLP used to score the resampled data
  experiment.py  the grid runner
notebooks/       original experiments on bankruptcy and loan data
tests/           64 tests

---

Bugs fixed since v0

Rebuilding this turned up five real bugs in my first version. Each one now has a regression test in tests/test_regressions.py. They are listed because the first one changed results, and because a repo that hides them is less useful than one that does not.

1. The objective was silently inverted. The fitness function identified the majority label with np.bincount(y).argmax() — after concatenation. But Re-SC exists to balance the classes, and |P_C| = |P|² is frequently the larger block once |Set_N| is rounded to an integer. Whenever it was, the two labels swapped and the score counted same-class neighbours instead of foreign ones, so the GA was maximising overlap. Labels now come from the blocks themselves. This is the one that changed results.

2. The random baseline could not be imported. Set_N_random_selection.py had an unindented docstring and raised IndentationError on import, so the comparison against random selection never actually ran.

3. Two-point crossover crashed for |Set_N| < 3. It drew two distinct cut points from range(1, len(p1)), which is empty or a singleton for short individuals — and short individuals are the normal case, since |Set_N| ≈ |P|²/|N| is small under severe imbalance. It now degenerates to a single cut.

4. The configured mutation rate was ignored. config['mutation_rate'] was documented and set, but the call site never passed it, so every run used the 0.05 default no matter what the config said.

5. F2 returned a meaningless per-class split. Both elements of the (majority, minority) tuple came from one identical expression and were always equal. F2 is a property of the class pair; it now returns a scalar, with F2_legacy() kept for the notebooks.

Decisions and trade-offs

Left in, not tuned away: roulette's weak selection pressure. Weights are 1 − fᵢ/Σf, so with a population of size P each weight sits within ~1/P of 1 and selection drifts towards uniform as the population grows. It is part of what the six-variant comparison measures, and it shows up in the table — roulette variants are not systematically worse here, which is itself informative about how much the operator choice matters on this problem. Use tournament when you want pressure that does not depend on fitness scale.

Repeated CV now actually repeats. A fixed random_state on StratifiedKFold inside the repeat loop meant all 10 repeats used identical folds, so the "repeats" varied only by model initialisation. The seed is offset per repeat. This changes the numbers, for the better.

Metrics are averaged over epochs. This mixes in under-trained early epochs and sits below peak performance. Kept because every method is scored identically, so the comparison holds — but the absolute values are not the model's best.

Complexity measures are subsampled. They need a dense n×n distance matrix and T1 adds an O(n²) scan, which is not viable on a 5,500-row concatenated frame. Scored on a stratified subsample (default 800 rows).

T1 is reported but proves nothing here. Absorption requires one hypersphere strictly inside another, which essentially never happens for distinct real-valued points: it returns 1.0 for both separable and overlapping data. Pinned by a test so it is not mistaken for a broken implementation, and deliberately not used as evidence.

Cost. Fitness is the bottleneck: every evaluation rebuilds the concatenated frame and fits a fresh ball tree over |N|·|Set_N| + |P|² rows, for every individual in every generation. Population size and generation count are the knobs that decide whether a run finishes.

Reproducibility

Every stochastic component takes an explicit numpy.random.Generator threaded from one seed. Two runs at the same seed produce identical results, which tests/test_ga.py::test_same_seed_gives_identical_results asserts. v0 seeded numpy globally at import time and left the GA itself unseeded.

---

Citation

The Re-SC method is from:

Shi, H., Zhang, Y., Chen, Y., Ji, S., & Dong, Y. (2022). Resampling algorithms based on sample concatenation for imbalance learning. Knowledge-Based Systems, 245, 108592. https://doi.org/10.1016/j.knosys.2022.108592

The paper contributes sample concatenation and the Re-SC / EnRe-SC algorithms. The genetic selection of Set_N, the overlap objective, the six-variant comparison and this implementation are mine.

My original thesis-submission code is preserved at tag v0-thesis.

Licence

MIT