PaperlayerView exact revision on arXiv

Source-linked AI summary

Bag-of-Words Representation for Biomedical Time Series Classification

Jin Wang, Ping Liu, Mary F. H. She, Saeid Nahavandi, and Abbas Kouzani

arXiv:1212.2262v1cs.LGcs.AI

TL;DR

Manual analysis of large volumes of long-term EEG and ECG signals is difficult because expert resources are limited and inspection is time-consuming. The paper proposes representing biomedical time series as codeword histograms built from local segments, achieving high accuracy across three datasets and robustness to noise.

  • Problem

    Manual analysis of abundant long-term EEG and ECG signals is difficult because experienced experts are limited and inspection is time-consuming.

  • Method

    The method treats a time series as a document, converts local segments into codewords, and represents the series as a histogram while using 1-NN classification.

  • Results

    The approach achieves the highest reported accuracies on EEG, ECG-40, and ECG-15 datasets: 93.8%, 99.5%, and 100%, respectively, and remains relatively robust to noise.

  • Takeaways & Limitations

    Bag-of-words representation effectively characterizes biomedical time series while remaining insensitive to local-segment length and codebook size and robust to noise.

  • Takeaways & Limitations

    The representation may be ineffective for short time series because they cannot provide enough meaningful and discriminative local segments.

Abstract

from arXiv · show

Automatic analysis of biomedical time series such as electroencephalogram (EEG) and electrocardiographic (ECG) signals has attracted great interest in the community of biomedical engineering due to its important applications in medicine. In this work, a simple yet effective bag-of-words representation that is able to capture both local and global structure similarity information is proposed for biomedical time series representation. In particular, similar to the bag-of-words model used in text document domain, the proposed method treats a time series as a text document and extracts local segments from the time series as words. The biomedical time series is then represented as a histogram of codewords, each entry of which is the count of a codeword appeared in the time series. Although the temporal order of the local segments is ignored, the bag-of-words representation is able to capture high-level structural information because both local and global structural information are well utilized. The performance of the bag-of-words model is validated on three datasets extracted from real EEG and ECG signals. The experimental results demonstrate that the proposed method is not only insensitive to parameters of the bag-of-words model such as local segment length and codebook size, but also robust to noise.

I. INTRODUCTION

Biomedical signals such as EEG and ECG are valuable but difficult to analyze efficiently at scale. The paper proposes a bag-of-words representation to capture structural information in these time series for automated analysis.

  • Motivation: Manual inspection of long-term EEG and ECG signals is time-consuming and constrained by the limited number of experienced experts.Automated systems that assist professional experts are therefore valuable for real-world applications.
  • Motivation: Existing representations often capture local temporal or frequency information but may miss structural similarity in long, repetitive, non-periodic waveforms.This limitation is relevant to biomedical signals such as ECG and EEG.
  • Proposed idea: The proposed bag-of-words representation treats local time-series segments as words and represents each time series through codeword frequencies.This extends the bag-of-words idea from document and image analysis to biomedical time series.
  • Proposed idea: The representation uses both local and global information to capture high-level time-series structure.Its dimension is described as much lower than that of the bag-of-patterns representation.
  • Proposed idea: The representation is incrementally constructed, allowing it to represent streaming data and time series with different lengths.

A. Overview of the Proposed Approach

The proposed approach converts biomedical time series into bag-of-words histograms by extracting and encoding local segments. It is presented as a simple representation intended to support classification experiments.

  • A. Overview of the Proposed Approach: The method extracts local segments with a sliding window and represents each segment using a DWT-derived feature vector.The approach follows the paper's flowchart for biomedical time-series analysis.
  • A. Overview of the Proposed Approach: All local segments from training time series are clustered to construct a codebook of codewords.The overview describes k-means clustering as the codebook-construction step.
  • A. Overview of the Proposed Approach: The paper investigates the representation's effectiveness and robustness through experiments on biomedical time-series classification.The paper identifies these experiments as a main contribution.
  • A. Overview of the Proposed Approach: The paper describes its method, datasets, experimental results, discussion, and conclusion in successive sections.
  • A. Overview of the Proposed Approach: Each local segment is assigned a codeword, and the time series is represented as a histogram of codeword occurrences while temporal order is ignored.The histogram provides the representation used for subsequent comparison.

