Algorithm Reference: the 37 Binning Engines

obwoe() does not forward algorithm-specific parameters

obwoe() builds a fixed argument list — min_bins, max_bins, bin_cutoff, max_n_prebins, convergence_threshold, max_iterations, and bin_separator for categorical features — and passes nothing else. An engine’s own parameters are unreachable through it, and routing them via control.obwoe() fails silently:

via_obwoe <- obwoe(gc_data, target = "target", feature = "duration",
                   algorithm = "dmiv",
                   control = control.obwoe(divergence_method = "kl"))
direct_dmiv <- ob_numerical_dmiv(target = gc_data$target,
                                 feature = gc_data$duration,
                                 divergence_method = "kl")

c(`through obwoe()` = via_obwoe$results$duration$divergence_method,
  `direct wrapper`  = direct_dmiv$divergence_method)
#> through obwoe()  direct wrapper 
#>            "l2"            "kl"

If you need an algorithm-specific parameter, call the engine directly.

Exact dynamic programming

Three engines genuinely solve an optimal-partition problem: having fixed an ordering of the levels, they find the contiguous partition maximising total IV by Bellman recursion, not by greedy merging.

ivb (ob_categorical_ivb()) — sorts levels by event rate, then runs an interval DP with cumulative-sum caching, so each DP cell is \(O(1)\) (src/OBC_IVB_v5.cpp:34-158, 369-442). \(O(L^2 k)\). No own parameters.

dp, categorical (ob_categorical_dp()) — the same DP, but with the monotonicity constraint built into the transition rather than repaired afterwards (src/OBC_DP_v5.cpp:666-717): transitions that would violate the requested trend are simply never considered. Own parameter: monotonic_trend ("auto", "ascending", "descending", "none"). The "auto" direction is detected by a Welford-stable online correlation (Welford, 1962).

sblp (ob_categorical_sblp()) — event-rate ordering, a rate-similarity pre-merge for rare levels, then interval DP. Its DP re-sums each candidate segment instead of using cumulative sums (src/OBC_SBLP_v5.cpp:485-505), making it \(O(L^3 k)\) where ivb and dp are \(O(L^2 k)\). Own parameter: alpha (Laplace constant). Name note: no logistic regression is fitted anywhere; the R documentation’s analogy to Jenks natural breaks has no counterpart in the code.

There is a fourth, hidden DP: sketch, numerical contains a correct Bellman DP over “best IV splitting the first i points into j bins” (src/OBN_Sketch_v5.cpp:277-470) — but it runs only when \(n \le 50\), a threshold hardcoded at src/OBN_Sketch_v5.cpp:979 and not exposed. For any real dataset, sketch takes its greedy branch.

Recursive entropy partitioning

fast_mdlp (ob_numerical_fast_mdlp()) — the only engine implementing the Fayyad–Irani (1993) criterion as published. It recursively splits top-down, accepting a cut when the information gain exceeds

\[ \frac{\log_2(N-1)}{N} + \frac{\Delta}{N}, \qquad \Delta = \log_2(3^k - 2) - \bigl[k\,\mathrm{Ent}(S) - k_1\mathrm{Ent}(S_1) - k_2\mathrm{Ent}(S_2)\bigr] \]

which for binary targets reduces to the log2(7) - 2*E_parent at src/OBN_FastMDLPM_v5.cpp:176. Own parameter: force_monotonicity.

Two caveats. max_n_prebins and bin_cutoff appear exactly once each in the file — in the signature — and have no effect. And max_bins is enforced by discarding the last-discovered splits (src/OBN_FastMDLPM_v5.cpp:548-575), by recursion order rather than by information content; the source comment admits this is “for simplicity”.

udt, numerical (ob_numerical_udt()) — scores every candidate midpoint by information gain in a single prefix-sum sweep, keeps the top max_n_prebins by gain, then merges bottom-up. Own parameters: laplace_smoothing, monotonicity_direction. Its split phase rescans the full feature vector per bin (src/OBN_UDT_v5.cpp:778-880), which the R documentation correctly warns is expensive. Name note: the package’s own roxygen states it plainly — the method is supervised and builds no tree.

Bottom-up MDL cost

mdlp (ob_numerical_mdlp()) — merges the adjacent pair that most reduces a global cost \(\log_2(k-1) + N H(S) - \sum_i n_i H(S_i)\) (src/OBN_MDLP_v5.cpp:915-966), then enforces max_bins as a hard post-condition. Own parameter: laplace_smoothing.

Name note. This is an MDL-flavoured cost, but it is not the Fayyad–Irani criterion: the term \(\log_2(3^k-2)\) appears nowhere in the file, and the algorithm is agglomerative bottom-up where the cited paper is recursive top-down. R/obn_mdlp.R:134 nonetheless claims a “Theoretical Guarantee (Fayyad & Irani, 1993)”. The guarantee does not transfer. Confusingly, the engine that does implement the paper is the one named fast_mdlp, whose name suggests it is merely a faster variant of this one.

Statistical merging

