changeforest 1.2.1

Random Forests for Change Point Detection
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

use crate::control::Control;
use crate::gain::{ApproxGainResult, FullGainResult};
use crate::optimizer::OptimizerResult;
use crate::ModelSelectionResult;

pub trait Gain {
    /// Total number of observations.
    fn n(&self) -> usize;

    #[allow(unused_variables)]
    /// Loss of segment `[start, stop)`.
    ///
    /// This is typically a parametric loss, i.e. minimal negative log-likelihood. Needs
    /// not be normalized the by segment length.
    fn loss(&self, start: usize, stop: usize) -> f64 {
        panic!("Not implemented.");
    }

    /// Gain when splitting segment [start, stop) at `split`.
    fn gain(&self, start: usize, stop: usize, split: usize) -> f64 {
        self.loss(start, stop) - self.loss(start, split) - self.loss(split, stop)
    }

    /// Gain when splitting segment `[start, stop)` at points in `split_candidates`.
    ///
    /// Returns an `ndarray::Array1` of length `stop - start`. Entries without
    /// corresponding entry in `split_candidates` are `f64::NAN`.
    fn gain_full(&self, start: usize, stop: usize, split_candidates: &[usize]) -> FullGainResult {
        let mut gain = ndarray::Array::from_elem(stop - start, f64::NAN);

        for split_point in split_candidates {
            gain[split_point - start] = self.gain(start, stop, *split_point);
        }

        FullGainResult {
            start,
            stop,
            gain,
            max_gain: None,
            best_split: None,
        }
    }

    /// Does a certain split corresponds to a true change point?
    fn model_selection(&self, optimizer_result: &OptimizerResult) -> ModelSelectionResult;

    /// Hyperparameters.
    fn control(&self) -> &Control;
}

pub trait ApproxGain {
    #[allow(unused_variables)]
    /// An approximation of the gain when splitting segment `[start, stop)` at points in `split_candidates`.
    ///
    /// Returns an `ndarray::Array1` of length `stop - start`. Entries without
    /// corresponding entry in `split_candidates` are `f64::NAN`.
    ///
    /// This can be useful when combining classifier-based gains and the two-step-search
    /// optimizer.
    fn gain_approx(
        &self,
        start: usize,
        stop: usize,
        guess: usize,
        split_points: &[usize],
    ) -> ApproxGainResult;
}

#[cfg(test)]
mod tests {

    use super::*;
    use crate::testing;
    use assert_approx_eq::*;
    use rstest::*;

    #[rstest]
    #[case(0, 4, 4. * 0.25)]
    #[case(0, 2, 0.)]
    #[case(0, 3, 4. / 6.)]
    #[case(1, 4, 4. / 6.)]
    #[case(1, 3, 4. * 0.125)]
    #[case(3, 3, 0.)]
    fn test_change_in_mean_loss(#[case] start: usize, #[case] stop: usize, #[case] expected: f64) {
        let X = ndarray::array![[0., 0.], [0., 0.], [0., 1.], [0., 1.]];
        let X_view = X.view();

        let control = Control::default();
        assert_eq!(X.shape(), &[4, 2]);

        let change_in_mean = testing::ChangeInMean::new(&X_view, &control);
        assert_approx_eq!(change_in_mean.loss(start, stop), expected);
    }

    #[rstest]
    #[case(0, 4, 2, 1.)]
    #[case(0, 4, 0, 0.)]
    #[case(0, 4, 1, 6. / 18.)]
    #[case(0, 4, 3, 6. / 18.)]
    #[case(0, 3, 2, 6. / 9.)]
    #[case(0, 3, 1, 6. / 36.)]
    #[case(0, 6, 0, 0.)]
    #[case(0, 6, 1, 6. / 90.)]
    #[case(0, 6, 2, 6. / 36.)]
    #[case(0, 6, 3, 6. / 18.)]
    #[case(0, 6, 4, 5. * 6. / 18.)]
    #[case(0, 6, 5, 6. / 90.)]
    fn test_change_in_mean_gain(
        #[case] start: usize,
        #[case] stop: usize,
        #[case] split: usize,
        #[case] expected: f64,
    ) {
        let X = ndarray::array![[1., 0.], [1., 0.], [1., 1.], [1., 1.], [0., -1.], [1., 0.]];
        let X_view = X.view();
        assert_eq!(X_view.shape(), &[6, 2]);

        let control = Control::default();
        let change_in_mean = testing::ChangeInMean::new(&X_view, &control);
        assert_approx_eq!(change_in_mean.gain(start, stop, split), expected);
        assert_approx_eq!(
            change_in_mean.gain_full(start, stop, &[split]).gain[split - start],
            expected
        );
    }
}