Learned Pattern Similarity (LPS)

This is a supporting page to our paper -  Time series similarity based on a pattern-based representation (LPS)

by Mustafa Gokce Baydogan and George Runger
* LPS is compared to 11 similarity measures on 75 time series classification problems. It is ranked first but it is not significantly outperforming the competitors. The detailed results are available below.
* this study is presented in INFORMS 2013@Minneapolis, IFORS 2014@Barcelona, FEAST Workshop at ICPR 2014@Stockholm.  The presentation (INFORMS 2013 one) is available here."
* the paper is submitted to IEEE Transactions on Pattern Analysis and Machine Intelligence on September 23rd, 2013 and rejected with one resubmit as new / one major revision / one reject decision on June 1st, 2014.
* During the review process, we came up with a more robust version of LPS that does not require tuning of any parameters. This version is submitted to Data Mining and Knowledge Discovery on September 28th, 2014.
 

Latest blog posts on Learned Pattern Similarity

DATASETS
LPS is compared to nearest neighbors (NN) classifiers discussed by Lines and Bagnall (2014) on 75 datasets from different sources. See Lines and Bagnall (2014) for details of the classifiers and the datasets. Eleven similarity measures are considered in our comprehensive evaluation: DTW and DDTW Dynamic time warping and derivative dynamic time warping that use the full warping window, DTWBest and DDTWBest DTW and DDTW with the window size setting determined through cross-validation, DTWWeight and DDTWWeigh Weighted version of DTW and DDTW, LCSS Longest common subsequence, MSM Move-Split- Merge, TWE Time warp edit distance, ERP Edit distance with real penalty, and ED Euclidean distance. LPS results (average over 10 replications) are also provided. For all datasets, LPS uses the same settings of the parameters. The number of trees is 200 and depth is 6. Error rates for each approach are provided below.
 
    DTW DDTW          
  LPS Full Best Weight Full Best Weight LCSS MSM TWE ERP ED