cm (ob_numerical_cm(), ob_categorical_cm()) — ChiMerge (Kerber, 1992): repeatedly merge the adjacent pair with the smallest \(\chi^2\), stop when the smallest exceeds a critical value. Own parameters: chi_merge_threshold, use_chi2_algorithm, and init_method on the numerical side. Setting use_chi2_algorithm = TRUE gives the genuine Chi2 extension of Liu and Setiono (1995): the same merge swept over a decreasing schedule of significance levels, stopping on an inconsistency-rate criterion.

Two implementation notes. The statistic includes a Yates continuity correction, \(\sum(|O-E| - 0.5)^2/E\) (src/OBN_CM_v5.cpp:266-310), which is not the form usually attributed to Kerber; the primary source could not be consulted directly to confirm whether Kerber’s own text includes it. And critical values come from a hard-coded 14-entry table for one degree of freedom, with the nearest tabulated level substituted for an untabulated chi_merge_threshold.

fetb (ob_numerical_fetb(), ob_categorical_fetb()) — merges the adjacent pair whose 2×2 table is least distinguishable. No own parameters.

What it computes. fisherProb() returns the hypergeometric point probability of the single observed table (src/OBN_FETB_v5.cpp:58-65), which is one term of a Fisher exact-test p-value, not the summed tail. The package is internally inconsistent about this: the function’s own comment says “point probability” and the roxygen says “the exact hypergeometric probability of independence” — both accurate — while the file header at src/OBN_FETB_v5.cpp:23 calls it a “two‑tail Fisher p‑value”, which it is not. As a similarity criterion the statistic is defensible; as a significance test it is not, and there is no α-based stopping rule. On the categorical side, max_n_prebins is accepted and never read.

Isotonic regression

ir (ob_numerical_ir()) — the one engine whose name fully survives inspection. Weighted Pool Adjacent Violators on bin event rates, correctly implemented (src/OBN_IR_v5.cpp:776-856), and — importantly — the bins that PAVA pools are then genuinely merged rather than having fitted values written over them, so the reported counts and the isotonic fit stay consistent. Own parameter: auto_monotonicity. min_bins is a target, not a guarantee: pooling can legitimately end below it, and the roxygen says so.

Two notes. The source comment at src/OBN_IR_v5.cpp:761 claims \(O(n)\), but the block merge shifts the whole vector (:822-827), making it \(O(k^2)\). And R/obn_ir.R:55 credits PAVA to Best and Chakravarti (1990) — a real paper about active-set methods for isotonic regression, but not the algorithm’s origin, which is Ayer, Brunk, Ewing, Reid and Silverman (1955).

Density-based

Both engines locate cut points from a Gaussian kernel density estimate, computed by linear binning on a grid and convolution — the technique of Silverman (1982), with linear binning as formalised by Wand (1994) — in the shared helper gaussian_kde_grid(). The grid is 512 points and is not user-adjustable, so structure narrower than 1/511 of the feature’s range is not resolved.

ldb (ob_numerical_ldb()) — cuts at local minima of the density. Bandwidth 0.9 * min(sd, IQR/1.34) * n^(-1/5) (src/OBN_LDB_v5.cpp:383), an exact match to Silverman’s rule of thumb (1986, p. 48, eq. 3.31). Own parameter: enforce_monotonic.

lpdb (ob_numerical_lpdb()) — cuts at extrema and inflection points, found by finite differences of the gridded density. Own parameters: polynomial_degree, enforce_monotonic.

Name note. No polynomial is fitted. polynomial_degree is validated and never read — setting it changes nothing. The R documentation already says the density is “currently approximated via KDE”. Its bandwidth also drops the robustness term, using 0.9 * sd * n^(-1/5) (src/OBN_LPDB_v5.cpp:784), which makes it more outlier-sensitive than ldb.

Distribution-based initialisation

ewb (ob_numerical_ewb()) — equal-width intervals, then supervised merging. Honestly labelled as hybrid. Own parameter: is_monotonic. Its WoE and IV use the same smoothed proportions, unlike ldb/lpdb/kmb/dp.

kmb (ob_numerical_kmb()) — centroids placed at min + (i+0.5)·range/n_bins and boundaries at their midpoints (src/OBN_KMB_v5.cpp:279-332). Name note: there is no assignment/update iteration, so this is not Lloyd’s algorithm (1982) — evenly spaced centroids with midpoint boundaries is equal-width binning under another name. The roxygen is careful and says “k-means inspired”. Two further quirks: bin assignment is a linear scan per observation, \(O(nk)\), the only engine not using binary search; and the initial bin count is capped at max_bins, so raising max_n_prebins above max_bins does nothing.

ubsd (ob_numerical_ubsd()) — edges at \(\mu \pm \sigma, \mu \pm 2\sigma\) unioned with equal-width points, then supervised refinement. Own parameter: laplace_smoothing. Note: alone among the numerical engines it offers no way to disable monotonicity enforcement — there is no such argument in the constructor or the exported function. The roxygen already corrects the “unsupervised” in its name: only initialisation is unsupervised.

Divergence-driven

