Algorithm: Understand when two lines chart are similar

user_6110040 0
Viewed 107

I am trying to develop a script capable of understanding when two lines chart are similar (they have similar direction or similar values).

For instance suppose I have two arrays:

array1 = [0,1,2,3,4,5,6,7,8,9,10];

array2 = [2,3,4,5,6,7,8,8,10,11,12];

As you can see they both growth and their values are quite similar.

At the moment I have found a perfectly working solution using a DTW algorithm. The problem is that the DTW has a "training part" very fast (I just have to store a lot of lines chart) but it has a heavy prediction part because it compares the last line chart with all the others in memory.

So my question is: is it possible to move the computational complexity time during the training part in order to have a faster prediction? For example creating a search tree or something like that? And if it is possible accordingly to which specific value can I cluster the information?

Do you have any advice or useful links?

cluster-analysis binary-search-tree machine-learning artificial-intelligence algorithm
2 Answers

It is often possible by mapping the objects from your domain to a linear space. For example, you can see how that works for word embeddings in natural languages (word2vec tutorial, skip to "Visualizing the Learned Embeddings"). In this setting, similarity between objects is defined by a distance in the linear space, which is very fast to compute.

How complex should the mapping be in your case greatly depends on your data: how diverse are the charts and what kind of similarity you wish to capture.

In your example with two vectors, it's possible to compute a single value: the slope of the regression line. This will probably work is your charts are "somewhat linear" in nature. If you'd like to capture sinusoidal patterns as well, you can try to normalize the time series by subtracting the first value. Again, in your particular example it'll show a perfect fit.

Bottom line: complexity of the mapping is determined by the complexity of the data.

user_7129950

If they always have the same length, Pearson correlation should be much more appropriate, and much faster.

If you standardize your vectors, Pearson is Euclidean and you can use any multidimensional search tree for further acceleration.

user_10603500
Related