<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/time-series-with-matrix-profile/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://r-posts.com/time-series-with-matrix-profile/"> R-posts.com</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Recently I began to look further into Time Series(TS). During the course of my Master’s degree, I used the <a rel="nofollow" href="https://cran.r-project.org/package=forecast" target="_blank">forecast</a> package quite a bit (Thanks to Prof. Hyndman), and TS got my attention. So, after reading lots of publications about everything you can imagine about TS, I came across one publication from Prof. Eamonn, of the University of California, that made me contact him to ask a few questions. After receiving a considerable amount of information from him, one particular subject caught my attention: Matrix Profile. I was so much impressed that I started to write the <a rel="nofollow" href="https://franzbischoff.github.io/tsmp/" target="_blank">TSMP R Package</a>.</p>
<p>Enough talking, so what is a Matrix Profile? Why should you care about it?</p>
<h2>Matrix Profile</h2>
<p>If you are here, you are likely aware of what a Distance Matrix (DM) is. If not, think about those tables that used to be on maps with the distance between cities. It is widely used in TS for clustering, classification, motif search, etc. However, even for modestly sized datasets, the algorithms can take months to compute it and even with speed-up techniques (i.e., indexing, lower-bounding, early abandoning) they can be, at best, one or two orders of magnitude faster.</p>
<p>Matrix Profile it’s like a DM but faster (much faster) to compute. <em>Figure 1</em> shows a DM and a Matrix Profile. As you can see, in the Matrix Profile, as the name suggests, you see the Profile of a DM. It stores the minimum Euclidean distance of every subset of one TS (think of a Sliding Window) with another (or itself, called Self-Join). It also stores a companion vector called Profile Index, that gives us the index of each nearest neighbor.</p>
<figure class="wp-caption"><img data-orig-file="https://i2.wp.com/r-posts.com/wp-content/uploads/2018/09/mp.png?fit=355%2C355&amp;ssl=1" data-orig-size="355,355" data-medium-file="https://i2.wp.com/r-posts.com/wp-content/uploads/2018/09/mp.png?fit=300%2C300&amp;ssl=1" data-attachment-id="659" data-image-meta="{" data-image-description="" src="https://i2.wp.com/r-posts.com/wp-content/uploads/2018/09/mp.png?resize=300%2C300" data-permalink="https://r-posts.com/time-series-with-matrix-profile/mp/" data-large-file="https://i2.wp.com/r-posts.com/wp-content/uploads/2018/09/mp.png?fit=355%2C355&amp;ssl=1" alt="Distance Matrix" data-image-title="Distance Matrix" sizes="(max-width: 300px) 100vw, 300px" width="300" data-comments-opened="1" class="wp-image-659" data-recalc-dims="1" height="300"><figcaption class="wp-caption-text">Figure 1: Distance Matrix and its Matrix Profile</figcaption></figure>
<p>And is this good?</p>
<h2>Why should you care?</h2>
<p>DM usually stores redundant information, useless for most TS applications. The Matrix Profile has a host of interesting and exploitable properties. For example, the highest point on the Matrix Profile corresponds to the TS discord, the (tied) lowest points correspond to the locations of the best TS motif pair, and the variance can be seen as a measure of the TS complexity. Moreover, the histogram of the values in the Matrix Profile is the exact answer to the TS density estimation. Particularly, it has implications for TS motif discovery, TS joins, shapelet discovery (classification), density estimation, semantic segmentation, visualization, rule discovery, clustering, etc.<a rel="nofollow" href="https://r-posts.com/time-series-with-matrix-profile/#fn1" target="_blank"><sup>1</sup></a></p>
<p>This method has the following advantages/features:</p>
<ul>
<li>It is <strong>exact</strong>, providing no false positives or false dismissals.</li>
<li>It is <strong>simple</strong> and parameter-free. In contrast, the more general metric space APSS<a rel="nofollow" href="https://r-posts.com/time-series-with-matrix-profile/#fn2" target="_blank"><sup>2</sup></a> algorithms require building and tuning spatial access methods and/or hash functions.</li>
<li>It requires an inconsequential space overhead, just O(<em>n</em>) with a small constant factor.</li>
<li>It is extremely <strong>scalable</strong>, and for <em>massive</em> datasets, we can compute the results in an anytime fashion, allowing ultra-fast <em>approximate</em> solutions.</li>
<li>Having computed the similarity join for a dataset, we can incrementally update it very efficiently. In many domains, this means we can effectively maintain exact joins on <strong>streaming data</strong> forever.</li>
<li>It provides <em>full joins</em>, eliminating the need to specify a similarity <em>threshold</em>, which is a near-impossible task in this domain.</li>
<li>It is embarrassingly <strong>parallelizable</strong>, both on multicore processors and in distributed systems.</li>
</ul>
<h3>Performance on an Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz using a random walk dataset</h3>
<pre>set.seed(2018)
data &lt;- cumsum(sample(c(-1, 1), 40000, TRUE))</pre>
<p></p>
<table>
<thead>
<tr>
<th></th>
<th align="center">Elapsed Time<a rel="nofollow" href="https://r-posts.com/time-series-with-matrix-profile/#fn3" target="_blank"><sup>3</sup></a></th>
<th align="center">Data size</th>
<th align="center">Window size</th>
<th align="center">Threads</th>
</tr>
</thead>
<tbody>
<tr>
<td>scrimp()</td>
<td align="center">45.30s</td>
<td align="center">40000</td>
<td align="center">1000</td>
<td align="center">1</td>
</tr>
<tr>
<td>stomp_par()</td>
<td align="center">52.72s</td>
<td align="center">40000</td>
<td align="center">1000</td>
<td align="center">8</td>
</tr>
<tr>
<td>stomp()</td>
<td align="center">136.01s</td>
<td align="center">40000</td>
<td align="center">1000</td>
<td align="center">1</td>
</tr>
<tr>
<td>stamp_par()</td>
<td align="center">140.25s</td>
<td align="center">40000</td>
<td align="center">1000</td>
<td align="center">8</td>
</tr>
<tr>
<td>stamp()</td>
<td align="center">262.03s</td>
<td align="center">40000</td>
<td align="center">1000</td>
<td align="center">1</td>
</tr>
</tbody>
</table>
<h2>Further readings</h2>
<p>All information you need to get started with Matrix Profiles is available at the <a rel="nofollow" href="http://www.cs.ucr.edu/~eamonn/MatrixProfile.html" target="_blank">UCR Matrix Profile</a> webpage. Papers, Slides, examples, are available there.</p>
<p>Once become more familiar with this concept, you can start reading the <a rel="nofollow" href="https://franzbischoff.github.io/tsmp/" target="_blank">TSMP R Package</a> documentation.</p>
<hr>
<ol>
<li>For pure <a rel="nofollow" href="https://en.wikipedia.org/wiki/Similarity_search" target="_blank">similarity search</a>, it is suggested you see <a rel="nofollow" href="http://www.cs.unm.edu/~mueen/FastestSimilaritySearch.html" target="_blank">MASS</a> for Euclidean Distance and the <a rel="nofollow" href="http://www.cs.ucr.edu/~eamonn/UCRsuite.html" target="_blank">UCR Suite</a> for DTW.</li>
<li>All Pairs Similarity Search.</li>
<li>These are results using only R code, no low-level C code optimizations.</li>
</ol>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://r-posts.com/time-series-with-matrix-profile/"> R-posts.com</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/st_A84oSULk" height="1"></a></div>