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 sorted the levels by event rate, they find the contiguous partition maximizing total IV by Bellman recursion, not by greedy merging. All three are \(O(K L^2)\) for \(L\) pre-bins (the levels left after rare-level pooling, at most max_n_prebins) and \(K = \texttt{max\_bins}\), and all three work on categorical features (dp is a dynamic program only in its categorical form).

ivb (ob_categorical_ivb()) — sorts levels by event rate, then runs an interval DP over cumulative counts with a segment-IV cache, so each DP cell is \(O(1)\) (CumulativeStatsCache and IVCache, src/OBC_IVB_v5.cpp:68-192; recurrence in perform_dynamic_programming(), :463-493). No own parameters.

dp, categorical (ob_categorical_dp()) — the same DP over the levels sorted by event rate (compute_and_sort_event_rates(), src/OBC_DP_v5.cpp:477-513; recurrence in perform_dynamic_programming(), :539-585). There is no trend test in the recurrence: the pooled event rate of a run of consecutive sorted levels lies between those of its first and last members, so every contiguous partition has monotone event rates by construction (the code comment at :545-557 records that an earlier test only fired on an artifact). A bin without events or without non-events is still reported with WoE = IV = 0 (:75-82, :662), which can break the order of the reported WoE. When there are more than max_bins levels, monotonic_trend therefore only orders the list: "descending" reverses it, and "auto" runs a Welford-stable online correlation (Welford, 1962) on rates that are already sorted ascending, so it always resolves to ascending. With at most max_bins levels the DP is skipped (compute_bins_no_optimization(), :346-368) and the levels come out in ascending event-rate order, so "descending" is ignored ("none" leaves them in hash order). Own parameter: monotonic_trend ("auto", "ascending", "descending", "none").

sblp (ob_categorical_sblp()) — event-rate ordering, a rate-similarity pre-merge for rare levels (handle_rare_categories(), src/OBC_SBLP_v5.cpp:289-376), then interval DP over prefix sums (perform_binning(), :441-502). The IV of a segment is \(O(1)\), so it is \(O(K L^2)\) like ivb and dp; the comment above perform_binning() records that an earlier version re-summed every candidate segment and was \(O(K L^3)\). Own parameter: alpha (Laplace constant). Two cautions. The DP adds alpha once per level in a segment (iv_from_counts(), :506-521), while the reported WoE and IV add it once per bin (prepare_output(), :592-605), so the partition is optimal for a slightly different objective than the IV it reports. And, as a name note, no logistic regression is fitted anywhere; the R documentation’s analogy to Jenks natural breaks is structural only — both are exact dynamic programs over a sorted sequence, but sblp maximizes IV, not within-class variance.

There is a fourth, hidden DP: sketch, numerical contains a correct Bellman DP over “best sum of \(|\mathrm{IV}|\) splitting the first i sorted points into j bins” (DynamicProgramming::optimize(), src/OBN_Sketch_v5.cpp:237-299) — but it runs only when \(n \le 50\), a threshold hardcoded as dp_size_limit(50) (:595), tested in select_optimal_cutpoints() (:447) 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 splits top-down, accepting a cut when the information gain exceeds

\[ \frac{\log_2(N_S-1)}{N_S} + \frac{\Delta}{N_S}, \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] \]

where \(N_S\) is the number of observations in the interval \(S\) and \(k, k_1, k_2\) count the classes present in the interval and in its two parts. For a binary target \(k = 2\), so \(\Delta = \log_2 7 - 2\,\mathrm{Ent}(S) + k_1\mathrm{Ent}(S_1) + k_2\mathrm{Ent}(S_2)\); the child terms stay in (best_mdlp_cut(), src/OBN_FastMDLPM_v5.cpp:217-272, \(\Delta\) at :261-262). Own parameter: force_monotonicity.

