0
$\begingroup$

I'm trying to cluster together different short audio files based on the zero-crossing rate (an integer) and the energy, spectral centroid, and spectral bandwidth (time-variant values). I've decided to use these time series as features rather than just taking an average and using that as a feature because one of the goals is, for example, to cluster together the audio files which rise in pitch over time but decay in energy. I'm assuming that K-means clustering might not be the best algorithm here given that it's meant for low-dimensional spaces, and I'll at least need to do some specific preprocessing first (maybe not just because it's a time series but because it's audio). What should I look into using here for what I'm trying to do? Should I look into different features?

Cheers and thanks for any help!

$\endgroup$
2
  • 1
    $\begingroup$ How short/long are the files? What kind of audio in there, and what kind of patterns do you want your clustering to find? $\endgroup$
    – Jon Nordby
    Dec 26 '20 at 21:33
  • $\begingroup$ @jonnor they're drum samples, like a kick or a snare, so usually about 0.5s or less. I'm looking for interesting timbre patterns or anything that can further categorize these files $\endgroup$
    – Jodast
    Dec 27 '20 at 0:57
1
$\begingroup$

TL;DR: For clustering time-series data, as a baseline, you can try using Dynamic Time Warping (DTW) as a distance metric for your favorite clustering algorithm, say $k$-means.

DTW is commonly used in applications like ASR (automatic speech recognition), and other sequence alignment problems. I believe the Python package tslearn implements DTW, though I have not used it myself.

What is DTW?

At a very high level, DTW is a measure of how "aligned" two time-series are, so it can capture features like "rise in pitch over time + decay in energy;" i.e. two sequences are "close" if you can stretch/compress a source sequence in the time dimension into the target sequence. To compute this, let's define $x, y$ as sequences of length $n, m$ respectively, and $\pi = [\pi_1, \pi_2, \dots \pi_N]$, where $\pi_k = (i_k, j_k)$, a tuple of indices into $x, y$ respectively. Intuitively, $\pi$ defines a "path" through sequences $x, y$ by pairing up indices. Then you minimize the following objective:

$$ \underset{\pi}{\min} \sqrt{\sum_{(i, j) \in \pi} d(x_i, y_j)^2} \quad\text{subject to}$$ $$ i_{k-1} \leq i_k \leq i_{k-1} + 1,\;\; j_{k-1} \leq j_k \leq j_{k-1} + 1 \quad\text{for}\quad (i_k, j_k) \in \pi, 0 < k \leq N;\\ i_0 = 0, j_0 = 0;\\ i_K = n, j_K = m.$$

where $d$ is some distance metric (say $\ell_1, \ell_2$). The final two constraints are just boundary conditions that specify that the path $\pi$ must align with the beginnings and ends of $x, y$ simultaneously; the top constraint specifies that indices $i_k, j_k$ must be monotonically non-decreasing in $k$.

This schematic from Wikipedia illustrates this quite succinctly:

Alignment of two sequences via DTW.

We can imagine each location where a dashed line originates/terminates as an element of a discrete time-series; these correspond to the various $i_k, j_k$ defined in $\pi$.

What about the curse of dimensionality?

Your intuition that $k$-means runs into the curse of dimensionality is generally correct in practice, and often becomes a problem when you're using Euclidean distance (see this previous answer for more details), but the curse of dimensionality is more nuanced than "more dimensions = bad;" it is important to realize that the curse of dimensionality affects different metrics in different ways. Very informally, DTW is a metric that is less "susceptible" to the same dimensionality problems with squared Euclidean distance, as it better preserves its "meaning" in high dimensional spaces.

More concretely, using nearest-neighbors search as an illustrative example, under reasonable assumptions about your data-generating distribution, data points tend to become uniformly distant from one another in Euclidean distance as your dimensionality (or in the context of time-series, sequence length) increases; i.e., most points are "almost-nearest" neighbors. DTW does not suffer as severely from this problem as sequence length increases. A more mathematical way to gauge the severity of the curse of dimensionality is shown in Section 3.4 of this paper.

$\endgroup$
3
  • $\begingroup$ How would I go from there? I looked into DTW and tslearn but I can't figure out how to combine it with single-element features $\endgroup$
    – Jodast
    Dec 27 '20 at 1:37
  • 1
    $\begingroup$ That's a good question -- DTW is intended for sequential features, so it doesn't take of combining with single-element features out of the box. Since you have a few time-series features and one scalar feature, a naive solution might be to use DTW for the sequential features and a scalar metric for the scalar features; then, you could add/average the aggregate cost, which should give you a notion of pairwise distance. Essentially, this clusters sets of features independently. I don't know if this is rigorous/optimal -- this is my first instinct, as I'm not too familiar with this area. $\endgroup$
    – tchainzzz
    Dec 27 '20 at 1:58
  • $\begingroup$ i'll try this out! it seems like there might be a better solution that i'll try to look for, but i appreciate this in-depth answer! $\endgroup$
    – Jodast
    Dec 27 '20 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.