API Reference / algorithms / timeseries / classification /

dictionary.py

BOSS - Bag-of-SFA-Symbols dictionary classification.

Classes

BOSSClassifier

class algorithms.timeseries.classification.dictionary.BOSSClassifier(TimeSeriesClassifier)

BOSS classifies by which symbolic patterns a series contains.

BOSS turns each series into a bag of words. Every sliding window is reduced to its lowest Fourier coefficients, those are quantised into letters, and the resulting words are counted. Two series are similar when they contain the same patterns in similar proportions — regardless of where those patterns occur.

The low-pass step is what distinguishes it: keeping only low-frequency coefficients discards high-frequency detail, which is where much of the noise lives.

Constructor 
__init__(
    self,
    window_size: float = 0.25,
    word_length: int = 8,
    alphabet_size: int = 4,
    norm_mean: bool = True,
    n_neighbors: int = 1,
)

Overview

  1. Slide a window over each series and take the DFT of each window.
  2. Keep the lowest word_length coefficients, dropping the DC term and
scaling by the window's standard deviation.
  1. Quantise each coefficient into one of alphabet_size letters, using
breakpoints fitted from the training data (Multiple Coefficient Binning).
  1. Drop a word identical to its predecessor, so a slowly varying stretch
contributes one word rather than hundreds.
  1. Count the surviving words per series and classify by nearest neighbour
under the asymmetric BOSS distance.

Theory

For histograms B_a, B_b the BOSS distance is

d(a, b) = \sum_{s \ \in \ B_a,\ B_a(s) > 0} \left( B_a(s) - B_b(s) \right)^2

The restriction to words present in a makes it asymmetric: d(a, b) \neq d(b, a) in general. That is deliberate, not an oversight — a reference series carrying extra noise words should not be penalised for them when the query does not contain them.

Numerosity reduction — collapsing runs of identical consecutive words — matters more than it looks. Without it a long flat stretch dominates the histogram purely because it is long, and the representation stops describing structure and starts describing duration.

Parameters

window_size
int or float = 0.25
Sliding window length. A float in (0, 1] is a fraction of the series length. Sets the time scale of the patterns BOSS can see.
word_length
int = 8
Number of Fourier coefficients retained per window. Longer words capture more shape detail and tolerate less noise.
alphabet_size
int = 4
Letters per coefficient. Four is the near-universal choice; the method is famously insensitive to this.
norm_mean
bool = True
Whether to drop each window's mean, making the representation invariant to local offset.
n_neighbors
int = 1
Neighbours to vote under the BOSS distance.

Attributes

breakpoints_
np.ndarray of shape (word_length, alphabet_size - 1)
Fitted quantisation breakpoints per coefficient.
histograms_
np.ndarray of shape (n_samples, n_words)
Training word-count histograms.
vocabulary_
np.ndarray of shape (n_words,)
The word codes actually observed during fit.
classes_
np.ndarray of shape (n_classes,)
Class labels seen during fit.

Notes

Complexity. Fitting is O(n L \ell) for n series of length L and word length \ell — the sliding DFT is advanced by the momentary Fourier transform in the shared C++ kernel tuiml._cpp_ext.timeseries.sfa_transform, so each window costs O(\ell) rather than O(w \ell). Prediction is O(m n V) for a vocabulary of size V, since it is a nearest neighbour search over histograms.

When to use — and where it does not win. BOSS represents a series by what patterns it contains and how often, discarding where they occur. That is a genuinely different view from every other member of this family, and it shows up where position-invariant content is the signal. Measured on two synthetic problems, 160 train / 160 test:

================================= ====== ========== ========= ===== ========= problem BOSS MiniRocket Shapelet DTW Euclidean ================================= ====== ========== ========= ===== ========= motif count (2 vs 6 repeats 0.844 1.000 0.956 0.950 0.588 at random positions) frequency under heavy noise 0.775 0.944 0.831 0.656 0.869 (sd 3.0) ================================= ====== ========== ========= ===== =========