dmiv (ob_numerical_dmiv(), ob_categorical_dmiv()) — merges by one of nine divergences: Hellinger, KL, triangular, J-divergence, symmetric \(\chi^2\), Jensen–Shannon (Lin, 1991), L1, L2, L∞. Own parameters: divergence_method, bin_method, and is_monotonic on the numerical side.

bin_method defaults to "woe1", which is not standard WoE. Zeng’s WOE1 is \(\ln(g_i/b_i)\) — a per-bin log-odds with no normalisation by the totals — so it differs from standard WoE by the constant \(\ln(g/b)\). IV is unaffected, because the offset cancels in the sum, and the code computes IV separately for exactly that reason (src/OBN_DMIV_v5.cpp:724-761). But the WoE values are not comparable with the other 27 engines, and a scorecard fitted on them carries a different intercept. Pass bin_method = "woe" to the wrapper for the standard definition.

Attribution note. The package presents the smoothed form \(\ln((g_i+0.5)/(b_i+0.5))\) as Zeng’s (R/obc_dmiv.R:38). Zeng’s published WOE1 is unsmoothed; the pseudo-count is this package’s own numerical-stability addition. Two further citation issues: R/obn_dmiv.R:86 gives the venue as Journal of the Operational Research Society 64(5), 712–731, but the verified publication is Journal of Mathematics 2013, article 848271; and two divergence methods behave globally rather than per bin — l2 rescales each bin’s share of the global norm, and l∞ assigns the maximum to whichever bins attain it and zero to all others.

Streaming

sketch (ob_numerical_sketch(), ob_categorical_sketch()) — the only engine whose memory does not grow with the data. The categorical variant uses Count-Min sketches (Cormode and Muthukrishnan, 2005) for category frequencies, making its cost independent of the number of levels; the numerical variant uses a multi-level compactor for approximate quantiles. Own parameters: sketch_k and monotonic (numerical); sketch_width, sketch_depth (categorical).

Two qualifications on the numerical side. The compactor uses the same capacity at every level and a deterministic parity rule to choose which item of a compacted pair survives (src/OBN_Sketch_v5.cpp:81, 107-108). Karnin, Lang and Liberty (2016) obtain their optimal bound from geometrically decreasing capacities and a randomised coin flip; neither is present here. The implementation is in the KLL family, but the \(\varepsilon \approx O(1/k)\) guarantee quoted in the documentation is not established for this variant. And max_n_prebins is never read — the candidate quantile grid is hardcoded.

Greedy merging under an IV or WoE criterion

The largest group. All follow the same shape — pre-bin, merge rare bins, merge until max_bins, repair monotonicity — and differ in three choices: how the levels are ordered, how the merge direction is decided, and which IV expression selects the merge.

Own parameters: laplace_smoothing for mob, mrblp, oslp; force_monotonic_direction for mblp; is_monotonic for bb; none for the rest.

jedi and jedi_mwoe are the package author’s own construction, combining adjacent published techniques rather than implementing a named method — there is no paper to cite and none is claimed. The numerical heuristic is: quantile pre-binning; merge bins below bin_cutoff into the smaller neighbour; infer trend direction by majority vote over pairwise WoE increments; merge violating adjacent pairs until monotone; then merge until max_bins, each time taking the adjacent pair with the smallest summed current IV; iterate until total IV stops changing by more than convergence_threshold (src/OBN_JEDI_v5.cpp:113-129, 235-425). jedi_mwoe is the same procedure with one-vs-rest WoE per class, requiring monotonicity in every class simultaneously. Name note: despite “Joint Entropy-Driven” in the title, the numerical implementation computes no entropy — the file contains no entropy, log2 or information-gain term anywhere. The optimisation is entirely WoE/IV-driven. The roxygen also describes the merge as choosing the smallest decrease in IV, while the code chooses the smallest summed current IV; those are different rules.

bb is named “Branch and Bound” but neither branches nor bounds: it repeatedly merges the single lowest-IV bin and never reconsiders (src/OBN_BB_v5.cpp:449-517). dp, numerical is named “Dynamic Programming” and builds no DP table — its own source comment says so and cites Navas-Palencia (2020) as what a real formulation would look like. milp solves no mixed-integer programme, and its header says so. mblp and oslp contain no linear programme. mrblp does no likelihood-ratio pre-binning: the word “likelihood” appears only in comments. swb slides no window — for unordered levels there is no axis to slide along; it is greedy divergence merging with an adjacency preference.

R/obn_oslp.R:135 recommends against oslp outright: “Use OSLP: Never. Use MBLP or MOB instead.”

Metaheuristic

sab (ob_categorical_sab()) — simulated annealing (Kirkpatrick, Gelatt and Vecchi, 1983) over category-to-bin assignments. Alone among the categorical engines it can move a level between non-adjacent bins, so it is not restricted to a single ordering. Rare-bin and monotonicity violations enter the objective as penalties rather than being repaired afterwards (src/OBC_SAB_v5.cpp:161-215). Own parameters: initial_temperature, cooling_rate, adaptive_cooling. Its generator is seeded from R’s RNG stream, so set.seed() makes it reproducible. max_n_prebins is validated and never used, so it anneals over the full level set.