Skip to main content

solow_preprocessing/
discretize.rs

1//! [`KBinsDiscretizer`] — bin each column of a feature matrix into a
2//! small integer alphabet.
3//!
4//! Three binning strategies:
5//!
6//! * [`BinStrategy::Uniform`] — equal-width bins between the observed
7//!   `min` and `max`.
8//! * [`BinStrategy::Quantile`] — equal-frequency bins from R type-7
9//!   quantiles (matches `numpy.quantile` and
10//!   `preprocessing.KBinsDiscretizer(strategy='quantile')`).
11//! * [`BinStrategy::KMeans`] — 1-D KMeans with `k-means++` initialisation
12//!   and deterministic MMIX-LCG seeding, so the resulting bin edges are
13//!   bit-for-bit reproducible across runs and platforms.
14//!
15//! # Output
16//!
17//! `transform` returns a `n × d` matrix of `usize` bin indices in
18//! `[0, n_bins)` — the ordinal encoding the reference calls
19//! `encode='ordinal'`. The one-hot encoding is trivially obtained by
20//! piping the output through
21//! [`crate::encoders::OneHotEncoder`] on the resulting numeric-
22//! categorical matrix.
23
24use ndarray::{Array2, ArrayView2};
25use solow_core::{Error, Result};
26
27/// Binning strategy for [`KBinsDiscretizer`].
28#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
29#[derive(Copy, Clone, Debug, PartialEq, Eq)]
30pub enum BinStrategy {
31    /// Equal-width bins on `[min, max]`.
32    Uniform,
33    /// Equal-frequency bins (per-column quantiles).
34    Quantile,
35    /// 1-D KMeans with `k-means++` init.
36    KMeans,
37}
38
39/// Fitted per-column bin edges.
40#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
41#[derive(Clone, Debug, PartialEq)]
42pub struct KBinsDiscretizer {
43    /// Per-column bin edges. Column `j` has `edges[j]` of length
44    /// `n_bins + 1`, ascending.
45    pub edges: Vec<Vec<f64>>,
46    /// Number of bins per column (same value for every column in this
47    /// implementation, matching the reference default).
48    pub n_bins: usize,
49    /// The binning strategy used at fit time.
50    pub strategy: BinStrategy,
51}
52
53impl KBinsDiscretizer {
54    /// Fit with the given number of bins and strategy.
55    pub fn fit(
56        x: ArrayView2<'_, f64>,
57        n_bins: usize,
58        strategy: BinStrategy,
59        seed: u64,
60    ) -> Result<Self> {
61        if x.nrows() == 0 || x.ncols() == 0 {
62            return Err(Error::Value(
63                "KBinsDiscretizer::fit: x must have at least one row and one column".into(),
64            ));
65        }
66        if n_bins < 2 {
67            return Err(Error::Value(format!(
68                "KBinsDiscretizer::fit: n_bins must be ≥ 2 (got {n_bins})"
69            )));
70        }
71        let d = x.ncols();
72        let mut edges = Vec::with_capacity(d);
73        for j in 0..d {
74            let col: Vec<f64> = x.column(j).iter().copied().collect();
75            let e = match strategy {
76                BinStrategy::Uniform => uniform_edges(&col, n_bins)?,
77                BinStrategy::Quantile => quantile_edges(&col, n_bins)?,
78                BinStrategy::KMeans => kmeans_edges(&col, n_bins, seed.wrapping_add(j as u64))?,
79            };
80            edges.push(e);
81        }
82        Ok(Self {
83            edges,
84            n_bins,
85            strategy,
86        })
87    }
88
89    /// Assign each value to a bin index in `[0, n_bins)`.
90    pub fn transform(&self, x: ArrayView2<'_, f64>) -> Result<Array2<usize>> {
91        if x.ncols() != self.edges.len() {
92            return Err(Error::Shape(format!(
93                "KBinsDiscretizer::transform: expected {} columns, got {}",
94                self.edges.len(),
95                x.ncols()
96            )));
97        }
98        let mut out = Array2::<usize>::zeros((x.nrows(), x.ncols()));
99        for j in 0..x.ncols() {
100            let e = &self.edges[j];
101            for i in 0..x.nrows() {
102                let v = x[[i, j]];
103                // Half-open bins `[e[k], e[k+1])`, last bin closed at both ends.
104                let mut b = 0usize;
105                for k in 0..(e.len() - 1) {
106                    if v >= e[k] {
107                        b = k;
108                    }
109                }
110                if b >= self.n_bins {
111                    b = self.n_bins - 1;
112                }
113                out[[i, j]] = b;
114            }
115        }
116        Ok(out)
117    }
118
119    /// One-call fit + transform.
120    pub fn fit_transform(
121        x: ArrayView2<'_, f64>,
122        n_bins: usize,
123        strategy: BinStrategy,
124        seed: u64,
125    ) -> Result<(Self, Array2<usize>)> {
126        let d = Self::fit(x, n_bins, strategy, seed)?;
127        let t = d.transform(x)?;
128        Ok((d, t))
129    }
130}
131
132fn uniform_edges(col: &[f64], n_bins: usize) -> Result<Vec<f64>> {
133    let (mut mn, mut mx) = (f64::INFINITY, f64::NEG_INFINITY);
134    for &v in col {
135        if !v.is_finite() {
136            return Err(Error::Value("KBinsDiscretizer: non-finite value".into()));
137        }
138        if v < mn {
139            mn = v;
140        }
141        if v > mx {
142            mx = v;
143        }
144    }
145    if mn == mx {
146        // Degenerate column — assign every value to bin 0 by returning trivial edges.
147        return Ok(vec![mn, mn + 1.0]);
148    }
149    let w = (mx - mn) / n_bins as f64;
150    Ok((0..=n_bins).map(|k| mn + k as f64 * w).collect())
151}
152
153fn quantile_edges(col: &[f64], n_bins: usize) -> Result<Vec<f64>> {
154    let mut sorted: Vec<f64> = col.to_vec();
155    for &v in &sorted {
156        if !v.is_finite() {
157            return Err(Error::Value("KBinsDiscretizer: non-finite value".into()));
158        }
159    }
160    sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
161    let n = sorted.len();
162    let mut edges = Vec::with_capacity(n_bins + 1);
163    for k in 0..=n_bins {
164        let q = k as f64 / n_bins as f64;
165        let h = (n as f64 - 1.0) * q;
166        let lo = h.floor() as usize;
167        let hi = (lo + 1).min(n - 1);
168        let frac = h - lo as f64;
169        edges.push((1.0 - frac) * sorted[lo] + frac * sorted[hi]);
170    }
171    Ok(edges)
172}
173
174fn kmeans_edges(col: &[f64], n_bins: usize, seed: u64) -> Result<Vec<f64>> {
175    // Simple 1-D KMeans with k-means++ init.
176    for &v in col {
177        if !v.is_finite() {
178            return Err(Error::Value("KBinsDiscretizer: non-finite value".into()));
179        }
180    }
181    let n = col.len();
182    if n < n_bins {
183        return Err(Error::Value(format!(
184            "KBinsDiscretizer: KMeans strategy needs n ≥ n_bins (got n={n}, k={n_bins})"
185        )));
186    }
187    let mut centers = kmeans_pp_init_1d(col, n_bins, seed);
188    let max_iter = 100;
189    for _ in 0..max_iter {
190        // Assign
191        let mut sums = vec![0.0_f64; n_bins];
192        let mut counts = vec![0usize; n_bins];
193        for &v in col {
194            let mut best = 0usize;
195            let mut best_d = f64::INFINITY;
196            for (c, &cent) in centers.iter().enumerate() {
197                let dd = (v - cent).powi(2);
198                if dd < best_d {
199                    best_d = dd;
200                    best = c;
201                }
202            }
203            sums[best] += v;
204            counts[best] += 1;
205        }
206        let mut moved = 0.0_f64;
207        for c in 0..n_bins {
208            if counts[c] > 0 {
209                let new_c = sums[c] / counts[c] as f64;
210                moved += (new_c - centers[c]).abs();
211                centers[c] = new_c;
212            }
213        }
214        if moved < 1e-12 {
215            break;
216        }
217    }
218    centers.sort_by(|a, b| a.partial_cmp(b).unwrap());
219    // Edges: midpoints between adjacent sorted centers, plus min/max as
220    // the outer edges.
221    let mut sorted = col.to_vec();
222    sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
223    let mut edges = Vec::with_capacity(n_bins + 1);
224    edges.push(sorted[0]);
225    for w in centers.windows(2) {
226        edges.push(0.5 * (w[0] + w[1]));
227    }
228    edges.push(*sorted.last().unwrap());
229    Ok(edges)
230}
231
232fn kmeans_pp_init_1d(col: &[f64], k: usize, seed: u64) -> Vec<f64> {
233    let mut state = seed.wrapping_add(0xC0DE_C0DE_C0DE_C0DE);
234    let mut centers: Vec<f64> = Vec::with_capacity(k);
235    // First centre: pick uniformly at random.
236    centers.push(col[uniform_index(&mut state, col.len() as u64)]);
237    while centers.len() < k {
238        // D²-proportional sampling.
239        let d2: Vec<f64> = col
240            .iter()
241            .map(|&v| {
242                centers
243                    .iter()
244                    .map(|&c| (v - c).powi(2))
245                    .fold(f64::INFINITY, f64::min)
246            })
247            .collect();
248        let total: f64 = d2.iter().sum();
249        let target = uniform_f64(&mut state) * total;
250        let mut acc = 0.0_f64;
251        let mut pick = 0usize;
252        for (i, &d) in d2.iter().enumerate() {
253            acc += d;
254            if acc >= target {
255                pick = i;
256                break;
257            }
258        }
259        centers.push(col[pick]);
260    }
261    centers
262}
263
264fn lcg_next(state: &mut u64) -> u64 {
265    *state = state
266        .wrapping_mul(6_364_136_223_846_793_005)
267        .wrapping_add(1_442_695_040_888_963_407);
268    *state
269}
270
271fn uniform_index(state: &mut u64, n: u64) -> usize {
272    let max = u64::MAX - (u64::MAX % n);
273    loop {
274        let r = lcg_next(state);
275        if r < max {
276            return (r % n) as usize;
277        }
278    }
279}
280
281fn uniform_f64(state: &mut u64) -> f64 {
282    // 53-bit uniform on [0, 1).
283    (lcg_next(state) >> 11) as f64 / ((1u64 << 53) as f64)
284}
285
286#[cfg(test)]
287mod tests {
288    use super::*;
289    use ndarray::array;
290
291    #[test]
292    fn uniform_bins_partition_the_range() {
293        let x = array![[0.0], [1.0], [2.0], [3.0], [4.0]];
294        let (d, t) = KBinsDiscretizer::fit_transform(x.view(), 4, BinStrategy::Uniform, 0).unwrap();
295        assert_eq!(d.edges[0].len(), 5);
296        // Edges are [0, 1, 2, 3, 4]; bins are the half-open intervals
297        // `[0, 1)`, `[1, 2)`, `[2, 3)`, `[3, 4]`. Values 0.0..4.0 fall in
298        // bins 0..3, with 4.0 clamped to the last bin (3).
299        assert_eq!(t.column(0).to_vec(), vec![0, 1, 2, 3, 3]);
300    }
301
302    #[test]
303    fn quantile_bins_are_equal_frequency() {
304        // 8 samples, 4 bins → 2 per bin.
305        let x = array![[1.0], [2.0], [3.0], [4.0], [5.0], [6.0], [7.0], [8.0]];
306        let (_d, t) =
307            KBinsDiscretizer::fit_transform(x.view(), 4, BinStrategy::Quantile, 0).unwrap();
308        let mut counts = [0usize; 4];
309        for &b in t.column(0).iter() {
310            counts[b] += 1;
311        }
312        for &c in &counts {
313            assert!(c >= 1 && c <= 3, "counts = {counts:?}");
314        }
315    }
316
317    #[test]
318    fn kmeans_is_deterministic_by_seed() {
319        let x = array![[1.0], [2.0], [10.0], [11.0], [20.0], [21.0]];
320        let a = KBinsDiscretizer::fit(x.view(), 3, BinStrategy::KMeans, 42).unwrap();
321        let b = KBinsDiscretizer::fit(x.view(), 3, BinStrategy::KMeans, 42).unwrap();
322        assert_eq!(a.edges, b.edges);
323    }
324}