Four caveats. (1) max_n_prebins and bin_cutoff are accepted and then discarded: (void) bin_cutoff; (void) max_n_prebins; at src/OBN_FastMDLPM_v5.cpp:541-542. (2) max_bins truncates by best-first expansion, not by recursion order: mdlp_cuts() (:285-304) keeps a priority queue of the accepted cut of every open interval, ordered by entropy reduction, pops the largest, splits that interval, and stops after max_bins - 1 cuts. The result is the best-first prefix of the Fayyad–Irani tree. That is not a global top-\((K-1)\) selection, because a child interval can offer a larger gain than its parent. (3) When the criterion accepts fewer than min_bins - 1 cuts, force_min_bins() (:361) discards them and places min_bins - 1 cuts spread approximately evenly over the distinct values. (4) The default force_monotonicity = TRUE then merges the adjacent pair with the closest WoE, until WoE is strictly monotone or min_bins bins remain (enforce_monotonicity(), :472), which can drop cuts the criterion accepted; with force_monotonicity = FALSE this step is skipped.

udt, numerical (ob_numerical_udt()) — scores every candidate midpoint by information gain in a single prefix-sum sweep (get_entropy_based_cutpoints(), src/OBN_UDT_v5.cpp:425-522), keeps the top max_n_prebins by gain, then merges bottom-up. Own parameters: laplace_smoothing, monotonicity_direction. A split phase (split_optimal_bin(), :794-876) runs only when fewer than min_bins bins remain, and it rescans the full feature vector once per bin it examines. 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, one at a time, the adjacent pair whose merge lowers the description-length cost

\[ \mathrm{MDL}(k) = \log_2(k-1) + \sum_i m_i\,\mathrm{Ent}(S_i) \]

where \(m_i\) is the number of observations in bin \(i\). Both terms carry a plus sign: the model cost, and the bits needed to encode the classes given the bins (the comment at src/OBN_MDLP_v5.cpp:107-112; the merge delta in apply_mdl_merging(), :755-814). A merge never lowers the data term (entropy is concave) and always lowers the model term, so the loop stops at the first local optimum, where no merge lowers the cost. It also stops once a merge brings the count to max_bins or below (:798-801), when min_bins is reached, or when max_iterations runs out (with a warning); a stop at the local optimum or on the iteration cap is what can leave more than max_bins bins. Three more passes then run, none of them MDL-optimal: enforce_max_bins() (:832-867) keeps merging the cheapest pair — every remaining delta is positive by now — until max_bins is met; bin_cutoff merges rare bins (merge_rare_bins(), :299); and, unless the WoE is already monotone, enforce_monotonicity() (:215-291) merges WoE-violating pairs, choosing the side by an IV-loss comparison rather than by MDL cost. The bins that come back can therefore still contain adjacent pairs whose merge would lower the MDL cost. Own parameter: laplace_smoothing.

Name note. This is an MDL-flavored 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:137 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 defines the Chi2 extension of Liu and Setiono (1995): the same merge swept over a decreasing schedule of significance levels (0.5 down to 0.001), with an inconsistency-rate check. Because max_bins is enforced first, the schedule ends after its first level: numerical cm returns the ChiMerge bins (without the rare-bin pass), and categorical cm returns one ChiMerge pass at chi_merge_threshold = 0.5, whatever threshold was passed. Unlike the ChiMerge path, the Chi2 path skips the bin_cutoff rare-level pass and the max_n_prebins limit (perform_chi2_binning(), src/OBC_CM_v5.cpp:450-480; compare perform_chimerge_binning(), :430-445), so the two can differ.

Three implementation notes. The statistic includes a Yates continuity correction with the deviation clamped at zero, \(\sum \max(|O-E| - 0.5,\ 0)^2/E\), as in chisq.test(correct = TRUE) (calculate_chi_square(), src/OBN_CM_v5.cpp:138-172). Kerber (1992, p. 124) prints the plain Pearson sum \(\sum (O-E)^2/E\) without a continuity correction, so the Yates form is this package’s choice, and the unclamped \((|O-E|-0.5)^2/E\) is not what the code computes. The critical value is qchisq(1 - alpha, 1) (chi_square_critical_value(), :965-967; 3.841 for alpha = 0.05), not a lookup table.

