oxits 0.1.0

Time series classification and transformation library for Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

/// LB_Kim: O(1) lower bound using first, last, min, max features.
///
/// Computes the Euclidean distance between the feature vectors
/// (first, last, min, max) of two time series.
pub fn lb_kim(a: &[f64], b: &[f64]) -> f64 {
    assert!(
        !a.is_empty() && !b.is_empty(),
        "Time series must be non-empty"
    );

    let a_first = a[0];
    let a_last = a[a.len() - 1];
    let a_min = a.iter().copied().fold(f64::INFINITY, f64::min);
    let a_max = a.iter().copied().fold(f64::NEG_INFINITY, f64::max);

    let b_first = b[0];
    let b_last = b[b.len() - 1];
    let b_min = b.iter().copied().fold(f64::INFINITY, f64::min);
    let b_max = b.iter().copied().fold(f64::NEG_INFINITY, f64::max);

    let d_first = (a_first - b_first).powi(2);
    let d_last = (a_last - b_last).powi(2);
    let d_min = (a_min - b_min).powi(2);
    let d_max = (a_max - b_max).powi(2);

    d_first.max(d_last).max(d_min).max(d_max).sqrt()
}

/// LB_Keogh: O(n) lower bound using envelope.
///
/// Computes the lower bound by comparing series `a` against an envelope
/// (upper, lower) derived from series `b` with a given window size.
pub fn lb_keogh(a: &[f64], b: &[f64], window_size: usize) -> f64 {
    assert_eq!(a.len(), b.len(), "Time series must have same length");
    let n = a.len();

    let mut sum = 0.0;
    for i in 0..n {
        let lo = i.saturating_sub(window_size);
        let hi = (i + window_size + 1).min(n);
        let b_slice = &b[lo..hi];

        let upper = b_slice.iter().copied().fold(f64::NEG_INFINITY, f64::max);
        let lower = b_slice.iter().copied().fold(f64::INFINITY, f64::min);

        if a[i] > upper {
            sum += (a[i] - upper).powi(2);
        } else if a[i] < lower {
            sum += (a[i] - lower).powi(2);
        }
    }

    sum.sqrt()
}

/// LB_Yi: O(n) lower bound using the range of one series.
///
/// Uses max and min of series `a` to bound distance from `b`.
pub fn lb_yi(a: &[f64], b: &[f64]) -> f64 {
    assert_eq!(a.len(), b.len(), "Time series must have same length");

    let a_max = a.iter().copied().fold(f64::NEG_INFINITY, f64::max);
    let a_min = a.iter().copied().fold(f64::INFINITY, f64::min);

    let sum: f64 = b
        .iter()
        .map(|&v| {
            if v > a_max {
                (v - a_max).powi(2)
            } else if v < a_min {
                (v - a_min).powi(2)
            } else {
                0.0
            }
        })
        .sum();

    sum.sqrt()
}

/// LB_Improved: improved lower bound combining LB_Keogh with refinement.
///
/// First computes LB_Keogh, then refines using the projection residuals.
pub fn lb_improved(a: &[f64], b: &[f64], window_size: usize) -> f64 {
    assert_eq!(a.len(), b.len(), "Time series must have same length");
    let n = a.len();

    // Phase 1: Standard LB_Keogh and compute projection
    let mut sum1 = 0.0;
    let mut projected = vec![0.0; n];

    for i in 0..n {
        let lo = i.saturating_sub(window_size);
        let hi = (i + window_size + 1).min(n);
        let b_slice = &b[lo..hi];

        let upper = b_slice.iter().copied().fold(f64::NEG_INFINITY, f64::max);
        let lower = b_slice.iter().copied().fold(f64::INFINITY, f64::min);

        if a[i] > upper {
            sum1 += (a[i] - upper).powi(2);
            projected[i] = upper;
        } else if a[i] < lower {
            sum1 += (a[i] - lower).powi(2);
            projected[i] = lower;
        } else {
            projected[i] = a[i];
        }
    }

    // Phase 2: Compute LB_Keogh of b against envelope of projected
    let mut sum2 = 0.0;
    for i in 0..n {
        let lo = i.saturating_sub(window_size);
        let hi = (i + window_size + 1).min(n);
        let p_slice = &projected[lo..hi];

        let upper = p_slice.iter().copied().fold(f64::NEG_INFINITY, f64::max);
        let lower = p_slice.iter().copied().fold(f64::INFINITY, f64::min);

        if b[i] > upper {
            sum2 += (b[i] - upper).powi(2);
        } else if b[i] < lower {
            sum2 += (b[i] - lower).powi(2);
        }
    }

    (sum1 + sum2).sqrt()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lb_kim_identical() {
        let a = vec![1.0, 2.0, 3.0, 4.0];
        assert!(lb_kim(&a, &a).abs() < 1e-10);
    }

    #[test]
    fn test_lb_kim_different() {
        let a = vec![0.0, 1.0, 2.0];
        let b = vec![3.0, 4.0, 5.0];
        let d = lb_kim(&a, &b);
        assert!(d > 0.0);
    }

    #[test]
    fn test_lb_keogh_identical() {
        let a = vec![1.0, 2.0, 3.0, 4.0, 5.0];
        let d = lb_keogh(&a, &a, 1);
        assert!(d.abs() < 1e-10);
    }

    #[test]
    fn test_lb_keogh_lower_bound() {
        use crate::metrics::dtw::dtw_classic;
        let a = vec![0.0, 1.0, 0.0, -1.0, 0.0];
        let b = vec![1.0, 0.0, -1.0, 0.0, 1.0];
        let lb = lb_keogh(&a, &b, 1);
        let dtw = dtw_classic(&a, &b);
        assert!(lb <= dtw + 1e-8, "LB_Keogh ({lb}) should be <= DTW ({dtw})");
    }

    #[test]
    fn test_lb_yi_identical() {
        let a = vec![1.0, 2.0, 3.0];
        assert!(lb_yi(&a, &a).abs() < 1e-10);
    }

    #[test]
    fn test_lb_yi_lower_bound() {
        use crate::metrics::dtw::dtw_classic;
        let a = vec![0.0, 1.0, 0.0, -1.0, 0.0];
        let b = vec![1.0, 0.0, -1.0, 0.0, 1.0];
        let lb = lb_yi(&a, &b);
        let dtw = dtw_classic(&a, &b);
        assert!(lb <= dtw + 1e-8, "LB_Yi ({lb}) should be <= DTW ({dtw})");
    }

    #[test]
    fn test_lb_improved_lower_bound() {
        use crate::metrics::dtw::dtw_classic;
        let a = vec![0.0, 1.0, 0.0, -1.0, 0.0];
        let b = vec![1.0, 0.0, -1.0, 0.0, 1.0];
        let lb = lb_improved(&a, &b, 1);
        let dtw = dtw_classic(&a, &b);
        assert!(
            lb <= dtw + 1e-8,
            "LB_Improved ({lb}) should be <= DTW ({dtw})"
        );
    }

    #[test]
    fn test_lb_improved_tighter_than_keogh() {
        let a = vec![0.0, 1.0, 2.0, 1.0, 0.0, -1.0, -2.0, -1.0];
        let b = vec![1.0, 2.0, 1.0, 0.0, -1.0, -2.0, -1.0, 0.0];
        let lb_k = lb_keogh(&a, &b, 1);
        let lb_i = lb_improved(&a, &b, 1);
        assert!(
            lb_i >= lb_k - 1e-10,
            "LB_Improved ({lb_i}) should be >= LB_Keogh ({lb_k})"
        );
    }
}