pr_ml/svm/

multi.rs

//! Multi-class classification support vector machine.

use std::collections::HashMap;

use rand::seq::SliceRandom;

use super::{BinarySVM, Kernel, RowVector, SVMParams};

/// A fitted multi-class classification support vector machine using One-vs-One strategy.
///
/// # Type Parameters
///
/// - `D` - The dimension or number of features.
/// - `K` - The type of the kernel function.
/// - `C` - The type of the class label.
///
/// # Strategy
///
/// Uses One-vs-One (OvO) approach: trains a binary classifier for each pair of classes.
/// For N classes, trains N*(N-1)/2 binary classifiers. Prediction is done by majority voting.
#[allow(clippy::doc_markdown)]
#[derive(Debug, Clone, PartialEq)]
pub struct MultiClassSVM<const D: usize, K, C>
where
    K: Kernel<D>,
    C: Eq + std::hash::Hash + Clone,
{
    /// Binary classifiers for each pair of classes.
    /// Key is (class1, class2) where class1 < class2 (in terms of internal ordering).
    classifiers: HashMap<(usize, usize), BinarySVM<D, K>>,
    /// Mapping from class label to internal index.
    class_to_index: HashMap<C, usize>,
    /// Mapping from internal index to class label.
    index_to_class: Vec<C>,
}

impl<const D: usize, K> SVMParams<D, K>
where
    K: Kernel<D>,
{
    /// Fits a multi-class SVM using One-vs-One strategy.
    ///
    /// # Arguments
    ///
    /// - `data` - Training data as an iterator of (`feature_vector`, `class_label`) tuples.
    ///
    /// # Returns
    ///
    /// A fitted [`MultiClassSVM`] that can predict class labels.
    ///
    /// # Notes
    ///
    /// Calling this method with large datasets may consume significant memory and time, consider using [`fit_multiclass_with_options`](Self::fit_multiclass_with_options) to limit samples per binary classifier.
    ///
    /// # Examples
    ///
    /// ```
    /// use pr_ml::{RowVector, svm::{SVMParams, LinearKernel, MultiClassSVM}};
    ///
    /// let data = vec![
    ///     (RowVector::from([1.0, 2.0]), 0),
    ///     (RowVector::from([2.0, 3.0]), 0),
    ///     (RowVector::from([-1.0, -2.0]), 1),
    ///     (RowVector::from([-2.0, -3.0]), 1),
    /// ];
    ///
    /// let svm: MultiClassSVM<2, LinearKernel, _> = SVMParams::new().fit_multiclass(data);
    /// let prediction = svm.predict(&RowVector::from([1.5, 2.5]));
    /// assert_eq!(prediction, 0);
    /// ```
    pub fn fit_multiclass<I, C>(self, data: I) -> MultiClassSVM<D, K, C>
    where
        I: IntoIterator<Item = (RowVector<D>, C)>,
        C: Eq + std::hash::Hash + Clone + Ord,
    {
        self.fit_multiclass_with_options(data, |_, _, _| {}, 0)
    }

    /// Fits a multi-class SVM using One-vs-One strategy with progress callback.
    ///
    /// # Arguments
    ///
    /// - `data` - Training data as an iterator of (`feature_vector`, `class_label`) tuples.
    /// - `callback` - Called after each binary classifier is trained with (`current`, `total`, `sample_count`).
    ///
    /// # Returns
    ///
    /// A fitted [`MultiClassSVM`] that can predict class labels.
    ///
    /// # Notes
    ///
    /// Calling this method with large datasets may consume significant memory and time, consider using [`fit_multiclass_with_options`](Self::fit_multiclass_with_options) to limit samples per binary classifier.
    pub fn fit_multiclass_with_callback<I, C, F>(
        self,
        data: I,
        callback: F,
    ) -> MultiClassSVM<D, K, C>
    where
        I: IntoIterator<Item = (RowVector<D>, C)>,
        C: Eq + std::hash::Hash + Clone + Ord,
        F: FnMut(usize, usize, usize),
    {
        self.fit_multiclass_with_options(data, callback, 0)
    }

    /// Fits a multi-class SVM using One-vs-One strategy with progress callback and optional subsampling.
    ///
    /// # Arguments
    ///
    /// - `data` - Training data as an iterator of (`feature_vector`, `class_label`) tuples.
    /// - `callback` - Called after each binary classifier is trained with (`current`, `total`, `sample_count`).
    /// - `max_samples_per_pair` - Maximum samples to use per binary classifier (0 = use all).
    ///
    /// # Returns
    ///
    /// A fitted [`MultiClassSVM`] that can predict class labels.
    pub fn fit_multiclass_with_options<I, C, F>(
        self,
        data: I,
        mut callback: F,
        max_samples_per_pair: usize,
    ) -> MultiClassSVM<D, K, C>
    where
        I: IntoIterator<Item = (RowVector<D>, C)>,
        C: Eq + std::hash::Hash + Clone + Ord,
        F: FnMut(usize, usize, usize),
    {
        // Collect all data points
        let data_vec: Vec<_> = data.into_iter().collect();

        // Build class mappings
        let mut unique_classes: Vec<C> = data_vec.iter().map(|(_, c)| c.clone()).collect();
        unique_classes.sort_unstable();
        unique_classes.dedup();

        let class_to_index: HashMap<C, usize> = unique_classes
            .iter()
            .enumerate()
            .map(|(i, c)| (c.clone(), i))
            .collect();

        let index_to_class = unique_classes;
        let num_classes = index_to_class.len();

        // Train binary classifiers for each pair of classes
        let mut classifiers = HashMap::new();
        let total_classifiers = num_classes * (num_classes - 1) / 2;
        let mut current_classifier = 0;

        for i in 0..num_classes {
            for j in (i + 1)..num_classes {
                // Filter data for classes i and j
                let mut binary_data: Vec<_> = data_vec
                    .iter()
                    .filter_map(|(x, c)| {
                        let class_idx = class_to_index[c];
                        if class_idx == i {
                            Some((*x, true)) // class i is positive
                        } else if class_idx == j {
                            Some((*x, false)) // class j is negative
                        } else {
                            None
                        }
                    })
                    .collect();

                // Subsample if requested
                if max_samples_per_pair > 0 && binary_data.len() > max_samples_per_pair {
                    let mut rng = rand::rng();
                    binary_data.shuffle(&mut rng);
                    binary_data.truncate(max_samples_per_pair);
                }

                // Train binary classifier
                if !binary_data.is_empty() {
                    let sample_count = binary_data.len();
                    let binary_svm = self.clone().fit_binary(binary_data);
                    classifiers.insert((i, j), binary_svm);
                    current_classifier += 1;
                    callback(current_classifier, total_classifiers, sample_count);
                }
            }
        }

        MultiClassSVM {
            classifiers,
            class_to_index,
            index_to_class,
        }
    }
}