Adiac 0.232 0.396 0.389 0.394 0.414 0.33 0.327 0.749 0.373 0.366 0.391 0.389
ArrowHead 0.169 0.429 0.217 0.211 0.32 0.211 0.206 0.217 0.257 0.229 0.183 0.183
ARSim 0.075 0.404 0.417 0.407 0.101 0.103 0.101 0.27 0.311 0.491 0.433 0.489
Beef 0.313 0.367 0.333 0.3 0.333 0.3 0.3 0.233 0.533 0.4 0.333 0.333
BeetleFly 0.145 0.35 0.35 0.45 0.15 0.1 0.2 0.35 0.6 0.55 0.3 0.35
BirdChicken 0.005 0.35 0.35 0.4 0.35 0.3 0.3 0.25 0.35 0.55 0.4 0.4
Car 0.148 0.267 0.233 0.217 0.267 0.217 0.217 0.167 0.1 0.083 0.233 0.267
CBF 0 0.003 0.006 0.003 0.408 0.428 0.409 0.01 0.03 0.009 0.002 0.148
ChlorineConc 0.36 0.378 0.375 0.373 0.353 0.351 0.349 0.441 0.382 0.379 0.362 0.369
CinCECGtorso 0.211 0.378 0.071 0.068 0.375 0.071 0.088 0.068 0.081 0.237 0.118 0.102
Coffee 0.029 0 0 0 0.071 0.036 0.036 0 0.107 0 0 0
Computers 0.316 0.124 0.124 0.124 0.212 0.2 0.212 0.244 0.22 0.16 0.116 0.272
CricketX 0.278 0.236 0.246 0.236 0.462 0.438 0.415 0.249 0.241 0.241 0.244 0.421
CricketY 0.232 0.218 0.205 0.187 0.546 0.482 0.454 0.182 0.177 0.238 0.162 0.346
CricketZ 0.238 0.215 0.177 0.187 0.459 0.454 0.408 0.215 0.249 0.221 0.179 0.387
DiatomSize 0.049 0.036 0.075 0.036 0.291 0.092 0.118 0.101 0.046 0.049 0.075 0.075
DistPhalanxAge 0.31 0.245 0.201 0.223 0.216 0.237 0.237 0.194 0.209 0.209 0.252 0.252
DistPhalanxOut 0.272 0.239 0.254 0.246 0.246 0.228 0.21 0.268 0.246 0.279 0.236 0.239
DistPhalanxTW 0.379 0.324 0.324 0.324 0.345 0.317 0.345 0.381 0.338 0.309 0.331 0.317
Earthquakes 0.332 0.295 0.309 0.281 0.353 0.331 0.353 0.317 0.338 0.324 0.295 0.302
ECGFiveDays 0.186 0.243 0.2 0.245 0.307 0.282 0.304 0.233 0.23 0.221 0.197 0.2
ElectricDevices 0.269 0.329 0.295 0.303 0.333 0.3 0.303 0.562 0.287 0.358 0.305 0.456
FaceAll 0.231 0.192 0.192 0.206 0.127 0.118 0.103 0.199 0.191 0.214 0.207 0.286
FaceFour 0.057 0.17 0.102 0.125 0.375 0.261 0.284 0.034 0.057 0.148 0.136 0.216
FacesUCR 0.068 0.106 0.091 0.087 0.166 0.152 0.149 0.046 0.037 0.083 0.077 0.229
fiftywords 0.19 0.31 0.235 0.229 0.308 0.237 0.231 0.202 0.187 0.207 0.288 0.369
fish 0.058 0.166 0.166 0.154 0.103 0.08 0.04 0.131 0.063 0.069 0.126 0.217
FordA 0.118 0.276 0.206 0.213 0.203 0.183 0.181 0.212 0.228 0.252 0.205 0.314
FordB 0.279 0.341 0.33 0.32 0.295 0.284 0.281 0.275 0.277 0.302 0.314 0.404
GunPoint 0.001 0.093 0.087 0.02 0.007 0 0.007 0.027 0.027 0.047 0.053 0.087
Haptics 0.568 0.601 0.594 0.607 0.698 0.591 0.594 0.623 0.578 0.549 0.627 0.627
Herring 0.405 0.406 0.344 0.313 0.344 0.406 0.438 0.328 0.344 0.25 0.266 0.266
InlineSkate 0.511 0.629 0.615 0.598 0.738 0.725 0.785 0.587 0.576 0.576 0.589 0.676
ItalyPower 0.072 0.06 0.039 0.057 0.11 0.027 0.054 0.049 0.064 0.05 0.04 0.039
LargeKitchen 0.348 0.264 0.264 0.264 0.269 0.285 0.269 0.456 0.243 0.299 0.387 0.517
Lightning2 0.21 0.131 0.131 0.098 0.328 0.23 0.18 0.23 0.18 0.164 0.131 0.246
Lightning7 0.314 0.274 0.288 0.233 0.425 0.301 0.315 0.425 0.247 0.26 0.26 0.425
MALLAT 0.106 0.069 0.09 0.058 0.074 0.052 0.048 0.091 0.067 0.067 0.09 0.09
MedicalImages 0.282 0.27 0.261 0.274 0.349 0.341 0.336 0.341 0.261 0.299 0.324 0.311
MidPhalanxAge 0.532 0.539 0.539 0.565 0.506 0.461 0.481 0.435 0.506 0.539 0.506 0.526
MidPhalanxOut 0.222 0.247 0.199 0.223 0.223 0.206 0.216 0.227 0.254 0.289 0.22 0.254
MidPhalanxTW 0.432 0.649 0.682 0.688 0.643 0.636 0.662 0.649 0.649 0.636 0.656 0.695
MoteStrain 0.077 0.175 0.134 0.141 0.291 0.228 0.204 0.131 0.128 0.191 0.13 0.125
NonInvThorax1 0.203 0.274 0.196 0.205 0.599 0.404 0.399 0.215 0.193 0.188 0.185 0.196
NonInvThorax2 0.164 0.173 0.132 0.142 0.421 0.304 0.274 0.17 0.117 0.128 0.121 0.132
OliveOil 0.127 0.167 0.133 0.167 0.133 0.167 0.133 0.6 0.167 0.133 0.133 0.133
OSULeaf 0.237 0.409 0.401 0.376 0.12 0.128 0.112 0.211 0.227 0.223 0.397 0.483
Phalanges 0.22 0.26 0.228 0.237 0.244 0.196 0.198 0.219 0.248 0.281 0.242 0.246
Plane 0 0 0 0 0 0 0 0 0.01 0 0 0.038
ProxPhalanxAge 0.132 0.137 0.127 0.137 0.141 0.156 0.141 0.112 0.122 0.122 0.132 0.127
ProxPhalanxOut 0.171 0.213 0.196 0.189 0.182 0.162 0.165 0.175 0.192 0.223 0.22 0.206
ProxPhalanxTW 0.247 0.234 0.278 0.239 0.22 0.224 0.229 0.229 0.273 0.224 0.259 0.278
Refr.Devices 0.323 0.509 0.515 0.488 0.549 0.56 0.549 0.376 0.416 0.48 0.365 0.515
ScreenType 0.433 0.427 0.445 0.448 0.477 0.485 0.477 0.435 0.536 0.485 0.459 0.533
ShapeletSim 0.086 0.333 0.328 0.261 0.494 0.456 0.511 0.106 0.139 0.178 0.367 0.444
ShapesAll 0.184 0.278 0.247 0.252 0.185 0.182 0.173 0.203 0.19 0.337 0.247 0.272
SmallKitchen 0.221 0.299 0.256 0.293 0.296 0.296 0.299 0.456 0.232 0.293 0.272 0.645
SonyRobot1 0.24 0.276 0.301 0.266 0.258 0.309 0.268 0.319 0.26 0.319 0.301 0.301
SonyRobot2 0.14 0.171 0.143 0.14 0.149 0.15 0.149 0.183 0.126 0.139 0.179 0.143
StarLightCurves 0.038 0.096 0.097 0.096 0.098 0.091 0.086 0.126 0.114 0.119 0.15 0.147
SwedishLeaf 0.072 0.208 0.154 0.126 0.115 0.096 0.107 0.112 0.104 0.109 0.138 0.211
Symbols 0.038 0.055 0.069 0.055 0.114 0.087 0.085 0.05 0.033 0.03 0.08 0.108
SyntheticControl 0.023 0.007 0.017 0.007 0.433 0.433 0.433 0.047 0.027 0.013 0.027 0.12
ToeSegmentation1 0.094 0.105 0.101 0.105 0.136 0.154 0.136 0.167 0.132 0.132 0.11 0.325
ToeSegmentation2 0.109 0.077 0.108 0.077 0.246 0.154 0.162 0.046 0.115 0.138 0.108 0.377
Trace 0.023 0 0.01 0 0 0.01 0 0.03 0.07 0.01 0.05 0.24
TwoLeadECG 0.055 0.134 0.149 0.134 0.084 0.086 0.084 0.203 0.06 0.04 0.102 0.26
TwoPatterns 0.008 0 0.002 0 0.003 0.003 0.003 0.001 0.001 0.002 0 0.093
UwaveX 0.177 0.278 0.226 0.226 0.357 0.27 0.269 0.229 0.232 0.229 0.228 0.265
UwaveY 0.243 0.376 0.302 0.303 0.463 0.377 0.368 0.332 0.302 0.314 0.319 0.336
UwaveZ 0.236 0.357 0.327 0.335 0.472 0.375 0.377 0.317 0.301 0.312 0.336 0.351
UwaveAll 0.033 0.107 0.035 0.034 0.15 0.066 0.063 0.038 0.036 0.061 0.044 0.052
wafer 0.004 0.02 0.004 0.003 0.022 0.003 0.003 0.01 0.003 0.004 0.004 0.005
WordSynonyms 0.253 0.367 0.26 0.276 0.417 0.315 0.303 0.26 0.229 0.254 0.321 0.382
yoga 0.128 0.164 0.157 0.147 0.18 0.171 0.16 0.14 0.135 0.132 0.153 0.17

