TL;DR
This paper introduces DUST, a novel distance measure for uncertain time series that generalizes existing similarity notions and handles multiple, arbitrary error distributions. DUST significantly improves classification accuracy and robustness to noise compared to traditional methods like Euclidean distance and Dynamic Time Warping, making it more suitable for real-world sensor data.
What Problem Does This Paper Address?
In many real-world applications, data is inherently uncertain due to imperfect sensors or intentional privacy-preserving transformations. Traditional distance measures like Euclidean distance and Dynamic Time Warping (DTW) struggle with this uncertainty, often yielding counter-intuitive results. While some methods have been proposed to account for uncertainty, they are often limited to specific error distributions (e.g., Normal) and don't easily accommodate the complex scenarios where different parts of a time series might have different sources or types of uncertainty. This paper tackles the challenge of developing a unified and flexible similarity measure for uncertain time series that can handle diverse error profiles and provide more intuitive distance calculations.
Methods
The core contribution is the DUST (Distance Unifying Similarity for Time Series) measure. DUST is built upon a theoretical framework that generalizes similarity by considering the probability of two uncertain values being equal.
- Probabilistic Foundation: DUST leverages the idea that if two uncertain values have a high probability of being equal, their distance should be small. This is formalized by considering the probability density function (pdf) of the error.
- Generalized Distance Function (
dust): For individual uncertain valuesxandy, DUST defines adustdistance that depends on the difference|x - y|and a functionφ(∆x) = p(dist(0, ∆x) = 0), which captures the probability of equality given the difference and error distribution. This function is derived using Bayes' theorem and considers the underlying data distribution and the error pdf. - DUST for Time Series: The overall DUST distance between two time series is computed as the square root of the sum of squared
dustdistances between corresponding elements. This approach allows for the combination of multiple, potentially different, error distributions across the time series. - Handling Multiple Distributions: A key innovation is the ability to combine different error distributions. The paper proposes a method to adjust error functions so that for larger separations, they converge to a common behavior, ensuring that DUST behaves intuitively even with diverse error sources.
- Efficient Computation: DUST is made computationally feasible through the use of pre-computed lookup tables (piecewise linear representations) for different error functions, allowing for efficient on-line distance calculations.
Datasets
The paper evaluates DUST on the UCR time series classification datasets [12]. These datasets are standard benchmarks for time series classification tasks. The authors also mention using datasets from previous work for motif detection (insect and EEG datasets) and for nearest-neighbor search (Wafer and Two_Patterns datasets).
Key Insights and Ideas
- Intuition over Raw Probability: Traditional probabilistic approaches to uncertain time series similarity can be complex and don't always yield intuitive distance values. DUST aims to bridge this gap by providing a measure that aligns better with human intuition about similarity.
- The Power of Multiple Error Distributions: Real-world sensor data rarely has a single, uniform error distribution. DUST's ability to handle arbitrary combinations of error distributions is crucial for its practical applicability.
- DUST's Resilience to Noise: The paper demonstrates that DUST is significantly more robust to noise and uncertainty than Euclidean distance and DTW, maintaining higher accuracy in classification and detection tasks.
- Breaking Triangle Inequality for Small Distances: To achieve intuitive results, DUST intentionally breaks the triangle inequality for small distances. This allows it to correctly identify that two time series with slightly different errors might be more similar than two with a larger, but still statistically possible, difference.
Key Results
- Classification Accuracy: DUST consistently outperforms Euclidean distance and DTW, achieving an average increase in classification accuracy of about 10% across the UCR datasets. In some cases, DUST almost completely recovers the accuracy lost due to introduced noise.
- Robustness to Error: Figures 7 and 8 show that while Euclidean distance and DTW accuracy drop significantly with increasing error, DUST maintains a much higher level of accuracy. For example, on average, DUST achieves 72% accuracy with noise compared to 62% for Euclidean distance.
- Motif Detection: DUST shows better resilience for motif detection, maintaining a higher accuracy for larger standard deviations of error compared to Euclidean distance.
- Nearest-Neighbor Search: DUST demonstrates superior performance in nearest-neighbor search, especially when dealing with a significant percentage of erroneous sensors. It shows considerably more resilience to errors than Euclidean distance.
Limitations and Future Work
- Triangle Inequality Violation: The paper acknowledges that DUST, by design, violates the triangle inequality for small distances. While this is crucial for intuitive similarity, it might affect certain algorithms that rely on this property.
- Future Work on Error Handling: The authors mention that the sharp dip in accuracy observed in nearest-neighbor search between 20% and 30% erroneous sensors warrants further investigation.
- Generalization to Other Distance Measures: The paper focuses on Euclidean distance and DTW. Future work could explore how DUST can be integrated with other distance measures.
- Computational Complexity for Very Large Datasets: While DUST is efficient due to lookup tables, the overhead of constructing these tables for a vast number of unique error distributions could be a consideration for extremely large and diverse datasets.
Summary updated