1use ndarray::{Array2, ArrayView2};
25use solow_core::{Error, Result};
26
27#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
29#[derive(Copy, Clone, Debug, PartialEq, Eq)]
30pub enum BinStrategy {
31 Uniform,
33 Quantile,
35 KMeans,
37}
38
39#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
41#[derive(Clone, Debug, PartialEq)]
42pub struct KBinsDiscretizer {
43 pub edges: Vec<Vec<f64>>,
46 pub n_bins: usize,
49 pub strategy: BinStrategy,
51}
52
53impl KBinsDiscretizer {
54 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 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 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 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 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 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 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, ¢) 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 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 centers.push(col[uniform_index(&mut state, col.len() as u64)]);
237 while centers.len() < k {
238 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 (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 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 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}