Table above summarizes the average error rates from 10 replications of our algorithm on the test data. Comparison of LPS to multiple classifiers over all datasets is done using a procedure suggested by Demˇsar (2006). The testing procedure employs a Friedman test (Friedman, 1940) followed by the Nemenyi test (Nemenyi, 1963) if a significant difference is identified by Friedman’s test. It is basically a non-parametric form of Analysis of Variance based on the ranks of the approaches on each dataset (Lines and Bagnall, 2014). Based on the Friedman test, we find that there is a significant difference between the 12 classifiers at the 0.05 level. Proceeding with the Nemenyi test, we compute the critical difference (CD) at 0.05 level to identify if the performance of two classifiers is different. This test concludes that two classifiers have a significant difference in their performances if the their average ranks differ by at least the critical difference. Figure below shows the average ranks for all classifiers on 75 datasets. The critical difference at significance level 0.05 is 1.924. There is no statistically significant difference between the performances of LPS.

CODES

We implemented LPS as an R package. The source files are available at CRAN.

Recently, we also made a MATLAB implementation of LPS available. The source file is provided here in the files section. This version is a slightly different version than the one implemented with R but the overall idea is the same. 

HOW TO RUN LPS

The details of R implementation are described in the blog entry here.
The details of MATLAB implementation are provided in the blog entry here.

REFERENCES

J. Demˇsar. Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res., 7:1–30, 2006.
P. Nemenyi. Distribution-free Multiple Comparisons. Princeton University, 1963
J. Lines and A. Bagnall. Time series classification with ensembles of elastic distance measures. Data Mining and Knowledge Discovery, pages 1–28, 2014
 

Copyright © 2014 mustafa gokce baydogan

LinkedIn
Twitter
last.fm