Skip to content

Association mining engines — the recorded decision

AssociationConfig.engine selects the mlxtend frequent-itemset miner. The default is hmine. fpgrowth is an explicit expert escape hatch; nothing selects it automatically.

In short

  • Leave engine at "hmine": it won every benchmarked cell by 23× to 806×, with identical itemset counts.
  • The gap grows with basket count, so do not read 806× as a bound.
  • The two engines can disagree on an itemset that sits exactly on the support boundary, because of floating-point rounding.
  • Rerun scripts/benchmark_association_engines.py before changing the default.

This page is the record the code points at. Change the default here, with a rerun behind it — not ad hoc in a docstring.

Reproduce with:

python scripts/benchmark_association_engines.py

which writes scripts/benchmark_association_engines.csv and asserts, per cell, that the two engines return the same itemset count before timing them.

Result

H-Mine wins every benchmarked cell, by 23× to 806×. Itemset counts are identical in all 8 pairs, so the win costs nothing in output.

dataset baskets × items min_support itemsets fpgrowth (s) hmine (s) speed-up fpgrowth RSS (MB)
retail_baskets_30k 30 000 × 66 0.0125 2 408 115.38 0.954 121× 22.9
retail_baskets_30k 30 000 × 66 0.00625 6 008 342.86 1.377 249× 19.0
telco_holdings_12k 12 000 × 7 0.000417 98 2.13 0.043 50× 0.0
telco_holdings_12k 12 000 × 7 0.000208 98 1.85 0.032 58× 0.0
synthetic_100k 100 000 × 20 0.000391 2 180 393.07 0.797 493× 0.0
synthetic_100k 100 000 × 20 0.000195 2 672 458.77 0.569 806× 0.0
dense_stress_5k 5 000 × 200 0.025 20 100 201.48 8.717 23× 72.3
dense_stress_5k 5 000 × 200 0.0125 20 626 304.96 8.737 35× 74.1

Why — and why the ratio is not a constant

The cause is not sparsity, and not the FP-growth algorithm. It is mlxtend's null-value bookkeeping in the fpgrowth code path, which makes its runtime Θ(n_baskets × n_itemsets).

Details: where the fpgrowth time goes

fpgrowth routes through mlxtend.frequent_patterns.fpcommon.generate_itemsets, which hmine does not call. That function carries the library's null-value bookkeeping, and it runs even when null_values=False — the only path this pipeline ever takes. Specifically it:

  • re-materialises df.values[:, itemset] inside the per-itemset loop, so the sparse frame is densified once per itemset, O(n_baskets × n_items) each time;
  • runs a Python-level loop over every basket for every itemset of length ≥ 2;
  • and setup_fptree additionally allocates two dense n × d float64 arrays (31.7 MB for the 30k × 66 retail set) that are entirely NaN and entirely discarded.

So fpgrowth's runtime here is Θ(n_baskets × n_itemsets) — independent of density. The CSV confirms it: dividing wall-clock by n_baskets × itemsets gives 1.57–2.96 µs across four structurally different datasets. That flat constant is the signature of an O(n · |F|) Python loop, not of FP-tree construction.

Consequence for the default: the gap is not a fixed property of the two algorithms — it grows with basket count. A 1M-basket dataset would widen it further. Do not read "23–806×" as a bound.

Parity caveat

The engines are interchangeable in practice but not bit-identical at a support boundary:

  • hmine computes minsup = ceil(min_support × n) and admits on count >= minsup — an integer threshold;
  • fpgrowth filters on the fraction support = count / n >= min_support.

count >= ceil(s·n) and count/n >= s agree in exact arithmetic but not in IEEE-754. The textbook instance: 0.07 * 100 == 7.000000000000001, so ceil gives 8 while 7/100 >= 0.07 is True.

This also means the auto-search's absolute floor — "at least _MIN_BASKETS_PER_ITEMSET = 5 baskets", implemented as the fraction 5 / n — can behave as 6 under hmine for values of n where fl(fl(5/n) × n) rounds above 5.

None of the eight benchmarked cells sits on such a boundary, so the recorded parity is consistent with this defect rather than evidence against it.

Coverage gaps

The benchmark does not yet cover:

  • the thorough tier's max_itemset_len = 5 (all cells use 4);
  • more than one dense dataset. dense_stress_5k is the only dense cell — and it is also the one where the auto-support search overshot its target by ~10× in a single halving (200 → 20 100 itemsets), which the benchmark records but does not flag;
  • a ceil support boundary, so parity there is untested.

Next: AssociationMiner · Association rules guide