impl<const D: usize, K, C> MultiClassSVM<D, K, C>
where
    K: Kernel<D>,
    C: Eq + std::hash::Hash + Clone,
{
    /// Predicts the class label for a given input vector using majority voting.
    ///
    /// # Arguments
    ///
    /// - `x` - The input feature vector.
    ///
    /// # Returns
    ///
    /// The predicted class label.
    #[must_use]
    pub fn predict(&self, x: &RowVector<D>) -> C {
        let num_classes = self.index_to_class.len();
        let mut votes = vec![0; num_classes];

        // Vote using all binary classifiers
        for (&(i, j), classifier) in &self.classifiers {
            if classifier.predict(x) {
                votes[i] += 1; // Vote for class i
            } else {
                votes[j] += 1; // Vote for class j
            }
        }

        // Find class with maximum votes
        let max_votes_idx = votes
            .iter()
            .enumerate()
            .max_by_key(|(_, v)| *v)
            .map_or(0, |(idx, _)| idx);

        self.index_to_class[max_votes_idx].clone()
    }

    /// Predicts the class label and returns vote counts for all classes.
    ///
    /// # Arguments
    ///
    /// - `x` - The input feature vector.
    ///
    /// # Returns
    ///
    /// A tuple of (`predicted_class`, `votes_per_class`).
    #[must_use]
    pub fn predict_with_votes(&self, x: &RowVector<D>) -> (C, Vec<(C, usize)>) {
        let num_classes = self.index_to_class.len();
        let mut votes = vec![0; num_classes];

        // Vote using all binary classifiers
        for (&(i, j), classifier) in &self.classifiers {
            if classifier.predict(x) {
                votes[i] += 1;
            } else {
                votes[j] += 1;
            }
        }

        // Find class with maximum votes
        let max_votes_idx = votes
            .iter()
            .enumerate()
            .max_by_key(|(_, v)| *v)
            .map_or(0, |(idx, _)| idx);

        let predicted_class = self.index_to_class[max_votes_idx].clone();

        // Build vote summary
        let vote_summary: Vec<_> = self
            .index_to_class
            .iter()
            .enumerate()
            .map(|(idx, class)| (class.clone(), votes[idx]))
            .collect();

        (predicted_class, vote_summary)
    }

    /// Returns the number of classes.
    #[must_use]
    pub const fn num_classes(&self) -> usize {
        self.index_to_class.len()
    }

    /// Returns the number of binary classifiers.
    #[must_use]
    pub fn num_classifiers(&self) -> usize {
        self.classifiers.len()
    }

    /// Returns a reference to the list of class labels.
    #[must_use]
    pub fn classes(&self) -> &[C] {
        &self.index_to_class
    }
}