CODEWITHSUNDEEP
pythonalgorithmgraphtime-seriessequence
Edwin Goh
Edwin Goh

Reputation: 41

How do I identify cycles in time series data with overlapping periods?

Given time series data with 4 task categories (A, B, C, D) and their corresponding time stamps, my task is to identify intervals/cycles of [(A,B,C,D)_1, (A,B,C,D)_2, ...]

This would be straightforward (e.g., hash map or linked list) with clean, non-overlapping events, but my data contains sequences (sorted by time) such as [A, B, A, B, C, D, C, D]. Here's an example:

EVENT TIME
Task A 11/1/16 3:57
Task B 11/1/16 4:19
Task A 11/1/16 7:43
Task B 11/1/16 7:43
Task C 11/1/16 7:51
Task D 11/1/16 7:51
Task C 11/1/16 8:11
Task D 11/1/16 8:13
Task A 11/3/16 3:49
Task B 11/3/16 4:11
Task B 11/3/16 7:34
Task A 11/3/16 7:34
Task C 11/3/16 7:43
Task D 11/3/16 7:43
Task C 11/3/16 8:03
Task D 11/3/16 8:05
Task A 11/5/16 3:41
Task B 11/5/16 4:03
Task A 11/5/16 7:26
Task B 11/5/16 7:26
Task D 11/5/16 7:35
Task C 11/5/16 7:35
Task C 11/5/16 7:54
Task D 11/5/16 7:56

In this situation, the correct answer would be to remove the "inner"/overlapping ABCDs once a Task A (beginning of a cycle) has already begun. This results in 3 periods:

Task A Task B Task C Task D
11/1/16 3:57 11/1/16 4:19 11/1/16 8:11 11/1/16 8:13
11/3/16 3:49 11/3/16 4:11 11/3/16 8:03 11/3/16 8:05
11/5/16 3:41 11/5/16 4:03 11/5/16 7:54 11/5/16 7:56

Ignoring (for now) edge cases such as incomplete event sequences, is there an efficient algorithm to identify cycles while merging the inner periods that overlap?

Upvotes: 0

Views: 260

Answers (2)

Ajax1234
Ajax1234

Reputation: 71461

You can use collections.defaultdict:

import collections, datetime, re
r, d = [], collections.defaultdict(list)
data = [['Task A', '11/1/16 3:57'], ['Task B', '11/1/16 4:19'], ['Task A', '11/1/16 7:43'], ['Task B', '11/1/16 7:43'], ['Task C', '11/1/16 7:51'], ['Task D', '11/1/16 7:51'], ['Task C', '11/1/16 8:11'], ['Task D', '11/1/16 8:13'], ['Task A', '11/3/16 3:49'], ['Task B', '11/3/16 4:11'], ['Task B', '11/3/16 7:34'], ['Task A', '11/3/16 7:34'], ['Task C', '11/3/16 7:43'], ['Task D', '11/3/16 7:43'], ['Task C', '11/3/16 8:03'], ['Task D', '11/3/16 8:05'], ['Task A', '11/5/16 3:41'], ['Task B', '11/5/16 4:03'], ['Task A', '11/5/16 7:26'], ['Task B', '11/5/16 7:26'], ['Task D', '11/5/16 7:35'], ['Task C', '11/5/16 7:35'], ['Task C', '11/5/16 7:54'], ['Task D', '11/5/16 7:56']]
for a, b in data: 
   v = list(map(int, re.findall('\d+', b)))
   _date = datetime.datetime(v[2], v[0], v[1], v[-2], v[-1], 0)
   if (k:=a.split()[-1]) == 'A' and all(j in d for j in ['A', 'B', 'C', 'D']):
       r.append(d)
       d = collections.defaultdict(list)
       d[k].append(_date)
   else:
       d[k].append(_date)

r.append(d)

f, f1 = {'A':min, 'B':min, 'C':max, 'D':max}, lambda x:f'{x.month}/{x.day}/{x.year} {x.hour}:{str(x.minute).zfill(2)}'
result = [{a:f1(f[a](b)) for a, b in i.items()} for i in r]

Output:

[{'A': '11/1/16 3:57', 'B': '11/1/16 4:19', 'C': '11/1/16 8:11', 'D': '11/1/16 8:13'}, 
 {'A': '11/3/16 3:49', 'B': '11/3/16 4:11', 'C': '11/3/16 8:03', 'D': '11/3/16 8:05'}, 
 {'A': '11/5/16 3:41', 'B': '11/5/16 4:03', 'C': '11/5/16 7:54', 'D': '11/5/16 7:56'}]

Upvotes: 1

Phenomenal One
Phenomenal One

Reputation: 2587

Just the approach that @user3386109 had mentioned and track the event timestamps as well.

Move the input into a file named events.txt.

file = open("events.txt", "r")
result = []
partial_result = {}
max_count =0;
tasks_count = [0,0,0,0]
for event in file:
    event = event.strip('\n')
    split_events = event.split()
    max_count = max(tasks_count)
    if len(split_events)==4: #Task data
        task_name = split_events[1]
        time =  split_events[2]+" "+split_events[3]
        idx = ord(task_name)-65
        curr_count = tasks_count[idx]
        if (curr_count==max_count or curr_count+1 == max_count) and task_name not in partial_result:
            partial_result[task_name] = time
        tasks_count[idx] +=1

    if len(partial_result)==4:
        result.append(partial_result)
        partial_result ={}
        tasks_count = [0,0,0,0]

print(result)

Final Ouput

[{'A': '11/1/16 3:57', 'B': '11/1/16 4:19', 'C': '11/1/16 8:11', 'D': '11/1/16 8:13'}, {'A': '11/3/16 3:49', 'B': '11/3/16 4:11', 'C': '11/3/16 8:03', 'D': '11/3/16 8:05'}, {'A': '11/5/16 3:41', 'B': '11/5/16 4:03', 'C': '11/5/16 7:54', 'D': '11/5/16 7:56'}]

Upvotes: 2

Related Questions