Sequential Pattern Mining on Multimedia Data

Corentin Hardy, Laurent Amsaleg, Guillaume Gravier, Simon Malinowski, René QuiniouAALTD@PKDD/ECML 2015 · OpenReview

Abstract

This research explores the challenge of discovering recurring motifs—such as jingles, advertisements, or specific keywords—within massive, high-dimensional audio streams. The authors propose a pipeline that converts complex audio signals into simplified symbolic sequences, enabling the use of efficient sequential pattern mining algorithms. By incorporating "wildcards" to account for temporal variations, the system achieves high precision and significant scalability, processing hours of audio in minutes.

Introduction

Extracting meaningful knowledge from multimedia data is often compared to finding a needle in a haystack. In audio analysis, identifying recurring structures (motifs) is essential for automatic segmentation and indexing. However, audio data presents significant hurdles due to its high dimensionality and inherent variability; the same word spoken by different individuals or recorded in different environments will never produce identical raw signals. While techniques like Dynamic Time Warping (DTW) offer accuracy, they are computationally prohibitive for large-scale databases. This paper addresses the need for a faster, symbolic approach capable of handling "temporal jitter" and spectral distortions.

Methodology

The proposed framework transitions from raw audio to searchable symbolic patterns through a multi-step process:

Feature Extraction and Symbolization

Initially, audio is converted into Mel-frequency cepstral coefficients (MFCCs), resulting in a 13-dimensional time series. To simplify this data, the time series is divided into windows. Using k-means clustering, a "codebook" is established where each window is replaced by a symbol representing its closest cluster center.

The symbolization pipeline: MFCC features are windowed and mapped to a discrete codebook via k-means clustering to create a symbolic sequence.

Sub-banding

To improve precision, the authors experiment with sub-banding, dividing the 13 MFCC dimensions into separate groups. This creates "itemsets"—multiple symbols occurring at the same time step—which capture more acoustic nuance than a single global symbol.

The sub-banding approach: multiple codebooks are used in parallel to generate itemset sequences, allowing for more detailed pattern representation.

Sequential Pattern Mining

The symbolic sequences are processed using two primary algorithms:

  • MaxMotif: Designed to find frequent closed patterns in single sequences.
  • CMP-Miner: Capable of handling the complex itemset sequences generated by sub-banding.

A critical feature of both algorithms is the support for "wildcards" or gaps. By defining a maxGap parameter, the system can identify a pattern even if certain symbols are missing or altered, effectively managing the variations in human speech speed.

Experimental Setup

The framework was evaluated using two datasets:

  1. Synthetic Dataset: 30 audio clips containing 10 utterances each of three French words ("affaires," "mondiale," and "cinquante"). This controlled environment allowed for testing the impact of codebook size on accuracy.
  2. Real-world Dataset: Approximately 7 hours of audio from 21 radio tracks, including music, speech, and environmental noise, to test scalability and robustness.

Results and Discussion

The study revealed that symbolization is the primary bottleneck. A codebook that is too small produces generic symbols, while one that is too large becomes overly sensitive to noise. In synthetic tests, precision improved with codebook size, reaching near 1.0 with a size of 20 for the MaxMotif algorithm, although recall remained relatively low (around 0.4).

The system demonstrated impressive scalability, extracting over one million patterns from the 7-hour radio dataset in less than four minutes. This highlights the speed advantage of symbolic mining over traditional signal processing methods. However, the process is "lossy," meaning that while the system is highly precise, it may miss several valid instances of a motif.

Conclusion and Future Work

This preliminary work establishes a viable path for rapid motif discovery in multimedia. The main limitation is low recall due to the rigid nature of k-means symbolization. Future research will focus on "soft matching"—incorporating acoustic distances between symbols—and refining dimension weighting and sub-banding techniques to improve the robustness of the symbolic representation.

Summary updated

BibTeX
@inproceedings{hardy2015sequential,
  author = {Corentin Hardy and Laurent Amsaleg and Guillaume Gravier and Simon Malinowski and René Quiniou},
  title = {{Sequential Pattern Mining on Multimedia Data}},
  booktitle = {AALTD@PKDD/ECML},
  year = {2015},
  url = {https://openreview.net/forum?id=NrfXYzLExEz},
}
Figure