And, in the numerical engine, chi_merge_threshold does not change the result. The initial bins are merged, smallest \(\chi^2\) first, down to max_bins before the significance test could be reached (enforce_bin_limits(), :597-615, is called right after pre-binning at :1099-1102 and again at the end), so chi_merge() (:622-687) has no merge left to decide; the Chi2 schedule (chi2_algorithm(), :694-767) behaves the same way. max_bins sets the bin count, and bin_cutoff and monotonicity can only merge further. The categorical engine differs: it merges down to max_bins and then keeps merging while the smallest \(\chi^2\) is below the critical value (merge_bins_chimerge(), src/OBC_CM_v5.cpp:582-630), so there the significance level does decide the bin count.

fetb (ob_numerical_fetb(), ob_categorical_fetb()) — merges the adjacent pair whose 2×2 table is least distinguishable: the pair with the highest two-sided Fisher p-value, computed in C++ with the same tolerance for “as extreme” tables as fisher.test() (fisher_two_sided_log_p(), src/OBN_FETB_v5.cpp:91-154; categorical fisherLogPValue(), src/OBC_FETB_v5.cpp:172). No own parameters.

What it computes. The p-value ranks the merges; it does not stop them. There is no α: merging continues until max_bins is met (fisher_merge_loop(), src/OBN_FETB_v5.cpp:325-342). Releases before 1.14.0 ranked merges by the hypergeometric point probability of the observed table, which is not a p-value. On the categorical side, max_n_prebins is accepted and never read (src/OBC_FETB_v5.cpp:423).

Isotonic regression

ir (ob_numerical_ir()) — an engine whose name survives inspection. Weighted Pool Adjacent Violators on bin event rates, correctly implemented (applyIsotonicRegression(), src/OBN_IR_v5.cpp:663-721), 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.

Three notes. The pass is a single stack scan in which every bin is pushed once and each pooling removes one block, so there are at most \(k-1\) poolings and PAVA is \(O(k)\) in the number of pre-bins, as the code comment at :641-662 says. The pre-bins themselves are capped: createRegularBins() uses min(max_n_prebins, distinct values, max_bins) bins at evenly spaced ranks of the distinct values (quantiles when all values are distinct; :313-327), raised to min_bins, so with the default max_bins = 5 the isotonic fit sees at most five pre-bins and max_n_prebins changes nothing above max_bins. And R/obn_ir.R:63 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 onto a grid followed by a direct convolution (not an FFT), in the shared helper gaussian_kde_grid() (src/common/optimal_binning_common.h:125-195; ldb reads the grid back at the observations through gaussian_kde_sorted(), :222-255). It is a binned estimator in the family of Silverman (1982) and Wand (1994), with \(O(G^2)\) cost for \(G\) grid points. The grid has 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), floored at range / 1000 (src/OBN_LDB_v5.cpp:379-410). That is Silverman’s rule of thumb (1986, p. 48, eq. 3.31) with at least two differences: sd is the population standard deviation (divisor \(n\), computed as \(E[x^2]-\bar x^2\), which loses precision when the feature has a large offset), and the floor applies whenever the rule gives a smaller value. It therefore differs from bw.nrd0() in both (and the IQR is taken from order statistics without interpolation). 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 (1 to 10) and never read — setting it changes nothing; the R documentation now says so. Its bandwidth also drops the robustness term and the floor, using 0.9 * sd * n^(-1/5) with the population standard deviation (src/OBN_LPDB_v5.cpp:820-836), which makes it more outlier-sensitive than ldb.

Distribution-based initialization

ewb (ob_numerical_ewb()) — equal-width intervals, then supervised merging. Honestly labeled 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 (createRegularBins(), src/OBN_KMB_v5.cpp:273-323). 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”. The initial bin count is also capped at max_bins, so raising max_n_prebins above max_bins does nothing.

ubsd (ob_numerical_ubsd()) — edges at \(\mu, \mu \pm \sigma, \mu \pm 2\sigma\) unioned with equal-width points (src/OBN_UBSD_v5.cpp:357-374), then supervised refinement. Own parameter: laplace_smoothing. Note: it has no argument to disable monotonicity enforcement; it always calls enforce_monotonicity() (:122), and ten other numerical engines also always enforce monotonicity (cm, fetb, ir, jedi, jedi_mwoe, mblp, mdlp, mob, mrblp, oslp). The roxygen already corrects the “unsupervised” in its name: only initialization 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(e_i/n_i)\) — a per-bin log-odds with no normalization by the totals — so it differs from standard WoE by the constant \(\ln(E/N)\). IV is unaffected, because the offset cancels in the sum, and the code computes IV separately from the smoothed class distributions for exactly that reason (src/OBN_DMIV_v5.cpp:790-822). 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.