1) Local Segments Extraction:

The representation builds a codebook from clustered local-segment features and assigns each segment to a codeword. Codebook size must balance discrimination against noise in the resulting histogram.

  • 1) Local Segments Extraction:: A codebook is constructed by clustering local segments from training time series, with cluster centers serving as codewords.The codebook formulation uses k-means clustering on the extracted segment vectors.
  • 1) Local Segments Extraction:: The codebook contains K codewords, each represented by a d-length vector matching the local-segment feature length.The learned codebook is reused for both training and test data.
  • 1) Local Segments Extraction:: The example representation assigns extracted local segments to codewords and records their occurrences in a codeword histogram.The example figure illustrates this assignment process for an EEG time series.
  • 1) Local Segments Extraction:: A compact codebook with too few entries has limited discriminative ability, whereas a large codebook can introduce noise through histogram sparsity.The codebook size should balance discrimination and noise.

3) Codewords Assignment:

Codewords are assigned by matching each local segment to its nearest codebook entry, after which the time series becomes a codeword-count histogram for distance-based classification.

  • Codewords Assignment: Each local segment is assigned the codeword with minimum Euclidean distance in the learned codebook.The assignment is c*=arg min_j d(b_j, x_i).
  • Codewords Assignment: Ignoring temporal order, the method represents a time series as a histogram counting each assigned codeword.An example uses codebook entries 432, 118, and 628 for three local segments.
  • Codewords Assignment: The classifier assigns a test series to the training category with the smallest histogram distance using 1-Nearest Neighbor.The paper uses 1-NN to focus on evaluating the representation.
  • Codewords Assignment: Several similarity measures are introduced to compare the resulting bag-of-words histograms.The supplied section identifies histogram comparison as the next stage after representation.

1) Euclidean Distance:

The Euclidean distance compares two histograms bin by bin, but frequent codewords can dominate even when rarer codewords are more discriminative.

  • Euclidean Distance: Euclidean distance is defined as the bin-by-bin squared difference between histogram entries.The paper identifies this as a commonly used pattern-recognition distance.
  • Euclidean Distance: Because every bin pair contributes equally, frequently occurring codewords can contribute disproportionately to the distance.The paper compares this issue with common words in document histograms.
  • Euclidean Distance: Rare codewords may carry more discriminative information than frequent codewords across categories.This motivates introducing the Chi-Squared distance.
  • Euclidean Distance: A small ε is used in the Chi-Squared formulation to avoid division by zero.The regularization term addresses a numerical denominator issue.
  • Euclidean Distance: The Chi-Squared distance normalizes histogram differences to emphasize rarely occurring codewords.The supplied passages state that common words are often shared between documents from different categories.

3) Jensen-Shannon Distance:

The histogram entries represent codeword frequencies and therefore define discrete distributions, enabling distribution-based distances and overlap comparisons.

  • Jensen-Shannon Distance: Each histogram entry is the frequency of a codeword, so the histogram represents a discrete probability distribution.This interpretation motivates using divergence measures for histogram comparison.
  • Jensen-Shannon Distance: The Kullback-Leibler divergence is introduced as a measure for comparing the resulting distributions.The supplied passage presents it after interpreting histograms probabilistically.
  • Jensen-Shannon Distance: KL divergence equals zero if and only if the two histograms are identical.The paper introduces Jensen-Shannon distance to obtain a symmetric extension.
  • Jensen-Shannon Distance: Jensen-Shannon distance symmetrizes KL divergence by combining the two directional divergences.The supplied equation passage gives the combination of DKL(h||k) and DKL(k||h).
  • Jensen-Shannon Distance: Histogram intersection measures total overlap and handles partial matches when histograms have different sums.For normalized histograms, larger overlap corresponds to smaller distance.

D. Practical Implementation

