81 lines
2.8 KiB
Markdown
81 lines
2.8 KiB
Markdown
# Dynamic Time Warping
|
||
|
||
ferro-ta ships three DTW entry points. Pick the one that matches your
|
||
workload — the distance-only path is measurably faster than the one that
|
||
reconstructs the warping path, and `BATCH_DTW` parallelises over rows.
|
||
|
||
## Quick reference
|
||
|
||
| Function | Returns | When to use |
|
||
|---|---|---|
|
||
| `DTW_DISTANCE(a, b, window=None)` | `float` | You only need the distance. Fastest. |
|
||
| `DTW(a, b, window=None)` | `(float, ndarray[N, 2])` | You need the alignment path for plotting or downstream analysis. |
|
||
| `BATCH_DTW(matrix, reference, window=None)` | `ndarray[N]` | You have N candidate series and one reference; uses rayon. |
|
||
|
||
## Distance convention
|
||
|
||
ferro-ta's DTW uses squared-Euclidean local cost accumulated along the
|
||
optimal path, with a single `sqrt()` applied at the end. This matches
|
||
`dtaidistance.dtw.distance()` to within floating-point tolerance (parity
|
||
tests assert numerical agreement, not bitwise identity). Example:
|
||
|
||
```python
|
||
>>> import ferro_ta as fta
|
||
>>> fta.DTW_DISTANCE([0.0, 1.0, 2.0], [1.0, 2.0, 3.0])
|
||
1.4142135623730951 # == sqrt(2), same as dtaidistance
|
||
```
|
||
|
||
If you are migrating from a library that uses absolute-difference local
|
||
cost without the final sqrt (e.g. `fastdtw`'s default), your numbers will
|
||
not line up. That is a choice ferro-ta made for parity with the
|
||
scientific-Python ecosystem.
|
||
|
||
## Window constraint (Sakoe-Chiba band)
|
||
|
||
Passing `window=w` constrains the DP to cells where `|i - j| < w`. This
|
||
turns the O(n·m) cost into O(n·w), which is typically a 5–20× speedup for
|
||
realistic `w`. A narrower band can only *increase* the distance, so
|
||
`window=` is safe to use whenever your series are roughly aligned.
|
||
|
||
```python
|
||
# Unconstrained
|
||
fta.DTW_DISTANCE(a, b)
|
||
|
||
# Constrained: warping may shift up to 5 positions
|
||
fta.DTW_DISTANCE(a, b, window=5)
|
||
```
|
||
|
||
## Batch usage
|
||
|
||
`BATCH_DTW` compares each row of a 2-D matrix against one reference
|
||
series, in parallel:
|
||
|
||
```python
|
||
import numpy as np
|
||
import ferro_ta as fta
|
||
|
||
reference = np.random.random(500)
|
||
candidates = np.random.random((1000, 500))
|
||
|
||
distances = fta.BATCH_DTW(candidates, reference, window=20)
|
||
nearest = int(np.argmin(distances))
|
||
```
|
||
|
||
Parallelism is via rayon; no thread-pool configuration is needed on the
|
||
Python side. For the sequence lengths ferro-ta targets (thousands of
|
||
bars, hundreds to low thousands of candidates), batch-parallel classic
|
||
DTW beats FastDTW-style approximations.
|
||
|
||
## Edge cases
|
||
|
||
- **Empty input:** raises `FerroTAInputError`.
|
||
- **NaN in input:** propagates to the output (matches IEEE 754). Call
|
||
`ferro_ta.core.exceptions.check_finite()` first if you want to fail
|
||
loudly instead.
|
||
- **Different-length series:** fully supported. The path array length
|
||
is bounded by `max(n, m) <= len(path) <= n + m - 1`.
|
||
|
||
## See also
|
||
|
||
- `tests/unit/indicators/test_statistic.py` — parity tests against `dtaidistance`.
|