-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathREADME.Rmd
107 lines (81 loc) · 4.48 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
---
output:
md_document:
variant: markdown_github
---
# rucrdtw - R Bindings for the UCR Suite
```{r echo=FALSE}
knitr::opts_chunk$set(
comment = "#>",
collapse = TRUE,
warning = FALSE,
message = FALSE,
fig.path="inst/img/"
)
```
<!-- badges: start -->
[](https://github.com/pboesu/rucrdtw/actions)
[](https://app.codecov.io/gh/pboesu/rucrdtw)
[](https://cran.r-project.org/package=rucrdtw)
[](http://doi.org/10.21105/joss.00100)
[](http://doi.org/10.21105/joss.00100)
<!-- badges: end -->
R bindings for functions from the [UCR Suite](http://www.cs.ucr.edu/~eamonn/UCRsuite.html) (Thanawin Rakthanmanon et al. 2012 SIGKDD), which enables ultrafast subsequence search under both Dynamic Time Warping and Euclidean Distance. UCR DTW is several orders of magnitudes faster than naive DTW searches.
```{r dtw-comparison, echo=FALSE, fig.width=7}
library("rucrdtw")
set.seed(123)
rwalk <- cumsum(runif(5e3, min = -0.5, max = 0.5))
qstart <- 876
query <- rwalk[qstart:(qstart+99)]
library(dtw)
#we create a small function that executes a sliding window search
naive_dtw <- function(data, query){
n_comps <- (length(data)-length(query)+1)
dtw_dist <- numeric(n_comps)
for (i in 1:n_comps){
dtw_dist[i] <- dtw(query, data[i:(i+length(query)-1)], distance.only = TRUE, window.type="sakoechiba", window.size=5)$distance
}
which.min(dtw_dist)
}
benchmarks <- rbenchmark::benchmark(
naive_1000 = naive_dtw(rwalk[1:1000], query),
naive_2000 = naive_dtw(rwalk[1:2000], query),
naive_5000 = naive_dtw(rwalk, query),
ucrdtw_1000 = ucrdtw_vv(rwalk[1:1000], query, 0.05),
ucrdtw_2000 = ucrdtw_vv(rwalk[1:2000], query, 0.05),
ucrdtw_5000 = ucrdtw_vv(rwalk, query, 0.05),
replications = 20)
#ensure benchmark test column is of type factor for compatibility with r-devel
benchmarks$test <- as.factor(benchmarks$test)
colors <- rep(c("#33a02c","#1f78b4"), each=3)
#plot with log1p transformed axes, as some execution times may be numerically zero
plot(log1p(benchmarks$elapsed*50) ~ benchmarks$test, cex.axis=0.7, las = 2, yaxt = "n", xlab = "", ylab = "execution time [ms]", ylim = c(0,10), medcol = colors, staplecol=colors, boxcol=colors)
axis(2, at = log1p(c(1,10,100,1000,10000)), labels = c(1,10,100,1000,10000), cex.axis = 0.7)
legend("topright", legend = c("naive DTW", "UCR DTW"), fill = c("#33a02c","#1f78b4"), bty="n")
```
## Installation
Install `rucrdtw` from GitHub:
```{r eval=FALSE}
install.packages("devtools")
devtools::install_github("pboesu/rucrdtw")
```
## Examples
Examples are contained in the vignette `rucrdtw`:
```{r}
library("rucrdtw")
vignette("using_rucrdtw")
```
## Citation
To cite rucrdtw in publications, please use:
Boersch-Supan (2016). rucrdtw: Fast time series subsequence search in R. The Journal of Open Source Software
http://doi.org/10.21105/joss.00100
Rakthanmanon et al. (2012). Searching and mining trillions of time series subsequences under dynamic time warping.
SIGKDD http://doi.org/10.1145/2339530.2339576
## Bug reports and contributions
Please file a github issue at https://github.com/pboesu/rucrdtw/issues if you find any problems or have feature suggestions. Contributions (via pull requests or otherwise) are welcome. Read more about how to contribute and the code of conduct for contributions [here](https://github.com/pboesu/rucrdtw/blob/master/CONTRIBUTING.md). If you don't like github you can contact the package maintainer at [email protected].
## License
COPYRIGHT 2012: Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista and Eamonn Keogh. (UCR Suite source code)
COPYRIGHT 2016: Philipp Boersch-Supan (R bindings)
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.