The implementation reduces codebook-construction and segment-extraction costs while evaluating the representation on EEG and ECG datasets described in the experiments.

  • Practical Implementation: K-means codebook construction uses a randomly selected subset of training segments instead of all extracted segments.This reduces the computational expense of clustering large segment collections.
  • Practical Implementation: Sliding the extraction window by multiple data points reduces the number of local segments and associated computation.The paper gives steps of n = 2, 4, 6, or 8 as practical choices.
  • Practical Implementation: The MATLAB implementation was made publicly available through the MATLAB File Exchange.The supplied passage provides the public code location.
  • Practical Implementation: The supplied table is identified as summarizing the three datasets used in the experiments.The passage does not provide the table's row values.
  • Practical Implementation: The experiments use three datasets constructed from EEG and ECG signals for biomedical time-series classification.The datasets include EEG seizure detection and ECG subject-identity classification settings.
  • Practical Implementation: The EEG dataset contains five classes with 100 single-channel sequences per class, each of length 4096.The classes are labeled A through E and were recorded with the same 128-channel amplifier system.

B. ECG-40 Dataset

The ECG-40 dataset contains long ECG recordings divided into 2,000 labeled time series, and experiments evaluate parameter sensitivity using repeated cross-validation.

  • Dataset construction: ECG-40 contains 2,000 length-2048 time series extracted from forty long ECG signals and evenly distributed across forty classes.The source signals were recorded from healthy youth and older adults for about two hours at 250 Hz.
  • Experimental setup: Ten-fold evaluation uses nine subsets for training and one for testing, repeating the process so every subset serves once as test data.
  • Experimental setup: The experiments vary local-segment length from 8 to 256 and evaluate classification using a codebook size of 1000 with Chi-Squared distance.The tested segment-length range reflects the relatively flat structure of biomedical signals.
  • Parameter sensitivity: Classification performance remains relatively stable when local-segment length is between 64 and 192 across the evaluated datasets.

B. Codebook Size

The experiments examine codebook size, distance measures, and comparisons with alternative representations and classifiers. Performance stabilizes for sufficiently large codebooks, while Chi-Squared distance performs slightly better overall.

  • Codebook size: Classification results become very stable when the codebook contains more than 500 entries, while sizes below 100 reduce accuracy quickly.The authors identify an approximate optimal codebook-size range of 1000–3500.
  • Distance measurement: The Chi-Squared distance measure performs slightly better than the other tested measures for codebook sizes of 10, 100, 1000, and 2000.The comparison covers the EEG, ECG-40, and ECG-15 datasets.
  • Comparison with other methods: The comparison includes DWT, DFT, DTW-based nearest neighbor classification, and bag-of-patterns representations.Bag-of-patterns represents a time series as a histogram of local patterns and is closely related to the proposed approach.
  • Comparison with other methods: The proposed bag-of-words method achieves accuracies of 93.8% on EEG, 99.5% on ECG-40, and 100% on ECG-15.These are the best results reported for the proposed approach in Table II.
  • Comparison with other methods: Bag-of-patterns achieves comparable accuracy on ECG-40 and ECG-15 but performs significantly worse than bag-of-words on EEG.

E. Robustness to Noise

The noise experiment evaluates the bag-of-words representation under zero-mean white Gaussian noise with SNRs from 10 dB to 0 dB. Accuracy declines modestly, especially on ECG-15.

  • Noise setting: The datasets are corrupted with zero-mean white Gaussian noise whose signal-to-noise ratios range from 10 dB to 0 dB.Training and test partitions remain separated as in the preceding experiments.
  • Results: At 10 dB SNR, classification accuracies decrease by less than 2 percentage points across the evaluated datasets.
  • Results: At 0 dB SNR, accuracy decreases by less than 10 percentage points on EEG and ECG-40 and by less than 2 percentage points on ECG-15.
  • Conclusion: The reported results characterize the bag-of-words approach as relatively robust to noise.

V. DISCUSSION

The proposed bag-of-words representation captures local and global structure in biomedical time series, but its usefulness depends on sequence length and codebook selection. Experiments found it effective, parameter-insensitive, and robust to noise, while adaptive codebook sizing remains unresolved.

  • Short time series may be ineffective because sliding-window extraction cannot provide enough meaningful and discriminative local segments.
  • The codebook size is pre-defined and empirically determined; small codebooks limit discrimination, whereas large codebooks may introduce noise.
  • The representation captures both local and global structure by converting time-series segments into codeword histograms, despite ignoring temporal order.It treats the time series as a document and local segments as words.
  • Experiments on three datasets found the representation effective for EEG and ECG classification and robust to noise.
  • Its performance was insensitive to local-segment length and codebook size, and Chi-Squared distance was more suitable for histogram comparison than alternatives.
Loading 1212.2262v1…