Edit Distance with Real Penalty (ERP)¶

Introduction¶

Edit Distance with Real Penalty (ERP) is a distance metric designed for measuring similarity between numerical time series. It combines the robustness of edit distance with the ability to handle real-valued sequences. ERP addresses limitations of other metrics by using a constant reference value (gap) when computing the cost of element mismatches, making it particularly effective for sequences with different lengths and numerical values.

Mathematical Definition¶

For two time series X = (x₁, …, xₙ) and Y = (y₁, …, yₘ), and a constant gap value g, ERP is defined recursively as:

\[\begin{split}ERP(X, Y) = ERP(i, j) = \begin{cases} \sum_{k=1}^{i} |x_k - g| & \text{if } j = 0 \\ \sum_{k=1}^{j} |y_k - g| & \text{if } i = 0 \\ min\begin{cases} ERP(i-1, j-1) + |x_i - y_j| \\ ERP(i-1, j) + |x_i - g| \\ ERP(i, j-1) + |y_j - g| \end{cases} & \text{otherwise} \end{cases}\end{split}\]

where: - \(|x_i - y_j|\) is the distance between elements - \(|x_i - g|\) and \(|y_j - g|\) are the penalties for gaps - \(g\) is the gap value (typically 0 or the mean of the series)

Properties¶

ERP possesses several important properties:

Metric Properties: - Non-negativity - Symmetry - Triangle inequality - Identity of indiscernibles
Advantages: - Handles sequences of different lengths - Supports real-valued elements - Less sensitive to noise than Euclidean distance - More robust than DTW in some scenarios
Characteristics: - Parameter-dependent (gap value) - Translation-invariant when using appropriate gap value - Handles local time shifting

Academic References¶

Chen, L., & Ng, R. (2004). “On the marriage of Lp-norms and edit distance.” Proceedings of the 30th International Conference on Very Large Data Bases, 792-803.
Chen, L., Özsu, M. T., & Oria, V. (2005). “Robust and fast similarity search for moving object trajectories.” Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, 491-502.
Wang, X., Mueen, A., Ding, H., Trajcevski, G., Scheuermann, P., & Keogh, E. (2013). “Experimental comparison of representation methods and distance measures for time series data.” Data Mining and Knowledge Discovery, 26(2), 275-309.

Use Cases¶

ERP is particularly effective in:

Financial time series analysis
Trajectory matching
Sensor data comparison
Pattern recognition in noisy environments
Sequence alignment with numerical values
Time series classification

Implementation Details¶

In the distancia package, ERP is implemented with the following key parameters:

gap_value: The reference value for computing penalties
window: Optional constraint on the matching window size
normalize: Boolean flag for result normalization

Example Usage¶

from distancia import ERP

# Initialize ERP with gap value
erp = ERP(gap_value=0)

# Calculate distance between two time series
distance = erp.calculate(series1, series2)

Complexity Analysis¶

Time Complexity: O(nm)
Space Complexity: O(nm)

where n and m are the lengths of the input sequences.

Conclusion¶

Edit Distance with Real Penalty (ERP) represents a powerful metric for time series comparison that combines the benefits of edit distance with the ability to handle numerical values. Its metric properties and robustness make it particularly suitable for applications requiring accurate similarity measurement between sequences of different lengths or with noise. The gap parameter provides flexibility in adapting the metric to specific domain requirements, while maintaining the mathematical properties necessary for various data mining tasks.

Note

The choice of gap value can significantly impact the results. It’s recommended to experiment with different values (such as 0 or the mean of the series) to find the most appropriate for your specific use case.