Merge rule (numerical). The merge phase does not compare pairs: it finds the single bin with the smallest absolute divergence contribution and absorbs it into the previous bin (into the next one when it is the first), until max_bins is met (fit(), src/OBN_DMIV_v5.cpp:720-761; the comment there calls this “Branch and Bound”, but nothing is branched or bounded).

Attribution note. The package presents the smoothed form \(\ln((e_i+0.5)/(n_i+0.5))\) as Zeng’s (R/obc_dmiv.R:44). Zeng’s published WOE1 is unsmoothed; the pseudo-count is this package’s own numerical-stability addition. In the numerical engine two divergence methods also 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 (src/OBN_DMIV_v5.cpp:426-449); the categorical engine uses them as ordinary pairwise distances between two bins.

Streaming

sketch (ob_numerical_sketch(), ob_categorical_sketch()) — built on streaming summaries, though both wrappers receive the full in-memory vectors. The categorical variant uses fixed-size Count-Min sketches (Cormode and Muthukrishnan, 2005) to decide which categories are heavy hitters. It does not make memory independent of the number of levels: the class counts of every distinct level are kept exactly (cat_pos, cat_neg and cat_index, src/OBC_Sketch_v5.cpp:231-233) and the bin statistics are read from them (exact_counts(), :289-299), so only the heavy-hitter decision is approximate. The numerical variant uses a multi-level compactor for approximate quantiles; the quantiles only propose candidate cutpoints, and every bin statistic is then computed exactly from the feature and target vectors, which the engine keeps (src/OBN_Sketch_v5.cpp:307-308). Own parameters: sketch_k and monotonic (numerical); sketch_width, sketch_depth (categorical).

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: the lower one on even levels, the upper one on odd levels (KLLSketch, src/OBN_Sketch_v5.cpp:43-161, rule at :99). Karnin, Lang and Liberty (2016) obtain their optimal bound from geometrically decreasing capacities and a randomized coin flip; neither is present here. The code comment at :54-59 derives a worst-case rank error of about \(2nH/k\) with \(H = \log_2(n/k)\) levels, that is \(O(\log(n/k)/k)\), and R/obn_sketch.R states the same bound next to the \(\varepsilon \approx O(1/k)\) of the original randomized algorithm, which is not established for this variant. And max_n_prebins is never read ((void)max_n_prebins, :700) — 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 numerical 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: pre-binning at evenly spaced ranks of the distinct values; merge bins below bin_cutoff into the smaller neighbor; 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 (fit(), src/OBN_JEDI_v5.cpp:136-166; the merge helpers are at :333-449). Numerical jedi_mwoe is the same procedure with one-vs-rest WoE per class, requiring monotonicity in every class simultaneously (the categorical version does not, see below). 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 optimization is entirely WoE/IV-driven. The merge criterion is the smallest summed current IV, which is only a proxy for the smallest IV loss; the roxygen now says so.

bb is named “Branch and Bound” but neither branches nor bounds: it repeatedly merges the single lowest-IV bin into a neighbor and never reconsiders (the loop headed “Branch and Bound optimization”, src/OBN_BB_v5.cpp:511-546). 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 program, and its header says so. mblp and oslp contain no linear program. 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:142 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. A move swaps two levels, reassigns one level to a random bin, or moves the level with the largest event-rate gap to its best bin (generate_neighbor(), src/OBC_SAB_v5.cpp:285-368), so levels are not tied to a single ordering — as in several other categorical engines (dmiv, mba, swb), which also merge non-adjacent bins. Violations enter the objective as penalties (calculate_iv(), :172-237): −1000 for each bin below bin_cutoff, −1000 for each bin short of min_bins, and −500 for a non-monotone solution; a final step still re-sorts the bins by event rate if the best solution is not monotone (ensure_monotonicity(), :567-632). Own parameters: initial_temperature, cooling_rate, adaptive_cooling. Its random draws come 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.