about summary refs log tree commit diff
path: root/src/pca.rs
blob: 23e3105261f1bd0a644515f1fee1c6938730f30c (plain)
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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
//! PCA over a correlation matrix.
//!
//! The correlation matrix is *the* input: PCA of standardised traits is the
//! eigendecomposition of R, so this needs no second data path and no refetch --
//! which is also why it waits for the matrix to be trustworthy (ai-memory #106:
//! the r matrix first, PCA behind its own parity test).
//!
//! Two decisions that a reader will want, both taken from #103:
//!
//! * **Traits with a gap are dropped, and named.** A correlation matrix from
//!   real data has cells that are null (overlap below `min_overlap`), and a
//!   component computed from a matrix with holes is not defined. GN2 silently
//!   mutates its shared-sample list to force a rectangle; that produces a
//!   component nobody can reproduce. Here every dropped trait travels in
//!   `dropped`, so a caller can see why their favourite trait is missing.
//! * **The sign convention is fixed**: within a component, the loading with the
//!   largest absolute value is made positive. Eigenvectors are defined up to
//!   sign, so without a rule two correct implementations disagree, and a parity
//!   test could never be exact.
//!
//! The decomposition itself is the cyclic Jacobi method -- symmetric, small
//! matrices, no LAPACK and no new dependency. It is the slow way to do it
//! (O(n^3) per sweep) and that is why `MAX_PCA_TRAITS` exists: this is for the
//! tens-to-hundreds of traits a collection holds, not for a whole dataset.

use crate::routes::correlation_matrix::Matrix;

/// Most traits a PCA will fold in. Jacobi is O(n^3) per sweep with several
/// sweeps, so 300 traits is already ~10^8 operations; a collection is a few
/// hundred traits at most, and a dataset is not what this is for.
pub const MAX_PCA_TRAITS: usize = 300;

/// One principal component.
#[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)]
pub struct Component {
    /// Eigenvalue of the correlation matrix (its variance, since the traits are
    /// standardised).
    pub eigenvalue: f64,
    /// `eigenvalue / number of traits`: the share of total variance.
    pub explained_variance_ratio: f64,
    /// Loading of each kept trait, in the reply's trait order, sign-fixed.
    pub loadings: Vec<f64>,
}

/// The eigendecomposition, plus what it had to leave out.
#[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)]
pub struct Pca {
    /// Components, largest eigenvalue first.
    pub components: Vec<Component>,
    /// Eigenvalues in the same order, so a scree plot does not have to dig.
    pub scree: Vec<f64>,
    /// `{dataset, trait_name}` of every trait the PCA could not use, with the
    /// reason.
    pub dropped: Vec<Dropped>,
    /// Eigenvalues should sum to the number of traits; reported so a caller can
    /// check that the decomposition is sane rather than trust it.
    pub trace: f64,
}

#[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)]
pub struct Dropped {
    pub dataset: String,
    pub trait_name: String,
    pub reason: String,
}

/// Eigenvalues (descending) and eigenvectors (columns) of a symmetric matrix.
///
/// Returns `None` when the matrix is not square, not symmetric within a
/// tolerance, or larger than [`MAX_PCA_TRAITS`].
pub fn symmetric_eigen(matrix: &[Vec<f64>]) -> Option<(Vec<f64>, Vec<Vec<f64>>)> {
    let n = matrix.len();
    if n == 0 || n > MAX_PCA_TRAITS || matrix.iter().any(|row| row.len() != n) {
        return None;
    }
    // Symmetry is a precondition, not a nicety: Jacobi silently produces
    // garbage for a matrix that only looks symmetric.
    for i in 0..n {
        for j in 0..i {
            let scale = matrix[i][j].abs().max(matrix[j][i].abs()).max(1.0);
            if (matrix[i][j] - matrix[j][i]).abs() > 1e-12 * scale {
                return None;
            }
        }
    }

    let mut a = matrix.to_vec();
    let mut v = vec![vec![0.0; n]; n];
    for (i, row) in v.iter_mut().enumerate() {
        row[i] = 1.0;
    }

    for _sweep in 0..100 {
        let mut off_diagonal = 0.0;
        for i in 0..n {
            for j in (i + 1)..n {
                off_diagonal += a[i][j] * a[i][j];
            }
        }
        if off_diagonal.sqrt() < 1e-14 {
            break;
        }
        for p in 0..n {
            for q in (p + 1)..n {
                if a[p][q].abs() < 1e-300 {
                    continue;
                }
                // Jacobi rotation that zeroes a[p][q].
                let theta = (a[q][q] - a[p][p]) / (2.0 * a[p][q]);
                let t = theta.signum() / (theta.abs() + (theta * theta + 1.0).sqrt());
                let c = 1.0 / (t * t + 1.0).sqrt();
                let s = t * c;
                for k in 0..n {
                    let akp = a[k][p];
                    let akq = a[k][q];
                    a[k][p] = c * akp - s * akq;
                    a[k][q] = s * akp + c * akq;
                }
                for k in 0..n {
                    let apk = a[p][k];
                    let aqk = a[q][k];
                    a[p][k] = c * apk - s * aqk;
                    a[q][k] = s * apk + c * aqk;
                }
                for k in 0..n {
                    let vkp = v[k][p];
                    let vkq = v[k][q];
                    v[k][p] = c * vkp - s * vkq;
                    v[k][q] = s * vkp + c * vkq;
                }
            }
        }
    }

    let mut order: Vec<usize> = (0..n).collect();
    order.sort_by(|x, y| a[*y][*y].partial_cmp(&a[*x][*x]).unwrap_or(std::cmp::Ordering::Equal));
    let eigenvalues: Vec<f64> = order.iter().map(|i| a[*i][*i]).collect();
    let mut eigenvectors = vec![vec![0.0; n]; n];
    for (column, source) in order.iter().enumerate() {
        // Sign convention: largest absolute loading positive.
        let mut largest = 0usize;
        for row in 0..n {
            if v[row][*source].abs() > v[largest][*source].abs() {
                largest = row;
            }
        }
        let flip = if v[largest][*source] < 0.0 { -1.0 } else { 1.0 };
        for row in 0..n {
            eigenvectors[row][column] = flip * v[row][*source];
        }
    }
    Some((eigenvalues, eigenvectors))
}

