sequences with the same order in an array - Identify sequences

Question

I'm looking for a hint towards a solution of the problem: Suppose there's an array with some numbers in ascending order and some in descending, for example [1,2,5,9,6,3,2,4,7,8] has sequences asc [1,2,5,9], desc [(9),6,3,2], asc [(2),4,7,8].

Now this isn't a problem, I could simply loop through an array and add them to some data structure, and when the direction changes - I store this structure somwhere and start filling next one.

What I've found tricky is if I want to have threshold of some sort. For example: [0,50,100,99,98,97,105,160] So the sequence in descending order [(100), 99, 98, 97] could be neglected, because overall change is -3, whereas the sequence was increasing much more dramatically (+100) and as a result, the algorithm identifies only one sequence in ascending order.

I have tried the same method as above, simply adding all sequences in a data structure and then comparing the change in values of two consequtive items: (100 vs -3 means -3 can be neglected). But then the problem is if I have say this situation:

(example only in change of values from start to end of sequense)

[+100, -3, +1, -50] in this situation I cannot neglect descending movement, because the numbers start to descend, then slightly ascend and again go down pretty significantly.

and it gets really confusing with stuff like that: [+100, -3, +3, -3, +3, -50]

this is quick sketch of representation of what I am trying to achieve: black lines represent initial data in an array, red thin lines are desired resulting output

Could somebody point me out in right direction? How would I approach this situation? Compare multiple sequences at a time slowly combining sequences together? Maybe I would need to go through sequences multiple times? I'm not sure If I've come across problem like that and don't know working algorithm. This is a problem I've faced myself trying to analyse some data.

Answer 1

I don't know if I understand your problem correctly, but I had to do this kind of dimensionality reduction many times before, so I wrote a small javascript library to do so. It uses the Perceptually Important Points algorithm.

In the algorithm you can define a custom metric of the distance between three consecutive points (to measure how much a single point adds in entropy).

Here is a demonstration (in JS). It works kind like a heap, where you remove points that do not contribute so much to the overall entropy:

for(var i=0; i<data.length; i++)
    heap.add(data[i]); 
    while(heap.minValue() < threshold)
        heap.removeMin();

And here is the library.

Answer 2

If I understand correctly, you expect your curve to be a succession of alternatively increasing and decreasing sequences, with a bit of added noise.

The usual way to get rid of noise is to filter data. There are millions of ways to do that, most of them requiring frequency analysis, but in your case you could probably get good enough results with something simple.

The main point is that the relevant variable is not the values in the array, but their variations.

Given N values, consider the array of N-1 elements holding the differences between two consecutive values.

[0,50,100,99,98,97,105,160] -> 50,100,-1,-1,-1,6,45

Now eliminate all values whose absolute value is below a given threshold (say 10 for instance)

-> 50,100,0,0,0,0,45

you can then detect a rising sequence by looking at streaks of all positive or null values (and the same for decreasing sequences, considering zero or negative values).

As for all filtering processes, you will have to find a sweet spot for your threshold. Too low and it will fail to eliminate insignificant variations, too high and it will wipe out significant slope inversions.