Read that honestly: BOSS beats a Euclidean neighbour decisively when position varies (0.844 against 0.588) and beats DTW under noise, but MiniRocketClassifier beat it on both. If you want one classifier, use MINIROCKET. BOSS earns its place as a diverse component — a symbolic, frequency-domain view that fails differently from convolutional and elastic methods, which is precisely why every strong meta-ensemble in the literature includes a dictionary member. Combine it through VotingClassifier.

Its cost also grows with the training set, like DTWNeighborsClassifier and unlike MINIROCKET, so it suits small to moderate datasets.

The published method ensembles many (window_size, word_length, norm_mean) settings and keeps those within 92% of the best cross-validated accuracy. This class implements a single parameter set, which is weaker; on the noise problem above, sweeping window sizes from 25 to 150 and word lengths from 4 to 10 moved accuracy only from 0.775 to 0.781, so the gap to MINIROCKET there is not a tuning artefact.

References

Schafer2015
Schäfer, P. (2015). The BOSS is Concerned with Time Series Classification in the Presence of Noise. Data Mining and Knowledge Discovery, 29(6), 1505-1530. :doi:`10.1007/s10618-014-0377-7`
Schafer2012
Schäfer, P., & Högqvist, M. (2012). SFA: A Symbolic Fourier Approximation and Index for Similarity Search in High Dimensional Datasets. EDBT, 516-527. :doi:`10.1145/2247596.2247656`

See Also

MiniRocketClassifier

Faster, and its cost does not grow with the training set.
ShapeletTransformClassifier

Also pattern-based, but interpretable and not noise-tolerant.
python 
>>> import numpy as np
>>> from tuiml.algorithms.timeseries.classification import BOSSClassifier
>>> rng = np.random.default_rng(0)
>>> t = np.linspace(0, 8 * np.pi, 160)
>>> # Two classes distinguished by frequency, buried in heavy noise.
>>> slow = np.sin(t) + rng.normal(0, 0.8, (40, 160))
>>> fast = np.sin(3 * t) + rng.normal(0, 0.8, (40, 160))
>>> X = np.vstack([slow, fast])
>>> y = np.array([0] * 40 + [1] * 40)
>>> model = BOSSClassifier(window_size=40, word_length=6).fit(X, y)
>>> bool((model.predict(X) == y).mean() > 0.9)
True

Methods

get_parameter_schema (cls) -> Dict[str, Dict[str, Any]]

Return JSON Schema for algorithm parameters.

get_capabilities (cls) -> List[str]

Return supported capabilities.

get_complexity (cls) -> str

Return complexity analysis.

get_references (cls) -> List[str]

Return academic citations.

fit (self, X: np.ndarray, y: np.ndarray) -> 'BOSSClassifier'

Fit the quantisation breakpoints and build training histograms.

Parameters
X
np.ndarray of shape (n_samples, n_timepoints) or (n_samples, n_channels, n_timepoints)
Training series.
y
np.ndarray of shape (n_samples,)
Training labels.
Returns
self
BOSSClassifier
The fitted classifier.
transform (self, X: np.ndarray) -> np.ndarray

Return the word-count histogram of each series.

Parameters
X
np.ndarray of shape (n_samples, n_timepoints) or (n_samples, n_channels, n_timepoints)
Series to transform.
Returns
histograms
np.ndarray of shape (n_samples, n_words)
Counts over the fitted vocabulary.
predict (self, X: np.ndarray) -> np.ndarray

Classify each series by nearest neighbour under the BOSS distance.

Parameters
X
np.ndarray of shape (n_samples, n_timepoints) or (n_samples, n_channels, n_timepoints)
Series to classify.
Returns
y_pred
np.ndarray of shape (n_samples,)
Predicted labels.
predict_proba (self, X: np.ndarray) -> np.ndarray

Return the neighbour vote share for each class.

Parameters
X
np.ndarray of shape (n_samples, n_timepoints) or (n_samples, n_channels, n_timepoints)
Series to classify.
Returns
proba
np.ndarray of shape (n_samples, n_classes)
Vote shares, rows summing to one.
__repr__ (self) -> str

Return a readable representation of the classifier.