/// PCA of a correlation matrix, dropping the traits the matrix cannot place.
pub fn analyse(matrix: &Matrix) -> Pca {
    let size = matrix.r.len();
    let mut dropped: Vec<Dropped> = Vec::new();
    let mut kept: Vec<usize> = Vec::new();
    for (index, trait_ref) in matrix.traits.iter().enumerate() {
        let mut reason = None;
        if index >= size {
            reason = Some("the matrix has no row for this trait".to_string());
        } else {
            for (other, cell) in matrix.r[index].iter().enumerate() {
                if cell.is_none() {
                    reason = Some(format!(
                        "no correlation with trait {}, so the matrix has a gap",
                        other + 1
                    ));
                    break;
                }
            }
        }
        match reason {
            Some(reason) => dropped.push(Dropped {
                dataset: trait_ref.dataset.clone(),
                trait_name: trait_ref.trait_name.clone(),
                reason,
            }),
            None => kept.push(index),
        }
    }

    let n = kept.len();
    if n < 2 || n > MAX_PCA_TRAITS {
        return Pca {
            components: Vec::new(),
            scree: Vec::new(),
            dropped,
            trace: 0.0,
        };
    }
    let small: Vec<Vec<f64>> = kept
        .iter()
        .map(|row| kept.iter().map(|column| matrix.r[*row][*column].unwrap_or(0.0)).collect())
        .collect();
    let Some((eigenvalues, eigenvectors)) = symmetric_eigen(&small) else {
        return Pca {
            components: Vec::new(),
            scree: Vec::new(),
            dropped,
            trace: 0.0,
        };
    };
    let trace: f64 = eigenvalues.iter().sum();
    let components = eigenvalues
        .iter()
        .enumerate()
        .map(|(column, eigenvalue)| Component {
            eigenvalue: *eigenvalue,
            // Traits are standardised, so the total variance is the number of
            // traits and the trace should equal it; the ratio divides by n, not
            // by the trace, so rounding in the trace cannot skew it.
            explained_variance_ratio: eigenvalue / n as f64,
            loadings: (0..n).map(|row| eigenvectors[row][column]).collect(),
        })
        .collect();
    Pca {
        components,
        scree: eigenvalues,
        dropped,
        trace,
    }
}

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

    fn assert_close(a: f64, b: f64, tolerance: f64) {
        assert!((a - b).abs() < tolerance, "{a} vs {b}");
    }

    #[test]
    fn identity_has_unit_eigenvalues() {
        let (values, vectors) =
            symmetric_eigen(&[vec![1.0, 0.0, 0.0], vec![0.0, 1.0, 0.0], vec![0.0, 0.0, 1.0]])
                .expect("identity");
        assert_eq!(values.len(), 3);
        for value in &values {
            assert_close(*value, 1.0, 1e-12);
        }
        // Orthonormal columns.
        for column in 0..3 {
            let norm: f64 = (0..3).map(|row| vectors[row][column].powi(2)).sum();
            assert_close(norm, 1.0, 1e-12);
        }
    }

    #[test]
    fn a_known_two_by_two_splits_into_1_plus_minus_rho() {
        // Eigenvalues of [[1, r], [r, 1]] are 1+r and 1-r.
        let rho = 0.5;
        let (values, vectors) =
            symmetric_eigen(&[vec![1.0, rho], vec![rho, 1.0]]).expect("2x2");
        assert_eq!(values.len(), 2);
        assert_close(values[0], 1.5, 1e-12);
        assert_close(values[1], 0.5, 1e-12);
        // Sign convention: the largest absolute loading is positive.
        assert!(vectors[0][0] > 0.0 && vectors[1][0] > 0.0);
    }

    #[test]
    fn the_trace_is_the_number_of_traits() {
        let rho = -0.3;
        let matrix = vec![
            vec![1.0, rho, 0.2],
            vec![rho, 1.0, 0.1],
            vec![0.2, 0.1, 1.0],
        ];
        let (values, _) = symmetric_eigen(&matrix).expect("3x3");
        let trace: f64 = values.iter().sum();
        assert_close(trace, 3.0, 1e-12);
        // Descending.
        assert!(values[0] >= values[1] && values[1] >= values[2]);
    }

    #[test]
    fn a_non_symmetric_matrix_is_refused() {
        assert!(symmetric_eigen(&[vec![1.0, 0.5], vec![0.4, 1.0]]).is_none());
    }

    #[test]
    fn the_too_large_case_is_refused() {
        let big = vec![vec![1.0; MAX_PCA_TRAITS + 1]; MAX_PCA_TRAITS + 1];
        assert!(symmetric_eigen(&big).is_none());
    }
}